Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding

Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respec- tive starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Coop- erative 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 condi- tions 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.