Efficient Search and Hierarchical Motion Planning by Dynamically Maintaining Single-Source Shortest Paths Trees

Hierarchical approximate cell decomposition is a popular approach to the geometric robot motion planning problem. Planners that use this approach iteratively refine an approximate representation of the robot configuration space, searching each refined representation for a solution path, until a solution path is found. In many cases, the search effort expended at a particular iteration can be greatly reduced by exploiting the work done during previous iterations. In this paper, we describe how this exploitation of past computation can be effected by the use of a dynamically maintained single-source shortest paths tree. Our approach is as follows. We embed a single-source shortest paths tree in the connectivity graph of the approximate representation of the robot configuration space. This shortest paths tree records the most promising path to each vertex in the connectivity graph from the vertex corresponding to the robot's initial configuration. At each iteration, some vertex in the connectivity graph is replaced with a new set of vertices, corresponding to a more detailed representation of the configuration space. Our new, dynamic algorithm is then used to update the single-source shortest paths tree to reflect these changes to the underlying connectivity graph. Thus, at each iteration of the planning algorithm, a representation of the best path from the initial configuration to the goal configuration is computed by a set of local tree update operations. Our planner is fully implemented and we give empirical results to illustrate the performance improvements of the dynamic algorithms.