Incremental plan insertion, a step toward coordinating multi-robot coordination

We present and discuss a generic scheme for multi-robot cooperation based on an incremental and distributed plan-merging process. Each robot, autonomously and incrementally builds and executes its own plans taking into account the multi-robot context. The robots are assumed to be able to collect the other robots plans and to coordinate their own plans with the other robots plans to produce coordinated plans that ensure their proper execution. We discuss the properties of this cooperative paradigm (coherence, detection of dead-lock situations, ...) , , how it fills the gap between centralized and distributed planning and the class of applications for which it is well suited. We finally illustrate this scheme through an implemented system which allows a fleet of autonomous mobile robots to perform load transfer tasks in a route network environment with a very limited centralized activity and important gains in system flexibility and robustness to execution contingencies.