Planning for Connected Agents in a Partially Known Environment
by Arthur Queffelec, Ocan Sankur, and François Schwarzentruber
Published onJun 08, 2021
Planning for Connected Agents in a Partially Known Environment
·
Abstract
The Connected Multi-Agent Path Finding (CMAPF) problem asks for a plan to move a group of agents in a graph while respecting a connectivity constraint. We study a generalization of CMAPF in which the graph is not entirely known in advance, but is discovered by the agents during their mission. We present a framework introducing this notion and study the problem of searching for a strategy to reach a configuration in this setting. We prove the problem to be PSPACE-complete when requiring all agents to be connected at all times, and NEXPTIME-complete in the decentralized case, regardless of whether we consider a bound on the length of the execution.
Creative Commons Attribution 4.0 International License (CC-BY 4.0)