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 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.

I. Introduction

Multi-Agent Path Finding (MA-PF) seeks to find collision-free paths for multiple agents from their respective start to goal locations, which has been widely studied over the last decade [16]. This problem often requires optimizing a single objective, such as min-sum, i.e., minimizing the sum of individual path costs [14] or min-max, i.e., minimizing the maximum of individual costs of the agents [17]. The objective is typically defined over all the agents and hence the name cooperative path finding [15]. In this paper, we are interested in a variant of MA-PF where agents are grouped into multiple teams, where each team seeks to optimize its own objective (Fig. 1).