On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning sub-problem: Given a set A of parts, find a subset S ⊂ A, referred to as a subassembly, such that S can be rigidly translated to infinity along a prescribed direction without colliding with A\S . While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning, which additionally requires each of the two subassemblies, S and A\S, to be connected. We obtain the following results. - We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when consists of unit-grid squares (i.e., is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. - On the positive side, we give an O(2^kn²)-time fixed-parameter tractable algorithm (requiring low degree polynomial-time preprocessing) for an assembly consisting of polygons in the plane, where n = |A| and k = |S| . We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in O(n)-time.

Duke Scholars

Author Pankaj K. Agarwal Computer Science