Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T17:04:51.240Z Has data issue: false hasContentIssue false
  • English
  • Français

Dual objective motion planning subject to state constraints

Published online by Cambridge University Press:  14 December 2015

Nader Sadegh
Nader Sadegh*
Affiliation:
The George W. Woodruff School of Mechanical Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332–0405, USA
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

This paper presents a novel motion planning approach inspired by the Dynamic Programming (DP) applicable to multi degree of freedom robots (mobile or stationary) and autonomous vehicles. The proposed discrete–time algorithm enables a robot to reach its destination through an arbitrary obstacle field in the fewest number of time steps possible while minimizing a secondary objective function. Furthermore, the resulting optimal trajectory is guaranteed to be globally optimal while incorporating state constraints such as velocity, acceleration, and jerk limits. The optimal trajectories furnished by the algorithm may be further updated in real time to accommodate changes in the obstacle field and/or cost function. The algorithm is proven to terminate in a finite number of steps without its computational complexity increasing with the type or number of obstacles. The effectiveness of the global and replanning algorithms are demonstrated on a planar mobile robot with three degrees of freedom subject to velocity and acceleration limits. The computational complexity of the two algorithms are also compared to that of an A*–type search.

Keywords

Time-OptimalMotion Planning Obstacle AvoidanceDynamic ProgrammingGlobal OptimizationSplineState ConstraintsMulti-objective
Type
Articles
Information
Robotica , Volume 35 , Issue 5 , May 2017 , pp. 1157 - 1175
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Blackmore, L., Li, H. and Williams, B., “A Probabilistic Approach to Optimal Robust Path Planning with Obstacles,” Proceedings of the 2006 American Control Conference (2006) pp. 2831–37.Google Scholar
2. Peterson, J., “Obstacle Avoidance using Hierarchical Dynamic Programming,” Proceedings of The 23rd Southeastern Symposium on System (1991) pp. 192–6.Google Scholar
3. Dijkstra, E., “A note on two problems in connexion with graphs,” Numer. Math. 1 (1), 269–271 (1959).CrossRefGoogle Scholar
4. Hart, P., Nilsson, N. and Raphael, B., “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern. 4 (2), 100–107 (1968).CrossRefGoogle Scholar
5. Wein, R., van den Berg, J. and Halperin, D., “The visibility–voronoi complex and its applications,” Comput. Geom. 36, 66–87 (2007).CrossRefGoogle Scholar
6. Dunlap, D. D., Caldwell, C. V., Collins, J. E. G. and Chuy, O., “Motion Planning for Mobile Robots Via Sampling-Based Model Predictive Optimization,” Recent Advances in Mobile Robotics, vol. 1, Dr. Andon Topalov (Ed.), (InTech, 2011), ISBN: 978-953-307-909-7.Google Scholar
7. Howard, T. M., Pivtoraiko, M., Knepper, R., Kelly, A., et al., “Model-predictive motion planning: Several key developments for autonomous mobile robots,” Robot. Autom. Mag. IEEE 21 (1), 64–73 (2014).CrossRefGoogle Scholar
8. Koenig, S. and Likhachev, M., “Fast replanning for navigation in unknown terrain,” IEEE Trans. Robot. 21 (3), 354–363 (2005).CrossRefGoogle Scholar
9. Rimon, E. and Koditschek, D., “Exact robot navigation using artificial potential functions,” IEEE Trans. Robot. Autom. 8 (5), 501–18 (1992).CrossRefGoogle Scholar
10. Eichhorn, M., “A Reactive Obstacle Avoidance System for an Autonomous Underwater Vehicle,” Proceedings of the IFAC World Congress (2005) p. CDRom.CrossRefGoogle Scholar
11. Bruijnen, D., van Helvoort, J. and van de Molengraft, R., “Realtime Motion Path Generation using Subtargets in a Changing Enviornment,” Proceedings of the 2006 American Control Conference (2006) pp. 4243–48.Google Scholar
12. Zhang, J.-Y., Zhao, Z.-P. and Liu, D., “A path planning method for mobile robot based on artificial potential field,” Adv. Robot. 38 (8), 1306–9 (2006).Google Scholar
13. Cetin, B., Bikdash, M. and Hadaegh, F., “Hybrid mixed-logical linear programming algorithm for collision–free optimal path planning,” IET Control Theory Appl. 1 (2), 522–31 (2007).CrossRefGoogle Scholar
14. Ma, C. and Miller, R., “Milp Optimal Path Planning for Real-Time Applications,” Proceedings of the 2006 American Control Conference (2006) p. 6.CrossRefGoogle Scholar
15. Balas, E., “Disjunctive programming,” Ann. Discrete Math. 5, 3–51 (1979).CrossRefGoogle Scholar
16. Bellman, R., Dynamic Programming (Dover Publications, Inc., Mineola, NY, 2003).Google Scholar
17. Yershov, D. and LaValle, S., “Simplicial dijkstra and A* algorithms: From graphs to continuous spaces,” J. Harbin Inst. Technol. 26 (17), 2065–2085 (2012).Google Scholar
18. Sadegh, N., “Time–Optimal Motion Planning of Autonomous Vehicles in the Presence of Obstacles,” Proceedings of the 2008 American Control Conference (2008) p. 6.CrossRefGoogle Scholar
19. Nagabhushan, P. and Manohara, P., “Cognition of free space for planning the shortest path: A framed free space approach,” Pattern Recognit. Lett. 22 (9), 971–82 (2001).CrossRefGoogle Scholar
20. Bakker, B., Zivkovic, Z. and Krose, B., “Hierarchical Dynamic Programming for Robot Path Planning,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (2005) pp. 2756–61.Google Scholar
21. Meystel, A. and Gues, A., H. G., “Minimum Time Path Planning for a Robot,” Proceedings of the 1986 IEEE International Conference on Robotics and Automation (1986) pp. 1678–87.Google Scholar
22. Chazelle, B., “Convex partitions of polyhedra: A lower bound and worst-case optimal algorithm,” SIAM J. Comput. 13 (3), 488–507 (1984).CrossRefGoogle Scholar
23. Puterman, M., Markov Decision Processes: Discrete Stochastic Dynamic Programming (Wiley–Interscience, 2005).Google Scholar
24. Royden, H., Real Analysis (Macmillan Publishing Co., Inc., New York, NY, 1968).Google Scholar