Path planning and collision avoidance for robots

Matthias Gerdts; René Henrion; Dietmar Hömberg; Chantal Landry

doi:10.3934/naco.2012.2.437

Article Contents

2012, Volume 2, Issue 3: 437-463. Doi: 10.3934/naco.2012.2.437

This issue Previous Article Preface Next Article Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems

Path planning and collision avoidance for robots

1.
Institute of Mathematics and Applied Computing (LRT), University of the Federal Armed Forces at Munich, Werner-Heisenberg-Weg 39, 85577 Neubiberg
2.
Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstraße 39, 10117 Berlin
3.
Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstraße 39, 10117 Berlin

Received: October 2011

Revised: December 2011

Published: August 2012

Abstract / Introduction Related Papers Cited by

Abstract

An optimal control problem to find the fastest collision-free trajectory of a robot surrounded by obstacles is presented. The collision avoidance is based on linear programming arguments and expressed as state constraints. The optimal control problem is solved with a sequential programming method. In order to decrease the number of unknowns and constraints a backface culling active set strategy is added to the resolution technique.

Keywords:

Mathematics Subject Classification: Primary: 49J15, 49M25, 49N90; Secondary: 90C30.

Citation:

Related Papers

Cited by

References

[1]	L. D. Berkovitz, "Convexity and Optimization in $\mathbbR^n$," John Wiley Sons, New York, 2001.
[2]	J. T. Betts, "Practical Methods for Optimal Control using Nonlinear Programming," Advances in Design and Control, volume 3, SIAM, Philadelphia, 2001.
[3]	J. E. Bobrow, Optimal robot path planning using the minimum-time criterion, IEEE J. Robotics and Automation, 4 (1988), 443-450.doi: 10.1109/56.811.
[4]	J. V. Burke and S. P. Han, A robust sequential quadratic programming method, Mathematical Programming, 43 (1989), 277-303.doi: 10.1007/BF01582294.
[5]	F. L. Chernousko, Optimization in control of robots, Computational Optimal Control, 115 (1994), 19-28.
[6]	M. Diehl, H. G. Bock, H. Diedam and P. Wieber, Fast direct multiple shooting algorithms for optimal robot control, Fast Motions in Biomechanics and Robotics: Optimization and Feedback Control, (2005), 65-94.
[7]	S. Dubowsky, M. A. Norris and Z. Shiller, Time optimal trajectory planning for robotic manipulators with obstacle avoidance: a CAD approach , in "Proc. of IEEE Int. Conf. on Robotics and Automation," (1989), 1906-1912.
[8]	R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269.doi: 10.1007/s101070100244.
[9]	R. Fletcher, S. Leyffer and P. Toint, On the global convergence of a filter-SQP algorithm, SIAM Journal on Optimization, 13 (2002), 44-59.doi: 10.1137/S105262340038081X.
[10]	J. D. Foley, A. van Dam, S. T. Feiner and J. F. Hughes, "Computer Graphics - Principles and Practice," Addison Wesley, 1990.
[11]	M. Gerdts, "Numerische Methoden Optimaler Steuerprozesse Mit Differential-Algebraischen Gleichungssystemen Höheren Indexes und ihre Anwendungen in der Kraftfahrzeugsimulation und Mechanik," Bayreuther Mathematische Schriften, 61 (2001).
[12]	M. Gerdts, Direct shooting method for the numerical solution of higher index DAE optimal control problems, Journal of Optimization Theory and Applications, 117 (2003), 267-294.doi: 10.1023/A:1023679622905.
[13]	M. Gerdts and F. Lempio, "Mathematische Optimierungsverfahren des Operations Research," De Gruyter, Berlin, 2011.doi: 10.1515/9783110249989.
[14]	E. M. Gertz and S. J. Wright, Object-oriented software for quadratic programming, ACM Transactions on Mathematical Software, 29 (2003), 58-81.doi: 10.1145/641876.641880.
[15]	E. G. Gilbert and S. M. Hong, A new algorithm for detecting the collision of moving objects, in "IEEE Proc. Int. Conf. on Robotics and Automation," 1 (1989), 8-14.
[16]	E. G. Gilbert and D. W. Johnson, Distance functions and their application to robot path planning in the presence of obstacles, IEEE Journal of Robotics and Automation, 1 (1985), 21-30.
[17]	P. E. Gill and W. Murray, Numerically stable methods for quadratic programming, Mathematical Programming, 14 (1978), 349-372.doi: 10.1007/BF01588976.
[18]	P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Inertia-controlling methods for general quadratic programming, SIAM Review, 33 (1991), 1-36.doi: 10.1137/1033001.
[19]	D. Goldfarb and A. Idnani, A numerically stable dual method for solving strictly convex quadratic programs, Mathematical Programming, 27 (1983), 1-33.doi: 10.1007/BF02591962.
[20]	K. Gupta and A. P. del Pobil, "Practical Motion Planning in Robotics," Wiley, New York, 1998.
[21]	M. E. Kahn and B. Roth, The near-minimum-time control of open-loop articulated Kinematic chains, J. of Dynamic Sys., Meas. and Contr., 93 (1971), 164-172.doi: 10.1115/1.3426492.
[22]	S. M. LaValle, "Planning Algorithms," Cambridge University Press, Cambridge, 2006.doi: 10.1017/CBO9780511546877.
[23]	M. Pérez-Francisco, A. P. del Pobil and B. Martinez-Salvador, Parallel collision detection between moving robots for practical motion planning, Journal of Robotic Systems, 18 (2001), 487-506.doi: 10.1002/rob.1039.
[24]	F. Pfeiffer, "Einführung in die Dynamik," B. G. Teubner, Stuttgart, 1992.
[25]	M. J. D. Powell, A fast algorithm for nonlinearily constrained optimization calculation, in "Lecture Notes in Mathematics, Numerical Analysis"(ed G. A. Watson), vol. 630, Springer, Berlin-Heidelberg-New York, 1978.
[26]	S. Redon, A. Kheddar and S. Coquillart, Hierarchical back-face culling for collision detection, Proceedings of IEEE International Conference on Robotics and Automation, (2002).
[27]	K. Schittkowski, The nonlinear programming method of Wilson, Han and Powell with an augmented Lagrangean type line search function. Part 1: Convergence analysis, Part 2: An efficient implementation with linear least squares subproblems, Numerische Mathematik, 38 (1981), 83-114, 115-127.
[28]	K. Schittkowski, On the convergence of a sequential quadratic programming method with an augmented Lagrangean line search function, Mathematische Operationsforschung und Statistik, Series Optimization, 14 (1983), 197-216.
[29]	Peter Spellucci, "Numerische Verfahren der Nichtlinearen Optimierung," Birkhäuser, Basel, 1993.
[30]	R. J. Vanderbei, "Linear programming, Foundations and Extensions," International Series in Operations Research & Management Science, 37, 2001.
[31]	G. Vaněček Jr., Back-face culling applied to collision detection of polyhedra, Journal of Visualization and Computer Animation, 5 (1994), 55-63.doi: 10.1002/vis.4340050105.
[32]	O. von Stryk and M. Schlemmer, Optimal control of the industrial robot manutec r3, Computational Optimal Control, 115 (1994), 367-382.