On the Scalable Multi-Objective Multi-Agent Pathfinding Problem

Abstract

The Multi-Agent Pathfinding problem (MAPF) has several applications in industry and robotics. The aim of a MAPF-solver is to find a set of optimal and non-overlapping paths for a number of agents in a navigation scenario. Existing approaches are shown to successfully deal with MAPF, where either the makespan or flow-time is used as a single objective. In this article, we treat the MAPF as a multi-objective optimisation problem (MOMAPF). In this paper, we consider three different objective functions, called makespan, flow-time and path-overlaps which are to be optimised at the same time. The MOMAPF problem in this paper is designed to be a scalable test problem for multi-objective optimisation algorithms, where we can scale up the variable space to reflect different real-world scenarios. We propose a new problem formulation for MOMAPF optimisation algorithms and implement it into the NSGA-II and NSGA-III and provide an experimental evaluation of the optimisation results.