The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True
The determination of the computational complexity of multi-agent pathfinding on directed graphs (diMAPF) has been an open research problem for many years. While diMAPF has been shown to be polynomial for some special cases, only recently, it has been established that the problem is NP-hard in general. Further, it has been proved that diMAPF will be in NP if the short solution hypothesis for strongly connected directed graphs is correct. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.
Code (1)
Similar Papers 제목 키워드 기반
Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning
Multi-agent path finding (MAPF) in large networks is computationally challenging. An approach for MAPF is prioritized planning (PP), in which agents plan sequentially according to their priority. Albeit a computationally…
Motion PlanningMulti-Agent Path FindingTowards Information-Optimized Multi-Agent Path Finding: A Hybrid Framework with Reduced Inter-Agent Information Sharing
Multi-agent pathfinding (MAPF) remains a critical problem in robotics and autonomous systems, where agents must navigate shared spaces efficiently while avoiding conflicts. Traditional centralized algorithms with global …
Reinforcement LearningConflict-Based Search for Connected Multi-Agent Path Finding
We study a variant of the multi-agent path finding problem (MAPF) in which agents are required to remain connected to each other and to a designated base. This problem has applications in search and rescue missions where…
Multi-Agent Path FindingOptimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
We consider anonymous multi-agent path finding (MAPF) where a set of robots is tasked to travel to a set of targets on a finite, connected graph. We show that MAPF can be cast as a special class of multi-marginal optimal…
EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazo…
Multi-Agent Path Finding