# American Institute of Mathematical Sciences

2012, 2(3): 437-463. doi: 10.3934/naco.2012.2.437

## 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, Germany 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, Germany, Germany

Received  October 2011 Revised  December 2011 Published  August 2012

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.
Citation: Matthias Gerdts, René Henrion, Dietmar Hömberg, Chantal Landry. Path planning and collision avoidance for robots. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 437-463. doi: 10.3934/naco.2012.2.437
##### References:
 [1] L. D. Berkovitz, "Convexity and Optimization in $\mathbbR^n$," John Wiley Sons, New York, 2001.  Google Scholar [2] J. T. Betts, "Practical Methods for Optimal Control using Nonlinear Programming," Advances in Design and Control, volume 3, SIAM, Philadelphia, 2001.  Google Scholar [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.  Google Scholar [4] J. V. Burke and S. P. Han, A robust sequential quadratic programming method, Mathematical Programming, 43 (1989), 277-303. doi: 10.1007/BF01582294.  Google Scholar [5] F. L. Chernousko, Optimization in control of robots, Computational Optimal Control, 115 (1994), 19-28.  Google Scholar [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.  Google Scholar [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. Google Scholar [8] R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.  Google Scholar [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.  Google Scholar [10] J. D. Foley, A. van Dam, S. T. Feiner and J. F. Hughes, "Computer Graphics - Principles and Practice," Addison Wesley, 1990. Google Scholar [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).  Google Scholar [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.  Google Scholar [13] M. Gerdts and F. Lempio, "Mathematische Optimierungsverfahren des Operations Research," De Gruyter, Berlin, 2011. doi: 10.1515/9783110249989.  Google Scholar [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.  Google Scholar [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. Google Scholar [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. Google Scholar [17] P. E. Gill and W. Murray, Numerically stable methods for quadratic programming, Mathematical Programming, 14 (1978), 349-372. doi: 10.1007/BF01588976.  Google Scholar [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.  Google Scholar [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.  Google Scholar [20] K. Gupta and A. P. del Pobil, "Practical Motion Planning in Robotics," Wiley, New York, 1998. Google Scholar [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.  Google Scholar [22] S. M. LaValle, "Planning Algorithms," Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511546877.  Google Scholar [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.  Google Scholar [24] F. Pfeiffer, "Einführung in die Dynamik," B. G. Teubner, Stuttgart, 1992. Google Scholar [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.  Google Scholar [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). Google Scholar [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.  Google Scholar [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.  Google Scholar [29] Peter Spellucci, "Numerische Verfahren der Nichtlinearen Optimierung," Birkhäuser, Basel, 1993.  Google Scholar [30] R. J. Vanderbei, "Linear programming, Foundations and Extensions," International Series in Operations Research & Management Science, 37, 2001.  Google Scholar [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.  Google Scholar [32] O. von Stryk and M. Schlemmer, Optimal control of the industrial robot manutec r3, Computational Optimal Control, 115 (1994), 367-382.  Google Scholar

show all references

##### References:
 [1] L. D. Berkovitz, "Convexity and Optimization in $\mathbbR^n$," John Wiley Sons, New York, 2001.  Google Scholar [2] J. T. Betts, "Practical Methods for Optimal Control using Nonlinear Programming," Advances in Design and Control, volume 3, SIAM, Philadelphia, 2001.  Google Scholar [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.  Google Scholar [4] J. V. Burke and S. P. Han, A robust sequential quadratic programming method, Mathematical Programming, 43 (1989), 277-303. doi: 10.1007/BF01582294.  Google Scholar [5] F. L. Chernousko, Optimization in control of robots, Computational Optimal Control, 115 (1994), 19-28.  Google Scholar [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.  Google Scholar [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. Google Scholar [8] R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.  Google Scholar [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.  Google Scholar [10] J. D. Foley, A. van Dam, S. T. Feiner and J. F. Hughes, "Computer Graphics - Principles and Practice," Addison Wesley, 1990. Google Scholar [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).  Google Scholar [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.  Google Scholar [13] M. Gerdts and F. Lempio, "Mathematische Optimierungsverfahren des Operations Research," De Gruyter, Berlin, 2011. doi: 10.1515/9783110249989.  Google Scholar [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.  Google Scholar [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. Google Scholar [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. Google Scholar [17] P. E. Gill and W. Murray, Numerically stable methods for quadratic programming, Mathematical Programming, 14 (1978), 349-372. doi: 10.1007/BF01588976.  Google Scholar [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.  Google Scholar [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.  Google Scholar [20] K. Gupta and A. P. del Pobil, "Practical Motion Planning in Robotics," Wiley, New York, 1998. Google Scholar [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.  Google Scholar [22] S. M. LaValle, "Planning Algorithms," Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511546877.  Google Scholar [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.  Google Scholar [24] F. Pfeiffer, "Einführung in die Dynamik," B. G. Teubner, Stuttgart, 1992. Google Scholar [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.  Google Scholar [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). Google Scholar [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.  Google Scholar [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.  Google Scholar [29] Peter Spellucci, "Numerische Verfahren der Nichtlinearen Optimierung," Birkhäuser, Basel, 1993.  Google Scholar [30] R. J. Vanderbei, "Linear programming, Foundations and Extensions," International Series in Operations Research & Management Science, 37, 2001.  Google Scholar [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.  Google Scholar [32] O. von Stryk and M. Schlemmer, Optimal control of the industrial robot manutec r3, Computational Optimal Control, 115 (1994), 367-382.  Google Scholar
 [1] Claudia Totzeck. An anisotropic interaction model with collision avoidance. Kinetic & Related Models, 2020, 13 (6) : 1219-1242. doi: 10.3934/krm.2020044 [2] Canghua Jiang, Dongming Zhang, Chi Yuan, Kok Ley Teo. An active set solver for constrained $H_\infty$ optimal control problems with state and input constraints. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 135-157. doi: 10.3934/naco.2021056 [3] Mehdi Badra. Abstract settings for stabilization of nonlinear parabolic system with a Riccati-based strategy. Application to Navier-Stokes and Boussinesq equations with Neumann or Dirichlet control. Discrete & Continuous Dynamical Systems, 2012, 32 (4) : 1169-1208. doi: 10.3934/dcds.2012.32.1169 [4] Adriano Festa, Andrea Tosin, Marie-Therese Wolfram. Kinetic description of collision avoidance in pedestrian crowds by sidestepping. Kinetic & Related Models, 2018, 11 (3) : 491-520. doi: 10.3934/krm.2018022 [5] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 [6] Helmut Maurer, Tanya Tarnopolskaya, Neale Fulton. Computation of bang-bang and singular controls in collision avoidance. Journal of Industrial & Management Optimization, 2014, 10 (2) : 443-460. doi: 10.3934/jimo.2014.10.443 [7] Yujing Wang, Changjun Yu, Kok Lay Teo. A new computational strategy for optimal control problem with a cost on changing control. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 339-364. doi: 10.3934/naco.2016016 [8] Hassan Tahir, Asaf Khan, Anwarud Din, Amir Khan, Gul Zaman. Optimal control strategy for an age-structured SIR endemic model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (7) : 2535-2555. doi: 10.3934/dcdss.2021054 [9] Jianfei Cheng, Xiao Wang, Yicheng Liu. Collision-avoidance and flocking in the Cucker–Smale-type model with a discontinuous controller. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021169 [10] Ka Wo Lau, Yue Kuen Kwok. Optimal execution strategy of liquidation. Journal of Industrial & Management Optimization, 2006, 2 (2) : 135-144. doi: 10.3934/jimo.2006.2.135 [11] Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 [12] Jian Chen, Lei Guan, Xiaoqiang Cai. Analysis on Buyers' cooperative strategy under group-buying price mechanism. Journal of Industrial & Management Optimization, 2013, 9 (2) : 291-304. doi: 10.3934/jimo.2013.9.291 [13] Divya Thakur, Belinda Marchand. Hybrid optimal control for HIV multi-drug therapies: A finite set control transcription approach. Mathematical Biosciences & Engineering, 2012, 9 (4) : 899-914. doi: 10.3934/mbe.2012.9.899 [14] Fengjun Wang, Qingling Zhang, Bin Li, Wanquan Liu. Optimal investment strategy on advertisement in duopoly. Journal of Industrial & Management Optimization, 2016, 12 (2) : 625-636. doi: 10.3934/jimo.2016.12.625 [15] François Alouges, Antonio DeSimone, Luca Heltai, Aline Lefebvre-Lepot, Benoît Merlet. Optimally swimming stokesian robots. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1189-1215. doi: 10.3934/dcdsb.2013.18.1189 [16] Jamal Mrazgua, El Houssaine Tissir, Mohamed Ouahi. Frequency domain $H_{\infty}$ control design for active suspension systems. Discrete & Continuous Dynamical Systems - S, 2022, 15 (1) : 197-212. doi: 10.3934/dcdss.2021036 [17] Anibal T. Azevedo, Aurelio R. L. Oliveira, Marcos J. Rider, Secundino Soares. How to efficiently incorporate facts devices in optimal active power flow model. Journal of Industrial & Management Optimization, 2010, 6 (2) : 315-331. doi: 10.3934/jimo.2010.6.315 [18] Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078 [19] Guibin Lu, Qiying Hu, Youying Zhou, Wuyi Yue. Optimal execution strategy with an endogenously determined sales period. Journal of Industrial & Management Optimization, 2005, 1 (3) : 289-304. doi: 10.3934/jimo.2005.1.289 [20] Chang-Feng Wang, Yan Han. Optimal assignment of principalship and residual distribution for cooperative R&D. Journal of Industrial & Management Optimization, 2012, 8 (1) : 127-139. doi: 10.3934/jimo.2012.8.127

Impact Factor: