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
Grid-based storage systems with uniformly shaped loads (e.g., containers, pallets, totes) are commonplace in logistics, industrial, and transportation domains. A key performance metric for such systems is the maximization of space utilization, which requires some loads to be placed behind or below others, preventing direct access to them. Consequently, dense storage settings bring up the challenge of determining how to place loads while minimizing costly rearrangement efforts necessary during retrieval. This paper considers the setting involving an inbound phase, during which loads arrive, followed by an outbound phase, during which loads depart. The setting is prevalent in distribution centers, automated parking garages, and container ports. In both phases, minimizing the number of rearrangement actions results in more optimal (e.g., fast, energy-efficient, etc.) operations. In contrast to previous work focusing on stack-based systems, this effort examines the case where loads can be freely moved along the grid, e.g., by a mobile robot, expanding the range of possible motions. We establish that for a range of scenarios, such as having limited prior knowledge of the loads’ arrival sequences or grids with a narrow opening, a (best possible) rearrangement-free solution always exists, including when the loads fill the grid to its capacity. In particular, when the sequences are fully known, we establish an intriguing characterization showing that rearrangement can always be avoided if and only if the open side of the grid (used to access the storage) is at least 3 cells wide. We further discuss useful practical implications of our solutions.
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