Complete motion planner for time-varying environments

Abstract

This paper presents a complete motion planner in three-dimensional changing environment. The robot is either a manipulator or a rigid object that translates and rotates, while obstacles are polyhedra translating and rotating along known trajectories. The motion planner is based on the SANDROS search strategy, which uses a hierarchical, multi-resolution representation of the product space of the time and the configuration space. A solution is found by generating a candidate sequence of subgoals and subsequently computing collision-free path along the sequence. For changing environments it is the first planner for non-point robots that is efficient and guarantees a solution. 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. This algorithm is useful for navigation of mobile robots and submarines, or motion planning of multiple robots by regarding other robots as moving obstacles.