AND OR GRAPH REPRESENTATION OF ASSEMBLY PLANS

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 enable 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. The same approach used to preselect the best assembly plan can be used to preselect the best disassembly plan. A change in the definition of goal nodes allows the preselection of the best disassembly plan that will release a given part for maintenance or repair tasks. An example of an assembly with four parts illustrates the use of the and/or graph representation to find the best assembly plan based on the weighing of operations according to complexity of manipulation and stability of subassemblies. In practice, a generic search algorithm, such as the AO*, may be used to find this plan. 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 and/or graph consistently reduces the average number of operations. © 1990 IEEE