A Multi-Label A* Algorithm for Multi-Agent Pathfinding
A Multi-Label A* Algorithm for Multi-Agent Pathfinding
复制标题
一种用于多智能体寻路的多标签 A* 算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Hooker
中科院分区：
文献类型：
--
作者：
Florian Grenouilleau;W. V. Hoeve;J. Hooker
给定一组代理，多代理寻路问题包括确定，为每个代理，从其起始位置到其指定的目标，同时避免与其他代理的冲突的路径。最近的工作已经研究了问题的变体，其中代理被分配了一系列目标（任务），随着时间的推移，如在线多代理拾取和交付（MAPD）问题。在本文中，我们提出了一个多标签A* 算法（MLA*）的这个问题。它扩展了经典的A* 算法，允许计算具有多个有序目标的路径（例如拾取和交付）。此外，我们开发了一个新的基于h值的集中式启发式的MAPD。计算实验表明，我们提出的MLA* 获得了显着的改善，在最大完工时间和服务时间相比，现有的方法，同时更计算效率。在具有一千个任务和数百个代理的实例上，与现有技术相比，我们的方法将平均服务时间减少了43%，并且计算量大大减少。
Given a set of agents, the multi-agent pathfinding problem consists in determining, for each agent, a path from its start location to its assigned goal while avoiding collisions with other agents. Recent work has studied variants of the problem in which agents are assigned a sequence of goals (tasks) that become available over time, such as the online multi-agent pickup and delivery (MAPD) problem. In this paper, we propose a multi-label A* algorithm (MLA*) for this problem. It extends the classic A* algorithm by allowing the computation of paths with multiple ordered goals (such as a pickup and delivery). Moreover, we develop a new h-value-based centralized heuristic for the MAPD. Computational experiments show that our proposed MLA* obtains substantial improvements in terms of makespan and service time as compared to existing methods, while being more computationally efficient. On instances with a thousand tasks and hundreds of agents, our method reduces the average service time by 43% compared to the state of the art, with considerably less computational effort.