Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments

International Journal of Robotics Research - Tập 29 Số 5 - Trang 485-501 - 2010
Dmitri Dolgov1, Sebastian Thrun2, Michael Montemerlo2, James Diebel2
1AI & Robotics Group, Toyota Research Institute, Ann Arbor, MI 48105, USA,
2Stanford Artificial Intelligence Laboratory, Stanford University, Stanford CA 94305, USA,

Tóm tắt

We describe a practical path-planning algorithm for an autonomous vehicle operating in an unknown semi-structured (or unstructured) environment, where obstacles are detected online by the robot’s sensors. This work was motivated by and experimentally validated in the 2007 DARPA Urban Challenge, where robotic vehicles had to autonomously navigate parking lots. The core of our approach to path planning consists of two phases. The first phase uses a variant of A* search (applied to the 3D kinematic state space of the vehicle) to obtain a kinematically feasible trajectory. The second phase then improves the quality of the solution via numeric non-linear optimization, leading to a local (and frequently global) optimum. Further, we extend our algorithm to use prior topological knowledge of the environment to guide path planning, leading to faster search and final trajectories better suited to the structure of the environment. We present experimental results from the DARPA Urban Challenge, where our robot demonstrated near-flawless performance in complex general path-planning tasks such as navigating parking lots and executing U-turns on blocked roads. We also present results on autonomous navigation of real parking lots. In those latter tasks, which are significantly more complex than the ones in the DARPA Urban Challenge, the time of a full replanning cycle of our planner is in the range of 50—300 ms.

Từ khóa


Tài liệu tham khảo

Andrews, J. and Hogan, N. ( 1983). Impedance control as a framework for implementing obstacle avoidance in a manipulator. Control of Manufacturing Processes and Robotic Systems, Boston: ASME: pp. 243-251.

Bekris, K.E., 2007, International Conference on Robotics and Automation, 704

Buehler, M., 2005, The 2005 DARPA Grand Challenge: The Great Robot Race

2008, Journal of Field Robotics, 25, 423, 10.1002/rob.20257

2008, Journal of Field Robotics, 25, 567, 10.1002/rob.20259

10.1177/02783640022066770

Choset, H., 2005, Principles of Robot Motion: Theory, Algorithms, and Implementations

Connolly, C., IEEE International Conference on Robotics and Automation (ICRA)

10.1002/rob.20135

Dolgov, D., Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA-09)

Dolgov, D., Proceedings of the First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR-08)

Ersson, T., IEEE International Conference on Intelligent Robots and Systems (IROS)

Ferguson, D., Proceedings of the International Symposium on Robotics Research (ISRR)

Fraichard, T., Proceedings of the IEEE International Conference on Robotics and Automation

Fraichard, T., Proceedings of the IEEE International Conference on Advanced Robotics

10.1109/TSSC.1968.300136

10.1145/1056777.1056779

10.1002/rob.20252

10.1109/70.508439

10.1177/027836498600500106

Koditschek, D.E., IEEE International Conference on Robotics and Automation (ICRA)

Koenig, S., IEEE International Conference on Robotics and Automation (ICRA)

Koren, Y., IEEE International Conference on Robotics and Automation (ICRA)

10.1109/70.954762

Laumond, J.-P., 1998, Robot Motion Planning and Control, 1

LaValle, S., 1998, Rapidly-exploring random trees: a new tool for path planning

10.1017/CBO9780511546877

Likhachev, M., Proceedings of Robotics: Science and Systems IV

10.1002/rob.20253

Miyazaki, F., 1985, Journal of Robotic Systems, 2, 53

Nash, A., Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)

Pavlov, V., 1984, Soviet Automatic Control, 17, 45

Pivtoraiko, M., 2007, Technical Report

10.15607/RSS.2007.III.040

10.2140/pjm.1990.145.367

10.1109/70.163777

10.1145/321356.321357

Scheuer, A., Proceedings of the IEEE-RSJ International Conference on Intelligent Robots and Systems

Seo, Y.-W., Proceedings of International Joint Conference on Artificial Intelligence (IJCAI-09)

Stentz, A., Proceedings of the International Joint Conference on Artificial Intelligence

Tilove, R., IEEE International Conference on Robotics and Automation

10.1002/rob.20255

Thông tin
Thông tin xuất bản

International Journal of Robotics Research

Tập 29 Số 5

485-501

Thông tin tác giả