We propose a resolution scheme that is aimed to solve a wide range of multi-robot planning problems in a 3D geometrical environment. This complements our efforts in developing manipulation planning algorithms [1, 15, 14] to deal with multiple robots and several movable objects problems. While the elementary planning step relies on Probabilistic Roadmap Methods (PRMs), the main contribution here is a reasoning level that adapts its control over the construction and extension of a number of roadmaps. The coherence between roadmaps and the hierarchical search process are done through a new type of graph built for a subset of objects or robots in the environment and called Elementary Kinematic Graph. This paper describes the main ingredients of the proposed framework, and its first results.
展开▼
