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