State-Based Disassembly Planning

Chao Lei, Nir Lipovetzky, Krista A. Ehinger

TL;DR

This paper introduces State-Based Disassembly Planning (SBDP), a novel approach that significantly improves the efficiency and success rate of automated disassembly for complex assemblies. By prioritizing translational motion, storing intermediate states, and leveraging Directional Blocking Graphs (DBGs) with state information, SBDP reduces redundant simulations and intelligently guides the search, outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

Automated assembly and disassembly are crucial for manufacturing, maintenance, and repair. While physics-based simulations have greatly enhanced the ability to plan disassembly for complex 3D assemblies with strict motion constraints, existing methods like PDP (Physics-Based Disassembly Planning) suffer from inefficiency. This inefficiency stems from the need for numerous simulations, especially in intricate tasks, and the regeneration of already simulated trajectories. Furthermore, current approaches often require human input to specify whether an operation should be translational or rotational, limiting autonomy. This paper aims to address these limitations by developing a more efficient, autonomous, and scalable disassembly planning approach.

Methods

The core of this work is the State-Based Disassembly Planning (SBDP) approach. Unlike previous methods that might re-simulate states or require manual input, SBDP introduces several key innovations:

  • State Storage and Prioritization: SBDP stores intermediate motion states and prioritizes translational motion over rotational motion. This strategy aims to reduce computational cost by avoiding redundant simulations and leveraging the efficiency of translational movements first.
  • Directional Blocking Graphs (DBGs) with State Information: The paper introduces novel evaluation functions derived from DBGs that are enriched with state information. DBGs, traditionally used for static analysis, are now dynamically updated based on simulation results. This allows SBDP to capture blockage relationships that evolve as parts are disassembled.
  • Novel Evaluation Functions: Two new evaluation functions, $f_c$ (number of colliding parts) and $f_a$ (number of available collision-free actions), are proposed. These functions guide the search by prioritizing nodes that are less obstructed and have fewer available actions, aiming to reduce unnecessary simulations.
  • Integrated Translational and Rotational Planning: SBDP seamlessly integrates both translational and rotational planning. Translational planning is prioritized, and rotational planning is used to address remaining complexities, allowing for a mixed-motion disassembly plan.
  • Collision State Management: SBDP explicitly stores and reuses information about collision states, preventing repeated simulations of the same problematic configurations.

Datasets

The authors evaluated their approach on a large-scale dataset introduced by Tian et al. (2022), comprising thousands of physically valid industrial assemblies. These assemblies were categorized into three groups: small (3-9 components), medium (10-49 components), and large (50+ components), totaling 4196 problems.

Key Insights and Ideas

  • The Power of Stored States: Storing and revisiting intermediate states, rather than regenerating them, is a crucial factor in improving scalability and efficiency for complex disassembly tasks.
  • Dynamic DBGs are Key: Moving beyond static DBGs to dynamically updated DBGs that incorporate state information allows for a more accurate and adaptive understanding of part interactions throughout the disassembly process.
  • Translational First, Then Rotational: Prioritizing translational motion significantly speeds up the initial stages of disassembly, and rotational motion is then strategically employed for more complex maneuvers, leading to a more efficient overall plan.
  • Heuristics Matter: The proposed $f_c$ and $f_a$ heuristics effectively guide the search, pruning less promising branches and avoiding computationally expensive simulations for actions that are known to lead to collisions.

Key Results

SBDP* (the proposed method with DBGs and heuristics) demonstrated state-of-the-art performance:

  • Success Rate: SBDP solved 4135 out of 4196 problems (98.55%), significantly outperforming existing methods like PDP, PDP, and PDPt across all assembly size categories.
  • Computational Efficiency: SBDP* achieved substantial reductions in search space and planning time. Compared to SBDP, it reduced average search space by 55%, path planning time by 40%, and disassembly planning time by 20%. Compared to the best PDP variants, these reductions were even more pronounced (up to 80% in search space and 70% in path planning time).
  • Coverage: Figure 4 shows that SBDP and SBDP solve more problems than PDP and PDP, even within short time windows, highlighting their superior efficiency and coverage.

Limitations and Future Work

  • Limitations: The paper acknowledges that in some cases, occasional incorrect collision detection can lead to penetration disassembly trajectories for all tested approaches. The computational intensity of rotational analysis is also a factor, leading to its omission in initial static analysis.
  • Future Work: The authors suggest incorporating more mature planning techniques, such as classical planners with search heuristics, into SBDP. They also propose exploring other learning-based methods to guide SBDP and leveraging SBDP-generated disassembly plans for robot learning from demonstrations in assembly training systems. The potential for applying SBDP to generate assembly plans by reversing disassembly sequences and paths is also highlighted.

Summary updated

Abstract

It has been shown recently that physics-based simulation significantly enhances the disassembly capabilities of real-world assemblies with diverse 3D shapes and stringent motion constraints. However, the efficiency suffers when tackling intricate disassembly tasks that require numerous simulations and increased simulation time. In this work, we propose a State-Based Disassembly Planning (SBDP) approach, prioritizing physics-based simulation with translational motion over rotational motion to facilitate autonomy, reducing dependency on human input, while storing intermediate motion states to improve search scalability. We introduce two novel evaluation functions derived from new Directional Blocking Graphs (DBGs) enriched with state information to scale up the search. Our experiments show that SBDP with new evaluation functions and DBGs constraints outperforms the state-of-the-art in disassembly planning in terms of success rate and computational efficiency over benchmark datasets consisting of thousands of physically valid industrial assemblies.
BibTeX
@inproceedings{lei2025state,
  author = {Chao Lei and Nir Lipovetzky and Krista A. Ehinger},
  title = {{State-Based Disassembly Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=iiHHETtsQk},
}
Figure