Improved Complexity Results and an Efficient Solution for Connected Multi-Agent Path Finding

Connected multi-agent path finding (CMAPF) consists in computing paths for multiple agents which must reach a goal configuration while remaining connected at all steps. We prove the PSPACEhardness of the problem when the underlying graph is a subgraph of a 3D grid and with range-based connectivity. Moreover, we provide an application of the WHCA * algorithm and show that it outperforms previously given algorithms by an order of magnitude in terms of the sizes of the instances it can handle.