The paper addresses multi-agent pathfinding (MAPF), in which multiple agents must move on a graph from individual start locations to individual goals without collisions. Agents operate in discrete time and may either wait or move to an adjacent location. The overall difficulty increases with the number of agents and the complexity of the environment, and learned policies may enter deadlocks involving several agents. A deadlock can be difficult to recognize from the behavior of a learned policy, while random or simple corrective actions may not resolve the interactions among the involved agents.
The central contribution is to use an LLM as a high-level monitoring and intervention component rather than as a low-level planner for every agent and time step. LLMDR combines LLM-based deadlock detection and strategy generation with learned MAPF policies and prioritized planning. The LLM supplies agent priorities and preferred actions, while Priority Inheritance with Backtracking (PIBT) converts those preferences into collision-free one-step actions. This division is intended to exploit LLM reasoning for diagnosis and decision making without relying on the LLM for detailed spatial motion planning. The experiments also evaluate the same intervention framework with multiple learned MAPF base models and different agent counts.
LLMDR repeatedly examines a fixed-length window of action logs produced by a base model. The detection prompt classifies agents showing no movement or wandering as deadlocked, while agents that have always arrived, have arrived and remain stationary, or show consistent movement are not classified as deadlocked under the stated rules. Detected agents are grouped when they are within Manhattan distance two of one another; a nearby arrived agent can also be included in a group. The proposed strategy is the leader method for independently deadlocked agents or groups containing an agent whose goal is more than eight Manhattan units away. The radiation method is used when all agents in a group are less than eight Manhattan units from their goals and are likely to experience repeated deadlocks. The resulting priorities and action preferences are passed to PIBT, which uses reservations and recursive conflict handling to produce collision-free actions for an execution-plan interval. After that interval, the system starts another detection loop even if a deadlock remains.
The evaluation uses four standard MAPF benchmark maps: random32, random64, den312d, and warehouse. The tested agent counts are 4, 8, 16, 32, and 64; the maximum episode length is 256 steps on random32, random64, and den312d, and 512 steps on warehouse. The primary metrics are success rate, defined as the proportion of instances solved within the maximum step limit, and average episode length, defined as the mean number of steps used to solve the test instances. LLMDR is combined with the learned models DCC, DHC, and EPH, and the language-model experiments use gpt-3.5-turbo and gpt-4o. The first experiment contains 300 test instances, while the second and third contain 100 each; unless otherwise specified for hyperparameter analysis, the detection window is four and the execution-plan length is sixteen.
The reported warehouse results show especially large gains at high agent counts. With 64 agents, adding LLMDR raises DHC success rate from 1% to 83%, DCC from 14% to 74%, and the EPH base model without its original inference strategies and ensemble from 6% to 68%. With four agents, DHC and the EPH base model reach 100% success when combined with LLMDR, although the excerpt does not establish that every metric improves in every condition. The hyperparameter observations suggest that increasing the detection window beyond four does not provide significant additional benefit in the reported scenarios, possibly because many of those deadlocks are stagnation rather than oscillation or wandering. An execution-plan length of sixteen is described as a balance between giving the intervention enough steps and avoiding inefficiency from an unnecessarily long intervention. The supplied excerpt does not establish complete results for every map, solver, language model, or configuration, nor does it report statistical significance, the number of LLM calls, or real-time latency.
MAPF research includes systematic search solvers, such as Conflict-Based Search, and learning-based policies trained with reinforcement learning or related techniques. Conflict-Based Search can face poor scalability because of its exponential worst-case time complexity in difficult instances. Learning-based methods such as PRIMAL, DHC, and DCC seek generalization, decentralized pathfinding, and agent communication through learning, imitation, or graph-based mechanisms. Prior work has also combined learned action distributions with prioritized methods such as PIBT or LaCAM, while rule-based approaches have attempted to detect deadlocks from recent actions.
A learned MAPF policy can fail in ways that are not easy to identify from individual actions. When several agents block one another, a locally reasonable move or a random change may preserve the deadlock or create another conflict. Ordinary prioritized planning can encourage cooperation by letting higher-priority agents act first, but its priorities can also cause other agents to become stuck. LLMDR therefore targets the intermediate problem of recognizing when execution has entered a deadlock and selecting a coordinated corrective intervention.
PIBT extends prioritized planning with priority inheritance, backtracking, reservations, and recursive conflict resolution to generate a collision-free action for one step. LLMDR does not ask the LLM to construct all low-level paths; it uses the model to decide which agents and actions should receive priority. The default detection window is four actions and the default execution-plan length is sixteen steps. The intervention cycle proceeds for that plan length and then returns to detection, whether or not all deadlock symptoms have disappeared.
The first experiment compares base learned solvers and their LLMDR-augmented versions across maps and agent counts. The second studies the effect of the language model, and the third examines hyperparameters. In the warehouse setting with 64 agents, the reported hyperparameter tests compare detection-window lengths of 2 and 4, and execution-plan lengths of 8, 16, and 32. The excerpt states that 16 offered the observed balance between intervention capability and the risk of unnecessary intervention, but it does not provide all numerical values from those comparisons.
The supplied warehouse data indicate that LLMDR improves success rates for DHC, DCC, and the EPH base model, with the largest reported gains at 64 agents. The corresponding success-rate changes are 1% to 83% for DHC, 14% to 74% for DCC, and 6% to 68% for the EPH base model. Average episode length is lower in many of the listed augmented conditions, but the excerpt does not justify a claim of improvement for every solver, map, agent count, or language model. The abstract and conclusion characterize the overall result as improved scalability and performance, particularly in deadlock-prone scenarios.
LLMDR is a hybrid architecture that uses an LLM to inspect execution traces and propose high-level deadlock resolutions, while learned MAPF policies and PIBT handle low-level movement and collision avoidance. The reported experiments support the claim that this architecture can improve several learned MAPF models across increasing agent counts. Its main value is not replacing a MAPF solver, but adding a targeted recovery mechanism for situations in which the solver becomes stuck.
The paper explicitly identifies the computational cost of LLM inference as a limitation for resource-constrained and real-time applications. LLMs also have known difficulties with multi-agent coordination and spatial reasoning; assigning low-level planning to the learned model and PIBT is intended to reduce, rather than eliminate, that risk. The supplied excerpt does not establish inference latency, monetary cost, robustness to prompt or model changes, or a complete catalog of failure cases. It also does not provide enough evidence to determine how the method compares with every non-LLM deadlock detector under matched computational budgets.
The work presents a practical hybrid pattern for learned MAPF: retain a fast learned policy for ordinary execution and invoke an LLM-based supervisor when behavior suggests a deadlock. The reported gains on crowded warehouse instances indicate that such selective intervention may improve the scalability of learning-based solvers without making the LLM responsible for all spatial decisions. This makes the paper relevant to research on MAPF recovery, learned multi-robot coordination, and high-level use of language models in planning.
This paper is suitable for researchers studying learning-based MAPF, deadlock detection and recovery, prioritized planning, PIBT, or LLM-assisted robot planning. It is particularly relevant to readers interested in augmenting an existing learned solver with an intervention layer for high-agent-count or deadlock-prone scenarios. Readers seeking detailed latency, cost, statistical testing, or exhaustive ablation evidence should treat those aspects as unresolved by the supplied excerpt.