Abstract

Abstract: Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents. Conflict-based search (CBS) is a state-of-the-art algorithm for solving MAPF optimally that repeatedly picks a collision (known as conflict) between two agents and resolves it by constraining the movement of the agents. One of the earliest runtime enhancement of CBS categorized conflicts into three groups (cardinal, semi-cardinal, and non-cardinal) and resolved them in that priority order. When multiple collisions share the same type, CBS typically breaks ties by selecting one at random. In this work, we show that CBS with disjoint splitting (which is another CBS' runtime enhancement) is further improved by introducing a more nuanced conflict prioritization strategy when multiple cardinal (or semi-cardinal) conflicts are present. More specifically, we prioritize conflicts that involve agents that participate in multiple cardinal (or semi-cardinal) conflicts. Our experiments show that the new conflict prioritization strategy reduces both the number of node expansions and the runtime of CBS with disjoint splitting for many instances from the standard MAPF benchmark suite.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.