The problem is multi-agent path finding on a 4-connected grid with obstacles, where every agent has both a location and an orientation. Agents receive a current goal from an external task-assignment module, and a new goal is assigned immediately after reaching the current one; future goals are not known in advance. The work focuses on online lifelong MAPF with a limited time budget and a rotation action model, in which changing orientation can consume multiple actions. Task assignment itself is outside the scope of the paper, so the proposed planner is evaluated as a routing component rather than as a complete task-allocation system. The supplied excerpt does not establish every detail of the action semantics or collision rules.
The main contribution is EPIBT, an enhanced version of PIBT that introduces bounded multi-action operations. Instead of invoking a separate path-planning routine, it evaluates short operation sequences directly, allowing the solver to look across several timesteps while retaining PIBT’s rule-based, local processing style. The method also adds agent revisiting within one step and operation inheritance, so an earlier decision can be reconsidered or an operation can be reused through the priority dependency structure. The paper further studies EPIBT together with large neighborhood search and graph guidance, reporting state-of-the-art performance for the evaluated online LMAPF-T problem. The excerpt does not provide all implementation details needed to reproduce every component independently.
Original PIBT is a single-step windowed solver. It assigns priorities, described as depending on distance to the goal, and processes agents in order while avoiding collisions; when an action requires another agent to move, priority is inherited and the procedure can backtrack to try alternatives. EPIBT replaces the single-action choice with a bounded set of multi-action operations, trying an operation and reverting it if the attempt fails. Agents may be revisited during the same step even after a collision-free choice has been found, but revisiting is limited to prevent excessive computation. Operation inheritance lets an agent receive an operation inherited from another agent when its own alternatives fail. In the broader configuration, large neighborhood search uses the remaining time budget to accept solutions that improve a goal-proximity-based metric, while graph guidance is also incorporated. For the rotation model, the excerpt names five operations used to mimic an omnidirectional action model: FWW, RFW, CFW, RRF, and WWW.
The evaluation uses the five maps from the League of Robot Runners competition: random-32-32-20, brc202d, Paris-1-256, sortation, and warehouse. Multiple agent-count instances are run using goal sequences from the public competition archive, while a cyclic task-pool assignment is used to avoid confounding effects from inter-agent task assignment. All methods run single-threaded on an Intel Xeon Gold 6338 system with 256 GB of RAM and receive a one-second time budget per timestep. Experiments use a 5,000-timestep horizon except on random-32-32-20, where the horizon is 1,000 timesteps. The ablation compares multi-action operations, revisiting, operation inheritance, and operation lengths of 3, 4, and 5, while the broader comparison includes PIBT, Causal PIBT, LNS-based configurations, graph-guided configurations, and other related approaches. The supplied excerpt does not report every per-instance number, complete baseline configuration, or statistical significance test.
The ablation evidence suggests that revisiting is valuable but that unlimited revisiting can consume the available time budget and reduce performance. Limiting revisits stabilizes both throughput and runtime. Longer operations increase runtime and only sometimes improve throughput, notably on large maps such as sortation and warehouse with 5,000 agents. The paper attributes the general advantage of length 3 to the fact that longer operations create more multi-agent collisions than the current collision-handling mechanism can resolve. The theoretical discussion preserves PIBT’s major properties only under the original graph assumption that adjacent nodes form simple cycles, so the guarantee is not established for arbitrary graphs. The authors identify better multi-agent collision handling and more efficient integration with LNS and graph guidance as future work. The excerpt also does not establish how the method behaves outside the selected maps, task sequences, and rotation-oriented setting.
Classical MAPF asks a group of agents to reach assigned goals without collisions, and optimal solving becomes difficult as the number or density of agents grows. Optimal methods such as CBS and ICTS face runtime and scalability challenges on large instances, motivating fast initial-solution methods, windowed approaches, and anytime optimization. PIBT is widely used as a low-level planner or action sampler because it can select collision-free actions for thousands of agents within milliseconds while considering only the immediate next timestep. That efficiency is also the source of its weakness when an agent must spend time rotating before it can make useful progress.
Each agent starts at a unique location and orientation on a grid whose cells may be traversable or blocked. Its state therefore includes both position and orientation, and only its currently assigned goal is visible at a given time. Once a goal is reached, the external assignment module supplies another one, producing a lifelong online routing problem. The experiments use a one-second computation budget per timestep, but the excerpt does not establish that this budget is a universal requirement of the problem definition.
A multi-action operation is a short action sequence rather than a single immediate action. Increasing operation length expands the number of reachable cells, states, and distinct occupied-cell sequences, which increases the search burden. The presented evaluation uses lengths 3, 4, and 5, and the rotation-model adaptation considers five named operations to emulate omnidirectional movement that may require two or three actions. EPIBT also supports revisiting and operation inheritance, while its theoretical analysis retains the original PIBT graph assumption. The excerpt states that the original PIBT proof properties are preserved under that assumption, but it does not establish stronger guarantees for arbitrary graphs or unrestricted operation lengths.
The first experimental component is an ablation of multi-action operations, revisiting, operation inheritance, and operation length. The authors evaluate lengths 3, 4, and 5 and examine their effects on runtime and throughput. The second component aggregates throughput across instances and compares EPIBT variants with PIBT, Causal PIBT, and configurations that add large neighborhood search or graph guidance. The final comparison evaluates EPIBT with both enhancements against other state-of-the-art approaches for online LMAPF-T. Exact per-map tables, all agent-count values, and full implementation parameters are not included in the supplied excerpt.
The paper reports that EPIBT consistently outperforms PIBT and Causal PIBT across all five evaluated maps. Limited revisiting improves performance substantially, whereas unlimited revisiting can exhaust the time budget; operation length 3 is usually best, although longer operations sometimes help on large maps. Even with 10,000 agents, EPIBT computes the next action in under 100 milliseconds according to the excerpt. EPIBT with length 3, LNS, and graph guidance achieves a score of 1.0 on three of the five maps and is reported to outperform the alternatives in most cases on the other two. Other methods occasionally do better on random-32-32-20 and brc202d, especially at low agent counts, so the claim is not that EPIBT wins every individual instance.
The paper introduces EPIBT as a PIBT modification designed for rotation action models. Multi-action operations provide a limited multi-timestep lookahead without launching a separate path planner, while revisiting and operation inheritance improve the handling of local dependencies. The reported evaluation shows improved throughput with fast runtime, and the combination with LNS and graph guidance is claimed to surpass the existing methods considered for online LMAPF-T. Within the supplied evidence, this supports a strong empirical result rather than a universal optimality or completeness claim.
The evaluation is confined to five competition-derived maps, selected goal sequences, a cyclic task-pool assignment, and the stated rotation-oriented problem setting. Generalization to other environments, task distributions, assignment policies, or action models is not established by the excerpt. Longer operations can create collisions that the current method cannot always resolve, and the theoretical properties rely on a graph-structure assumption inherited from PIBT. The excerpt also omits complete numerical results and does not quantify the contribution of every LNS or graph-guidance design choice separately.
The work is important because it targets a practical weakness of a highly scalable MAPF primitive without abandoning its lightweight local decision process. It offers a way to handle orientation and rotation costs while still generating actions quickly enough for large agent populations. The combination of a fast reactive core with LNS and graph guidance is relevant to warehouse logistics, transportation, and other settings where goals arrive online and computation is tightly bounded.
This paper is recommended for researchers studying MAPF, lifelong MAPF, MAPD, or online routing with orientation-dependent actions. It is particularly relevant to readers who use PIBT as a low-level planner or want to combine fast local planning with LNS and graph-guided improvement. Readers primarily interested in optimality guarantees or arbitrary-graph theory should treat the empirical scope and the stated graph assumption as important qualifications. It is also useful for comparing operation length, controlled revisiting, and inherited decisions as design choices in high-throughput multi-agent routing.