Paper deep dive
From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs
Hiroki Nagai, Keisuke Okumura
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/8/2026, 4:02:55 PM
Summary
This paper introduces Multi-Agent Warehouse Pathfinding (MAWPF), a practical extension of classical Multi-Agent Pathfinding (MAPF) tailored for differential-drive AGVs in warehouse automation. MAWPF incorporates four key constraints: straight motion and in-place rotation, multi-step rotation costs, acceleration/deceleration dynamics, and follower collision avoidance. The authors adapt and benchmark four lightweight MAPF algorithms (PP, LNS2, PIBT, LaCAM) on this problem, finding that while PP and LNS2 struggle with large agent counts, PIBT-based approaches (especially multi-step variants) offer superior scalability. The work bridges the gap between theoretical gridworld MAPF and real-world warehouse operations.
Entities (8)
Relation Signals (9)
Multi-Agent Pathfinding → extendedby → Multi-Agent Warehouse Pathfinding
confidence 95% · We introduce the multi-agent warehouse pathfinding (MAWPF) problem as a gridworld counterpart of MAPF tailored to warehouse environments
Multi-Agent Warehouse Pathfinding → targets → Differential-drive AGVs
confidence 92% · tailored to differential-drive AGVs
PIBT → adaptedfor → Multi-Agent Warehouse Pathfinding
confidence 91% · We therefore extend PIBT to a multi-step variant... enabling PIBT-style coordination for differential-drive MAPF.
LaCAM* → adaptedfor → Multi-Agent Warehouse Pathfinding
confidence 90% · We retain the high-level search and replace the configuration generator with PIBT for MAWPF
Multi-Agent Warehouse Pathfinding → includesconstraint → Follower collisions
confidence 90% · follower collisions are prohibited to prevent rear-end crashes
PIBT-based approaches → achieves → Preferable scalability
confidence 89% · PIBT-based approaches achieve preferable scalability with increased solution cost.
LNS2 → evaluatedon → Multi-Agent Warehouse Pathfinding
confidence 88% · we adapt representative suboptimal MAPF algorithms-PP, LNS2, PIBT, and LaCAM-and conduct comprehensive benchmarking.
Prioritized Planning → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-agent pathfinding (MAPF) under one-shot planning is a core component of warehouse automation, yet classical formulations typically assume four-connected 2D grids with unit-time moves in four directions. To fill reality gaps while still being trackable with discrete combinatorial search, this work proposes a more practical counterpart tailored to differential-drive AGVs. We term this multi-agent warehouse pathfinding (MAWPF), featured with four constraints: (i) agent actions are restricted to straight motion and in-place rotation; (ii) rotations require multi-step costs; (iii) acceleration and deceleration are considered, and; (iv) follower collisions are prohibited to prevent rear-end crashes. To solve MAWPF efficiently, we adapt representative suboptimal MAPF algorithms-PP, LNS2, PIBT, and LaCAM-and conduct comprehensive benchmarking. Our experiments reveal that PP and LNS2 struggle to solve instances with many agents, while PIBT-based approaches achieve preferable scalability with increased solution cost. We believe that these constitute an important step toward adapting classical gridworld MAPF to operational warehouse setups.
Tags
Links
- Source: https://arxiv.org/abs/2605.15799v1
- Canonical: https://arxiv.org/abs/2605.15799v1
Trouble viewing inline? Open PDF directly →
Full Text
40,980 characters extracted from source content.
Expand or collapse full text
From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs Hiroki Nagai 1,2 , Keisuke Okumura 1 1 National Institute of Advanced Industrial Science and Technology (AIST), Japan 2 Keio University, Japan nagai.hiroki39,okumura.k@aist.go.jp Abstract Multi-agent pathfinding (MAPF) under one-shot planning is a core component of warehouse au- tomation, yet classical formulations typically as- sume four-connected 2D grids with unit-time moves in four directions. To fill reality gaps while still being trackable with discrete combinatorial search, this work proposes a more practical coun- terpart tailored to differential-drive AGVs. We term this multi-agent warehouse pathfinding (MAWPF), featured with four constraints: (i) agent actions are restricted to straight motion and in-place rotation; (i) rotations require multi-step costs; (i) acceler- ation and deceleration are considered, and; (iv) fol- lower collisions are prohibited to prevent rear-end crashes. To solve MAWPF efficiently, we adapt representative suboptimal MAPF algorithms—P, LNS2, PIBT, and LaCAM—and conduct com- prehensive benchmarking.Our experiments re- veal that P and LNS2 struggle to solve instances with many agents, while PIBT-based approaches achieve preferable scalability with increased solu- tion cost. We believe that these constitute an im- portant step toward adapting classical gridworld MAPF to operational warehouse setups. 1 Introduction Multi-agent pathfinding (MAPF) is a versatile abstraction for a variety of multi-agent planning problems, such as traffic in- tersection management [ Dresner and Stone, 2008 ] , railway scheduling [ Li et al., 2021a ] , autonomous parking [ Okoso et al., 2019 ] , and conveyor routing [ Kato and Okumura, 2026 ] . To enhance its engineering transferability beyond spe- cific applications or infrastructures, most academic studies on MAPF adopt a gridworld scenario [ Stern et al., 2019 ] , in which all agents use a planar graph as a workspace represen- tation—typically a four-connected 2D grid—and take unit- length actions in unit time, in a fully synchronous manner. In this gridworld context, at each timestep, each agent occu- pies exactly one cell, which simplifies collision management. Such an assumption indeed reflects several characteristics of real-world warehouse setups [ Wurman et al., 2008 ] , a repre- sentative MAPF application, where autonomous guided ve- state action 푥,푦 stay MAPF MAWPF state action 푥,푦,휃,푣 stay Figure 1: Classical MAPF and MAWPF. hicles (AGVs) perform tasks while following predefined grid structures. This gridworld abstraction has enabled the research com- munity to develop a wide variety of capable and foundational MAPF algorithms. In fact, recent developments of real-time, scalable MAPF algorithms—such as PIBT [ Okumura et al., 2022 ] and LaCAM [ Okumura, 2023b ] —are remarkable, ca- pable of handling hundreds of agents in a second. Meanwhile, to deploy these algorithms in actual warehouse setups and maximize overall system performance, it is necessary to in- corporate robot kinodynamic constraints tailored to AGVs. Such constraints include (i) rotation constraints, where an AGV cannot move in an arbitrary direction, (i) turning ac- tion costs, where an AGV cannot complete a 90-degree rota- tion within a single time unit, (i) follower conflicts, where an AGV must avoid entering a cell that was just vacated, and (iv) acceleration and deceleration considerations, where an AGV can traverse multiple cells within a single time unit. Although several established post-processing methods ex- ist to translate gridworld MAPF plans into AGV-compatible ones [ H ̈ onig et al., 2016 ] , these approaches inherently rely on suboptimal plans due to their use of over-simplified robot dynamics, making it difficult to achieve high system perfor- mance [ Yan et al., 2025 ] . Several studies have also explored extensions of gridworld MAPF—for example, incorporating rotation constraints [ Zhang et al., 2023; Chan et al., 2024 ] — yet a unified formulation that integrates multiple practical AGV-specific considerations within a single framework is missing. The aforementioned four AGV-related considerations are common in multi-AGV systems across different infrastruc- arXiv:2605.15799v1 [cs.MA] 15 May 2026 tures. Given their economic impact and universality, we con- sider it valuable to define the corresponding problem that bridges academic research and industrial practice in MAPF. To this end, we introduce the multi-agent warehouse pathfinding (MAWPF) problem as a gridworld counterpart of MAPF tailored to warehouse environments, and investi- gate how computationally lightweight MAPF algorithms can be adapted to this setting. MAWPF is carefully designed to capture the aforementioned four constraints stemming from AGV dynamics, while discrete, combinatorial search-based MAPF algorithms remain applicable with modest adapta- tion. In particular, we describe how representative MAPF solvers—Prioritized Planning (P) [ Erdmann and Lozano- Perez, 1987 ] , LNS2 [ Li et al., 2022 ] , PIBT, and LaCAM— are applied to MAWPF. We then systematically evaluate these solvers to delineate their current capabilities and limitations. We believe that this effort represents an important step to- ward upgrading conventional MAPF benchmarking with real- world grounding and operational relevance. We begin the rest with the classical MAPF formulation and then define MAWPF, followed by reviews of MAPF al- gorithms and kinematics-aware variants. After that, we de- scribe how MAPF algorithms are applied to MAWPF and re- port their empirical performance. The code and appendix are available from https://github.com/hirokiNagai-39/mawpf. 2 Classical MAPF To facilitate understanding of MAWPF, we here describe the classical yet most commonly-used MAPF formulation [ Stern et al., 2019 ] to date. The system consists of a set of agents A = 1, 2,...,n operating on a graph G = (V,E) un- der a discrete, globally synchronized time model. At each timestep, an agent may either wait at its current vertex or move to an adjacent vertex. Feasibility is defined with respect to two collision constraints: (i) vertex conflicts, where two agents occupy the same vertex at the same time, and (i) edge conflicts, where two agents traverse the same edge in oppo- site directions within a single timestep. Given distinct start and goal vertices (s i ,g i ) ∈ V × V for each agent i ∈ A, the one-shot MAPF problem asks for a finite sequence of actions for every agent that brings all agents from their starts to their respective goals without conflicts. Solution quality is eval- uated using the sum-of-costs (SoC) (aka. flowtime), defined as the sum, over all agents, of the time until each agent first reaches its goal and remains there thereafter. 3 MAWPF Classical MAPF provides a simple and intuitive abstraction for coordinating multiple agents, which has made it a widely used benchmark problem. However, it often departs from the operational realities of warehouse transportation, where differential-drive AGVs are prevalent and their motion is con- strained by heading changes and speed control. To investigate how standard MAPF algorithms behave under such more re- alistic conditions, we first introduce a problem formulation that reflects these constraints. Specifically, we propose multi- agent warehouse pathfinding (MAWPF) as an MAPF tailored to the realities of automated warehouse distribution. The dif- ferences from classical MAPF are described below, and Fig. 1 provides an overview. 3.1 Problem Definition Workspace. We consider a four-connected 2D grid map with static obstacles. The workspace is modeled as a graph G = (V,E), where V is the set of obstacle-free cells and E connects pairs of four-neighbor cells; agents move along edges in E. Configuration. In MAWPF, a configurationQ refers to the array of states of all agents at a given timestep. Unlike classi- cal MAPF, each agent state includes not only its grid location but also its direction and speed. Formally, Q[i] = (x i ,y i ,θ i ,v i ) v i ∈0, 1,...,V max .(1) Here, speed v is the number of grid cells advanced in the next time step, and θ is the angle measured counterclockwise from the positive x-axis. In addition, the model is parameterized by V max , the maximum number of grid cells an agent can traverse in one timestep, and T rot , the number of timesteps required to complete a 90 deg rotation. Action. At each timestep, agent i updates its state by ap- plying (i) movement and then (i) speed change. In the move- ment phase, the agent selects exactly one of the following: stay, forward, or rotation. The stay action keeps the agent at the current cell and is available only when v i = 0. The forward action moves the agent straight ahead by v i cells in the direction θ i ; this action is available only when θ i ∈ 0, 90, 180, 270 deg. The rotation action rotates the agent on the spot by 90/T rot deg clockwise or counterclockwise, and it is available only when v i = 0. After the movement phase, the agent performs a speed change by selecting exactly one of keep, acceleration, or deceleration. The keep action leaves the speed unchanged. The acceleration action increases the speed by one, i.e., v i ← v i + 1, and is available only when v i < V max and θ i ∈ 0, 90, 180, 270 deg. The deceleration action de- creases the speed by one, i.e., v i ← v i − 1, and is available only when v i > 0 and θ i ∈ 0, 90, 180, 270 deg. Conse- quently, an agent cannot accelerate or stop abruptly. Vertex Occupation. At timestep t, during the movement Q t [i]→Q t+1 [i], agent i occupies the entire line segment range from geometric vertex (x t i ,y t i ) to (x t+1 i ,y t+1 i ): e.g., when an agent with v i = 2 moves from (0, 0) to (2, 0), it oc- cupies the three geometric vertices (0, 0), (1, 0), and (2, 0). Collision. At a given time step, a collision is considered to occur when a geometric vertex (x,y) is occupied by a pair of agents i,j ∈ A, i ̸= j. This collision definition encom- passes not only vertex collisions and edge collisions, but also follower collisions. A follower collision is a constraint pre- venting agents from entering the grid cells occupied by other agents in the previous timestep, in case those agents malfunc- tioned and did not move during that step. MAWPF problem. Let S and G denote the start and goal configurations, respectively. The solution to MAWPF is a sequence of collision-free configurations Π = (Q 0 ,...,Q k ) that satisfyQ 0 =S andQ k =G. Problem Difficulty. While it is possible to comprehend MAPF and MAWPF as pathfinding on a graph whose vertices are the configurations, a key difference between the MAWPF graph and the one used in classical MAPF is that the MAWPF graph is directed. This directionality arises from the assump- tion that agents cannot accelerate or decelerate abruptly: once an agent commits to a motion state, the set of feasible next states is constrained, and an agent is not guaranteed to be able to return to its previous vertex. As a result, the planner can easily enter a stuck (dead-end) situation where no feasible continuation exists without violating kinematic feasibility or collision constraints. With multiple agents, such irreversibil- ity increases the likelihood of system-wide deadlocks, mak- ing planning failures more frequent. In these senses, solv- ing MAWPF is inherently more difficult than solving classical MAPF on undirected graphs where agents can more readily backtrack and resolve local conflicts. 4 Related Work Having defined MAWPF as a warehouse-grounded extension of classical MAPF, we next review prior work that informs our study from two perspectives: scalable MAPF solvers de- veloped under the classical formulation, and MAPF variants that explicitly incorporate kinodynamic constraints. MAPF Solvers. A naive approach to solve MAPF opti- mally is to employ joint-state search over configurations via A ∗ [ Hart et al., 1968; Standley, 2010 ] . However, it is imprac- tical because the branching factor grows exponentially with the number of agents, quickly making the search intractable. This motivates researchers to explore a different style of plan- ning representation; for example, CBS [ Sharon et al., 2015 ] , a celebrated MAPF algorithm, searches over constraint sets and replans agent-wise paths to resolve collisions. CBS and its extension (e.g., [ Li et al., 2021b ] ) is more scal- able than joint A ∗ , yet it can still miss tight time budgets in scenarios with hundreds of agents or more. Therefore, a sub- stantial line of research has focused on unbounded subopti- mal but scalable MAPF algorithms that sacrifice some de- gree of optimality to achieve real-time performance on large instances. Representative lightweight methods include Pri- oritized Planning (P) [ Erdmann and Lozano-Perez, 1987 ] , LNS2 [ Li et al., 2022 ] , PIBT [ Okumura et al., 2022 ] , and La- CAM [ Okumura, 2023b ] ; these will be reviewed in Sec. 5. In particular, the combination of LaCAM with PIBT has been reported as highly effective, enabling genuinely large-scale planning (on the order of thousands to even ten-thousands of agents) while maintaining practical runtime. In this paper, we build on these scalable, lightweight MAPF techniques rather than relying on optimal algorithms since our target application is large-scale warehouse trans- portation. Moreover, the increased problem complexity aris- ing from advanced kinodynamic constraints makes optimal planning less tractable, thereby reinforcing the practical rele- vance of suboptimal approaches. Kinodynamic-considered MAPF. Classical MAPF typi- cally abstracts away robot kinodynamics by assuming holo- nomic, discrete-time motion with instantaneous turns and in- stantaneous changes of velocity; however, for real AGVs in warehouses, such simplifications can misrepresent the true feasibility and execution cost. Two approaches are commonly adopted to address this mismatch.The first category post-processes gridworld MAPF solutions to make them compatible with AGV dy- namics. For example, [ H ̈ onig et al., 2016 ] employs a sim- ple temporal network to translate kinematics-agnostic plans into ones that respect non-holonomic motion with bounded translational and rotational velocities, while [ Yan and Li, 2025 ] uses a continuous-time single-agent search to obtain such plans. This direction benefits from the scalability of grid-based solvers; however, the resulting solutions are often suboptimal, as high-level grid-based plans inherently intro- duce discrepancies between estimated and actual execution costs [ Yan et al., 2025 ] . Another line of work extends the classical MAPF formu- lation to account for robot dynamics explicitly and solves the resulting problem directly. This approach narrows the real- ity gap and enables the computation of plans with improved execution fidelity. For example, MAPF with Turn Actions (MAPF T ) [ Zhang et al., 2023 ] augments the action space by modeling turning as an explicit action, while MAPF with Kinematic Constraints (MAPFKC) [ Ali and Yakovlev, 2021 ] incorporates speed and acceleration, and CL-MAPF [ Wen et al., 2022 ] focuses on Ackermann-steering, car-like robots, to name just a few. Our MAWPF falls within this category, but two features distinguish it in terms of the practicality and ap- plicability of existing MAPF methods: (i) MAWPF adopts a fully discrete state space, which allows existing discrete search-based MAPF algorithms to be adapted directly (un- like MAPFKC); (i) MAWPF jointly considers AGV-specific constraints, including motion, rotation, and collision charac- teristics (unlike MAPF T and CL-MAPF). 5 Algorithms This section describes how we adapt existing lightweight MAPF algorithms to solve MAWPF under our differential- drive action model and warehouse-specific safety constraints. 5.1 Prioritized Planning (P) P [ Erdmann and Lozano-Perez, 1987 ] is a sub-optimal and incomplete solver that assigns priorities to agents and then plans collision-free paths in priority order. Similar to MAPF implementation, P for MAWPF plans agents sequen- tially with a fixed priority ordering. For each agent, we run space–time A* [ Silver, 2005 ] on the MAWPF configu- ration graph, whose vertices encode kinodynamic configu- rations and whose edges correspond to admissible MAWPF actions (e.g., forward motion and in-place rotation). Previ- ously planned trajectories are treated as dynamic obstacles via a time-indexed reservation table: a transition at time t is rejected if it occupies any reserved cell at layer t. Since one MAWPF action may traverse multiple cells, we reserve and check all cells along the swept segment. The resulting path is then committed to the reservation table, including goal-hold after arrival. Overall, this algorithm constitutes the simplest baseline approach for solving MAWPF. 5.2 MAPF Large Neighborhood Search (LNS2) LNS2 [ Li et al., 2022 ] is a sub-optimal and incomplete solver that first computes each agent’s path without considering collisions, and then resolves collisions via large neighbor- hood search. LNS2 for MAWPF is a destroy-and-repair local search that reduces collisions by replanning only a subset of agents. It starts with soft prioritized planning: as in P for MAWPF, each agent is planned on the MAWPF state graph with a time-indexed reservation structure, but collisions are allowed with an extra penalty proportional to the number of reserved cells intersected by the swept motion segment. It then repeatedly selects a subset of agents and destroys and repairs their paths until collisions are eliminated or the time budget is exhausted. 5.3 PIBT PIBT [ Okumura et al., 2022 ] maps a collision-free configu- ration Q from ∈ V |A| to another Q to ; iterating this mapping yields an MAPF solver that is incomplete and sub-optimal. Agents are assigned priorities and reserve vertices for the next timestep in priority order according to their preferences. If a low-priority agent conflicts with a high-priority agent, it inherits the higher-priority agent’s position, recursively calls PIBT to vacate the cell, and then reserves another vertex. Multi-step PIBT. Under a differential-drive model with only move forward and rotate in place, an agent receiv- ing priority inheritance cannot always vacate immediately: because it cannot move laterally, side interactions may re- quire multiple primitive actions before the contested cell is cleared. As shown in Table 1, the original PIBT can hardly solve MAWPF. We therefore extend PIBT to a multi-step variant, allowing an inherited agent to execute a short ac- tion sequence (e.g., rotate then move forward) to vacate in a kinematically feasible way, enabling PIBT-style coordina- tion for differential-drive MAPF. Along this line, Enhanc- ing PIBT [ Yukhnevich and Andreychuk, 2026 ] solves life- long MAPF for differential two-wheeled AGVs by reserving short-horizon segments rather than a single vertex; we simi- larly develop a multi-step PIBT-based algorithm for one-shot MAWPF, detailed at the end of this section. Definition of Stop Path. In original PIBT, if agent i’s plan fails, it chooses stay; in MAWPF, emergency stops are im- possible, so stay is not always selectable. We thus define the stop path (the counterpart of stay) as the shortest path from the current state to a stop. For L = 3, examples include: (0, 0, 0, 3) → (3, 0, 0, 2) → (5, 0, 0, 1) → (6, 0, 0, 0). When agent i’s plan fails, it is assigned the stop path. Priority Inheritance for MAWPF. While several inheri- tance rules are possible, using the stop path as the analogue of stop makes the following rule natural: as shown in Fig. 2, among agents not yet assigned a path, priority is inherited by the agent whose stop path conflicts with agent i. MAWPF Adaptation. The blue parts in Alg. 1 indicate the modifications from the original PIBT. Starting from the current configuration Q from , the procedure constructs an L- length configuration sequence Q to 0 ,Q to 1 ,...,Q to L−1 by as- signing each agent i ∈ A a feasible horizon path; agents |A|=5101520 PIBT0.760.200.040.00 Multi-step PIBT (L=6)1.001.001.001.00 Table 1: Success rate comparison between original PIBT and multi- step PIBT for MAWPF on random-64-64-20 with V max =2,T rot =2, using the rolling horizon method. |A|=50100150200 Macro-successor0.000.000.000.00 Rolling horizon1.001.001.001.00 Table 2:Effect of rolling horizon (random-64-64-20, L=6, V max =2, T rot =2). with Q to L−1 [i]=⊥ are planned via the recursive procedure PIBT(i) (Lines 1–3). We enumerate all admissible L-step action sequences via Breadth-First Search on the MAWPF configuration graph. Inside PIBT(i), candidate horizon paths Paths ← path(Q from [i]) are sorted by the distance from Path[L− 1] to g i (Lines 8–9), and tested in that order: the al- gorithm checks whether reserving the entire segment causes any collision (Lines 10–12) and commits a feasible candi- date by setting Q to [i] ← Path (Line 13). It then applies segment-level priority inheritance: for each unplanned agent j, it checks whether its default StopPath[j] would collide with current reservations (Procedure inherit, Lines 4–6; con- dition in Lines 15); if so, it calls PIBT(j), and if this fails it backtracks and rejects the current candidate (Lines 15– 16). If no candidate yields consistent reservations, it assigns Q to [i]← StopPath[i] and returns INVALID (Lines 20–21). Algorithm Improvements. PIBT for MAWPF incorpo- rates implementation-level refinements to improve scalability under kinodynamic constraints. • Division sort (Line 9): Instead of fully sorting Paths, we repeatedly sort only the top-K candidates and, if none is adopted, proceed to the next top-K until a path is selected. In practice, substantially fewer than|Paths| elements are often sorted, yielding a noticeable reduc- tion in computation. • Pruning (Line 8): Among length-L candidate paths with identical first and last configurations, we keep only the one with the smallest number of moves, removing redundant candidates that return to the same endpoint configuration and discouraging oscillatory behavior. By reducing |Paths|, pruning directly accelerates a single configuration-generation call. 5.4 LaCAM LaCAM [ Okumura, 2023b ] is a search-based meta-algorithm for MAPF that rapidly finds feasible solutions on large, dense instances. It reduces branching by avoiding explicit enumer- ation of the joint action space and instead generating succes- sors lazily using constraints. LaCAM is complete: it returns a solution if one exists and otherwise reports failure. To do so, LaCAM employs two level search. The high level searches H H H H H H 's desired path's stop path L L L L L L Priority Inheritance L L L L L H H H H H 푡=0 푡=1 푡=2 푡=3 푡=4 Figure 2: Priority Inheritance for MAWPF. Illustrates case L = 4. Colored vertices represent those occupied by agents at each time step. The path of the higher-priority agent (left) and the stopping path of the lower-priority agent (center) collide at t = 4, triggering priority inheritance. The lower-priority agent is then planned (right). over configurations, constructing a sequence from S to G. The low level grows a constraint tree whose nodes impose requirements such as “agent i must be at vertex v in the next configuration.” For a selected node, LaCAM invokes a con- figuration generator such as PIBT to produce a valid next con- figuration; if generation fails, it switches to another node, by lazy successor enumeration. MAWPF Adaptation. We retain the high-level search and replace the configuration generator with PIBT for MAWPF (Alg. 1). As this generator returns an L-step configuration array, two integration options arise. One treats the L-step array as a macro-successor, advancing the high level by L timesteps per expansion. The other uses only the first config- uration and advances in a rolling-horizon manner, committing one timestep and re-invoking the generator at the next node. Our evaluation shows that the macro-successor scheme fails to solve MAWPF instances (Table 2); thus, we adopt the rolling-horizon integration. This is likely due to the directed MAWPF configuration graph, where committing to multi- step expansions can quickly lead to dead-end configurations. Further details are provided in the appendix. Following this observation, we also adopt the rolling-horizon scheme when using PIBT for MAWPF alone. 6 Evaluation This section evaluates the performance of the MAWPF algo- rithms: P, LNS2, PIBT, and LaCAM. 6.1 Experimental Setup The evaluation metrics are planning success rate, runtime, and sum-of-cost. Experiments were conducted on a laptop equipped with an M3 Pro Apple Silicon chip and 18 GB of RAM. All code was written in C++. Unless specified, V max and T rot were set to 2. For PIBT, we varied the lookahead horizon L from 5 to 7. The evaluation used 12 maps from the MAPF benchmark [ Stern et al., 2019 ] ; see Fig. 3. The values reported were generated from 25 test cases, prepared for each map and each number of agents, with randomized start and goal states. In addition to positions, each start/goal includes a Algorithm 1 PIBT for MAWPF input: configurationQ from , agents A, goals (g i ) i∈A output: configurationsQ to 0 ,Q to 1 ,...,Q to L−1 1: for i∈ A do 2: ifQ to L−1 [i] =⊥ then PIBT(i) 3: returnQ to 0 ,Q to 1 ,...,Q to L−1 4: procedure inherit(j) 5:if StopPath[j] would cause a collision then return TRUE 6:return FALSE 7:procedure PIBT(i) 8: Paths← path(Q from [i]) 9:sort Paths in ascending order of dist(Path[L− 1],g i ) for Path∈ Paths 10: for Path∈ Paths do 11: collision← FALSE 12:if Path would cause a collision then continue 13: Q to [i]← Path 14:for j ∈ A do 15: if j ̸= i∧Q to L−1 [j] =⊥∧ inherit(j) then 16: if PIBT(j) = INVALID then 17:collision← TRUE ; break 18:if collision then continue 19:return VALID 20: Q to [i]← StopPath[i] 21:return INVALID heading sampled uniformly from 0, 90, 180, 270 deg, and the agent speed at both the start and the goal is set to 0. 6.2 One-shot MAWPF Results Overview. The results, shown in Fig. 3, follow a trend sim- ilar to classical MAPF. Across most maps, LaCAM achieved the highest success rate and consistently solved instances with several hundred agents within a few seconds. This sug- gests that the LaCAM+PIBT pipeline preserves a certain de- gree of scalability and real-time performance in MAWPF de- spite richer kinodynamic constraints. In contrast, PIBT alone yielded lower success rates, indicating that LaCAM is critical for handling difficult configurations. P and LNS2 showed lower success rates and generally longer runtimes than La- CAM. Although performance depended on each map, P and LNS2 typically succeeded on instances with about 50–100 agents, while LaCAM solved a substantially larger fraction within the same time budget. Figure 4 summarizes the re- lationship between runtime and success rate across all sce- narios and further highlights LaCAM’s high success rate and responsiveness. Anomaly on warehouse-20-40-10-2-1. A notable excep- tion is warehouse-20-40-10-2-1, where LaCAM attains sub- stantially lower success rates than P and LNS2. This is con- sistent with PIBT’s sensitivity to narrow passages: width- one corridors often induce severe contention and block- ing, making greedy, inheritance-based decisions prone to stalling [ Okumura, 2023a ] . This interpretation is supported by warehouse-20-40-10-2-2: LaCAM solved all instances there but failed frequently on warehouse-20-40-10-2-1, with corridor width (two vs. one) as the key difference. Thus, the drop is a plausible consequence of applying PIBT to maps dominated by long, width-one corridors. Figure 3: Results for one-shot MAPF. The success rate of planning within 10 s (top), average runtime (middle) and SoC normalized by lower bound (LB = P i∈A c ⋆ i , where c ⋆ i is the shortest-path cost of agent i on the MAWPF configuration graph, from (x s i ,y s i ,θ s i ,v=0) to (x g i ,y g i ,θ g i ,v=0), ignoring all other agents; 1.0 is minimum; bottom) for successful cases are shown. V max =2 and T rot =2 were used. P LNS2 PIBT-L5 PIBT-L7 PIBT-L6 LaCAM-L5 LaCAM-L7 LaCAM-L6 Figure 4: The number of solved instances among 1,200 instances on 12 four-connected grid maps shown in Fig. 3. Solution Quality was broadly consistent with classical MAPF [ Okumura, 2023b ] .P and LNS typically pro- duced smaller sum-of-cost than LaCAM+PIBT. This is ex- pected because P/LNS repeatedly compute (near-)shortest single-agent paths via A*-like searches, whereas PIBT is a feasibility-driven heuristic based on greedy ordering, and does not explicitly optimize objectives such as sum-of-cost. Effects of Path Length in PIBT/LaCAM. Larger L gener- ally increased runtime because our PIBT adaptation employs a rolling-horizon interface: PIBT computes an L-step config- uration array at each expansion, while LaCAM commits only the first configuration. On many maps, L=6, 7 achieved higher success rates thanL = 5, suggesting that longer looka- head reduces dead-ends and failed successor generation. It can also improve solution quality by mitigating locally feasi- ble but globally inefficient choices that later require detours or waiting, thereby reducing sum-of-cost. 6.3 Ablation Study To assess division sort and pruning for improving PIBT, we conducted an ablation study (Fig. 6). Division sort reduced Figure 5: Results of experiments using LaCAM for MAWPF, varying the maximum speed and the number of steps required for a 90 deg turn. The success rate of planning within 10 s (left), average runtime (middle), and normalized SoC for successful cases are shown. Figure 6: Results of the ablation study (LaCAM, L = 6, V max = T rot = 2). “All” denotes the full method, while “-Division sort” and “-Pruning” indicate ablated variants where each respective compo- nent is excluded. Planning was successful in all scenarios. runtime, indicating that ranking candidate paths is a non- trivial bottleneck, since PIBT for MAWPF generates far more candidates than the original PIBT under the enriched transi- tion model. Pruning further decreased runtime by removing candidates with identical endpoint configurations, and it im- proved sum-of-cost by filtering redundant detours such as os- cillatory motions. 6.4 Experiments with Other Problem Settings We further examined how kinodynamic parameters influence performance, focusing on LaCAM, which achieved the high- est success rate among the compared methods. We fixed L = 6 and varied V max and T rot , summarizing success rate, runtime, and sum-of-cost in Fig. 5. Overall, larger T rot degrades success rate and solution quality. Longer rotations consume more timesteps within the short horizon, leaving fewer steps for translation; thus, looka- head becomes less effective, and the planner behaves more like a smaller-L setting, making feasibility harder to sustain and typically increasing sum-of-cost. The effect of V max on runtime depends on map structure. On random-64-64-20, runtime increases with V max , consis- tent with a larger search space. On warehouse-20-40-10-2-2, higher V max can reduce runtime, likely because long straight corridors better exploit acceleration and yield simpler, less congested progress, thereby reducing planning effort. We also conducted experiments allowing follower collisions; de- tails are provided in the appendix. 7 Conclusion and Discussion We define multi-agent warehouse pathfinding (MAWPF), extending classical MAPF with differential-drive AGV constraints—multi-step rotations, acceleration/deceleration, and conservative collision definition to enhance safety. Our empirical observation is that, among popular lightweight MAPF solvers, a rolling-horizon LaCAM+PIBT adaptation scales to hundreds of agents on benchmarks, achieving high success rates within a few seconds. Why can’t we scale to thousands of agents? In classical MAPF, LaCAM can solve benchmark instances with on the order of thousands of agents. In MAWPF, while LaCAM was the most scalable among the compared methods, its practical limit in our experiments was only a few hundred agents. We attribute this gap to two factors. First, configuration generation is expensive. Each LaCAM expansion must produce a feasible next configuration, imple- mented in our MAWPF adaptation via a PIBT-style short- horizon procedure. Because MAWPF imposes richer kino- dynamic constraints, even after pruning each agent can still have dozens to ∼100 candidate short paths, increasing the cost per configuration. Second, as discussed in Sec. 3, the MAWPF configuration graph is directed since heading/speed constraints make tran- sitions hard to reverse. This encourages dead-end states and can slow LaCAM’s high-level search. These observations are for one-shot MAWPF; lifelong MAWPF may handle more agents via frequent replanning and incremental progress. Outlook. Future work includes improving solution quality and robustness on challenging layouts (e.g., narrow corridors) via more cost-aware successor generation and additional re- finement mechanisms. Acknowledgments This research was supported by a gift from Murata Machin- ery, Ltd. References [ Ali and Yakovlev, 2021 ] Zain Alabedeen Ali and Kon- stantin Yakovlev. Prioritized sipp for multi-agent path finding with kinematic constraints. In Interactive Collab- orative Robotics (ICR 2021), Lecture Notes in Computer Science (LNAI), 2021. [ Chan et al., 2024 ] Shao-Hung Chan, Zhe Chen, Teng Guo, Han Zhang, Yue Zhang, Daniel Harabor, Sven Koenig, Cathy Wu, and Jingjin Yu. The league of robot runners competition: Goals, designs, and implementation. In Pro- ceedings of International Conference on Automated Plan- ning and Scheduling (ICAPS), 2024. [ Dresner and Stone, 2008 ] Kurt Dresner and Peter Stone. A multiagent approach to autonomous intersection manage- ment. Journal of Artificial Intelligence Research (JAIR), 2008. [ Erdmann and Lozano-Perez, 1987 ] Michael Erdmann and Tomas Lozano-Perez. On multiple moving objects. Al- gorithmica, 1987. [ Hart et al., 1968 ] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968. [ H ̈ onig et al., 2016 ] Wolfgang H ̈ onig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, and Sven Koenig. Multi-agent path finding with kinematic constraints. In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS), 2016. [ Kato and Okumura, 2026 ] Takuro Kato and Keisuke Oku- mura. Conveyor parcel routing with order-contiguous ar- rivals. arXiv preprint arXiv:2605.13035, 2026. [ Li et al., 2021a ] Jiaoyang Li, Zhe Chen, Yi Zheng, Shao- Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma, and Sven Koenig.Scalable rail planning and replan- ning: Winning the 2020 flatland challenge. In Proceed- ings of International Conference on Automated Planning and Scheduling (ICAPS), 2021. [ Li et al., 2021b ] Jiaoyang Li, Wheeler Ruml, and Sven Koenig. Eecbs: A bounded-suboptimal search for multi- agent path finding. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2021. [ Li et al., 2022 ] Jiaoyang Li, Zhe Chen, Daniel Harabor, Pe- ter J. Stuckey, and Sven Koenig. Mapf-lns2: Fast repairing for multi-agent path finding via large neighborhood search. In Proceedings of AAAI Conference on Artificial Intelli- gence (AAAI), 2022. [ Okoso et al., 2019 ] Ayano Okoso, Keisuke Otaki, and Tomoki Nishi. Multi-agent path finding with priority for cooperative automated valet parking. In ITSC, 2019. [ Okumura et al., 2022 ] Keisuke Okumura, Manao Machida, Xavier D ́ efago, and Yasumasa Tamura. Priority inheri- tance with backtracking for iterative multi-agent path find- ing. Artificial Intelligence (AIJ), 2022. [ Okumura, 2023a ] Keisuke Okumura. Improving lacam for scalable eventually optimal multi-agent pathfinding. In Proceedings of International Joint Conference on Artifi- cial Intelligence (IJCAI). International Joint Conferences on Artificial Intelligence Organization, 2023. [ Okumura, 2023b ] Keisuke Okumura. Lacam: Search-based algorithm for quick multi-agent pathfinding. In Proceed- ings of AAAI Conference on Artificial Intelligence (AAAI), 2023. [ Sharon et al., 2015 ] Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Conflict-based search for opti- mal multi-agent pathfinding. Artificial Intelligence (AIJ), 2015. [ Silver, 2005 ] David Silver. Cooperative pathfinding. In Pro- ceedings of AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2005. [ Standley, 2010 ] Trevor Scott Standley. Finding optimal so- lutions to cooperative pathfinding problems. In Proceed- ings of AAAI Conference on Artificial Intelligence (AAAI), 2010. [ Stern et al., 2019 ] Roni Stern, Nathan Sturtevant, Ariel Fel- ner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, et al. Multi-agent pathfinding: Definitions, variants, and bench- marks. In Proceedings of Annual Symposium on Combi- natorial Search (SoCS), 2019. [ Wen et al., 2022 ] Licheng Wen, Yong Liu, and Hongliang Li. Cl-mapf: Multi-agent path finding for car-like robots with kinematic and spatiotemporal constraints. Robotics and Autonomous Systems, 2022. [ Wurman et al., 2008 ] PeterR.Wurman,Raffaello D’Andrea, and Mick Mountz.Coordinating hun- dreds of cooperative, autonomous vehicles in warehouses. AI Magazine, 2008. [ Yan and Li, 2025 ] Jingtian Yan and Jiaoyang Li.Multi- agent motion planning for differential drive robots through stationary state search. In Proceedings of AAAI Confer- ence on Artificial Intelligence (AAAI), 2025. [ Yan et al., 2025 ] Jingtian Yan, Zhifei Li, William Kang, Stephen F Smith, and Jiaoyang Li. Analyzing planner de- sign trade-offs for mapf under realistic simulation. arXiv preprint arXiv:2512.09736, 2025. [ Yukhnevich and Andreychuk, 2026 ] Egor Yukhnevich and Anton Andreychuk. Enhancing pibt via multi-action op- erations. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2026. [ Zhang et al., 2023 ] Yue Zhang, Daniel Harabor, Pierre Le Bodic, and Peter J. Stuckey. Efficient multi agent path finding with turn actions. In Proceedings of Annual Sym- posium on Combinatorial Search (SoCS), 2023. A Algorithm Details The original PIBT algorithm and our MAWPF adaptation of LaCAM are summarized in Algorithms 2 and 3, respectively. Algorithm 2 PIBT input: configurationQ from , agents A, goals (g i ) i∈A output: configurationQ to (initiallyQ to [i] =⊥ for all i∈ A) 1:for i∈ A do 2: ifQ to [i] =⊥ then 3:PIBT(i) 4: returnQ to 5:procedure PIBT(i) 6: C ← neigh(Q from [i])∪Q from [i] 7:sort C in ascending order of dist(u,g i ) for u∈ C 8: for v ∈ C do 9:if assigning v to agent i inQ to would cause a collision then 10:continue 11: Q to [i]← v 12: if∃j ∈ A such that j ̸= i∧Q from [j] = v∧Q to [j] =⊥ then 13: if PIBT(j) = INVALID then 14:continue 15:return VALID 16: Q to [i]←Q from [i] 17:return INVALID Algorithm 3 LaCAM for MAWPF input: MAPF instance output: a solution or FAILURE 1: initialize Open as a stack 2: initialize Explored as a hash table mapping configurations to nodes 3: N init ← config : S, tree :⟨C init ⟩, parent :⊥ 4: push(Open,N init );Explored[S]←N init 5: while Open̸=∅ do 6: N ← top(Open) 7:ifN.config =G then▷ goal 8:return backtrack (N) 9:ifN.tree =∅ then 10:pop(Open)▷ discard this search node 11:continue 12: C ← next element removed fromN.tree▷ take one constraint 13:lowlevelexpansion (N,C) 14: Q to 0 ,...,Q to L−1 ← configuration generator(N,C) 15: Q new ←Q to 0 ▷ Rolling horizon method 16:ifQ new =⊥ then; continue▷ generator may fail 17:if Explored[Q new ]̸=⊥ then;continue 18: N new ← config :Q new , tree :⟨C init ⟩, parent :N 19:push(Open,N new ) 20:Explored[Q new ]←N new 21: return FAILURE▷ no solution exists Figure 7: Results of experiments using LaCAM for MAWPF with follower collisions allowed, varying the maximum speed and the number of steps required for a 90 deg turn. The success rate of planning within 10 s (left), average runtime (middle) and SoC normalised by lower bound (1.0 is minimum; right) for successful cases are shown. B Influence of Follower Collision To examine the impact of the follower-collision constraint, we repeated the same experimental protocol as in Sec. 6.4 while allowing follower collisions. The results are summarized in Figure 7. Contrary to our initial expectation, enforcing the follower- collision constraint yields a higher success rate. We conjecture that prohibiting follower collisions acts as an implicit congestion- avoidance mechanism: it discourages tailgating behaviors that create tightly packed queues, thereby reducing the likelihood of entering irreversible “deadlock” states.