SANDROS: A motion planner with performance proportional to task difficulty

Abstract

To address the need of a practical motion planner for manipulators, we present an efficient and resolution-complete algorithm that has performance commensurate with task difficulty. The algorithm uses SANDROS, a new search strategy that combines hierarchical, nonuniform-multi-resolution, and best-fit search to find a near-optimal solution in the configuration space. This algorithm can be applied to any manipulator, and has been tested with 5 and 6-degree-of-freedom robots, with execution time ranging from 20 seconds to 10 minutes on a 16 MIPS workstation. 14 refs., 3 figs., 1 tab.