Planning Assembly Sequence with Graph Transformer

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

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 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 experiment. The results show that the similarity of the predicted and ground truth sequences can reach 0.44, a medium correlation measured by Kendall's $\tau$. 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.

Introduction

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, such as assembly-by-disassembly or combinatorial optimization, are often tailored to specific products and fail to generalize. This research aims to bridge the gap by developing a learning-based approach that captures general assembly logic.

Methodology

The proposed framework utilizes a Graph Transformer to treat assembly as a sequence prediction task. LEGO models are represented as heterogeneous graphs where bricks are nodes and their relationships are edges.

Step-by-step assembly sequence for a LEGO model.

The model distinguishes between two primary edge types:

  1. Link edges: Representing physical connections (knob-to-cavity).
  2. Block edges: Representing spatial interference, where one brick's presence prevents the placement of another.

A Heterogeneous Graph Transformer (HGT) encoder processes these relationships, allowing the model to differentiate between physical connectivity and spatial constraints. A Transformer decoder then predicts the next assembly position, selecting the real brick closest to that prediction.

The LEGO-ASP Dataset

To train and evaluate the model, the researchers introduced the LEGO-ASP benchmark. This dataset consists of 100 LEGO animal models with brick counts ranging from 3 to 44.

Diverse LEGO models included in the LEGO-ASP dataset.

Ground truth sequences were initially generated via brute-force search to ensure physical feasibility and then manually refined to align with "human rational habits," such as building from the bottom up or completing sub-assemblies (e.g., a limb) before moving to other sections.

Key Insights and Results

A significant finding from the ablation studies was that edge features (spatial relationships) are more critical than node features (brick types). In fact, including brick types as node features slightly decreased performance, suggesting that the logic of assembly is driven more by how parts relate to each other than by the specific identity of the parts themselves. The inclusion of "block edges" was particularly vital for predicting feasible sequences.

The model achieved a Kendall’s $\tau$ of 0.44 on the test set, indicating a medium correlation with human-rational sequences. Performance was notably higher on smaller models (up to 60% of the dataset size), where Kendall’s $\tau$ reached 0.4482. The framework also excelled at "in-process" tasks, successfully completing models that were already 40-60% assembled.

Conclusion and Future Work

While the Graph Transformer framework shows promise, scalability remains a challenge. As models grow in brick count, the graph complexity increases, leading to performance degradation. Future research will explore hierarchical structures, grouping bricks into semantic sub-assemblies (like a head or leg) to mirror human "divide and conquer" strategies in 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 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 experiment. The results show that the similarity of the predicted and ground truth sequences can reach 0.44, a medium correlation measured by Kendall's $\tau$. 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 data set and code is available on https://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