Multiple Path Coordination for Mobile Robots: A Geometric Algorithm

Stéphane Leroy, Jean-Paul Laumond, Thierry Siméon

Introduction

In the late 1990s, Leroy, Laumond, and Simeon introduced a landmark approach to the multi-robot coordination problem. While contemporary algorithms struggled with more than a handful of agents, their geometric method demonstrated the capability to coordinate over 100 robots simultaneously. This paper presents a decoupled algorithm that manages the timing of multiple robots along pre-planned paths to ensure collision-free navigation in cluttered environments.

The Multi-Robot Coordination Problem

Planning for multiple agents is fundamentally difficult due to the "curse of dimensionality," where the configuration space grows exponentially with the number of robots. To address this, the authors utilize a decoupled approach:

  1. Path Planning: A path is planned for each robot independently.
  2. Velocity Coordination: Robots' velocities are coordinated along these paths to avoid collisions.

The core challenge lies in searching the high-dimensional space for a collision-free "schedule." Unlike previous methods that relied on rigid grids or were limited to very few robots, this algorithm seeks a scalable solution that maintains resolution completeness.

Geometric Methodology

Coordination Diagrams and Bounding Boxes

The problem is represented in an $n$-dimensional cube where each axis represents the progress of a robot along its path. To simplify the search, the authors avoid calculating exact collision zone shapes. Instead, they use minimal bounding boxes defined by "coordination configurations"—the specific points where a robot enters and leaves the swept area (trace) of another.

Geometric representation of robot paths and swept areas used to define collision intervals (a1, b1, etc.).

Paths are restricted to sequences of straight lines and circular arcs, allowing for rapid and exact geometric calculations of the swept volumes. The algorithm then uses A* search to find a path through the coordination diagram. It specifically targets "Manhattan paths," where only one robot moves at a time, simplifying the search space significantly.

The coordination pipeline: (a) robot paths, (b) collision zones in the coordination space, (c) grid discretization, and (d) the resulting Manhattan search path.

Scalability via Interaction Graphs

The primary engine for scalability is the interaction graph. The algorithm constructs a graph where robots are nodes and edges represent intersecting paths. By identifying the connected components of this graph, the algorithm breaks a massive swarm into smaller, independent subgroups. This insight reveals that even in a swarm of 150 robots, most coordination tasks are actually several small, independent problems involving only 5 to 10 robots.

Results and Discussion

The algorithm was evaluated on complex simulated scenarios, including a large-scale test with 150 robots in a highly cluttered environment. Key results include:

  • Efficiency: For a 32-robot case, the entire process took roughly 40 seconds on a Sparc Ultra-1.
  • Search Speed: Once the coordination diagram was constructed, the A* search for a 150-robot solution required only 1.5 seconds.

Limitations

Despite its efficiency, the algorithm is strictly decoupled; if pre-planned paths make coordination impossible (e.g., a head-on meeting in a narrow corridor), it cannot re-route robots. Additionally, the Manhattan motion produced is not time-optimal, though the authors suggest a smoothing post-processing step to enable simultaneous motion. Finally, performance may degrade if the interaction graph forms a single, massive connected component.

Summary updated

Abstract

This paper presents a geometric based approach for multiple mobile robot motion coordination. All the robot paths being computed independently, we address the problem of coordinating the motion of the robots along their own path in such a way they do not collide each other. The proposed algorithm is based on a bounding box representation of the obstacles in the so-called coordination diagram. The algorithm is resolution-complete. Its efficiency is illustrated by examples involving more than 100 robots. 1 Introduction: Path coordination This paper addresses the following problem: consider n mobile robots sharing the same workspace and planning their paths independently; n such paths being given we want to devise an algorithm deciding whether coordinated motions exist for the mobile robots along their own paths, so that each robot can reach its own goal without colliding the other ones. The problem is known as the multiple robot path coordination problem [ Latombe, 1991b ] ....
BibTeX
@inproceedings{leroy1999multiple,
  author = {Stéphane Leroy and Jean-Paul Laumond and Thierry Siméon},
  title = {{Multiple Path Coordination for Mobile Robots: A Geometric Algorithm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure