Virtual Obstacles Regulation for Multi-Agent Path Finding

Abstract

Multi-agent path finding (MAPF) involves finding collision-free paths for multiple agents while minimizing the total path costs. Explicit estimation conflict-based search (EECBS) represents a state-of-the-art variant of the widely used conflict-based search (CBS) method, offering bounded-suboptimal solutions. However, both CBS and its variants rely on pairwise conflict resolution methods. A conflict boom means many conflicts occur at one location, which frequently exists in scenarios that a large number of agents operate in small space, and usually leads to heavy computational burden. The location that conflict boom occurs is regarded as conflict boom vertex. This letter proposes a novel method, the Virtual Obstacles Regulation, to expedite algorithmic solving processes (such as EECBS) for MAPF. The proposed method identifies conflicts boom vertices and strategically regulates them as global or local virtual obstacles to circumvent concentrated conflicts. Then, the pairwise conflict resolution processes on conflicts boom vertices are significantly simplified, hence accelerating overall algorithm runtime–often dominated by conflict resolution. Numerical studies validate the efficacy of this approach.