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:
- Path Planning: A path is planned for each robot independently.
- 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.
Trace Decomposition and Search
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.
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