Abstract
Multi-robot path planning (MRPP) is a fundamental challenge in robotics, requiring the coordination of multiple agents to reach targets without collisions. While finding any feasible solution is known to be solvable in polynomial time, this paper proves that finding the optimal makespan—the minimum time required for all robots to reach their destinations—is NP-complete. By employing a polynomial-time reduction from the 3-SAT problem, the author demonstrates that the introduction of parallelism and transitive moves does not alleviate the underlying computational complexity of optimization in MRPP.
Introduction
Multi-robot path planning involves navigating a set of robots across a graph from initial positions to target vertices. In modern applications like automated warehouses or swarm robotics, robots often move in parallel or follow each other in "train-like" transitive moves. Previous research established that the "pebble motion" problem (where only one agent moves at a time) is NP-hard to optimize. However, it remained an open question whether the added flexibility of parallel movement in modern MRPP systems simplifies the optimization task. This paper addresses the decision version of the makespan-optimal MRPP: determining if a solution exists within a given time bound $\zeta$.
Methodology: The 3-SAT Reduction
To prove NP-hardness, the author constructs a reduction from the Boolean Satisfiability problem (3-SAT). The reduction relies on two primary "gadgets" that translate logical constraints into spatial and temporal constraints within a graph.
The Conjugation Principle
The "Conjugation Principle" gadget is designed to simulate Boolean variables. It forces a group of robots to act as a single unit. In an optimal solution, this group must move collectively to one of two sets of vertices, $V^L$ (representing TRUE) or $V^R$ (representing FALSE). The structure of the graph ensures that the robots cannot split between these sets without violating the optimal makespan constraint.
Vertex Locking and Formula Construction
The second key component is "Vertex Locking," which prevents specific vertices from being used at certain time steps. By creating auxiliary paths and "bottleneck" robots that must occupy a vertex at a precise time to achieve the optimal makespan, the author can effectively "lock" that vertex against other robots.
By combining these gadgets, a complex graph is constructed where a valid path with a specific makespan exists if and only if the corresponding 3-SAT formula is satisfiable. Figure 3 illustrates how a specific 3-SAT formula $F$ is mapped onto the MRPP graph structure.
Results and Complexity Analysis
The paper successfully demonstrates that the makespan-optimal MRPP is NP-complete.
- Membership in NP: Since any solvable instance of the pebble motion problem has a solution of length $O(|V|^3)$, a candidate path sequence can be verified in polynomial time.
- NP-Hardness: The 3-SAT reduction confirms that the problem is at least as hard as any problem in NP.
The results highlight that while parallelism allows for faster execution, it significantly complicates the search for an absolute optimal schedule. The "transitive move" model, where a robot can enter a vertex as another leaves, is shown to be insufficient for reducing the problem's complexity class.
Conclusion and Future Work
This work provides a rigorous theoretical foundation for the difficulty of optimal multi-robot coordination. Because finding the exact optimal makespan is intractable, future research and practical applications should focus on approximation algorithms and heuristics that provide near-optimal solutions with manageable computational overhead. While this paper focuses on makespan, the techniques used—particularly the temporal "locking" of vertices—provide a framework for analyzing other optimization criteria in robotic motion planning.
Summary updated