Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding [Extended Abstract]

Abstract

Multi-Agent Path Finding (MA-PF) finds collision-free paths for multiple agents from their respective start to goal locations. This paper investigates 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 minimize. 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. We show that the existing CBS and M* for MA-PF can be modified to solve MA-TC-PF, which is verified with tests. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front for MA-TC-PF.