Multi-agent path finding in configurable environments

Multi-Agent Path Finding (MAPF) plays an important role in many real-life applications where autonomous agents must coordinate to reach their goals without collisions. MAPF problems often take place in structured environments that are usually assumed to be static and known in advance. In this paper, we introduce C-MAPF, i.e., MAPF in Configurable environments, a novel variant of the MAPF problem in which the environment is configurable, namely its structure and topology can be controlled within some given constraints. Consider, for instance, a warehouse logistics application: the environment can be changed (at least to some degree) by the managers of the warehouse, for example by re-arranging the positions of the shelves or by removing or adding temporary walls. We study the properties of the C-MAPF problem and we devise two algorithms for solving it, both based on Conflict-Based Search (CBS), a state-of-the-art MAPF algorithm. First, we present Parallel CBS (P-CBS), that searches for a solution by simultaneously considering all the possible configurations of the environment. We then present Abstract CBS (A-CBS), an extended version of the CBS algorithm that solves C-MAPF problems by introducing a new type of conflict on the allowable configurations of the environment. We prove that our solvers are both complete and optimal and we experimentally assess their performance in different settings.