Embedded Files
A solution without rearrangement for a 3x4 storage grid at 100% capacity with loads arriving in the order (8, 12, 1, 9, 6, 7, 4, 11, 5, 2, 10, 3) and then departing in the order (1, 2, ..., 12).
High-Density, Rearrangement-Free, Grid-Based Storage and Retrieval
High-Density, Rearrangement-Free, Grid-Based Storage and Retrieval
Summary
We consider an ordered storage and retrieval problem: a set of uniform-sized, labeled loads (e.g., containers, pallets, or totes) must be placed in a 2D grid storage area as they arrive sequentially, and then be retrieved in some (possibly different) order. Each load occupies a grid cell and may be moved by a robot or manipulator along the cardinal directions. Such storage systems arise in logistics, industrial, and transportation domains, where space utilization and retrieval time are critical metrics. To maximize space utilization, loads must be densely packed with some loads blocking access to others, which raises a key question: How should one store the loads to minimize costly rearrangements, i.e., the number of relocated loads, during retrieval?
We identify conditions, alongside efficient algorithms, for achieving either zero or near-optimal rearrangements under different knowledge assumptions. While the online case (i.e., no prior knowledge of the storage and retrieval sequences) induces a trade-off between density and rearrangement, we show that even partial prior knowledge essentially eliminates the trade-off. When the sequences are fully known, we further provide an intriguing characterization: rearrangement can always be eliminated if the grid's open side (used to access the loads) is at least 3 cells wide, even for full capacity storage.
Paper
Fully Packed and Ready to Go: High-Density, Rearrangement-Free, Grid-Based Storage and Retrieval
Tzvika Geft, Kostas Bekris, Jingjin Yu
Summary
This work settles a 25-year-old open question that lies at the heart of assembly planning, which is a fundamental problem in robotics and automation. In assembly planning, the goal is to design a sequence of motions that bring the separate constituent parts of a product into their final placement in the product. The problem gives rise to a key sub-problem called Connected Assembly Partitioning, which involves finding a motion that separates a given product into two connected pieces. Such a motion can be used, when applied in reverse, as part of an assembly process. We prove that the problem is NP-complete even when the motion is a single translation, thereby settling an open question posed by Wilson et al. (1995) a quarter of a century earlier [1]. Our hardness result holds for the utterly simple case of a planar assembly consisting of unit-grid squares (i.e., grid cells of a unit grid).
Towards this result, we prove the NP-hardness of a new Planar SAT variant having an adjacency requirement for variables appearing in the same clause, which we believe to be of independent interest (indeed the new SAT variant was used by others to resolve several long-standing open problems in Tile Self-Assembly [2].)
On the positive side, we give a parameterized algorithm for the case of an assembly consisting of polygons in the plane. Initially, in the conference version of the paper, we presented such an algorithm for the special case of unit-grid squares. The generalized version of the algorithm applies similar reasoning to the algorithm for the distilled special case, thereby demonstrating the utility of studying the distilled problem variant.
Paper
On Two-Handed Planar Assembly Partitioning with Connectivity Constraints
Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin
In 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) [SODA version]
Talks: [Summary (25 min)] [Algorithm (55 min)] [Hardness (50 min)]
References
[1] R.H. Wilson, L.E. Kavraki, T. Lozano-Pérez, and J.-C. Latombe. Two-handed assembly sequencing. Int. J. Robotics Res., 14(4):335–350, 1995.
[2] D. Caballero, T. Gomez, R. Schweller, and T. Wylie. Unique assembly verification in two-handed self-assembly. In ICALP, vol. 229 of LIPIcs, pp. 34:1–34:21, Schloss Dagstuhl, 2022.
The construction used in the hardness result.
The construction used in the hardness result.
Page updated
Google Sites
Report abuse