Solving the Multi-Agent Path Finding Problem Using a Hierarchical Multi-Resolution Planner

Abstract

Multi-Agent Path Finding (MAPF) studies how to compute collision-free routes for multiple robots moving simultaneously on a shared map, a setting in which naive shortest-path behavior often leads to bottlenecks, deadlocks, and costly replanning. This paper proposes a hierarchical, reservation-based, multi-resolution planner for discrete-time grid environments. This paper extends CREDAR, our previously published algorithm [3], along the hierarchical direction that was proposed there as a future work. Each robot plans in a time-expanded state space ((x, y, t)) using A* while coordinating through a shared reservation table that prevents both vertex conflicts and edge-swap collisions. To improve guidance beyond Manhattan distance in maps with large obstacles and dead ends, the method builds a block-level abstraction of the grid. It computes a goal-rooted “true distance” estimate by running Reverse Dijkstra on the abstract graph. The resulting abstract distance map is cached per goal location and reused across agents and timesteps, enabling fast heuristic lookups during repeated replans. Several robustness mechanisms are included to stabilize execution in dense traffic, including deadline-aware priority guidelines to resolve reservation contention, boundary-based validation of abstract connectivity to avoid phantom links, and a wait-and-retry fallback when planning temporarily fails. To reduce agent convergence in narrow corridors without explicit communication, the planner adds a small congestion penalty derived from historical reservations, thereby biasing the search toward underutilized routes whilst preserving feasibility.