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

Research output: Contribution to journalJournal article – Annual report year: 2019Researchpeer-review



View graph of relations

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
Pages (from-to)497-527
Publication statusPublished - 2019
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • 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
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

Download statistics

No data available

ID: 178279891