On Geometric Assembly Planning.
Abstract
This dissertation addresses the problem of generating feasible assembly sequences for a mechanical product from a geometric model of the product. An operation specifies a motion to bring two subassemblies together to make a larger subassembly. An assembly sequence is a sequence of operations that construct the product from the individual parts. I introduce the non-directional blocking graph, a succinct characterization of the blocking relationships between parts in an assembly. I describe efficient algorithms to identify removable subassemblies by constructing and analyzing the NDBG. For an assembly A of n parts and m part-part contacts equivalent to k contact points, a subassembly that can translate a small distance from the rest of A can be identified in O(mk2) time. When rotations are allowed as well, the time bound is O(mk5). Both algorithms are extended to find connected subassemblies in the same time bounds. All free subassemblies can be identified in output-dependent polynomial time. Another algorithm based on the NDBG identifies subassemblies that can be completely removed by a single translation. For a polyhedral assembly with V vertices, the algorithm finds a removable subassembly and direction in O(n2v4) time. When applied to find the set of translations separating two parts, the algorithm is optimal. A final method accelerates the generation of linear assembly sequences, in which each operation mates a single part with a subassembly. The results of geometric calculations are stored in logical expressions and later retrieved to answer similar geometric queries. Several types of expressions with increasing descriptive power are given. An assembly sequencing testbed called GRASP was implemented using the above methods.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1992
- Accession Number
- ADA325963
Entities
People
- Randall H. Wilson
Organizations
- Stanford University