AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

A Hierarchical Approach to Multi-Agent Path Finding

Authors

Han Zhang,Mingze Yao,Ziang Liu,Jiaoyang Li,Lucas Terr,Shao-Hung Chan,T. K. Satish Kumar,Sven Koenig

University of Southern California,University of Southern California,University of Southern California,University of Southern California,University of Southern California,University of Southern California,University of Southern California,University of Southern California


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Extended Abstracts

Downloads:

Download PDF

Abstract:

Solving Multi-Agent Path Finding (MAPF) instances optimally is NP-hard, and existing optimal and bounded suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP is able to solve as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.

DOI:

10.1609/socs.v12i1.18586


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search