EFFICIENT SEARCH AND HIERARCHICAL MOTION PLANNING BY DYNAMICALLY MAINTAINING SINGLE-SOURCE SHORTEST PATHS TREES

Hierarchical approximate cell decomposition is a popular approach to t he geometric robot motion planning problem, Planners that use this app roach iteratively refine an approximate representation of the robot co nfiguration space, searching each refined representation for a solutio n path, until a solution path is found, In many cases, the search effo rt expended at a particular iteration can be greatly reduced by exploi ting the work done during previous iterations, In this paper, we descr ibe how this exploitation of past computation can be effected by the u se of a dynamically maintained single-source shortest paths tree. Our approach is as follows. We embed a single-source shortest paths tree i n the connectivity graph of the approximate representation of the robo t configuration space, This shortest paths tree records the most promi sing path to each vertex in the connectivity graph from the vertex cor responding to the robot's initial configuration, At each iteration, so me vertex in the connectivity graph is replaced with a new set of vert ices, corresponding to a more detailed representation of the configura tion space, Our new, dynamic algorithm is then used to update the sing le-source shortest paths tree to reflect these changes to the underlyi ng connectivity graph, Thus, at each iteration of the planning algorit hm, a representation of the best path from the initial configuration t o the goal configuration is computed by a set of local tree update ope rations. Our planner is fully implemented and we give empirical result s to illustrate the performance improvements of the dynamic algorithms .