Multiresolution approach for motion planning under differential constraints

In this paper, we present an incremental, multiresolution motion planning algorithm designed for systems with differential constraints. Planning for these systems is more difficult than ordinary path planning due to the presence of momentum (drift) or nonholonomic velocity constraints. Given a motion planning problem for such a system and that a solution to the problem exists, then a finite reachability graph containing a solution trajectory is guaranteed to exist, under very reasonable conditions. In general, this graph can be generated using sufficiently dense input space sampling, sufficiently small time step, and sufficiently large tree depth. We show how to find and search such a tree in an incremental, multiresolution way. We prove the completeness of our algorithm, discuss related practical concerns, and show experimental results for several systems