Optimal Robotic Assembly Sequence Planning (ORASP): A Sequential Decision-Making Approach

Kartik Nagpal, Negar MehrIROS 2024 · OpenReview

TL;DR

This paper tackles the complex problem of finding the optimal sequence of robotic actions to assemble products, which grows exponentially with the number of parts. They introduce a novel sequential decision-making framework that models assembly planning as a Markov Decision Process, enabling them to leverage dynamic programming and graph search algorithms for efficient and optimal planning, even for very large structures.

What Problem Does This Paper Address?

Automated manufacturing relies heavily on efficient robotic assembly. The core challenge is determining the best sequence of actions for robots to assemble a product, minimizing objectives like time or cost. This problem becomes incredibly difficult as the number of possible assembly sequences explodes exponentially with the number of parts. Traditional heuristic methods are often specific to particular robots or cost structures, lacking generalizability. Furthermore, assembly plans must often satisfy complex constraints, such as the order in which parts must be attached.

Methods

The authors propose a novel sequential decision-making framework that reframes robotic assembly planning as an optimal control problem. They model this as a Markov Decision Process (MDP) and, crucially, use an "assembly-by-disassembly" approach. This means they start with the fully assembled product and plan the sequence of disassembly steps, which can then be reversed to get the optimal assembly sequence.

Key techniques include:

  • Markov Decision Process (MDP) Formulation: Defining states (progress of assembly), actions (removing a connection), and rewards.
  • Consolidated State-Action Graph: They represent the assembly process as a directed graph where nodes are states and edges are actions. A key innovation is "consolidating" this graph by recognizing that different sequences of removing the same connections lead to the same intermediate state, significantly reducing the graph's size.
  • Dynamic Programming (DP): Adapting traditional value iteration to find optimal paths on the consolidated graph.
  • Graph Exploration Assembly Planners (GEAPs): Leveraging shortest-path algorithms (like Dijkstra's and Bellman-Ford) on the consolidated graph to find optimal assembly sequences for moderately-sized structures.
  • ORASP Search Method: A more efficient graph generation approach that prunes suboptimal branches early, avoiding the need to build the entire graph.
  • Deep Q Network (DQN): For very large structures where even consolidated graphs are intractable, they employ a deep reinforcement learning approach. A DQN learns an optimal policy by approximating the quality function, allowing it to generate near-optimal assembly sequences without exploring the full state-action space.

Datasets

The paper evaluates their methods on several structures, including:

  • "4Brick": A small, toy example used throughout the paper for illustration.
  • Furniture and "2x3": Benchmarks adapted from existing works ([31], [32]).
  • Hubble Space Telescope, International Space Station (ISS), and James Webb Space Telescope (JWST): Large-scale structures, some of which are intractable for prior state-of-the-art methods.

Key Insights and Ideas

  • Assembly-by-Disassembly Equivalence: Framing assembly planning as disassembly planning simplifies the problem by aligning with existing cost functions and objective engineering, while maintaining symmetry.
  • State-Action Graph Consolidation: Recognizing that the order of removing identical sets of connections doesn't change the resulting subassembly is crucial for dramatically reducing the state-action space's complexity.
  • GEAPs for Moderate Scale: For structures that can be represented by a consolidated graph, shortest-path algorithms offer a computationally efficient way to find provably optimal solutions.
  • DQN for Scalability: Deep Reinforcement Learning is essential for tackling extremely large assembly problems where graph-based methods fail due to combinatorial explosion.
  • Constraint Integration: The framework naturally incorporates constraints (like precedence) by modifying the transition function or pruning branches, which not only ensures satisfaction but also reduces the search space.

Key Results

  • Speedup: GEAP methods achieved significant speedups compared to the state-of-the-art ILP method, with improvements of 3x to 50x on various scenarios (e.g., Lattice, Hubble). Dijkstra's method provided over a 4,000x speedup for the Lattice min-travel scenario.
  • Scalability: The DQN approach successfully handled extremely large structures (ISS, JWST) that were infeasible for prior methods.
  • Performance: The DQN approach consistently outperformed a distribution of 100 random assembly sequences on all tested scenarios, including recovering optimal solutions for smaller structures like Hubble.
  • Constraint Handling: The paper demonstrates how sequential constraints effectively prune the state-action space, leading to more efficient search and potentially different optimal solutions.

Limitations and Future Work

  • Global Optimality of DQN: While the DQN approach scales well, it provides near-optimal solutions, and global optimality is not guaranteed, unlike the GEAP methods.
  • Computational Intractability of GEAPs: For extremely large structures, even the consolidated graph generation for GEAPs becomes computationally intractable.
  • Deterministic Assumption: The current framework primarily considers deterministic scenarios. Extending it to handle uncertainties (e.g., chances of failure) is a promising future direction.
  • Full-Stack Integration: The authors suggest that pairing their planning framework with existing resource tracking, agent assignment, and motion planning systems could provide a complete solution for robotic manufacturing.

Summary updated

Abstract

The optimal robotic assembly planning problem entails determining the sequence of actions for a robot to feasibly assemble a product from its components which minimizes a given objective. This problem is made especially challenging as the number of potential sequences increase exponentially with respect to the number of parts in the assembly. Additionally, the optimal sequence must also consider and satisfy a selection of constraints such as attachment precedence or a maximum robot carry weight. Traditionally, robotic assembly planning problems have been solved using heuristics, but these methods are specific to a given robot or cost structure. In this paper, we propose to model robotic assembly planning as a decision-making problem which enables us to use tools from shortest path algorithms and reinforcement learning. We formulate assembly sequencing as a Markov Decision Process and use Dynamic Programming (DP) to find optimal assembly policies that far outperform the state-of-the-art in terms of speed. We further exploit the deterministic nature of assembly planning to introduce a class of optimal Graph Exploration Assembly Planners (GEAPs) and even propose our own ORASP Search Method. We further showcase how we can produce high-reward assembly plans for larger structures using our deep Reinforcement Learning (RL) method. We evaluate this method on large robotic assembly problems such as the assembly of the Hubble Space Telescope, the International Space Station, and the James Webb Space Telescope. We further discuss how our DP, GEAP, and RL methods are capable of finding optimal solutions under a variety of different objective functions and how we translate any form of precedence constraints to branch pruning and further improve performance. We have published our code at https://github.com/labicon/ORASP-Code.
BibTeX
@inproceedings{nagpal2024optimal,
  author = {Kartik Nagpal and Negar Mehr},
  title = {{Optimal Robotic Assembly Sequence Planning (ORASP): A Sequential Decision-Making Approach}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=KigGXKZRUh},
}
Figure