Motion planning for multiple moving objects

Abstract

We present a motion planner for multiple moving objects in two dimensions. The search for collision-free paths is performed in the composite configuration space of all the moving objects to guarantee a solution, and the efficiency of our planner is demonstrated with examples. Our motion planner can be characterized with a hierarchical, multiresolution search of the configuration space along with a generate-and-test paradigm for solution paths. Because of the high dimensionality of the composite configuration space, our planner is most useful for cases with a small number of moving objects. Some of the potential applications are navigation of several mobile robots, and planning part motions for a multihanded assembly operation.