Motion Planning With Dynamics by a Synergistic Combination of Layers of Planning

摘要

To efficiently solve challenges related to motion-planning problems with dynamics, this paper proposes treating motion planning not just as a search problem in a continuous space but as a search problem in a hybrid space consisting of discrete and continuous components. A multilayered framework is presented which combines discrete search and sampling-based motion planning. This framework is called synergistic combination of layers of planning ( ${{{tt SyCLoP}}}$) hereafter. Discrete search uses a workspace decomposition to compute leads, i.e., sequences of regions in the neighborhood that guide sampling-based motion planning during the state-space exploration. In return, information gathered by motion planning, such as progress made, is fed back to the discrete search. This combination allows ${{{tt SyCLoP}}}$ to identify new directions to lead the exploration toward the goal, making it possible to efficiently find solutions, even when other planners get stuck. Simulation experiments with dynamical models of ground and flying vehicles demonstrate that the combination of discrete search and motion planning in ${{{tt SyCLoP}}}$ offers significant advantages. In fact, speedups of up to two orders of magnitude were obtained for all the sampling-based motion planners used as the continuous layer of ${{{tt SyCLoP}}}$.