On the Scalable Multi-Objective Multi-Agent Pathfinding Problem
On the Scalable Multi-Objective Multi-Agent Pathfinding Problem
复制标题
可扩展的多目标多智能体寻路问题
DOI：
10.1109/cec48606.2020.9185585
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sanaz Mostaghim
中科院分区：
文献类型：
--
作者：
Jens Weise;Sebastian Mai;Heiner Zille;Sanaz Mostaghim
多智能体寻路问题（MAPF）在工业和机器人领域有着广泛的应用。一个MAPF求解器的目的是找到一组最佳的和非重叠的路径，为一些代理在导航方案。现有的方法成功地处理MAPF，无论是最大完工时间或流时间被用作一个单一的目标。在这篇文章中，我们把MAPF作为一个多目标优化问题（MOMAPF）。在本文中，我们考虑三个不同的目标函数，称为最大完工时间，流时间和路径重叠，这是在同一时间进行优化。本文中的MOMAPF问题被设计为多目标优化算法的可扩展测试问题，在这里我们可以扩展变量空间以反映不同的现实场景。我们提出了一个新的问题制定MOMAPF优化算法，并将其实施到NSGA-II和NSGA-III，并提供优化结果的实验评估。
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.