Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal with It
Abstract
In the Multiagent Connected Path Planning problem (MCPP), a team of agents moving in a graph-represented environment must plan a set of start-goal joint paths which ensures global connectivity at each time step, under some communication model. The decision version of this problem asking for the existence of a plan that can be executed in at most a given number of steps is claimed to be NP-complete in the literature. The NP membership proof, however, is not detailed. In this paper, we show that, in fact, even deciding whether a feasible plan exists is a PSPACE-complete problem. Furthermore, we present three algorithms adopting different search paradigms, and we empirically show that they may efficiently obtain a feasible plan, if any exists, in different settings.
Cite
Text
Tateo et al. "Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal with It." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11587Markdown
[Tateo et al. "Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal with It." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/tateo2018aaai-multiagent/) doi:10.1609/AAAI.V32I1.11587BibTeX
@inproceedings{tateo2018aaai-multiagent,
title = {{Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal with It}},
author = {Tateo, Davide and Banfi, Jacopo and Riva, Alessandro and Amigoni, Francesco and Bonarini, Andrea},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {4735-4742},
doi = {10.1609/AAAI.V32I1.11587},
url = {https://mlanthology.org/aaai/2018/tateo2018aaai-multiagent/}
}