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, (2001).

[2]

J. T. Betts, "Practical Methods for Optimal Control using Nonlinear Programming,", Advances in Design and Control, (2001).

[3]

J. E. Bobrow, Optimal robot path planning using the minimum-time criterion,, IEEE J. Robotics and Automation, 4 (1988), 443. doi: 10.1109/56.811.

[4]

J. V. Burke and S. P. Han, A robust sequential quadratic programming method,, Mathematical Programming, 43 (1989), 277. doi: 10.1007/BF01582294.

[5]

F. L. Chernousko, Optimization in control of robots,, Computational Optimal Control, 115 (1994), 19.

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

[7]

S. Dubowsky, M. A. Norris and Z. Shiller, Time optimal trajectory planning for robotic manipulators with obstacle avoidance: a CAD approach ,, in, (1989), 1906.

[8]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Mathematical Programming, 91 (2002), 239. 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. 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. doi: 10.1023/A:1023679622905.

[13]

M. Gerdts and F. Lempio, "Mathematische Optimierungsverfahren des Operations Research,", De Gruyter, (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. doi: 10.1145/641876.641880.

[15]

E. G. Gilbert and S. M. Hong, A new algorithm for detecting the collision of moving objects,, in, 1 (1989), 8.

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

[17]

P. E. Gill and W. Murray, Numerically stable methods for quadratic programming,, Mathematical Programming, 14 (1978), 349. 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. 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. doi: 10.1007/BF02591962.

[20]

K. Gupta and A. P. del Pobil, "Practical Motion Planning in Robotics,", Wiley, (1998).

[21]

M. E. Kahn and B. Roth, The near-minimum-time control of open-loop articulated Kinematic chains,, J. of Dynamic Sys., 93 (1971), 164. doi: 10.1115/1.3426492.

[22]

S. M. LaValle, "Planning Algorithms,", Cambridge University Press, (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. doi: 10.1002/rob.1039.

[24]

F. Pfeiffer, "Einführung in die Dynamik,", B. G. Teubner, (1992).

[25]

M. J. D. Powell, A fast algorithm for nonlinearily constrained optimization calculation,, in, (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.

[28]

K. Schittkowski, On the convergence of a sequential quadratic programming method with an augmented Lagrangean line search function,, Mathematische Operationsforschung und Statistik, 14 (1983), 197.

[29]

Peter Spellucci, "Numerische Verfahren der Nichtlinearen Optimierung,", Birkhäuser, (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. 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.

show all references

References:
[1]

L. D. Berkovitz, "Convexity and Optimization in $\mathbbR^n$,", John Wiley Sons, (2001).

[2]

J. T. Betts, "Practical Methods for Optimal Control using Nonlinear Programming,", Advances in Design and Control, (2001).

[3]

J. E. Bobrow, Optimal robot path planning using the minimum-time criterion,, IEEE J. Robotics and Automation, 4 (1988), 443. doi: 10.1109/56.811.

[4]

J. V. Burke and S. P. Han, A robust sequential quadratic programming method,, Mathematical Programming, 43 (1989), 277. doi: 10.1007/BF01582294.

[5]

F. L. Chernousko, Optimization in control of robots,, Computational Optimal Control, 115 (1994), 19.

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

[7]

S. Dubowsky, M. A. Norris and Z. Shiller, Time optimal trajectory planning for robotic manipulators with obstacle avoidance: a CAD approach ,, in, (1989), 1906.

[8]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Mathematical Programming, 91 (2002), 239. 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. 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. doi: 10.1023/A:1023679622905.

[13]

M. Gerdts and F. Lempio, "Mathematische Optimierungsverfahren des Operations Research,", De Gruyter, (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. doi: 10.1145/641876.641880.

[15]

E. G. Gilbert and S. M. Hong, A new algorithm for detecting the collision of moving objects,, in, 1 (1989), 8.

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

[17]

P. E. Gill and W. Murray, Numerically stable methods for quadratic programming,, Mathematical Programming, 14 (1978), 349. 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. 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. doi: 10.1007/BF02591962.

[20]

K. Gupta and A. P. del Pobil, "Practical Motion Planning in Robotics,", Wiley, (1998).

[21]

M. E. Kahn and B. Roth, The near-minimum-time control of open-loop articulated Kinematic chains,, J. of Dynamic Sys., 93 (1971), 164. doi: 10.1115/1.3426492.

[22]

S. M. LaValle, "Planning Algorithms,", Cambridge University Press, (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. doi: 10.1002/rob.1039.

[24]

F. Pfeiffer, "Einführung in die Dynamik,", B. G. Teubner, (1992).

[25]

M. J. D. Powell, A fast algorithm for nonlinearily constrained optimization calculation,, in, (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.

[28]

K. Schittkowski, On the convergence of a sequential quadratic programming method with an augmented Lagrangean line search function,, Mathematische Operationsforschung und Statistik, 14 (1983), 197.

[29]

Peter Spellucci, "Numerische Verfahren der Nichtlinearen Optimierung,", Birkhäuser, (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. 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.

[1]

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 - A, 2012, 32 (4) : 1169-1208. doi: 10.3934/dcds.2012.32.1169

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Jingang Zhai, Guangmao Jiang, Jianxiong Ye. Optimal dilution strategy for a microbial continuous culture based on the biological robustness. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 59-69. doi: 10.3934/naco.2015.5.59

[15]

Yuxue Li, Maozhu Jin, Peiyu Ren, Zhixue Liao. Research on the optimal initial shunt strategy of Jiuzhaigou based on the optimization model. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1239-1249. doi: 10.3934/dcdss.2015.8.1239

[16]

Heman Shakeri, Faryad Darabi Sahneh, Caterina Scoglio, Pietro Poggi-Corradini, Victor M. Preciado. Optimal information dissemination strategy to promote preventive behaviors in multilayer epidemic networks. Mathematical Biosciences & Engineering, 2015, 12 (3) : 609-623. doi: 10.3934/mbe.2015.12.609

[17]

Lv Chen, Hailiang Yang. Optimal reinsurance and investment strategy with two piece utility function. Journal of Industrial & Management Optimization, 2017, 13 (2) : 737-755. doi: 10.3934/jimo.2016044

[18]

Gongpin Cheng, Lin Xu. Optimal size of business and dividend strategy in a nonlinear model with refinancing and liquidation value. Mathematical Control & Related Fields, 2017, 7 (1) : 1-19. doi: 10.3934/mcrf.2017001

[19]

Siyu Liu, Yong Li, Yingjie Bi, Qingdao Huang. Mixed vaccination strategy for the control of tuberculosis: A case study in China. Mathematical Biosciences & Engineering, 2017, 14 (3) : 695-708. doi: 10.3934/mbe.2017039

[20]

Ellina Grigorieva, Evgenii Khailov. Optimal control of pollution stock. Conference Publications, 2011, 2011 (Special) : 578-588. doi: 10.3934/proc.2011.2011.578

 Impact Factor: 

Metrics

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

[Back to Top]