Publication

Y. Tang, Z. Ren, J. Li and K. Sycara. Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree. In International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pages 8-14, 2023.

Abstract: The Combined Target-Assignment and Path-Finding (TAPF) problem requires simultaneously assigning targets to agents and planning collision-free paths for them from their start locations to their assigned targets. As a leading approach to addressing TAPF, Conflict-Based Search with Target Assignment (CBS-TA) leverages K-best target assignments to create multiple search trees and Conflict-Based Search (CBS) to resolve collisions in each tree. While CBSTA finds optimal solutions, it faces scalability challenges due to the duplicated collision resolution in multiple trees and the expensive computation of K-best assignments. We introduce 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 ITA-CBS, in theory, is guaranteed to find optimal solutions and, in practice, runs faster than CBS-TA in 96.1 percent of 6,334 test cases.

Download the paper in pdf.