Multi-Agent Path Finding For Large Agents Is Intractable

• URL: http://arxiv.org/abs/2505.10387v1
• Date: Thu, 15 May 2025 15:07:40 GMT
• Title: Multi-Agent Path Finding For Large Agents Is Intractable
• Authors: Artem Agafonov, Konstantin Yakovlev,
• Abstract summary: The multi-agent path finding (MAPF) problem asks to find a set of paths on a graph such that when synchronously following these paths the agents never encounter a conflict.<n>In this paper we, for the first time, establish that the latter problem is NP-hard and, thus, if P!=NP no algorithm for it can, unfortunately, be presented.
• Score: 1.0550841723235613
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multi-agent path finding (MAPF) problem asks to find a set of paths on a graph such that when synchronously following these paths the agents never encounter a conflict. In the most widespread MAPF formulation, the so-called Classical MAPF, the agents sizes are neglected and two types of conflicts are considered: occupying the same vertex or using the same edge at the same time step. Meanwhile in numerous practical applications, e.g. in robotics, taking into account the agents' sizes is vital to ensure that the MAPF solutions can be safely executed. Introducing large agents yields an additional type of conflict arising when one agent follows an edge and its body overlaps with the body of another agent that is actually not using this same edge (e.g. staying still at some distinct vertex of the graph). Until now it was not clear how harder the problem gets when such conflicts are to be considered while planning. Specifically, it was known that Classical MAPF problem on an undirected graph can be solved in polynomial time, however no complete polynomial-time algorithm was presented to solve MAPF with large agents. In this paper we, for the first time, establish that the latter problem is NP-hard and, thus, if P!=NP no polynomial algorithm for it can, unfortunately, be presented. Our proof is based on the prevalent in the field technique of reducing the seminal 3SAT problem (which is known to be an NP-complete problem) to the problem at hand. In particular, for an arbitrary 3SAT formula we procedurally construct a dedicated graph with specific start and goal vertices and show that the given 3SAT formula is satisfiable iff the corresponding path finding instance has a solution.

Related papers

• Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
  Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide. Finding optimal solutions to MAPF is NP-Hard, yet modern optimal solvers can scale to hundreds of agents and even thousands in some cases. We show how this encoding can be effectively joined with existing encodings, resulting in a novel AS method we call MAPF Algorithm selection via Graph embedding.
  arXiv  Detail & Related papers  (2024-06-16T07:41:58Z)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP) We adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints.
  arXiv  Detail & Related papers  (2024-04-25T07:41:47Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
  We consider an Anonymous Multi-Agent Path-Finding (AMAPF) problem where the set of agents is confined to a graph. We suggest a specific search algorithm that leverages the idea of exploring the search space not through considering separate search states but rather bulks of them simultaneously. The resultant AMAPF solver demonstrates superior performance compared to the state-of-the-art competitor and is able to solve all publicly available MAPF instances in less than 30 seconds.
  arXiv  Detail & Related papers  (2023-12-17T00:49:30Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
  We show that 2-colored MAPF, where the agents are divided into two teams, each with its own set of targets, remains NP-hard. For the flowtime objective, we establish a tractability frontier based on the number of directions agents can move in. This result sheds new light on the structure of optimal solutions, which may help guide algorithm design for the general problem.
  arXiv  Detail & Related papers  (2023-05-25T17:56:24Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
  In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation. Traditional MAPF algorithms are not equipped to directly handle explainable-MAPF. We adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF.
  arXiv  Detail & Related papers  (2022-02-20T23:13:14Z)
• Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
  Multi-Agent Path Finding (MAPF) is a challenging problem that asks us to plan collision-free paths for a team of cooperative agents. We show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry. We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints.
  arXiv  Detail & Related papers  (2021-03-12T07:27:35Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.