Publications Details

An efficient hybrid planner in changing environments

Chen, P.C.

In this paper, we present a new hybrid motion planner than is capable of exploiting previous planning episodes when confronted with new planning problems. Our approach is applicable when several (similar) problems are successively posed for the same static environment, or when the environment changes incrementally between planning episodes. At the heart of our system lie two low-level motion planners: a fast, but incomplete planner (which we call LOCAL), and a computationally costly (possibly resolution) complete planner (which we call GLOBAL). When a new planning problem is presented to our planner, a meta-level planner (which we call MANAGER) decomposes the problem into segments that are amenable to solution by LOCAL. This decomposition is made by exploiting a task graph, in which successful planning episodes have been recorded. In cases where the decomposition fails, GLOBAL is invoked. The key to our planner`s success is a novel representation of solution trajectories, in which segments of collision-free paths are associated with the boundary of nearby obstacles.