K. E. Bekris and L. E. Kavraki, “Greedy but Safe Replanning under Kinodynamic Constraints,” in International Conference on Robotics and Automation, Rome, Italy, 2007, pp. 704–710.
We consider motion planning problems for a vehicle with kinodynamic constraints, where there is partial knowledge about the environment and replanning is required. We present a new tree-based planner that explicitly deals with kinodynamic constraints and addresses the safety issues when planning under finite computation times, meaning that the vehicle avoids collisions in its evolving configuration space. In order to achieve good performance we incrementally update a tree data-structure by retaining information from previous steps and we bias the search of the planner with a greedy, yet probabilistically complete state space exploration strategy. Moreover, the number of collision checks required to guarantee safety is kept to a minimum. We compare our technique with alternative approaches as a standalone planner and show that it achieves favorable performance when planning with dynamics. We have applied the planner to solve a challenging replanning problem involving the mapping of an unknown workspace with a non-holonomic platform.
Publisher: http://dx.doi.org/10.1109/ROBOT.2007.363069
PDF preprint: http://kavrakilab.org/publications/bekris-kavraki2007greedy-but-safe.pdf