Reference implementation for the paper "Optimal Robotic Assembly Sequence Planning: A Sequential Decision-Making Approach."

ORASP is the problem of deciding in what order a robot (or team of robots) should join the parts of a structure so that the full assembly is completed at minimum cost, while respecting feasibility and precedence constraints. This repository formulates that problem as a Markov Decision Process (MDP) and solves it with two complementary families of planners:

• Key idea
• Problem formulation
• Repository layout
• Installation
• Quick start
• Notebook walkthrough
  • GEAP notebook
  • DQN notebook
• Defining your own scenario
• Precedence / sequencing constraints
• Reward functions
• Bundled scenarios
• Outputs
• Notation notes & caveats
• Citation
• License

Planning an assembly sequence is equivalent to planning a disassembly sequence and then reversing it. Disassembly is easier to reason about because every intermediate state is a well‑defined subgraph of the finished structure. All of the planners here therefore start from the fully‑assembled structure and search for the cheapest way to remove every connection one at a time; the optimal assembly plan is that removal order played backwards.

The finished structure is a graph H (called G in the paper — see caveats):

• Nodes = parts.
• Edges = connections between parts.
• Each node carries a loc attribute describing where that part currently lives (CL = construction location, SV = supply vehicle, CAZ = construction assembly zone). This is what the cost model keys off of.

The MDP is:

GEAP consolidates the whole reachable state–action space into a directed graph G (nodes = subassemblies, edges = actions with cost r), then finds the optimal policy with Value Iteration, Dijkstra / shortest‑path, or tabular Q‑learning. The DQN approach instead samples episodes and regresses the Q‑function with a small MLP, avoiding explicit construction of G for large structures.

The notebooks currently embed a copy of the helpers.py functions in their "Helper Functions" cell so they can be run without the module on the path. helpers.py is the canonical version.

Requires Python 3.10. Core dependencies: networkx 2.8, torch 1.13, numpy 1.23, matplotlib 3.6, pyvis 0.3, and Jupyter.

conda create --name orasp --file requirements.txt
conda activate orasp

python3 -m venv env
source env/bin/activate
pip install -r pipRequirements.txt

If you only want to run the notebooks and don't need to reproduce the exact environment:

pip install networkx==2.8.8 torch==1.13.1 numpy==1.23.4 matplotlib==3.6.2 pyvis==0.3.0 jupyter

jupyter notebook            # or: jupyter lab

Open AssemblyPlanning-GEAP.ipynb and run cells top to bottom:

1. Imports
2. Helper Functions
3. One cell from Scenario Initializations (this defines H, seqConstraint, and the size counters)
4. Running the Assembly Generation — builds the state graph G
5. Value Iteration — prints the optimal connection‑removal order and its cost
6. (optional) Graphing Suite — renders H, the policy path through G, and per‑step disassembly frames into RESULTS/

The DQN notebook follows the same pattern (imports → helpers → a scenario → training).

Key knobs in the DQN cell:

• num_episodes — training length.
• BATCH_SIZE — defaults to 3 × (#connections).
• EPS_START / EPS_END / EPS_DECAY, TAU, GAMMA, LR — standard DQN hyperparameters, documented inline.
• CUDA is used automatically when torch.cuda.is_available().

A scenario is just a networkx graph plus (optionally) a precedence dictionary. Drop a new cell in the Scenario Initialization section:

import networkx as nx

Scenario = "MyStructure"          # used to name output files (DQN notebook)

H = nx.Graph()
H.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1)])   # parts + connections
nx.set_node_attributes(H, "CL", "loc")               # every part starts at the construction location

numParts       = H.number_of_nodes()
numConnections = H.number_of_edges()
# size estimates used only for the printout:
numActions = (numConnections - 1) * pow(2, numConnections) + 1
numStates  = numConnections * pow(2, numConnections - 1) + 1

seqConstraint = {}                                    # see next section

Scaling warning. GEAP's recurGen enumerates the reachable subassembly space, which grows combinatorially in the number of connections. It is exact and fast for the small/medium structures here (≈ up to ~20 connections), but the large scenarios (ISS, JWST, 100RandomTree, long chains) are intended for the DQN path and/or to stress‑test state/action growth. seqConstraint entries prune the tree and make larger problems tractable.

seqConstraint maps a connection to a connection that must be removed first:

seqConstraint = {
    (2, 5): (1, 4),   # connection (2,5) can only be removed after (1,4) is gone
    (4, 5): (1, 2),
}

During graph generation, any action that would remove a key while its required predecessor edge is still present is treated as infeasible and skipped, so infeasible sequences never enter G (GEAP) or the reachable set (DQN).

All reward functions live in helpers.py and share the signature R_x(s, a, H) -> (reward, H_after_removal). The dispatcher R(s, a, H) decides which one is used (and memoizes results in the global Rewards dict). To change the objective, edit the call inside R:

Every variant gives a terminal reward of +1 for reaching the fully‑disassembled state.

Defined in the DQN notebook's Scenario Initialization section (a subset also appears in the GEAP notebook):

Written under RESULTS/ (git‑ignored):

• RESULTS/<Scenario>.eps / .svg — structure and state‑graph figures.
• RESULTS/<Scenario>/<step>.png — per‑step disassembly render frames.
• RESULTS/DQN/<Scenario> Training.eps — DQN training‑reward curve.
• RESULTS/DQN/<Scenario>.json — learned strategy, random‑baseline strategies, rewards, and the hyperparameters used.
• StateGrowthComparison.eps / ActionGrowthComparison.eps — scaling plots across scenarios.

• H vs G are swapped relative to the paper. In this code H is the physical assembly graph and G is the explored state–action graph; the paper uses the opposite letters.
• The disassembly plan the notebooks print must be reversed to obtain the assembly plan.
• Notebook cells assume you have run, in order: imports → helper functions → exactly one scenario cell, before running any solver cell. Re‑run the scenario cell to reset Rewards / seqConstraint before switching problems.
• recurGen uses recursion; very large structures may need sys.setrecursionlimit(...).

If you use this code, please cite:

@article{nagpal_orasp,
  title   = {Optimal Robotic Assembly Sequence Planning: A Sequential Decision-Making Approach},
  author  = {Nagpal, Kartik and others},
  year    = {2022}
}

(Update with the final venue / DOI once available.)

Released under the MIT License. © 2022 Kartik Nagpal.