Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree
This addresses scalability issues in multi-agent systems for applications like robotics or logistics, though it is incremental as it builds on existing CBS-TA methods.
The paper tackles the Combined Target-Assignment and Path-Finding problem (TAPF) by developing Incremental Target Assignment CBS (ITA-CBS), which generates a single search tree and incrementally computes assignments to avoid computational bottlenecks, resulting in guaranteed optimal solutions and improved computational efficiency.
Combined Target-Assignment and Path-Finding problem (TAPF) requires simultaneously assigning targets to agents and planning collision-free paths for agents from their start locations to their assigned targets. As a leading approach to address TAPF, Conflict-Based Search with Target Assignment (CBS-TA) leverages both K-best target assignments to create multiple search trees and Conflict-Based Search (CBS) to resolve collisions in each search tree. While being able to find an optimal solution, CBS-TA suffers from scalability due to the duplicated collision resolution in multiple trees and the expensive computation of K-best assignments. We therefore develop Incremental Target Assignment CBS (ITA-CBS) to bypass these two computational bottlenecks. ITA-CBS generates only a single search tree and avoids computing K-best assignments by incrementally computing new 1-best assignments during the search. We show that, in theory, ITA-CBS is guaranteed to find an optimal solution and, in practice, is computationally efficient.