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.
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).
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:
- 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.
- 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