Searching with Consistent Prioritization for Multi-Agent Path Finding

By Hang Ma, Daniel Damir Harabor, Peter James Stuckey, Jiaoyang Li, Sven Koenig. AAAI Conference on Artificial Intelligence, 2018

301 citations recorded by the source corpus.

We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/ea6214459ad9577ddefc3faca6500f785300a4ba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

A review of cooperative multi-agent deep reinforcement learning (2019, background): “Multi-agent path finding (MAPF) problem is an NPhard problem [101, 125].”
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning (2018, background): “MAPF is an NP-hard problem even when approximating optimal solutions [14], [15].”
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks (2019, methodology): “Most prior work on classical MAPF assumed stay-at-target, but recent work also considered the disappear-at-target assumption (Ma et al. 2019a).”