An Optimization Variant of Multi-Robot Path Planning Is Intractable

Pavel SurynekAAAI 2010 · DOI

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.

The Conjugation Principle gadget forces a group of robots to move collectively to simulate a Boolean variable assignment.

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.

The complete reduction mapping a 3-SAT formula $F$ to a multi-robot path planning instance.

Results and Complexity Analysis

The paper successfully demonstrates that the makespan-optimal MRPP is NP-complete.

  1. 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.
  2. 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

BibTeX
@inproceedings{surynek2010optimization,
  author = {Pavel Surynek},
  title = {{An Optimization Variant of Multi-Robot Path Planning Is Intractable}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7767},
}
Figure