nach oben

Optimization and Engineering

Erschienen in:

04.11.2015

Combining discrete and continuous optimization to solve kinodynamic motion planning problems

verfasst von: Chantal Landry, Wolfgang Welz, Matthias Gerdts

Erschienen in: Optimization and Engineering | Ausgabe 3/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A new approach to find the fastest trajectory of a robot avoiding obstacles, is presented. This optimal trajectory is the solution of an optimal control problem with kinematic and dynamic constraints. The approach involves a direct method based on the time discretization of the control variable. We mainly focus on the computation of a good initial trajectory. Our method combines discrete and continuous optimization concepts. First, a graph search algorithm is used to determine a list of intermediate points. Then, an optimal control problem of small size is defined to find the fastest trajectory that passes through the vicinity of the intermediate points. The resulting solution is the initial trajectory. Our approach is applied to a single body mobile robot. The numerical results show the quality of the initial trajectory and its low computational cost.

Vorheriger Artikel High fidelity multidisciplinary design optimization of a wing using the interaction of low and high fidelity models

Nächster Artikel An illumination problem with tradeoff between coverage of a dataset and aperture angle of a conic light beam

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Barclay A, Gill PE, Ben Rosen J (1997) SQP methods and their application to numerical optimal control. University of California, San DiegoMATH

Berkovitz LD (2001) Convexity and optimization in \(\mathbb{R}^{n}\). Wiley, New York

Betts JT (2001) Practical methods for optimal control using nonlinear programming. Advances in design and control. Society for Industrial and Applied Mathematics (SIAM), PhiladelphiaMATH

Bobrow JE (1988) Optimal robot path planning using the minimum-time criterion. IEEE J Robot Autom 4:443–450CrossRef

Bobrow JE, Dubowsky S, Gibson JS (1985) Time-optimal control of robotic manipulators along specified paths. Int J Robot Res 4:3–17CrossRef

Bohlin R (2002) Robot path planning. Chalmers University of Technology, Goteborg

Cameron SA, Culley RK (1986) Determining the minimum translational distance between two convex polyhedra. In: Proceedings of international conference on robotics and automation, pp 591–596

Diehl M, Walther A, Bock HG, Kostina E (2010) An adjoint-based SQP algorithm with quasi-Newton Jacobian updates for inequality constrained optimization. Optim Methods Softw 25(4–6):531–552MathSciNetCrossRefMATH

Donald B, Xavier P, Canny J, Reif J (1993) Kinodynamic motion planning. J Assoc Comput Mach 40:1048–1066MathSciNetCrossRefMATH

Dubowsky S, Norris MA, Shiller Z (1989) Time optimal trajectory planning for robotic manipulators with obstacle avoidance: a CAD approach. In: Proceedings of IEEE international conference on robotics and automation, pp 1906–1912

Escande A, Miossec S, Benallegue M, Kheddar A (2014) A strictly convex hull for computing proximity distances with continuous gradients. IEEE Trans Robot 30(3):666–678CrossRef

Fletcher R, Leyffer S (2002) Nonlinear programming without a penalty function. Math Program 91(2):239–269MathSciNetCrossRefMATH

Fletcher R, Leyffer S, Toint P (2002) On the global convergence of a filter-SQP algorithm. SIAM J Optim 13(1):44–59MathSciNetCrossRefMATH

Gerdts M (2013) OCPID-DAE1: optimal control and parameter identification with differential-algebraic equations of index 1, User Manual, Version 1.3, Department of Aerospace Engineering, Universität der Bundeswehr München. http://www.optimal-control.de

Gerdts M (2012) Optimal Control of ODEs and DAEs. De Gruyter, De Gruyter textbook

Gerdts M, Henrion R, Hömberg D, Landry C (2012) Path planning and collision avoidance for robots. Numer Algebra Control Optim 2(3):437–463MathSciNetCrossRefMATH

Gilbert EG, Johnson DW (1985) Distance functions and their application to robot path planning in the presence of obstacles. IEEE J Robot Autom RA–1:21–30CrossRef

Gilbert EG, Johnson DW, Keerthi SS (1988) A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE J Robot Autom 4(2):193–203CrossRef

Goerzen C, Kong Z, Mettler B (2010) A survey of motion planning algorithms from the perspective of autonomous UAV guidance. J Intell Robot Syst 57(1–4):65–100CrossRefMATH

Hart GD, Anitescu M (2010) An O(m + n) measure of penetration depth between convex polyhedral bodies for rigid multibody dynamics

Johnson DW, Gilbert EG (1985) Minimum time robot path planning in the presence of obstacles, vol 24. In: 24th IEEE conference on decision and control, pp 1748–1753

Kim YJ, Lin MC, Manocha D (2002) DEEP: dual-space expansion for estimating penetration depth between convex polytopes. In: IEEE conference on robotics and automation, pp 921–926

Landry C, Gerdts M, Henrion R, Hömberg D (2013) Path-planning with collision avoidance in automotive industry. In: 25th IFIP TC 7 conference system modeling and optimization, Berlin. 12–16 Sep 2011. Revised Selected Papers IFIP AICT 391, Springer, Heidelberg; Approx. IX, 575 pp 2013

LaValle SM (2006) Planning algorithms. Cambridge University Press, CambridgeCrossRefMATH

LaValle SM, Kuffner JJ (2001) Randomized kinodynamic planning. Int J Robot Res 20(5):378–400CrossRef

Lewis AS, Overton ML (2008) Nonsmooth optimization via BFGS. Technical report, http://www.cs.nyu.edu/overton/ papers/pdffiles/bfgs_inexactLS.pdf

Lewis AS, Overton ML (2013) Nonsmooth optimization via quasi Newton methods. Math Progr 141(1–2):135–163MathSciNetCrossRefMATH

Lin MC (1993) Efficient collision detection for animation and robotics. PhD thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley

Lin MC, Canny JF (1991) A fast algorithm for incremental distance calculation. In: IEEE international conference on robotics and automation, pp 1008–1014

Lin Q, Loxton RC, Teo KL (2014) The control parameterization method for nonlinear optimal control: a survey. J Ind Manag Optim 10(1):275–309MathSciNetCrossRefMATH

Loxton RC, Teo KL, Rehbock V, Yiu KFC (2009) Optimal control problems with a continuous inequality constraint on the state and the control. Automatica 45(10):2250–2257MathSciNetCrossRefMATH

Maheshwari A, Sack JR, Djidjev HN (1999) Link distance problems. Handbook of computational geometry, pp 519–558

Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn., Springer series in operations research and financial engineering. Springer, New YorkMATH

Powell MJD (1978) A fast algorithm for nonlinearly constrained optimization calculations. In: Watson GA (ed) Numerical analysis, vol 630. Lecture notes in mathematics. Springer, Berlin, pp 144–157

Quarteroni A, Sacco R, Saleri F (2007) Numerical mathematics., Texts in applied mathematics. Springer, ParisCrossRefMATH

Saramago SFP, Steffen V (2001) Trajectory modeling of robot manipulators in the presence of obstacles. J Optim Theory Appl 110:17–34MathSciNetCrossRefMATH

Schittkowski K (1983) On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function 2. Mathematische Operationsforschung und Statistik. Series Optimization 14(2):197–216MathSciNetCrossRefMATH

Schramm H, Zowe J (1992) A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J Optim 2(1):121–152MathSciNetCrossRefMATH

Shor NZ (1985) Minimization methods for non-differentiable functions, vol 3., Springer series in computational mathematics. Springer, BerlinMATH

Sprunk C, Lau B, Pfaffz P, Burgard W (2011) Online generation of kinodynamic trajectories for non-circular omnidirectional robots. In: IEEE international conference on Robotics and automation (ICRA), pp 72–77

Winter S (2002) Modeling costs of turns in route planning. GeoInformatica 6(4):345–361CrossRefMATH

Titel: Combining discrete and continuous optimization to solve kinodynamic motion planning problems
verfasst von: Chantal Landry
Wolfgang Welz
Matthias Gerdts
Publikationsdatum: 04.11.2015
Verlag: Springer US
Erschienen in: Optimization and Engineering / Ausgabe 3/2016
Print ISSN: 1389-4420
Elektronische ISSN: 1573-2924
DOI: https://doi.org/10.1007/s11081-015-9291-0

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2016

High fidelity multidisciplinary design optimization of a wing using the interaction of low and high fidelity models

Parametric design and optimization of high speed train nose

Announcement: Howard Rosenbrock Prize 2015

Integration of expert knowledge into radial basis function surrogate models

An illumination problem with tradeoff between coverage of a dataset and aperture angle of a conic light beam

Premium Partner

Marktübersichten