Automatic construction of assembly partial-order graphs

A system is presented which automatically constructs an assembly partial-order graph from an object-oriented model describing parts and their connections. The construction is based on the principle of assembly by disassembly and on assembly heuristics representing criteria for preferred subassemblies. The system first identifies disassemblable parts and subassemblies by reasoning geometric and physical constraints as well as resource requirements, and then assigns preference to the identified disassembly options based on assembly heuristics. The recursive application of this process to the selected disassemblies results in a hierarchical partial-order graph (HPOG). The HPOG not only specifies the required precedence in part assembly but also provides parallelism for implementing multiple-robot distributed and cooperative assembly. The software is organized under the cooperative-problem-solving paradigm