SANDROS: a motion planner with performance proportional to task difficulty

To address the need of a practical motion planner for manipulators, the authors present an efficient and resolution-complete algorithm that has performance commensurate with task difficulty. The algorithm uses SANDROS, a search strategy that combines hierarchical, nonuniform multiresolution, and best-first search to find a near-optimal solution in the configuration space. This algorithm can be applied to any manipulator, and has been tested with five- and six-degree-of-freedom robots, with execution times ranging from 20 seconds to 10 minutes on a 16 MIPS workstation