Carnegie Mellon University
Fast and Feasible Deliberative Motion Planner for Dynamic Environments

Mikhail Pivtoraiko and Alonzo Kelly
International Conference on Robotics and Automation, May, 2009.

  • Adobe portable document format (pdf) (3MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

We present an approach to the problem of differentially constrained mobile robot motion planning in arbitrary time-varying cost fields. We construct a special search space which is ideally suited to the requirements of dynamic environments including a) feasible motion plans that satisfy differential constraints, b) efficient plan repair at high update rates, and c) deliberative goal-directed behavior on scales well beyond the effective range of perception sensors. The search space contains edges which adapt to the state sampling resolution yet aquire states exactly in order to permit the use of the dynamic programming principle without introducing infeasibility. It is a symmetric lattice based on a repeating unit of controls which permits off-line computation of the planner heuristic, motion simulation, and the swept volumes associated with each motion. For added planning efficiency, the search space features fine resolution near the vehicle and reduced resolution far away. Furthermore, its topology is updated in real-time as the vehicle moves in such a way that the underlying motion planner processes changing topology as an equivalent change in the dynamic environment. The planner was originally developed to cope with the reduced computation available on the Mars rovers. Experimental results with research prototype rovers demonstrate that the planner allows us to exploit the entire envelope of vehicle maneuverability in rough terrain, while featuring real-time performance.

robot navigation, real-time planning, rough terrain

Associated Project(s): Very Rough Terrain Nonholonomic Trajectory Generation and Motion Planning for Rovers
Number of pages: 7

Text Reference
Mikhail Pivtoraiko and Alonzo Kelly , "Fast and Feasible Deliberative Motion Planner for Dynamic Environments," International Conference on Robotics and Automation, May, 2009.

BibTeX Reference
   author = "Mikhail Pivtoraiko and Alonzo {Kelly }",
   title = "Fast and Feasible Deliberative Motion Planner for Dynamic Environments",
   booktitle = "International Conference on Robotics and Automation",
   month = "May",
   year = "2009",