Multi-Agent Path Finding for Large Agents

January 2019

Multi-Agent Path Finding for Large Agents

Authors:

Jiaoyang Li, Pavel Surynek, Ariel Felner, Hang Ma, T. K. Satish Kumar, and Sven Koenig

Abstract:

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a twolevel tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as “large” agents because they can occupy multiple points at the same time. In this paper, we formalize and study LAMAPF, i.e., MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MCCBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.
@conference{Li-2019-131435,
author = {Jiaoyang Li And Pavel Surynek And Ariel Felner And Hang Ma And T. K. Satish Kumar And Sven Koenig},
title = {Multi-Agent Path Finding for Large Agents},
booktitle = {Proceedings of 33rd AAAI Conference on Artificial Intelligence (AAAI '19)},
year = {2019},
month = {January},
pages = {7627 - 7634},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.