A Multi-Label A* Algorithm for Multi-Agent Pathfinding

Authors

  • Florian Grenouilleau Polytechnique Montreal
  • Willem-Jan van Hoeve Carnegie Mellon University
  • J. N. Hooker Carnegie Mellon University

Abstract

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.

Downloads

Published

2021-05-25

How to Cite

Grenouilleau, F., Hoeve, W.-J. van, & Hooker, J. N. (2021). A Multi-Label A* Algorithm for Multi-Agent Pathfinding. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 181-185. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/3474