Title :
Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest paths trees
Author :
Barbehenn, Michael ; Hutchinson, Seth
Author_Institution :
Beckman Inst. for Adv. Sci. & Technol., Illinois Univ., Urbana, IL, USA
fDate :
4/1/1995 12:00:00 AM
Abstract :
Hierarchical approximate cell decomposition is a popular approach to the geometric robot motion planning problem. 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. 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
Keywords :
dynamics; iterative methods; path planning; robots; search problems; trees (mathematics); connectivity graph; dynamic algorithm; hierarchical motion planning; iterative method; robot configuration space; search problem; single-source shortest paths trees; Artificial intelligence; Autonomous agents; Helium; Heuristic algorithms; Labeling; Motion planning; Orbital robotics; Path planning; Robot motion; Tree graphs;
Journal_Title :
Robotics and Automation, IEEE Transactions on