Robust Multiagent Combinatorial Path Finding

Consider a system of multiple physical agents tasked with collaboratively collecting a set of spatially distributed goals as quickly as possible while avoiding collisions with the environment and with each other. This type of problem, which involves Multi-Agent Path Finding (MAPF) and task allocation, is called Multi-Agent Combinatorial Path Finding (MACPF). Prior work on MACPF assumed each agent has a final goal it must reach, there are no orientation constraints on the agents' movements, and the agents will follow their planned actions as intended. These assumptions rarely hold in real physical robots, which limits the applicability of existing MACPF algorithms in practical applications. We propose the Robust CBSS framework, a robust planning approach that solves MACPF without the aforementioned simplifying assumptions, and provide two implementations: a baseline version (RCbssBase) and an efficient version (RCbssEff). RCbssEff generalizes the Conflict-Based Steiner Search (CBSS) algorithm, building on ideas from the p-Robust CBS algorithm and algorithms for solving the Equality Generalized Traveling Salesman Problem. We prove that RCbssEff is complete and can be configured to return optimal solutions. Experimental results on benchmark MACPF problems show that RCbssEff balances planning time, solution cost, and collision reduction compared to baselines.