A Hierarchical Approach to Multi-Agent Path Finding

Authors

  • Han Zhang University of Southern California
  • Mingze Yao University of Southern California
  • Ziang Liu University of Southern California
  • Jiaoyang Li University of Southern California
  • Lucas Terr University of Southern California
  • Shao-Hung Chan University of Southern California
  • T. K. Satish Kumar University of Southern California
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/socs.v12i1.18586

Keywords:

Problem Solving Using Search

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.

Downloads

Published

2021-07-21