An artificial intelligence approach to planning the robotic assembly of large tetrahedral truss structures is presented. Based on the computational formalism known as production system, the approach exploits the simplicity and uniformity of the shapes of the parts and the regularity of their interconnection to drastically reduce the required geometric reasoning computation. The global database consists of a hexagonal grid representation of the truss structure. This representation captures the multiple hierarchies in tetrahedral truss structures and allows a substantial reduction of the search space without sacrificing completeness. It allows the choice of a hierarchy to be made only when needed, thus allowing a more informed decision. Testing the preconditions of the production rules is computationally inexpensive because the patterned way in which the struts are interconnected is incorporated into the topology of the hexagonal grid representation. A directed graph representation of assembly sequences allows the use of both graph search and backtracking control strategies. The extension of the approach to planning repair sequences is outlined. A prototype planner, named TASP, has been implemented and successfully generated assembly sequences for a structure made of 102 struts.>

A hexagonal grid representation of tetrahedral truss structures that explicitly incorporates the geometry of the set of parts and simplifies the reasoning needed in planning assembly sequences is introduced. This representation captures the regularity of tetrahedral truss structures and their multiple hierarchies. The hexagonal grid maps into a rectangular grid and therefore into a 2D array. The adoption of this representation and its associated data structure makes it practicable to automate the assembly planning for large structures.>

Five types of representations for assembly sequences are reviewed: the directed graph of feasible assembly sequences; the AND/OR graph of feasible assembly sequences; the set of establishment conditions, and two types of precedence relationships namely those between the establishment of one connection between parts and the establishment of another connection, and those between the establishment of one connection and states of the assembly process. The mappings of one representation into the others are established. The correctness and completeness of these representations are established. The results presented are needed in the proof of correctness and completeness of algorithms for the generation of mechanical assembly sequences.>

An algorithm for the generation of all mechanical assembly sequences for a given product is presented. It uses a relational model of assemblies. In addition to the geometry of the assembly, this model includes a representation of the attachments that bind parts together. The problem of generating the assembly sequences is transformed into the problem of generating disassembly sequences in which the disassembly tasks are the inverse of feasible assembly tasks. The problem of disassembling one assembly is decomposed into distinct disassembly subproblems. The algorithm returns the AND/OR graph representation of assembly sequences. The correctness of the algorithm is based on the assumption that it is always possible to decide correctly whether two subassemblies can be joined, based on geometrical and physical criteria. An approach to computing this decision is presented. An experimental implementation for the class of products made up of polyhedral and cylindrical parts with planar or cylindrical contacts among themselves is described. Bounds for the amount of computation involved are presented.>

The authors introduce two criteria for the evaluation and selection of assembly plans. The first criterion is to maximize the number of different sequences in which the assembly tasks can be executed. The second criterion is to minimize the total assembly time through simultaneous execution of assembly tasks. An algorithm that performs a heuristic search for the best assembly plan over the AND/OR graph representation of assembly plans is discussed. Admissible heuristics for each of the two criteria introduced are presented. Some implementation issues that affect the computational efficiency are addressed.>

Two criteria are introduced for the evaluation and selection of assembly plans. The first criterion is to maximize the number of different sequences encompassed by the assembly plan. The second criterion is to maximize the amount of parallelism (i.e., simultaneity) that is possible in the execution of the assembly tasks. While the metrics corresponding to the criteria used in previous work can be expressed as a sum of terms, each being a function of a task or a state, the metrics corresponding to the criteria introduced are more complex functions of the whole assembly plan. An algorithm that performs a heuristic search for the best assembly plan over an AND/OR graph representation of assembly plans is presented. Admissible heuristics for each of the two criteria are presented.>

A compact representation of all possible assembly plans of a given product using AND/OR graphs is presented. Such a representation forms the basis for efficient planning algorithms that make possible an increase in assembly system flexibility by allowing an intelligent robot to pick a course of action according to instantaneous conditions. The AND/OR graph is equivalent to a state transition graph but requires fewer nodes and simplifies the search for feasible plans. Three applications are discussed: the preselection of the best assembly plan, the recovery from execution errors, and the opportunistic scheduling of tasks. A hypothetical error situation in the assembly of the four-part assembly is discussed to show how a bottom-up search of the AND/OR graph leads to an efficient recovery. The scheduling efficiency using this representation is compared with fixed sequence and precedence graph representations.>

The authors present an algorithm for the generation of mechanical assembly sequences and a proof of its correctness and completeness. The algorithm uses a relational model which describes the geometry of the assembly and the attachments that bind one part to another. The problem of generating the assembly sequences is transformed into the problem of generating disassembly sequences, in which the disassembly tasks are the reverse of feasible assembly tasks. This transformation leads to a decomposition approach in which the problem of disassembling one assembly is decomposed into distinct subproblems, each involving the disassembly of one subassembly. It is assumed that at each assembly task exactly two subassemblies are mated and that all contacts between the parts in the two subassemblies are established. The algorithm yields an AND/OR graph representation of assembly sequences. The correctness of the algorithm is based on the assumption that it is always possible to decide correctly whether two subassemblies can be joined based on geometrical and physical criteria. An approach to compute this decision is given, and bounds for the amount of computation required are presented.>

A simple modification is shown in the set of goal nodes of the AND/OR graph that allows its use in planning repairs such as the replacement of a part or a subassembly. An algorithm for the generation of all feasible sequences for disassembly and reassembly of parts that will achieve a repair is shown. This approach has been demonstrated for the example of the repair of space-based satellite equipment.>