SANDROS: a dynamic graph search algorithm for motion planning

Abstract

We present a general search strategy called SANDROS for motion planning, and its applications to motion planning for three types of robots: (1) manipulator; (2) rigid object; and (3) multiple rigid objects. SANDROS is a dynamic-graph search algorithm, and can be described as a hierarchical, nonuniform-multiresolution, best-first search to find a heuristically short motion in the configuration space. The SANDROS planner is resolution complete, and its computation time is commensurate with the problem difficulty measured empirically by the solution-path complexity. For many realistic problems involving a manipulator or a rigid object with six degrees of freedom, its computation times are under 1 minute for easy problems involving wide free space, and several minutes for relatively hard problems.