Multi-Agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds

Klaus-Tycho Förster, Linus Groner, Torsten Hoefler, Michael König, Sascha Schmid, Roger Wattenhofer

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

3 Citations (Scopus)

Abstract

We investigate the multi-agent pathfinding (MAPF) problem with $n$ agents on graphs with $n$ vertices:
Each agent has a unique start and goal vertex, with the objective of moving all agents in parallel movements to their goal s.t.~each vertex and each edge may only be used by one agent at a time.
We give a combinatorial classification of all graphs where this problem is solvable in general, including cases where the solvability depends on the initial agent placement.
Furthermore, we present an algorithm solving the MAPF problem in our setting, requiring O(n²) rounds, or O(n³) moves of individual agents.
Complementing these results, we show that there are graphs where Omega(n²) rounds and Omega(n³) moves are required for any algorithm.
Original languageEnglish
Title of host publicationAlgorithms and Complexity : 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings
Number of pages13
PublisherSpringer
Publication date17 Apr 2017
Pages247
Chapter259
ISBN (Print)978-3-319-57585-8
ISBN (Electronic)978-3-319-57586-5
DOIs
Publication statusPublished - 17 Apr 2017
EventAlgorithms and Complexity - Athens, Greece
Duration: 24 May 201726 May 2017
Conference number: 10
http://www.corelab.ntua.gr/ciac2017/

Conference

ConferenceAlgorithms and Complexity
Number10
Country/TerritoryGreece
CityAthens
Period24/05/201726/05/2017
Internet address
SeriesLecture Notes in Computer Science
Volume10236
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Multi-Agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds'. Together they form a unique fingerprint.

Cite this