AND/OR graph representation of assembly plans

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>