Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree
Yimin Tang, Zhongqiang Ren, Jiaoyang Li, Katia Sycara
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% of 6,334 test cases.