Optimal Robotic Assembly Sequence Planning (ORASP)

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:

Family	Notebook	Idea
GEAP – Graph‑Exploration Assembly Planners	AssemblyPlanning-GEAP.ipynb	Enumerate the reachable subassembly space as a graph, then run exact dynamic‑programming / shortest‑path search over it.
Learning‑based	AssemblyPlanning-DQN.ipynb	Train a Deep Q‑Network (and tabular RL baselines) to learn a disassembly policy without building the full graph.

---

Table of contents

• 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

---

Key idea

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.

Problem formulation

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:

Element	Meaning in code
State s ∈ S	A subassembly — i.e. some subset of H's edges still connected.
Action a ∈ A(s)	Remove one currently‑present connection (an edge of the current subgraph).
Transition T(s' | s, a)	Deterministic edge removal; infeasible actions (precedence violations) are pruned during graph generation.
Reward R(s, a)	Negative transport/handling cost of performing the maneuver, plus a terminal +1 for reaching the fully‑disassembled state. See Reward functions.

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.

Repository layout

Path	Description
AssemblyPlanning-GEAP.ipynb	Graph‑Exploration Assembly Planners: full state‑space generation + Value Iteration + Dijkstra + plotting.
AssemblyPlanning-DQN.ipynb	Deep Q‑Network planner, random baselines, and tabular DP / Q‑learning for comparison.
helpers.py	Shared code: the DQN network, ReplayMemory, recursive state‑space generator (recurGen), single‑step expansion (nextGen), hierarchical graph layout, and the family of reward functions (RNOcaz, Rcaz, Rcustom, Rsimple, dispatched by R).
requirements.txt	Conda environment spec (Python 3.10).
pipRequirements.txt	pip freeze of the same environment for venv users.
RESULTS/	Figures (.eps/.svg), step‑by‑step render frames, and per‑scenario DQN result JSON produced by the notebooks. Git‑ignored by default.
LICENSE	MIT.

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.

Installation

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

Option A — Conda

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

Option B — venv + pip

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

Minimal install

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

Quick start

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).

Notebook walkthrough

GEAP notebook

Section	What it does
Imports / Helper Functions	Loads networkx, torch, etc. and defines recurGen, R, layout helpers.
Scenario Initializations	Two example topologies (a 3‑part triangle and a 20‑part "Hubble"‑style tree). Each cell sets H, resets seqConstraint, and prints a configuration summary (parts, connections, subassembly/edge counts, #constraints).
Running the Assembly Generation	recurGen(1, H, G) recursively enumerates every feasible subassembly into the directed graph G; prints generation time and G's size.
Value Iteration	ValueIteration(G, H, maxIter, eps) returns V and a greedy policy π; the cell then walks π from the start state to recover the ordered list of connections to remove.
Dijkstra	Re‑weights G with negated costs and calls nx.dijkstra_path as an independent check on the optimum.
Graphing Suite	Colours and lays out H, overlays the optimal policy path on G, and writes step‑by‑step PNG frames (e.g. RESULTS/2x3/0.png …).

DQN notebook

Section	What it does
Imports / Helper Functions	Same helpers plus pyvis for interactive graph views.
Scenario Initialization	Nine ready‑made structures — see Bundled scenarios. Run exactly one.
DQN	Builds policy_net / target_net (helpers.DQN, a 3‑layer MLP), an AdamW optimizer, and a 100k‑transition replay buffer. Trains for num_episodes (default 1000) with an ε‑greedy schedule (EPS_START=0.85 → EPS_END=0.05, EPS_DECAY=1000), soft target updates (TAU=0.01), GAMMA=1, LR=1e-3. Saves a training‑reward curve to RESULTS/DQN/<Scenario> Training.eps.
Baselines	Rolls out the learned greedy policy and numBaselines=5 random policies, then dumps strategies, rewards, and hyperparameters to RESULTS/DQN/<Scenario>.json.
Assembly Generation & Tabular DP	Runs recurGen + a maximizing ValueIteration and a tabular Q‑learning loop (nextGen) on the same scenario for an exact reference.
Graphing Suite	Hierarchical layout of G with the policy path highlighted; prints the recovered strategy and its reward.

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().

Defining your own scenario

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.

Precedence / sequencing constraints

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).

Reward functions

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:

Function	Cost model
RNOcaz (default)	Structures are built at the supply vehicle; cost = round‑trip transport for each newly freed piece of size 1–3.
Rcaz	Adds an intermediate Construction Assembly Zone; single parts return to the SV, pairs/triples are staged in the CAZ, with distinct transit costs. Updates each part's loc.
Rcustom	Simple hand‑tuned costs (-1 / -1.5 / -1.75 by freed‑piece size, -0.1 step cost).
Rsimple	Purely index‑based shaping reward, useful for debugging the search.

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

Bundled scenarios

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

Scenario	Parts	Connections	Notes
3Piece	3	3	Triangle; smallest non‑trivial case.
4Brick	4	3	Open chain.
2x3	6	7	Grid with cross‑links + precedence constraints.
Lattice	9	12	3×3 lattice with precedence constraints.
Hubble	20	19	Tree‑structured telescope mock‑up.
ISS	32	31	International Space Station‑style truss.
JWST	180	256	Large multi‑module telescope; stress test.
NLongChain	N (default 50)	N-1	Parametric chain; every 3rd edge gets a precedence constraint.
NRandomTree	N (default 100)	N-1	Random spanning tree for scaling experiments.

Outputs

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.

Notation notes & caveats

• 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(...).

Citation

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.)

License

Released under the MIT License. © 2022 Kartik Nagpal.