Anytime Motion Planning using the RRT
The Rapidly-exploring Random Tree (RRT) algorithm, based on incremental sampling, efficiently computes motion plans. Although the RRT algorithm quickly produces candidate feasible solutions, it tends to converge to a solution that is far from optimal. Practical applications favor “anytime algorithms that quickly identify an initial feasible plan, then, given more computation time available during plan execution, improve the plan toward an optimal solution. This paper describes an anytime algorithm based on the RRT which (like the RRT) finds an initial feasible solution quickly, but (unlike the RRT) almost surely converges to an optimal solution. We present two key extensions to the RRT, committed trajectories and branch-and-bound tree adaptation, that together enable the algorithm to make more efficient use of computation time online, resulting in an anytime algorithm for real-time implementation. We evaluate the method using a series of Monte Carlo runs in a high-fidelity simulation environment, and compare the operation of the RRT and RRT methods. We also demonstrate experimental results for an outdoor wheeled robotic vehicle.
Sertac Karaman Matthew R. Walter Alejandro Perez Emilio Frazzoli Seth Teller
Laboratory for Information and Decision Systems,Massachusetts Institute of Technology,Cambridge,MA,U Computer Science and Artificial Intelligence Laboratory,Massachusetts Institute of Technology,Cambri Polytechnic University of Puerto Rico,San Juan,PR,USA
国际会议
2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)
上海
英文
1478-1483
2011-05-09（万方平台首次上网日期，不代表论文的发表时间）