We present and discuss the use of a generic scheme for multi-robot cooperation called the "plan-merging paradigm" for managing a large fleet of autonomous mobile robots. Each robot, autonomously and incrementally builds and executes its own plans taking into account the multi-robot context obtained by collecting the current plans and goals of the other robots. We describe the overall system architecture and discuss the properties of our cooperative scheme. We show how the plan-merging paradigm (PMP) can be used in a hierarchical manner and how it "fills the gap" between centralized planning and distributed execution. 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. The central activity is limited to task allocation and important gains are obtained in system flexibility and robustness to execution contingencies. Simulations (using up to 30 robots) as well as experiments with real robots (3) are presented and discussed.

Our approach in proposing the plan-merging paradigm as a cooperation scheme was to allow an efficient distribution of the decisions for a better reactivity to contingencies for multi-robot applications with loosely coupled tasks. The paradigm proved to be quite efficient because it exploits the fact that most conflicts can be solved locally and because it allows a finer overlapping between plan refinement, plan coordination and execution. We develop in this paper the mechanisms which allow one to extend this paradigm in order to obtain a scheme which distributes as much as possible the decision processes for planning and coordination while maintaining two key features: the coherence of the global system and the ability to detect the situations where it is not applicable; and a localized management of the planning and coordination processes with, in particularly intricate situations, a progressive transition to more global schemes which may "degrade" to a unique and centralized planning activity.