Polynomial-time Configuration Generator for Connected Unlabeled Multi-Agent Pathfinding

Abstract

We consider Connected Unlabeled Multi-Agent Pathfinding (CUMAPF), a variant of MAPF where interchangeable agents must be connected at all times. This problem is fundamental to swarm robotics applications such as self-reconfiguration and marching, where standard MAPF is insufficient as it does not guarantee the connectivity constraint. Despite its simple structure, CUMAPF remains understudied and lacks practical algorithms. We first develop an Integer Linear Programming (ILP) reduction to solve CUMAPF. Although this formulation provides a makespan-optimal plan, it is severely limited in terms of scalability and real-time responsiveness due to the large number of variables. We therefore propose a suboptimal but complete algorithm named PULL. It is based on a rule-based one-step function that computes a subsequent configuration that preserves connectivity and advances towards the target configuration. PULL is lightweight, and runs in O(n^2) time per step in 2D grid, where n is the number of agents. Empirically, PULL can quickly solve randomly generated instances containing hundreds of agents, which ILP cannot handle. Furthermore, PULL's solution substantially improves upon a naive approach to CUMAPF.