Conflict-Based Search for Connected Multi-Agent Path Finding
This addresses the need for monitored execution in search and rescue scenarios, but it is incremental as it adapts an existing algorithm to a specific variant.
The paper tackles the problem of multi-agent path finding where agents must stay connected to each other and a base, applying it to search and rescue missions, and presents a variant of conflict-based search that handles disconnections instead of collisions, with experimental comparisons to existing methods.
We study a variant of the multi-agent path finding problem (MAPF) in which agents are required to remain connected to each other and to a designated base. This problem has applications in search and rescue missions where the entire execution must be monitored by a human operator. We re-visit the conflict-based search algorithm known for MAPF, and define a variant where conflicts arise from disconnections rather than collisions. We study optimizations, and give experimental results in which we compare our algorithms with the literature.