Optimal Arrangement and Rearrangement of Objects on Shelves to Minimize Robot Retrieval Cost
IEEE Xplore is the flagship digital platform for discovery and access to scientific and technical content published by the IEEE (Institute of Electrical and Electronics Engineers) and its publishing partners.
IEEE Xplore contains more than 6 million documents and other materials from some of the world's most cited publications in electrical engineering, computer science, and related sciences.
Ken Goldberg is a professor and the William S. Floyd Jr. Distinguished Chair in Engineering at UC Berkeley, a co-founder and chief scientist at robotics parcel sorting startup Ambidextrous and a fellow at IEEE. Along with Lawrence Yunlian Chen and Huang Huang, Ken Goldberg was published by IEEE Transactions on Automation Science and Engineering (Early Access) with their findings on "Optimal Arrangement and Rearrangement of Objects on Shelves to Minimize Robot Retrieval Cost."
Abstract:
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 ...