Turning Procedures Into Task Graphs: Steps, Dependencies and Partial Order

Why a numbered list is not enough

Procedures are written as numbered lists because documents are linear. The work usually is not. Staging fasteners can happen at any point before they are needed; cleaning a groove must happen before a gasket goes in; isolating power must happen before a guard opens, whatever the physics allows.

Published procedural datasets show both kinds of order. FineBio's biology protocols have a strict order of steps but a flexible order of the atomic operations inside them (Yagi et al., 2024). Assembly101 recorded people assembling and disassembling toy vehicles without a script, mistakes included (Sener et al., 2022), so the same goal is reached through different orders.

If you train or evaluate against the numbered list, valid reorderings look like errors and a planner cannot interleave independent steps. A task graph records what the list leaves implicit.

This page covers dependency structure, meaning partial order. Decision points, where a condition selects one path or another, are a different structure, specified on branching procedures and decision points. The states that dependencies are built from are specified on preconditions and postconditions.

Graph elements

Nodes are procedure steps, each linked to its record in the procedure step schema. For long tasks, add subgoal nodes that group steps. Hierarchical task analysis is an established ergonomics method, originally developed to identify training needs, that decomposes goals this way (Stanton, 2006); where a supplier already holds such analyses, see hierarchical task analyses.

Edges carry a type, because not all "before" relations mean the same thing:

Steps with no path between them may run in any order or in parallel. Safety-critical edges deserve their own review; safety-critical steps in procedures covers how to flag them.

Where edges come from

Record the evidence for every edge. Four sources are common, and they disagree often enough that provenance matters.

1. Text cues. "After", "once", "do not ... until". Fast to extract, but documents leave many dependencies implicit.
2. State reasoning. If step A's postcondition is step B's precondition, A precedes B. This catches implicit dependencies when pre- and postconditions are well specified.
3. Observed executions. Across many recorded instances, orders that occur without defects show which swaps are acceptable. An order never observed is not proof of a dependency, only an absence of evidence. Research on procedure learning from multiple videos of the same task, such as EgoProceL's 62 hours of egocentric video from 130 subjects across 16 tasks with key-step annotations (Bansal et al., 2022), works from exactly this kind of repeated-execution data.
4. Expert review. An engineer or supervisor confirms each hard and safety edge and signs the graph.

Illustrative graph specification

# Illustrative only — synthetic task graph for one procedure revision
graph_id: tg_WI-ASM-212_revE
source: {doc_id: WI-ASM-212, revision: E, site_scope: [site_031, site_034]}
nodes:
  - {id: n1, step_ref: s01, action: inspect, object: housing, produces: [housing_ok]}
  - {id: n2, step_ref: s02, action: clean, object: housing_groove, requires: [housing_ok], produces: [groove_clean]}
  - {id: n3, step_ref: s03, action: place, object: gasket, requires: [groove_clean], produces: [gasket_seated]}
  - {id: n4, step_ref: s04, action: stage, object: screws_m4_x4, produces: [screws_staged]}
  - {id: n5, step_ref: s05, action: fit, object: cover_plate, requires: [gasket_seated], produces: [cover_on]}
  - {id: n6, step_ref: s06, action: hand_start, object: screws_m4_x4, requires: [cover_on, screws_staged]}
edges:
  - {from: n1, to: n2, type: hard_precedence,    evidence: state,  confirmed_by: eng_03}
  - {from: n2, to: n3, type: quality_precedence, evidence: text,   confirmed_by: eng_03}
  - {from: n3, to: n5, type: hard_precedence,    evidence: state,  confirmed_by: eng_03}
  - {from: n5, to: n6, type: hard_precedence,    evidence: state,  confirmed_by: eng_03}
  - {from: n4, to: n6, type: hard_precedence,    evidence: state,  confirmed_by: eng_03}
free_nodes: [n4]                                 # may occur anywhere before n6
documented_order: [n1, n2, n3, n4, n5, n6]       # must be one valid topological order
observed: {instances: 214, distinct_orders: 5, instances_violating_hard_edges: 3}
validation: {acyclic: true, documented_order_valid: true, expert_review: 2026-05-02}

Field-level specification

Keep state names in a controlled vocabulary shared with the step schema, so "gasket_seated" means the same thing in every graph that uses it.

How graphs get used

• Planning. ProgPrompt generates plans against program-like specifications of available actions and objects (Singh et al., 2022); a task graph tells such a planner which steps it may reorder or interleave. Behavior trees structure how a robot switches between tasks in a modular, reactive way (Colledanchise and Ögren, 2017), and PDDL is a language for specifying planning domains (McDermott et al., 1998); conversion to either is covered on procedures to PDDL and behavior trees.
• Evaluation. Ordering and next-step questions can be graded against every valid order instead of one; see procedural reasoning evaluation sets.
• Video labels. The "reordered" match type in SOP-to-video step alignment should be judged against the graph, not the document's list.
• Knowledge graphs. Task graphs can be joined across procedures through shared objects and states; procedural knowledge graphs covers that larger structure.

Acceptance tests

• Acyclic. No dependency cycles.
• Documented order valid. The procedure's own order is one valid ordering of the graph; if not, either the graph or the document is wrong.
• Evidence complete. Every hard and safety edge has an evidence source and a named reviewer.
• Observed conformance. Recorded instances that violate a hard edge are each reviewed: either the edge is wrong or the instance contains an error.
• Full mapping. Every node maps to a procedure step, and every step maps to a node.
• Safety review. Safety edges are confirmed by someone responsible for safety at the site.

Limitations

• A graph encodes task logic, not skill. It contains no motion, force or perception data, and every node still needs demonstrations or robot data to execute.
• Text-derived edges miss implicit dependencies; observation-derived edges need many instances and still cannot prove a dependency.
• Graphs vary by site and equipment; a graph built at one site may not hold at another.
• Over-constraining turns valid variation into errors; under-constraining can drop a safety edge. Err toward keeping safety edges.

Questions to ask suppliers and annotation vendors

1. Do procedures state dependencies explicitly, or only as numbered order?
2. Are recorded executions available, so observed orders can be compared with the document?
3. Who at the site can confirm hard and safety dependencies, and will they sign the graph?
4. Are hierarchical task analyses or time studies available for the same tasks?
5. How will you represent steps that share a tool, hand or workstation?
6. How do you handle differences in order between sites using the same procedure?
7. Which procedure revision is each graph built from, and how will graphs be updated when it changes?

Discuss your requirements

If you need task graphs built from real workplace procedures, describe the tasks, sites and graph detail you need to SourceX. SourceX looks for US businesses that hold suitable procedures, checks the data and the supplier's licensing permissions, and coordinates the license and delivery. SourceX's role is sourcing, rights review, licensing and delivery coordination; it can also arrange annotation, scoped case by case. It reviews each requirement and follows up about potential sources; a request does not guarantee a match. See the procedures hub, the humanoid training data guide and the catalog entry for SOPs, playbooks and knowledge bases.

Explore sourcing and licensing options with SourceX

Sources

• FineBio: A Fine-Grained Video Dataset of Biological Experiments with Hierarchical Annotation — strict step order with flexible order of atomic operations.
• Assembly101: A Large-Scale Multi-View Video Dataset for Understanding Procedural Activities — unscripted procedural recordings with mistakes.
• Hierarchical task analysis: Developments, applications, and extensions — hierarchical decomposition of goals into subgoals.
• My View is the Best View: Procedure Learning from Egocentric Videos — key steps learned from repeated egocentric executions.
• ProgPrompt: Generating Situated Robot Task Plans using Large Language Models — plans against program-like action specifications.
• Behavior Trees in Robotics and AI: An Introduction — modular, reactive task switching for robots.
• PDDL - The Planning Domain Definition Language (Version 1.2) — formal planning domain language.