Preference-Based Multi-Objective Multi-Agent Path Finding

Multi-Agent Path Finding (MAPF) consists in computing a set of collision-free paths for a team of agents on a given graph while minimizing one objective, such as the sum of paths costs or the makespan. However, real-world applications may require the consideration of multiple objectives. Thus, in this work, we propose to address a novel extension of MAPF, Scalarized Multi-Objective MAPF (MOMAPF), that aims to optimize multiple given objectives while computing collision-free paths for all agents and incorporating the preferences of a decision maker over each objective. The preferences of a decision maker are reflected by a weight value associated to each objective and all weighted objectives are combined into one scalar to minimize. We introduce a solver for Scalarized MOMAPF based on Conflict-Based Search (CBS), Scalarized MO-CBS, that incorporates an adapted path planner based on an evolutionary algorithm, the Genetic Algorithm (GA). We also introduce three practical objectives to consider in path planning: efficiency, safety, and smoothness. We evaluate the performance of our proposed method in function of the input parameters of GA on experimental simulations.