Planning Coordination and Execution in Multi-robots Environment

Rachid Alami, Félix Ingrand, Qutub, Samer

TL;DR

This paper introduces the Plan-Merging Paradigm (PMP), a novel approach for enabling multiple robots to coordinate their actions in a shared environment. PMP allows robots to incrementally build and adapt their plans, ensuring overall system coherence and detecting potential deadlocks, thus bridging the gap between centralized planning and distributed execution.

What Problem Does This Paper Address?

Coordinating multiple robots in a shared environment is a complex challenge. Existing approaches often focus on either decomposing and allocating tasks (C1) or managing the simultaneous operation of robots with independent goals (C2). However, many real-world multi-robot applications require both, where allocated tasks need further refinement and robots must navigate a dynamic environment with uncertainties and potential conflicts. This paper addresses the gap in providing a generic, robust framework for the C2 aspect, specifically focusing on how robots can collaboratively plan and execute tasks while avoiding collisions and ensuring system-wide coherence, especially when dealing with shared resources.

Methods

The core of the paper is the Plan-Merging Paradigm (PMP). PMP operates on a distributed, incremental, and cooperative scheme. Each robot maintains its own "world model" and plans. When a robot needs to incorporate a new goal or adapt to changes, it uses a Plan-Merging Operation (PMO).

There are two main PMO strategies:

  • Plan then Insert: A robot first generates a plan for its new goal independently, then attempts to integrate this plan into the existing coordinated plans of other robots. This involves communicating with relevant robots to obtain their current plans and then scheduling the new tasks while respecting existing constraints.
  • Search for an Insertable Plan: This more powerful approach integrates the coordination aspect directly into the planning process. The robot plans its actions while simultaneously considering the current plans of other potentially interacting robots. This requires a more comprehensive understanding of the multi-robot context.

A key aspect of PMP is its ability to detect "Planning Deadlock" situations, where a robot cannot insert its plan due to conflicts with other robots' plans. This signals a need for a more centralized or aggregated planning effort. The system also uses a distributed mutual exclusion protocol (DMEX) for managing access to shared planning resources.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and illustrates its application with simulated examples.

Key Insights and Ideas

  • Recursive Nature of Cooperation: The paper highlights that task decomposition (C1) and simultaneous operation (C2) are not always separate but can be recursively intertwined. A robot's execution of a task might necessitate further planning and coordination.
  • Incremental and Distributed Planning: PMP emphasizes that robots can build and adapt their plans incrementally and in a distributed manner, reducing reliance on a central authority and increasing robustness.
  • Plan-Merging as a Bridge: The PMP effectively bridges the gap between centralized planning (where a single entity plans for all) and distributed execution (where robots act independently). It allows for distributed planning with mechanisms for global coordination.
  • Deadlock Detection as a Control Mechanism: The ability to detect "Planning Deadlocks" is crucial. It acts as a signal that the current distributed approach is insufficient and a more coordinated or centralized planning effort is required, preventing system failure.
  • Hierarchical Cooperation: PMP can be applied hierarchically, starting with simpler cell-level coordination and progressing to more complex trajectory-level coordination when necessary, adapting to the complexity of the environment and tasks.

Key Results

The paper demonstrates the effectiveness of PMP through two examples:

  • Coordination at Cell Level: A simulation shows a fleet of mobile robots navigating a route network. PMP successfully coordinated their movements to avoid collisions at cell crossings, with robots performing Plan-Merging Operations in a specific order to ensure smooth transitions.
  • Trajectory Level Coordination: In a scenario with a large open area and obstacles, PMP was used to coordinate robot trajectories. The example illustrates how robots synchronize their paths to reach destinations, with synchronization holding between multiple robots.

While quantitative results are not the primary focus, the qualitative demonstrations show that PMP can achieve:

  • Coherent System Behavior: The union of all robot plans remains consistent and avoids conflicts.
  • Robustness to Execution Contingencies: The incremental and adaptive nature of PMP allows robots to handle unexpected events.
  • Flexibility: The system can adapt to changing environments and task requirements.

Limitations and Future Work

  • Intricate Puzzle-like Situations: The authors acknowledge that PMP might be insufficient in highly complex, "puzzle-like" situations where the conjunction of goals of multiple robots needs to be explicitly considered in a single planning step.
  • Scalability of Deadlock Resolution: While deadlocks are detected, the paper suggests that resolving them might lead to more aggregated or even fully centralized planning in very intricate scenarios, which could impact scalability.
  • Future Work: The paper implies that further research could explore more sophisticated deadlock resolution strategies and investigate the performance of PMP in larger, more complex multi-robot systems. The possibility of negotiating goals within the PMP framework is also mentioned as an area for further exploration.

Summary updated

Abstract

We present and discuss a generic cooperative s c heme 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 t h e m ulti-robot context. The robots are assumed to be able to collect the other robots current plans and goals and to produce plans which satisfy a set of constraints that will be discussed. We discuss the properties of this cooperative s c heme (coherence, detection of deadlock situations) as well as the class of applications for which i t i s w ell suited. We show h o w this paradigm can be used in a hierarchical manner, and in contexts where planning is performed in parallel with plan execution. We also discuss the possibility to negotiate goals within this framework and how this paradigm \\lls the gap" between centralised planning and distributed execution. We nally illustrate this scheme through an implemented system which allows a eet of autonomous mobile robots to perform load transfer tasks in a route network environment with a very limited cen-tralised activity and important gains in system ex-ibility and robustness to execution contingencies.
BibTeX
@inproceedings{alami1997planning,
  author = {Rachid Alami and Félix Ingrand and Qutub, Samer},
  title = {{Planning Coordination and Execution in Multi-robots Environment}},
  booktitle = {HAL},
  year = {1997},
}
Figure