A Conflict-Based Search Framework for Multiobjective Multiagent Path Finding

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. The goal of the problem is thus to find a Pareto-optimal set of solutions instead of a single optimal solution. Naively applying existing multi-objective search algorithms, such as multi-objective A* (MOA*), to multi-agent path finding may prove to be inefficient as the dimensionality of the search space grows exponentially with the number of agents. This article presents an approach named Multi-Objective Conflict-Based Search (MO-CBS) that attempts to address this so-called curse of dimensionality by leveraging prior Conflict-Based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We also develop several variants of MO-CBS to improve its performance. We prove that MO-CBS and its variants can compute the entire Pareto-optimal set. Numerical results show that MO-CBS outperforms MOM*, a recently developed state-of-the-art multi-objective multi-agent planner. Note to Practitioners—The motivation of this article originates from the need to optimize multiple path criteria when planning conflict-free paths for multiple mobile robots in applications such as warehouse logistics, surveillance, construction site routing, and hazardous material transportation. Existing methods for multi-agent planning typically consider optimizing a single path criteria. This article develops a novel multi-objective multi-agent planner as well as its variants that are guaranteed to find all Pareto-optimal solutions for the problem. We also provide an illustrative example of the algorithm to plan paths for multiple agents that transport materials in a construction site while optimizing both path length and risk. In this example, computing and visualizing a set of Pareto-optimal solutions makes it intuitive for the practitioner to understand the underlying trade-off between conflicting objectives and to choose the most preferred solution for execution based on their domain knowledge.

I. Introduction

Multi-Agent Path Finding (MAPF) computes a set of collision-free paths for multiple agents connecting their respective start and goal locations while optimizing a scalar measure of paths. Variants of MAPF have been widely studied in the robotics community over the last few years [33]. In this article, we investigate a natural generalization of the MAPF to include multiple objectives for multiple agents and hence the name Multi-Objective Multi-Agent Path Finding (MOMAPF). In MOMAPF, agents have to trade-off multiple objectives such as completion time, travel risk and other domain-specific measures. MOMAPF is a generalization of MAPF, and is therefore NP-Hard [41].