Implicitly coordinated multi-agent path finding under destination uncertainty: Success guarantees and computational complexity

Bernhard Nebel, Thomas Bolander, Thorsten Engesser, Robert Mattmüller

Research output: Contribution to journalJournal articleResearchpeer-review

210 Downloads (Pure)

Abstract

In multi-agent path finding (MAPF), it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe. In the distributed setting, we either have to solve a sequence of NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, bounded plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.
Original languageEnglish
JournalJournal of Artificial Intelligence Research
Volume64
Pages (from-to)497-527
ISSN1076-9757
DOIs
Publication statusPublished - 2019

Keywords

  • Computer Theory (Includes Formal Logic, Automata Theory, Switching Theory and Programming Theory)
  • Computational complexity
  • Common knowledge
  • Computational costs
  • Multi agent
  • Path finding
  • PSPACE-complete
  • Multi agent systems

Fingerprint

Dive into the research topics of 'Implicitly coordinated multi-agent path finding under destination uncertainty: Success guarantees and computational complexity'. Together they form a unique fingerprint.

Cite this