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.

本研究提出了一种名为 ITA-CBS 的增量目标指派 CBS 方法，该方法不需要计算 K 个最佳任务分配，只在搜索过程中增量计算新的最佳分配，有效避免了多个搜索树中的冲突，保证了最优解和计算效率。