Optimal Arrangement and Rearrangement of Objects on Shelves to Minimize Robot Retrieval Cost

From residential homes to commercial outlets and industrial warehouses, shelves are widely used to store a variety of objects. We conjecture that optimizing object arrangements can significantly improve the efficiency of searching and retrieving target objects for robots and automation systems. We formalize the Optimal Shelf Arrangement (OSA) problem, which, given a set of objects' access frequencies and movement costs, optimizes their placement on a shelf to minimize access time. We present, a mixed-integer program (MIP), show that it finds an optimal solution for OSA under certain conditions, and provide bounds on its suboptimality in general cost settings. We further present -Stack, which extends the setting to environments that allow object stacking. Additionally, we consider improving a given suboptimal object arrangement through efficient rearrangement. Experiment results from over 2,700 simulated shelf trials and 54 physical trials using a Fetch robot equipped with a suction grasping tool and pushing blade suggest that an optimal arrangement can reduce the expected retrieval cost by 60-80% in fully-observed configurations and reduce the expected search cost by 50-70% while increasing the search success rate by up to 2x in partially-observed configurations. Note to Practitioners-While there is a large literature on task and motion planning that studies how to rearrange objects from one arrangement to another, there is little research on what an ideal "target" arrangement should be. This article demonstrates that an optimal arrangement of objects makes searching and retrieving objects on shelves significantly easier. We present the Optimal Shelf Arrangement (OSA) problem and algorithms to solve it. Although we assume access to a robot that can push and use a vacuum suction cup gripper, practitioners can adapt the OSA model to their own hardware and shelf constraints and objectives. Also, the algorithms for improving existing shelf arrangements can be applied to scenarios where the objects are already on the shelves rather than to be arranged from scratch.