Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
- URL: http://arxiv.org/abs/2305.16303v1
- Date: Thu, 25 May 2023 17:56:24 GMT
- Title: Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
- Authors: Tzvika Geft
- Abstract summary: 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.
- Score: 0.190365714903665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem
arising in multi-agent systems with a wide range of applications. The problem's
intractability has led to extensive research on improving the scalability of
solvers for it. Since optimal solvers can struggle to scale, a major challenge
that arises is understanding what makes MAPF hard. We tackle this challenge
through a fine-grained complexity analysis of time-optimal MAPF on 2D grids,
thereby closing two gaps and identifying a new tractability frontier. First, we
show that 2-colored MAPF, i.e., where the agents are divided into two teams,
each with its own set of targets, remains NP-hard. Second, for the flowtime
objective (also called sum-of-costs), we show that it remains NP-hard to find a
solution in which agents have an individually optimal cost, which we call an
individually optimal solution. The previously tightest results for these MAPF
variants are for (non-grid) planar graphs. We use a single hardness
construction that replaces, strengthens, and unifies previous proofs. We
believe that it is also simpler than previous proofs for the planar case as it
employs minimal gadgets that enable its full visualization in one figure.
Finally, for the flowtime objective, we establish a tractability frontier based
on the number of directions agents can move in. Namely, we complement our
hardness result, which holds for three directions, with an efficient algorithm
for finding an individually optimal solution if only two directions are
allowed. This result sheds new light on the structure of optimal solutions,
which may help guide algorithm design for the general problem.
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) - 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) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - 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) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts.
We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances.
We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
arXiv Detail & Related papers (2023-04-28T07:09:23Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - 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) - Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy
Minimization [96.1052289276254]
We consider the maximum-a-posteriori inference problem in discrete graphical models and study solvers based on the dual block-coordinate ascent rule.
We map all existing solvers in a single framework, allowing for a better understanding of their design principles.
arXiv Detail & Related papers (2020-04-16T15:49:13Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
Some problems have many objectives which lead to a large number of non-dominated solutions.
This paper presents a new algorithm that has been designed to obtain the most significant solutions.
This new algorithm has been applied to the real world application in Unmanned Air Vehicle (UAV) Mission Planning Problem.
arXiv Detail & Related papers (2020-02-20T17:07:08Z)
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.