Abstract

Abstract: Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment. As solving MAPF optimally is NP-hard, researchers have been looking into algorithms that solve MAPF suboptimally but efficiently. Prioritized Planning (PP) and Priority-Based Search (PBS) are the leading algorithms in solving MAPF suboptimally by finding paths for individual agents, one at a time. PP pre-assigns a total priority ordering, while PBS only assigns a partial priority ordering on the fly to pairs of agents when a collision between them is detected. However, both algorithms become inefficient in MAPF instances with high densities of agents and obstacles. In this paper, we target PBS and introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques to further speed up GPBS, namely partial expansion, target reasoning, implicit constraints, and random restart. While the success rates among all MAPF instances under the 1-minute runtime limit of the state-of-the-art PP and PBS are 45 percent and 31 percent respectively, GPBS with all the improved techniques outperforms them and reaches 92 percent.

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.