Journal of Artificial Intelligence Research · 2019 · 16 citations · 33 references
ComputingAutonomous SystemsComputer ScienceAlgorithmsDistributed SystemsPath PlanningDecentralized PlanningDistributed AlgorithmsDistributed ComputingDistributed CoordinationMulti-agent SystemsMulti-robot CoordinationComplete ProblemsCoordination Under Communication ConstraintsDistributed Path PlanningMulti-agent Decision MakingMulti-agent Path PlanningMulti-agent PlanningNp-complete Problems
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.
33
Congenital Torticollis (Torticollis Not Related to Trauma) Chapter 28
edoc (University of Basel) · 2019 · 11.5K citations · Full text
Word problems requiring exponential time(Preliminary Report)
Larry J. Stockmeyer, Albert R. Meyer · 1973 · 874 citations