Planning Assembly Sequence with Graph Transformer

Lin Ma, Jiangtao Gong, Hao Xu, Hao Chen, Hao Zhao, Wenbing Huang, Guyue Zhou

TL;DR

Researchers have developed a new framework that uses Graph Transformers to solve Assembly Sequence Planning (ASP)—the complex puzzle of determining the best order to put parts together. By treating a LEGO model as a heterogeneous graph and training on a custom-built dataset, the system learns to predict feasible assembly sequences, moving beyond traditional, slow optimization methods toward more generalizable AI for manufacturing.

What Problem Does This Paper Address?

In modern manufacturing, Assembly Sequence Planning (ASP) is a critical but notoriously difficult task. It involves determining the exact order in which components should be joined to create a finished product. Because the number of possible sequences grows exponentially with the number of parts, ASP is classified as NP-complete.

Traditional approaches usually fall into two camps:

  1. Assembly-by-disassembly: Recursively finding a path to take a product apart and then reversing it.
  2. Combinatorial optimization: Using algorithms like Ant Colony Optimization to find a valid path under constraints.

The "gap" is that these methods are usually tailored to one specific product at a time. They don't "learn" the general rules of assembly that could be applied to new, unseen designs. Furthermore, there hasn't been a high-quality, standardized dataset for training deep learning models specifically on the logic of assembly sequences—until now.

Methods

The authors propose a Graph Transformer-based framework that treats assembly as a sequence prediction task.

  • Graph Representation: They represent a LEGO model as a heterogeneous graph. Each brick is a node (containing features like its type and 3D position). The relationships between bricks are edges.
  • Edge Types: Crucially, they distinguish between two types of edges:
  • Link edges: Physical connections (knob-to-cavity).
  • Block edges: Spatial interference (e.g., "Brick A cannot be placed if Brick B is already there because they occupy the same path").
  • Heterogeneous Graph Transformer (HGT): The encoder uses an attention mechanism that treats different edge types differently. This allows the model to understand that a physical connection is logically different from a spatial blockage.
  • Transformer Decoder: The decoder predicts the next assembly position in the sequence. The system then selects the real brick closest to that predicted position to be the next step in the assembly.

Datasets

The researchers introduced a new benchmark: LEGO-ASP.

  • Content: 100 LEGO animal models ranging from 3 to 44 bricks.
  • Ground Truth: They generated "correct" sequences using a brute-force search to ensure physical feasibility, then manually adjusted them to align with "human rational habits" (e.g., building from the bottom up or finishing one limb before starting another).
  • Comparison: Unlike existing datasets (like IKEA furniture sets), which are often too simple or lack complex interlocking relationships, LEGO models provide a rich variety of spatial constraints.

Key Insights and Ideas

  • Edges Matter More Than Nodes: In a surprising ablation study, the authors found that including the brick type (node feature) actually decreased performance. They concluded that the specific shape of a brick is less important for the sequence than its spatial relationship (edges) to its neighbors.
  • The Power of "Block" Edges: The inclusion of "block edges" (representing spatial interference) significantly boosted the model's ability to predict a feasible sequence. This confirms that understanding what prevents an action is just as important as understanding what enables it.
  • Human Logic vs. Machine Logic: By manually adjusting the ground truth, the authors acknowledged that a "feasible" sequence isn't always a "good" one. Humans prefer semantic continuity (finishing a sub-assembly), and training the model on these adjusted sequences helps it produce more "rational" results.

Key Results

  • Similarity Metrics: The model achieved a Kendall’s $\tau$ of 0.44 on the test set. While not a perfect correlation (1.0), it represents a "medium correlation" that significantly outperforms random guessing in an NP-complete search space.
  • Complexity Scaling: The model performed much better on simpler models. For the smallest 60% of the dataset, Kendall’s $\tau$ jumped to 0.4482, and the Regularized Location Swap Deviation (RLSD) dropped to 0.2440, indicating the sequence was very close to the ground truth.
  • In-Process Success: The model proved highly effective at "In-process" tasks—taking a 40% or 60% completed model and successfully predicting the remaining steps.

Limitations and Future Work

The primary limitation is scalability. As the number of bricks increases, the graph becomes more complex, and the model’s performance begins to degrade. The authors note that for very large models, the pattern of the graph becomes less consistent, making it harder for the Transformer to capture general rules.

Future Direction: The authors suggest moving toward a hierarchical structure. Instead of treating every brick as an individual node, future models could group bricks into "sub-assemblies" (like a leg or a head), solving the sequence for those sub-units first before planning the overall assembly. This "divide and conquer" approach mirrors how humans tackle complex builds.

Summary updated

Abstract

Assembly Sequence Planning (ASP) is the essential process for modern manufacturing, proven to be NP-complete thus its effective and efficient solution has been a challenge for researchers in the field. In this paper, we present a graph-transformer based framework for the ASP problem which is trained and demonstrated on a self-collected ASP database. The ASP database contains a self-collected set of LEGO models. The LEGO model is abstracted to a heterogeneous graph structure after a thorough analysis of the original structure and feature extraction. The ground truth assembly sequence is first generated by brute-force search and then adjusted manually to be in line with human rational habits. Based on this self-collected ASP dataset, we propose a heterogeneous graph-transformer framework to learn the latent rules for assembly planning. We evaluated the proposed framework in a series of experiments. The results show that the similarity of the predicted and ground truth sequences can reach 0.44, a medium correlation measured by Kendall's τ. Meanwhile, we compared the different effects of node features and edge features and generated a feasible and reasonable assembly sequence as a benchmark for further research. Our dataset and code are available on: htps://github.com/AIR-DISCOVER/ICRA_ASP.
BibTeX
@inproceedings{ma2023planning,
  author = {Lin Ma and Jiangtao Gong and Hao Xu and Hao Chen and Hao Zhao and Wenbing Huang and Guyue Zhou},
  title = {{Planning Assembly Sequence with Graph Transformer}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2023},
  url = {https://openreview.net/forum?id=FPOJwBeZE4},
}

Loading related content...

Figure