Solving Multiagent Path Finding on Highly Centralized Networks

Foivos Fioravantes, Dusan Knop, Jan Matyás Kristan, Nikolaos Melissinos, Michal Opler, Tung Anh VuAAAI 2025 · DOI

TL;DR

This paper investigates the computational complexity of the Multi-Agent Path Finding (MAPF) problem, focusing on its tractability in graphs with specific structural properties. The authors present new hardness results for MAPF on trees with bounded vertex cover or a limited number of leaves, while also introducing an efficient algorithm for graphs with bounded "distance to clique," a structure common in real-world networks.

What Problem Does This Paper Address?

The Multi-Agent Path Finding (MAPF) problem is a fundamental challenge in robotics and AI, concerned with finding collision-free paths for multiple agents to reach their designated goals in a shared environment (represented as a graph). The primary objective is to minimize the "makespan," which is the time taken for the last agent to reach its destination. While MAPF is known to be computationally hard (NP-complete), much research has focused on heuristic approaches. This paper delves into the realm of parameterized complexity, aiming to identify specific structural properties of the graph that, when bounded, allow for efficient (Fixed-Parameter Tractable or FPT) exact algorithms. The authors address gaps in understanding MAPF's complexity on certain graph structures and propose a novel FPT algorithm for a class of graphs that mirrors real-world scenarios.

Methods

The paper contributes both hardness results and an efficient algorithm.

Hardness Results: The authors prove that MAPF remains NP-hard even for graphs with specific structural constraints:

  • Bounded Vertex Cover: They show hardness for trees with a bounded vertex cover number (specifically, 7). This is surprising because vertex cover is often a parameter that leads to tractability.
  • Limited Leaves: They demonstrate hardness for trees with a limited number of leaves (specifically, 11). This is also unexpected, as trees with few leaves have a highly constrained structure.
  • Colored MAPF: They extend the hardness result to a variant called Colored MAPF, where agents of the same type share a set of possible destinations.

Efficient Algorithm (FPT): The main algorithmic contribution is an FPT algorithm for MAPF parameterized by the "distance to clique" of the graph. A graph has a distance to clique $d$ if removing $d$ vertices results in a complete graph (a clique). The algorithm works by:

  1. Bounding Makespan: Proving that if a solution exists, an optimal solution's makespan is bounded by a function of the distance to clique ($d$).
  2. Reducing the Problem: Creating a smaller, related MAPF instance on a subgraph that captures the essential constraints, particularly focusing on agents interacting with the non-clique part of the graph.
  3. Solving the Reduced Instance: Efficiently solving this smaller instance using FPT techniques, leveraging the bounded size of the subgraph.
  4. Extending the Solution: Extending the solution from the smaller instance back to the original graph.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unexpected Hardness: The paper reveals that even graphs with seemingly restrictive structures like bounded vertex cover or a small number of leaves can still pose significant computational challenges for MAPF. This suggests that simple structural properties might not be sufficient to guarantee tractability for MAPF.
  • "Distance to Clique" as a Tractable Parameter: The most significant algorithmic contribution is the FPT algorithm parameterized by distance to clique. This parameter is particularly interesting because it captures the essence of many real-world networks, such as transportation hubs connected to peripheral areas. This suggests that MAPF might be efficiently solvable in many practical scenarios.
  • Bridging Theory and Practice: The work highlights the importance of parameterized complexity in understanding the practical solvability of hard problems like MAPF. By identifying parameters that lead to efficient algorithms, researchers can better guide the development of practical solutions.

Key Results

  • NP-hardness: MAPF is proven to be NP-hard on trees with 9 internal vertices and vertex cover number 7.
  • NP-hardness: MAPF is proven to be NP-hard on trees with 11 leaves.
  • NP-hardness for Colored MAPF: Colored MAPF is NP-hard even with 6 agent groups and a tree with 11 leaves.
  • FPT Algorithm: An efficient (FPT) algorithm is presented for MAPF parameterized by the distance to clique ($d$). The algorithm guarantees an optimal solution and its runtime is bounded by a computable function of $d$.

Limitations and Future Work

  • Heuristic Motivation: The hardness results for bounded vertex cover and limited leaves suggest that heuristic approaches might still be necessary for these specific graph structures, as exact algorithms are unlikely to be efficient in general.
  • Practical Evaluation of FPT Algorithm: While the paper presents a theoretically efficient FPT algorithm for distance to clique, its practical performance on real-world instances would require further empirical evaluation.
  • Exploration of Other Parameters: The paper focuses on a few structural parameters. Future work could explore other graph parameters or combinations of parameters that might lead to tractability for MAPF.
  • Real-world Network Analysis: Further study could investigate the distribution of the "distance to clique" parameter in various real-world networks to assess the practical applicability of the proposed algorithm.

Summary updated

BibTeX
@inproceedings{fioravantes2025solving,
  author = {Foivos Fioravantes and Dusan Knop and Jan Matyás Kristan and Nikolaos Melissinos and Michal Opler and Tung Anh Vu},
  title = {{Solving Multiagent Path Finding on Highly Centralized Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i22.34484},
}
Figure