🤖 AI

Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

This paper presents a novel, complete, and scalable prioritized planning algorithm for multi-robot ordered storage and retrieval in maximum-capacity puzzle-based warehouses, which guarantees deadlock-free execution and near-linear makespan improvement while maintaining negligible overhead for robustness against uncertain departure sequences.

Original authors: William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

Published 2026-08-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where every square inch of a warehouse is packed to the brim, like a Tetris board that has been filled to the very top with no gaps left behind. This is the dream of modern logistics: maximizing storage density to save money on rent, especially in crowded cities. But there's a catch. If you pack a room so tightly that there are no aisles for forklifts or robots to drive through, how do you get anything out? This is the puzzle of "Puzzle-Based Storage." Think of it like a sliding-tile puzzle game (like the classic 15-puzzle), where every item is a tile, and the only way to move one is to shuffle the others around it. Now, imagine you don't have one person moving tiles, but a whole team of robots working at once. The challenge becomes a chaotic dance: if the robots aren't perfectly coordinated, they might get stuck in a traffic jam where no one can move, a situation known as a "deadlock." Solving this is crucial because as online shopping explodes, warehouses need to be both incredibly full and incredibly fast.

This paper tackles that exact chaos. The authors, a team from Rutgers University, propose a new way to coordinate a swarm of robots in a fully packed, aisle-less warehouse. They introduce a system that handles two distinct phases: first, stuffing the warehouse to its absolute maximum capacity with incoming goods, and second, pulling them out in a specific order as trucks arrive to take them away. The core of their solution is a "prioritized planning" algorithm. Instead of trying to calculate the perfect path for every single robot simultaneously (which is like trying to solve a million-piece puzzle at once and usually leads to the computer crashing), they let robots take turns. When a robot finishes a job, it grabs the next available task and plots a path, while the others wait their turn or move out of the way.

The paper demonstrates that this approach is not just a clever trick but a robust solution. They prove mathematically that their method guarantees the robots will never get stuck in a deadlock, even when the warehouse is 100% full. In their simulations, they tested grids as large as 30 by 30 cells with up to 30 robots. The results showed that adding more robots made the job finish almost linearly faster; for example, using 20 robots on a 20x20 grid made the process nearly 20 times faster than using just one. Perhaps most surprisingly, they found that making the system "robust" against uncertainty—meaning the warehouse can handle it if the order of trucks changes slightly at the last minute—comes with almost no penalty in speed. The robots move just as fast whether the plan is rigid or flexible. While their method isn't theoretically perfect compared to a super-complex, slow central planner, it is fast enough to run in real-time and scales up beautifully, offering a practical way to turn a crowded, static puzzle into a high-speed, moving machine.

Technical Summary: Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

1. Problem Definition

The paper addresses the challenge of coordinating multiple robots in high-density, puzzle-based storage (PBS) systems, specifically for the "ordered storage and retrieval problem at maximum capacity."

Context and Challenges:

High-Density Constraints: Unlike traditional Automated Storage and Retrieval Systems (AS/RS) that rely on dedicated aisles (e.g., Kiva-style), PBS architectures eliminate internal aisles to maximize storage density. The storage grid functions like a sliding-tile puzzle where loads are rearranged using limited empty cells.
Operational Phases: The system operates in two distinct phases:
1. Storage: Loads arrive via a conveyor belt in a specific sequence and must be stored up to 100% grid capacity.
2. Retrieval: Loads must be retrieved in a pre-planned departure sequence.
The Core Conflict: While prior work (StoRMR and R-StoRMR) established that sequential (single-robot) relocation-free arrangements are geometrically feasible, the execution of these arrangements using multiple robots in parallel remains unexplored. Coordinating multiple robots in such dense, aisle-less environments is computationally difficult due to the high risk of deadlocks and the curse of dimensionality in centralized planners.
Uncertainty: The system must also handle uncertainty in the departure sequence, where the actual order of retrieval may deviate slightly from the plan (modeled as $k$ -bounded perturbations).

2. Methodology

The authors propose an online, prioritized Multi-Agent Path Finding (MAPF) algorithm that leverages the specific geometric invariants of relocation-free storage arrangements to guarantee completeness and prevent deadlocks.

System Model

Environment: A rectangular grid ( $R \times C$ ) with an I/O row and a conveyor belt below it.
Agents: $m$ robots ( $m \le C$ ) that can move, rotate, pick up, and drop off loads.
Two-Level Height Model: Robots navigate beneath stationary loads (AMR style), allowing them to pass under stored items without collision, provided they do not occupy the same cell simultaneously.
Constraints: The system avoids positional collisions (two entities in one cell) and directional collisions (swapping or orthogonal conflicts), though "train" movement (following in the same direction) is permitted.

The Algorithm: Asynchronous Prioritized Planning

The approach decouples the planning process, assigning tasks dynamically to idle robots rather than solving for all agents simultaneously.

Task Assignment:
- Storage: When a robot becomes idle, it is assigned the next unclaimed load in the arrival sequence. The robot closest to the pickup point is selected greedily.
- Retrieval: Robots claim the next unclaimed load in the departure sequence. A robot only claims a load once a valid path is successfully computed.
Path Planning:
- The planner uses a space-time A* search to generate time-minimal trajectories from the robot's current position to the pickup/drop-off points.
- Global Reservation Table: To prevent collisions, the system maintains a reservation table tracking space-time constraints $(p, t, d)$ , where $p$ is position, $t$ is timestep, and $d$ is the prohibited entry direction. This explicitly prevents directional following conflicts.
- Obstacle Management: Stored loads are treated as static obstacles. Their status updates dynamically: a load is removed from the obstacle table when a robot plans to pick it up and re-added when it is dropped off.
Handling Retrieval Complexity:
- A critical challenge in retrieval is determining where a robot should wait after dropping off a load.
- Strategy: The algorithm attempts to position the robot under the next unclaimed load in the sequence. If that is inaccessible, it falls back to waiting under the closest accessible unclaimed load. If no load is accessible, the robot moves to a guaranteed non-obstructing cell in the back row.
- Sequence Enforcement: To ensure the departure sequence is respected, a robot only plans a path for load $j$ once the path for load $j-1$ to the I/O row is queued.

Theoretical Guarantees

The paper proves completeness (the algorithm will always find a solution if one exists) for both storage and retrieval phases.

Basis: The proof relies on the properties of relocation-free arrangements (established in prior StoRMR/R-StoRMR work). These arrangements guarantee that for any load in the sequence, a collision-free path exists to/from the I/O row, provided other loads are not moved.
Induction: The authors use induction to show that if the first $k-1$ loads are successfully stored/retrieved, the geometric properties of the arrangement ensure that the $k$ -th load can also be accessed by at least one idle robot, preventing deadlocks even at 100% density.

3. Key Contributions

Multi-Robot Formulation: Introduces a novel formulation for ordered storage and retrieval at maximum capacity, bridging the gap between geometric feasibility (sequential) and execution efficiency (parallel).
Prioritized Planning Algorithm: Proposes an asynchronous, online algorithm that utilizes the invariants of relocation-free arrangements to guarantee completeness and deadlock prevention in dense environments, a rare achievement for prioritized MAPF methods.
Scalability and Efficiency: Demonstrates that the approach achieves near-linear improvement in makespan (total time) as the number of robots increases, up to $m = C$ (grid width).
Robustness with Negligible Overhead: Shows that using robust storage arrangements (R-StoRMR) to handle departure sequence uncertainty incurs no significant penalty in execution speed compared to non-robust baselines.
Low Suboptimality: The algorithm exhibits low makespan suboptimality (ratio of 1.09 to 1.21) when compared to a theoretically optimal but non-scalable centralized coupled planner.

4. Experimental Results

Experiments were conducted on grids up to $30 \times 30$ with varying numbers of robots (1 to $C$ ).

Scalability: The system achieves near-linear speedup in makespan reduction as robot count increases. For a $20 \times 20$ grid, the improvement ratio closely follows the ideal linear benchmark up to 20 robots.
Runtime: The planning time per load remains in the sub-second range even as grid size and robot count increase, making the system suitable for real-time online operation.
Robustness Penalty: Comparing standard arrangements ( $k=0$ ) with robust arrangements ( $k=0.4C$ ), the execution penalty was found to be negligible. The makespan and total distance traveled were nearly identical.
Coordination Overhead: While total distance traveled increases slightly with more robots due to collision avoidance maneuvers, the increase is shallow (less than 5% for 20 robots compared to a single robot).
Optimality: Compared to a coupled A* solver (limited to small batches due to computational complexity), the prioritized planner shows a suboptimality ratio between 1.09 and 1.21. The authors attribute part of this gap to the coupled planner's ability to exploit the conveyor model for slight reordering, which the prioritized approach avoids to maintain strict sequence guarantees.

5. Significance and Claims

The paper claims to solve a fundamental trade-off in automated logistics: maximizing storage density while maintaining high retrieval throughput. By proving that prioritized planning can be complete and deadlock-free in 100% density environments when guided by specific geometric invariants, the work enables the practical deployment of multi-robot systems in puzzle-based storage.

The authors emphasize that their approach does not require the "curse of dimensionality" associated with centralized planners. Instead, it exploits the structural properties of the storage layout to allow for scalable, parallel execution. Crucially, the work demonstrates that robustness against uncertainty (handling variable departure sequences) can be integrated without sacrificing the speed or efficiency of the system, making it a viable solution for real-world logistics where arrival and departure times may vary.

The paper concludes that while there is a small optimality gap compared to coupled search, the scalability and robustness of the proposed method make it superior for large-scale, real-time applications. Future work is suggested to explore other MAPF techniques (like PIBT) to narrow the optimality gap and to investigate arrangements specifically tailored for multi-robot coordination.