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 and 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.

[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.

show all references

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.

[1]

Claudia Totzeck. An anisotropic interaction model with collision avoidance. Kinetic and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - S, 2022, 15 (7) : 1733-1748. doi: 10.3934/dcdss.2021169

[10]

Ka Wo Lau, Yue Kuen Kwok. Optimal execution strategy of liquidation. Journal of Industrial and Management Optimization, 2006, 2 (2) : 135-144. doi: 10.3934/jimo.2006.2.135

[11]

Jian Chen, Lei Guan, Xiaoqiang Cai. Analysis on Buyers' cooperative strategy under group-buying price mechanism. Journal of Industrial and Management Optimization, 2013, 9 (2) : 291-304. doi: 10.3934/jimo.2013.9.291

[12]

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

[13]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[14]

Fengjun Wang, Qingling Zhang, Bin Li, Wanquan Liu. Optimal investment strategy on advertisement in duopoly. Journal of Industrial and 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 and Continuous Dynamical Systems - B, 2013, 18 (5) : 1189-1215. doi: 10.3934/dcdsb.2013.18.1189

[16]

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 and Management Optimization, 2010, 6 (2) : 315-331. doi: 10.3934/jimo.2010.6.315

[17]

Jamal Mrazgua, El Houssaine Tissir, Mohamed Ouahi. Frequency domain $ H_{\infty} $ control design for active suspension systems. Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : 197-212. doi: 10.3934/dcdss.2021036

[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]

Lican Kang, Yuan Luo, Jerry Zhijian Yang, Chang Zhu. A primal and dual active set algorithm for truncated $L_1$ regularized logistic regression. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022050

[20]

Guibin Lu, Qiying Hu, Youying Zhou, Wuyi Yue. Optimal execution strategy with an endogenously determined sales period. Journal of Industrial and Management Optimization, 2005, 1 (3) : 289-304. doi: 10.3934/jimo.2005.1.289

 Impact Factor: 

Metrics

  • PDF downloads (246)
  • HTML views (0)
  • Cited by (7)

[Back to Top]