On two-handed planar assembly partitioning with connectivity constraints

Conference Paper

Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A \ S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O(2kn2)-time algorithm, where n = |A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O(n) time.

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; Geft, T; Halperin, D

Published Date

  • January 1, 2021

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 1740 - 1756

International Standard Book Number 13 (ISBN-13)

  • 9781611976465

Citation Source

  • Scopus