Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding
Zhongqiang Ren, Chaoran Zhang, Sivakumar Rathinam, Howie Choset
Abstract
Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. To solve MA-TC-PF, we propose two algorithms TC-CBS and TC-M*, which leverage the existing CBS and M* for conventional MA-PF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front. We present numerical results for several types of MA-TC-PF problems.
BibTeX
@inproceedings{icra2023_searchalgorithms,
title = {Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding},
author = {Zhongqiang Ren and Chaoran Zhang and Sivakumar Rathinam and Howie Choset},
booktitle = {ICRA 2023},
year = {2023}
}