This paper proposes a framework for improving the operational efficiency of automated storage systems under uncertainty. Recent years have seen a rise in automated grid-based storage for uniform-sized \emph{loads}, e.g., containers, pallets, totes. Such systems face a fundamental tradeoff between maximizing space utilization and minimizing costly load relocation efforts during storage and retrieval operations. The focus here is on a setting with unique loads that can move along cardinal directions using a single mobile manipulator, such as a robot. The setting consists of two distinct phases, common in some logistics applications, such as last-mile distribution centers and shipyards: i) storage of all the loads, followed by ii) their retrieval. The goal is to minimize relocations for both phases, especially when the storage system is at capacity. Previous efforts have shown that with known storage and retrieval orders, zero relocations can be achieved for storage at full capacity, provided that the size of the opening through which loads are stored and retrieved (grid width) is at least 3.

In realistic scenarios, however, schedules may be uncertain, i.e., loads may be stored or retrieved out of order, rendering previous approaches suboptimal. The model of uncertainty in this work assumes that any two departing loads may depart out of order if they are originally at most $k$ positions apart. Under this model, this work generalizes the previous result and proves that a grid width of $\Theta(k)$ is necessary and sufficient for eliminating relocations via robust storage arrangements. An efficient solver is introduced to find such robust arrangements. Furthermore, when relocations become inevitable, such as when loads are retrieved out of order by more than $k$, a strategy is introduced that effectively minimizes total relocations. Extensive experiments show that, for $k$ up to half the grid width, the proposed storage and retrieval approaches essentially eliminate relocations. For high uncertainty, i.e., $k$ values up to the full grid width, relocations are reduced by $50\%+$.