On the Complexity of Partitioning an Assembly.

Abstract

We consider the following problem that arises in assembly planning: given an assembly, identify a subassembly that can be removed as a rigid object without disturbing the rest of the assembly. This is called the assembly partitioning problem. Polynomial-time solutions have been presented when the motions allowed for the separation are of certain restricted types. We show that for assemblies of polyhedra, the partitioning problem for arbitrary sequences of translations is NP-complete. The reduction is from 3-SAT. The proof applies equally when each part in the assembly is limited to a constant number of vertices; when rotations are allowed; when both subassemblies are required to be connected; and for assemblies in the plane where each part may consist of a number of unconnected polygons.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1992
Accession Number
ADA326085

Entities

People

  • Jean-claude Latombe
  • Randall H. Wilson
  • Tomas Lozano-Pérez

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Assembly
  • Computer Science
  • Construction
  • Disassembly
  • Manufacturing
  • Motion Planning
  • Polynomials
  • Rotation
  • Sequences
  • Spatial Partitioning
  • Translations

Readers

  • Computer Vision.
  • Electronics Engineering
  • Graph Algorithms and Convex Optimization.