Accession Number:

ADA326877

Title:

Two-Handed Assembly Sequencing,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Wilson, R. H.
• Kavraki, L.
• Lozano-Perez, T.
• Latombe, J. C.

Report Date:

1993-06-01

Pagination or Media Count:

29.0

Abstract:

This paper considers the computational complexity of automatically determining assembly sequences for mechanical products. Specifically, we address the partitioning problem given an assembly of rigid parts, identify a proper subassembly that can be removed as a rigid object without disturbing the rest of the assembly. We examine the complexity of the partitioning problem under varying types of relative motions allowed for the subassemblies. We show that when arbitrary motions are allowed to separate the two subassemblies, partitioning is NP-complete. We then describe a general framework for reasoning about assembly motions called the interference diagram. In its most general form the interference diagram yields an exponential-time algorithm to partition an assembly. However, two special cases of the interference diagram studied in this paper yield polynomial-time sequencing algorithms. The first case occurs when assembly motions are restricted to single translations. The second case considers infinitesimal rigid motions in translation and rotation, and yields a superset of all feasible partitionings.

Descriptors:

• *ALGORITHMS
• *ROBOTICS
• *ASSEMBLY
• AUTOMATION
• INDUSTRIAL PRODUCTION
• PRODUCTION CONTROL
• SYSTEMS ANALYSIS
• COMPUTER AIDED MANUFACTURING

Subject Categories:

• Cybernetics
• Manufacturing and Industrial Engineering and Control of Production Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE