Mutex Propagation in Multi-Agent Path Finding for Large Agents

Authors

  • Han Zhang University of Southern California
  • Yutong Li University of Southern California
  • Jiaoyang Li University of Southern California
  • T. K. Satish Kumar University of Southern California
  • Sven Koenig University of Southern California

Keywords:

Problem Solving Using Search, Symmetry Handling

Abstract

Mutex propagation and its concomitant symmetry-breaking techniques have proven useful in Multi-Agent Path Finding (MAPF) with point agents. In this paper, we show that they can be easily generalized to richer MAPF problems. In particular, we demonstrate their application to MAPF with ``Large'' Agents (LA-MAPF). Here, agents can occupy multiple points at the same time according to their fixed shapes and sizes. While existing rule-based symmetry-breaking techniques are difficult to generalize from point agents to large agents, mutex-based symmetry-breaking techniques can be generalized easily. In a Conflict-Based Search (CBS) framework for LA-MAPF, we also develop a mutex-based conflict-selection strategy to further enhance the efficiency of the search. Through experiments on various maps, we show that our techniques significantly improve MC-CBS, a state-of-the-art optimal LA-MAPF algorithm, in terms of both success rate and runtime.

Downloads

Published

2022-07-17