On Merging Agents in Multi-Agent Pathfinding Algorithms

Authors

  • Eli Boyarski Ben-Gurion University of the Negev
  • Shao-Hung Chan University of Southern California
  • Dor Atzmon Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Sven Koenig University of Southern California

Keywords:

Analysis Of Search Algorithms, Meta Reasoning And Search

Abstract

In Multi-Agent Pathfinding (MAPF), the task is to find non-colliding paths for a set of agents. This paper focuses on search-based MAPF algorithms from the Conflict-Based Framework, which is introduced here. A common technique in such algorithms is to merge a group of dependent agents into a meta-agent and plan non-colliding paths for the meta-agent using a low-level MAPF sub-solver. We analyze the patterns that emerge when agents are merged in an arbitrary order. We then introduce policies for choosing which agents or meta-agents to merge to achieve improved efficiency in three algorithms: Independence Detection (ID) and Improved Conflict-Based Search (ICBS), which are optimal, and Priority-Based Search (PBS), which is a fast suboptimal algorithm. Experimental results show a significant improvement in efficiency

Downloads

Published

2022-07-17