Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree

August 2023

Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree

Authors:

Yimin Tang
Technical Report
CMU-RI-TR-23-41

Abstract:

Multi-Agent Path Finding (MAPF) and Combined Target-Assignment and Path-Finding problem (TAPF) arise in many applications such as robotics, computer gaming, warehouse automation and traffic management at road intersections.
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 Conflict-Based Search (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.
@techreport{Tang-2023-137482,
author = {Yimin Tang},
title = {Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree},
year = {2023},
month = {August},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-23-41},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.