On Two-Handed Planar Assembly Partitioning with Connectivity Constraints (SODA '21)

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 independently used 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] Randall H. Wilson, Lydia E. Kavraki, Tomás Lozano-Pérez, and Jean-Claude Latombe. Two-handed assembly sequencing. I. J. Robotics Res., 14(4):335–350, 1995.

[2] David Caballero, Timothy Gomez, Robert Schweller, Tim Wylie. Unique assembly verification in two-handed self-assembly, in ICALP, vol. 229 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2022, pp. 34:1–34:21.