Robust Out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity

AI summary

Overview

Research area: Robotics and algorithmic logistics — specifically high-density grid-based automated storage and retrieval (related to Puzzle-Based Storage and the Block Relocation Problem), combining combinatorial optimization, algorithm design, and empirical robotics evaluation.

Technical level: Advanced. The paper mixes formal definitions, proofs of necessary and sufficient column bounds, a constructive storage algorithm with pseudocode, a greedy relocation heuristic, and a large simulation-based experimental study.

Scope in one sentence: The paper studies how wide a fully packed 2D grid storage area must be (and how to arrange loads within it) so that loads can still be retrieved without relocations when the retrieval order is only approximately known.

What This Paper Is About

Uniform-sized loads (containers, pallets, totes) are stored in a rectangular grid in a known arrival order and are later retrieved in a departure order that may differ from the one that was planned. Because the grid is operated at full capacity, any load that is retrieved early may be blocked by loads that were meant to depart later, forcing the robot to relocate blockers. The paper formalizes uncertainty as k-bounded perturbations — two loads may swap relative order only if they were planned at most k positions apart — and asks how many grid columns are needed, and what storage arrangement and retrieval strategy should be used, to eliminate or minimize those relocations.

Key Contributions

1. A new problem formulation under uncertainty. The paper defines R-StoRMR (Robust Storage and Retrieval with Minimum Relocations): store all loads according to a known arrival sequence A, then retrieve them according to a sequence that is revealed one load at a time and is a k-bounded perturbation of the planned departure order D = (1, …, n), all at full capacity.

2. Tight asymptotic column bounds for zero-relocation operation. The paper proves a Θ(k) characterization: 3k+3 columns always suffice (Theorem 2, any r ≥ 1 rows), while 2k+3 columns are necessary in general (Theorem 3, r > 1 rows). It also shows the problem reduces to finding an arrangement that satisfies A and is k-robust for D (Corollary 1), built on "robust adjacency conditions" (Proposition 1).

3. A constructively fast robust-storage solver. An algorithm that fills pairs of adjacent columns from the bottom row upward, alternating adjacency responsibilities between a left column (arrival-order adjacencies) and a right column (departure-order adjacencies), plus a "load-skipping" enhancement that tries every offset for the first assigned load of the reversed arrival sequence.

4. A greedy retrieval/relocation strategy plus extensive experiments. A relocation procedure that picks a retrieval path minimizing blocking loads and reassigns blockers to empty cells that avoid blocking other loads, constrained so the I/O row is empty after each retrieval and relocated loads return to their original cells.

Main Findings

• Θ(k) columns are necessary and sufficient. The upper bound is 3k+3 columns; the lower bound is 2k+3 columns. The paper states the bounds are "tight up to 1.5," and notes the bounds hold for any number of rows r > 1 in the lower bound and r ≥ 1 in the upper bound — the number of columns, not rows, governs zero-relocation solutions.

• A practical operating window falls out of the bounds. Rephrasing, the authors conclude that for k/c ≈ k/(c−3) ≤ 1/3 relocations can be avoided, whereas for k/c ≈ k/(c−3) ≥ 1/2 they cannot.

• Robustness requires stricter adjacencies. Proposition 1 states an arrangement is k-robust for D if and only if every load d_i is either in the bottom row or adjacent to a load d_j with i − j ≥ k + 1, i.e., at least k + 1 positions earlier in D (the non-robust condition in Observation 2 only requires j < i).

• The prior deterministic result is a special case. A previous result (Geft et al. 2025) guarantees a zero-relocation solution when the access side is at least 3 cells wide and the sequences are fully known; Theorem 1 gives that arrangement in O(n) time. The new upper bound of 3k+3 columns reduces to that regime structure by partitioning A into k+1 subsequences by residue modulo k+1 and giving each 3 dedicated contiguous columns.

• Fewer columns may still work for specific instances. The lower bound requires 2k+3 columns in general, but the paper notes the 3 × 3 example in Figure 1 needs only 3 columns for k = 1 instead of 5.

• Storage and retrieval improvements complement each other. Experiments show the combined RobustS + ImpR configuration outperforms the baseline and the singly improved variants. For k/c ≤ 0.5, RobustS nearly eliminates rearrangements; for larger k, the paper reports relocations reduced by up to 60-70% (the abstract summarizes this as relocations reduced by 50%+ for k values up to the full grid width).

• Relocations stay inside the grid. In nearly all cases, loads relocated within W are not relocated again, indicating cascading relocations are avoided. ImpR significantly reduces relocations to the I/O row, and RobustS reduces them further, up to elimination for k/c ≤ 0.5.

• Compute times are small. RobustS runs in under 1 minute and ImpR in under 1 second for every grid size tested (Python on an Apple M3 with macOS 15.5).

• The load-skipping enhancement materially raises success. On a 15 × 15 grid (theoretical limit k = 6) and 19 × 19 grid (limit k = 8), the enhanced RobustS achieves 80%+ success even for higher k than those theoretical limits, beyond which relocations can occur.

Methodology in Plain English

The grid is modeled as an r × c area of cells, each holding one labeled load, opened on one side (the bottom/front row), with an Input/Output row adjacent to it that acts as a temporary buffer rather than storage. The robot can store, retrieve, or relocate a load along empty cells in the four cardinal directions, and density is defined as n/(r·c) with the paper assuming full capacity, n = r·c.

For the theory, the authors use a reversal trick: storing loads in order A is equivalent to retrieving them in the reverse order A^R, so an arrangement must simultaneously satisfy two departure orders. They then check when an arrangement survives every k-bounded perturbation, which leads to the stricter adjacency rule. To prove the upper bound they split arrivals into k+1 residue classes modulo k+1 and solve each class independently in its own 3 columns using the existing BaseS algorithm. To prove the lower bound they construct an adversarial arrival sequence filling the grid and argue by induction that 2k+3 loads must all sit on the bottom row.

For practice, the storage solver sweeps upward in pairs of adjacent columns, greedily matching one load that is departure-order-valid with one that is arrival-order-valid, relying on horizontal adjacencies to satisfy the other ordering. If it cannot pair loads, it reports failure and the enhancement retries with different starting offsets, decrementing k until a robust arrangement is found. During retrieval, given a target load, the algorithm computes the path to the I/O row that crosses the fewest blocking loads (ties broken by path length), then relocates each blocker outward-in, preferring destination cells that do not block currently accessible loads and that leave enough empty cells for remaining blockers. Experiments run 50 trials per combination of grid side length and k ∈ {0.25c, 0.5c, 0.75c, c} at 100% density, generating random arrival sequences and random k-bounded perturbations, and measuring relocations, I/O row usage, and distance suboptimality relative to the lower bound c·r·(r+1).

Why This Matters

The work converts a design question — how wide should the open side of a dense storage grid be? — into a quantitative trade-off between space utilization and retrieval robustness under uncertainty. It extends a deterministic zero-relocation guarantee into the realistic case where the planned departure order changes, and its bounds give practitioners a rule of thumb (k/c ≤ 1/3 is safe, k/c ≥ 1/2 is not) rather than only a worst-case construction.

Real-world applications:

• Last-mile and small-scale distribution centers, where incoming trucks trigger a storage phase and local delivery trucks trigger a retrieval phase with a partially different order.
• Container terminals and shipyards, where containers are stacked densely and departure order is driven by vessel and truck schedules that change.
• Cross-docking facilities, where loads are briefly buffered and then dispatched in a different sequence than they arrived.
• Automated warehouses with mobile robot fleets and AS/RS, where maximizing storage density directly trades against access time.

Industry relevance: the I/O-row usage metric matters because that row may be needed for other transport operations besides providing access, and the paper's constraint that the I/O row be empty after each retrieval keeps it free. The reported run times (storage under 1 minute, retrieval under 1 second) suggest the heuristics are practical at the grid sizes tested, and keeping relocations inside the grid reduces interference with external transport.

Future Directions

• Is deciding existence of a robust arrangement polynomial-time? The paper's solver is a heuristic that can return failure even when a valid arrangement exists; the authors pose whether this can be strengthened to an exact polynomial-time decision procedure.
• Can the gap between the bounds be closed? The upper bound is 3k+3 and the lower bound is 2k+3; whether a robust arrangement can always be found with 2k+3 columns remains open.
• Multi-robot systems. Extending the framework to multiple robots, including multi-agent path finding reasoning in this dense, sequential-motion setting.
• Broader uncertainty models. The current model is limited to k-bounded perturbations where inversions are bounded by distance in the sequence; other structures of order change are not addressed.

Target Audience

Researchers in algorithmic robotics and warehouse automation, operations researchers working on storage, retrieval, and container-relocation problems, and graduate students in combinatorial optimization or multi-robot coordination. Engineers designing dense AS/RS, PBS-style grids, or cross-dock and yard layouts will find the column bounds and the k/c guidelines directly actionable. Readers should be comfortable with proofs, asymptotic notation, and algorithmic pseudocode, though the experimental section and high-level findings are accessible to a broader logistics audience.

Authors’ abstract

This paper proposes a framework for improving the operational efficiency of automated storage systems under uncertainty. It considers a 2D grid-based storage for uniform-sized loads (e.g., containers, pallets, or totes), which are moved by a robot (or other manipulator) along a collision-free path in the grid. The loads are labeled (i.e., unique) and must be stored in a given sequence, and later be retrieved in a different sequence -- an operational pattern that arises in logistics applications, such as last-mile distribution centers and shipyards. The objective is to minimize the load relocations to ensure efficient retrieval. A previous result guarantees a zero-relocation solution for known storage and retrieval sequences, even for storage at full capacity, provided that the side of the grid through which loads are stored/retrieved is at least 3 cells wide. However, in practice, the retrieval sequence can change after the storage phase. To address such uncertainty, this work investigates \emph{$k$-bounded perturbations} during retrieval, under which any two loads may depart out of order if they are originally at most $k$ positions apart. We prove that a $Θ(k)$ grid width is necessary and sufficient for eliminating relocations at maximum capacity. We also provide an efficient solver for computing a storage arrangement that is robust to such perturbations. To address the higher-uncertainty case where perturbations exceed $k$, a strategy is introduced to effectively minimize relocations. Extensive experiments show that, for $k$ up to half the grid width, the proposed storage-retrieval framework essentially eliminates relocations. For $k$ values up to the full grid width, relocations are reduced by $50\%+$.