A heuristic and complete planner for the classical mover's problem

Abstract

We present a motion planner for the classical mover's problem in three dimensions that is both resolution-complete and efficient in that it has performance commensurate with task difficulty. It is based on the SANDROS search strategy, which uses a hierarchical, multi-resolution representation of the configuration space along with a generate-and-test paradigm for solution paths. This planner can control the trade-offs between the computation resource and algorithmic completeness/solution path quality, and thus can fully utilize the available computing power. It is useful for navigation of mobile robots, submarines and spacecraft, or part motion feasibility in assembly planning.