
We study the computational complexity of multi-agent path finding (MAPF) on grid graphs.
Given a graph $G$ and a set of agents, each having a start and target vertex, the goal is to find collision-free paths minimizing the total distance traveled.
Formulations restricting $G$ to be a 2D grid are ubiquitous, as it conveniently allows for modeling well-structured environments (e.g., warehouses).
Previous hardness results had $G$ either (1) be a 2D grid or (2) have more than one vertex unoccupied by a agent, but never considered both properties simultaneously.
The most restricted result for property (2) was shown for (non-grid) planar graphs.
We refine previous results by proving that distance-optimal MAPF remains NP-hard for both properties simultaneously, thereby settling an open problem posed in Banfi et al. (2017).
We present a reduction directly from 3SAT using simple gadgets, making our proof arguably more comprehensible and informative.
We explain the potential benefits of these qualities towards positive results.
Furthermore, our result is the first linear-time/size reduction for the case where $G$ is planar, appearing nearly four decades after the first related result.
This allows us to go a step further and exploit the Exponential Time Hypothesis (ETH) to obtain an exponential lower bound for the running time.
To the best of our knowledge, this is the first application of ETH to show \textit{any} concrete lower bound for MAPF.
Finally, as a stepping stone, we also show hardness for the monotone case, in which agents move one by one with no intermediate stops.

Refined Hardness of Distance-Optimal Multi-Agent Path Finding


**Session Chair:** <br><br> Angelo Ferrando

Oral Session 1C3-2

technical paper

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS 2022

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Tzvika Geft

1

8

SHORT BIO

Presentations

Refined Hardness of Distance-Optimal Multi-Agent Path Finding

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES