On Two-Handed Planar Assembly Partitioning

Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, Dan HalperinarXiv 2020 · arXiv

Abstract

This paper settles a 25-year-old open question in robotics by proving that partitioning a planar assembly into two connected subassemblies is NP-complete, even for simple grid-based parts. To counter this theoretical "wall," the authors provide a fixed-parameter tractable (FPT) algorithm and identify specific assembly classes where the problem can be solved in linear time.

Introduction

In robotics and automated manufacturing, assembly planning involves finding a sequence of motions to assemble a set of parts. This is often studied in reverse as a disassembly problem: given a finished product, how can it be taken apart?

The "two-handed" model assumes the use of two hands or fixtures to pull two rigid subassemblies apart. While finding any way to separate parts is computationally straightforward, practical manufacturing requires a connectivity constraint. Each subassembly must remain a single connected unit during the move to prevent parts from falling apart.

The two-handed model with connectivity constraints: a subassembly is pulled away as a single connected unit.

Since 1995, it remained unknown whether finding such a "connected partition" using a single translation was polynomial-time solvable or NP-hard. This work provides the definitive answer.

Complexity and Hardness Reduction

The authors prove that the problem is NP-complete even when parts are restricted to simple unit-grid squares (polyominoes). To achieve this, they introduced a new variant of SAT called Monotone Planar 3-SAT with Neighboring Variable Pairs (MP-3SAT-NVP).

A logical structure representing a SAT formula variant used in the hardness reduction.

By constructing elaborate geometric "gadgets"—logic gates composed of polygons and unit squares—the authors demonstrated that solving a SAT formula is equivalent to finding a valid connected partition in a specific assembly. This reduction shows that the difficulty arises from "interlocking hook" structures that create complex dependencies between parts.

Algorithmic Solutions

To address the NP-completeness, the paper offers two primary algorithmic contributions:

  1. Fixed-Parameter Tractable (FPT) Algorithm: Using a bounded search tree method, the algorithm builds a partition incrementally. It alternates between satisfying geometric feasibility (ensuring no collisions via directional blocking graphs) and maintaining connectivity. The algorithm runs in $O(2^k n^2)$ time, where $n$ is the total number of parts and $k$ is the size of the subassembly. This makes the problem manageable when only a few parts are moved at a time.
  2. Linear Time Special Case: The authors identify "horizontally monotone" assemblies—structures lacking complex interlocking hooks—and prove they can always be partitioned in $O(n)$ time.

Key Insights

  • The "Hook" as a Complexity Source: The search for a connected subassembly becomes combinatorially explosive due to interlocking structures, not just the raw number of parts.
  • Connectivity as a Parameter: Treating subassembly size ($k$) as a parameter aligns with practical robotics, where grippers typically handle a small fraction of the total assembly.
  • Geometric SAT Variants: The MP-3SAT-NVP variant provides a more effective way to represent logical variables as adjacent physical parts in a 2D plane compared to standard Planar 3-SAT.

Conclusion and Future Work

While this work settles the 2D grid case, several open questions remain. The complexity of partitioning in arbitrary directions in 3D is still unknown. Furthermore, finding a single partition is only one step; a complete disassembly sequence requires ensuring that each step leads to a state that remains disassemblable. Future research will focus on extending these hardness results and algorithmic solutions to more general 3D environments and complete sequences.

Summary updated

BibTeX
@misc{agarwal2020two,
  author = {Pankaj K. Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin},
  title = {{On Two-Handed Planar Assembly Partitioning}},
  year = {2020},
  eprint = {2009.12369},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.12369},
}
Figure