And/Or Graph Representation of Assembly Plans

Luiz Homem de Mello, Arthur C. SandersonAAAI 1986

Summary

This research introduces a compact representation for all possible assembly paths of a product using AND/OR graphs. By moving beyond rigid linear instructions, this method enables robots to dynamically select the most efficient assembly sequence based on real-time conditions, enhancing flexibility and error recovery in automated manufacturing.

Introduction: The Limitations of Fixed Sequences

Traditional robotic assembly typically relies on "fixed sequences"—predefined, step-by-step instructions. This rigidity becomes a liability when parts arrive out of order or when a robot encounters an error; the system lacks the intelligence to "pivot" to an alternative valid state. While precedence diagrams offer some variation, they are often mathematically insufficient for representing all valid sequences and fail to account for the physical context of operations. The authors propose a representation that is both exhaustive and context-aware.

Methodology: AND/OR Graphs

The core of this approach is the use of AND/OR graphs (or hypergraphs) to map the entire state space of an assembly.

  1. Backward Search (Disassembly): To efficiently map construction paths, the authors utilize a backward search starting from the finished product. Since disassembly moves are reversible, this process identifies all possible assembly routes while managing branching complexity.
  2. Nodes and Hyperarcs: In this graph, nodes represent subassemblies, while hyperarcs represent assembly operations. This structure allows for a compact representation where any unique subassembly appears only once, regardless of how it was reached.
  3. Optimization via AO* Search: Weights are assigned to hyperarcs based on operation difficulty and subassembly stability. The AO* algorithm then identifies the minimum-cost solution tree.
  4. Opportunistic Scheduling: This representation supports real-time scheduling, allowing robots to identify the most efficient next step based on currently available parts.
Ten possible assembly sequences for the simple product, illustrating the variety of paths the AND/OR graph must consolidate.

Experimental Setup: The Four-Part Assembly

The approach was evaluated using a custom-designed four-part assembly: a cap, a stick, a receptacle, and a handle. Despite its simplicity, this model demonstrates the combinatorial complexity that traditional methods struggle to capture. The authors simulated 24 different random arrival sequences of these four parts to test the efficiency of different representation schemes.

A simple four-part product consisting of a cap, stick, receptacle, and handle used for testing.

Results and Discussion

The authors compared three representation schemes across 24 random part-arrival sequences:

  • Fixed Sequence: Averaged 9.8 operations per assembly due to excessive buffering and retrieving.
  • Precedence Graph: Improved slightly to 9.2 operations.
  • AND/OR Graph: Achieved the theoretical optimum of 8.0 operations.

Key Insights

  • Contextual Operations: AND/OR graphs distinguish between physically different tasks (e.g., attaching a cap to a lone receptacle vs. one already attached to a handle).
  • Flexibility as Efficiency: By knowing every valid move, the robot minimizes wasted motions like buffering and retrieving, directly driving operational efficiency.

Conclusion and Future Work

While effective for simple products, scaling AND/OR graphs to complex assemblies (e.g., engines) requires enhanced computational power and optimized heuristics. Future work will focus on automatically generating these graphs from CAD data and developing more sophisticated buffering strategies for space-constrained environments.

Summary updated

BibTeX
@inproceedings{mello1986or,
  author = {Luiz Homem de Mello and Arthur C. Sanderson},
  title = {{And/Or Graph Representation of Assembly Plans}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure