Introduction
Multi-Robot Path Planning (MRPP) is a fundamental challenge in robotics, particularly in automated logistics and warehouse management. While finding any collision-free path for multiple robots on a graph can be achieved in polynomial time, the computational cost of finding the optimal path is significantly higher. This paper, presented at AAAI 2013, explores the theoretical foundations of MRPP, proving that finding optimal solutions is NP-hard across various movement models and optimization objectives.
Problem Formulation
The study considers a set of robots moving on a discrete graph. The goal is to transition from an initial configuration to a target configuration without collisions. The paper evaluates three primary optimization objectives:
- Minimum Total Arrival Time: Minimizing the sum of times each robot reaches its goal.
- Minimum Makespan: Minimizing the time the final robot reaches its destination (the deadline approach).
- Minimum Total Distance: Minimizing the total number of edges traversed by all robots.
These objectives are analyzed under three movement models: Pebble Motion on Graphs (PMG), where only one robot moves at a time; Parallel Moves (MPPp), allowing simultaneous movement; and Parallel Moves with Rotations (MPPpr), which permits synchronous rotations along fully occupied cycles.
Complexity and the 3SAT Reduction
The core contribution of this work is the proof of universal intractability. The authors demonstrate that computing the optimal solution for any of the three objectives is NP-complete for all movement models. To prove NP-hardness, they employ a reduction from the classic 3-Satisfiability (3SAT) problem.
As shown in the reduction gadgets above, the authors construct specialized graph structures where a valid, optimal robot path exists if and only if the corresponding logic formula is satisfiable. These "variable diamonds" and "clause nodes" ensure that the physical constraints of robot movement mirror the logical constraints of the 3SAT problem. Interestingly, the paper proves that even with only two groups of interchangeable robots, the problem remains NP-hard.
Structural Trade-offs and the Pareto Front
Beyond complexity, the paper identifies a fundamental structural conflict between different optimization goals. In many scenarios, it is impossible to optimize for speed and distance simultaneously.
In a simple cycle graph, a path that minimizes the makespan (getting the last robot home as fast as possible) might force other robots to take longer routes, thereby increasing the total distance traveled. This creates a "Pareto front" of solutions where improving one metric necessitates the degradation of another. The authors formally prove that this Pareto optimal structure is inherent to parallel and rotational movement models.
Conclusion and Future Work
The findings establish that optimal MRPP is fundamentally difficult, regardless of the movement model or objective chosen. This universal intractability suggests that future research should focus on two areas: developing efficient approximation algorithms that provide "near-optimal" solutions in polynomial time, and identifying specific graph topologies (such as grids or trees) where the problem might be more tractable. While this work focuses on discrete graphs, extending these proofs to continuous spaces with complex robot dynamics remains an open challenge.
Summary updated