Source-linked AI summary
TaPeR: Probabilistic Recovery of Sparse Task Precedence Graphs from a Handful of Demonstrations
Adrian Röfer, Karla Stepanova, Abhinav Valada
TL;DR
Long-horizon manipulation tasks contain subtasks that may be reordered, but existing demonstration-based approaches often rely on difficult-to-ground symbolic predicates. TaPeR uses kinematic graphs and relative-pose distributions to estimate pairwise dependencies and filter them into task precedence graphs, recovering task structures from few demonstrations and generating multiple valid execution orders.
Problem
Recovering partial task order from demonstrations is difficult because existing approaches commonly require symbolic supervision whose predicates are hard to ground in realistic settings.
Method
TaPeR fuses temporal, topological, and spatial evidence from kinematic graphs and relative-pose distributions into pairwise precedence probabilities, then incrementally prunes a fully connected graph.
Results
TaPeR recovers more accurate task structures from fewer demonstrations than baselines across an existing benchmark and a new dataset of longer, more complex tasks.
Takeaways & Limitations
The inferred task precedence graphs can generate multiple valid robotic execution orders while preserving mandatory dependencies.
Abstract
from arXiv · showhide
Long-horizon manipulation tasks are often only partially ordered. For example, when assembling an electronic device, the battery and circuit board may be installed in either order, but both must be in place before the enclosure is closed. Recovering such dependencies enables robots to flexibly reorder subtasks while preserving task validity. Existing approaches typically infer task structure from human demonstrations using both temporal and symbolic supervision. However, symbolic predicates require explicit grounding, which is difficult to obtain in realistic settings. In this work, we present an approach for extracting task dependency structures from demonstrations using only simple kinematic graphs and distributions over relative object poses. From these representations, our method estimates pairwise task-step-dependency probabilities and uses them to initialize the edge weights of a precedence graph. We then introduce a filtering pipeline that converts this graph of probability estimates into the final task dependency graph. We evaluate our approach on an existing benchmark and on a new dataset comprising longer tasks with more complex dependencies. We find that our method recovers more accurate task structures from fewer demonstrations than the baselines. Finally, we demonstrate that the inferred graphs can be used to generate multiple valid robotic execution orders for the same task.
I. INTRODUCTION
TaPeR addresses the challenge of recovering partially ordered manipulation tasks without requiring explicit symbolic predicate grounding. It combines kinematic and geometric observations into probabilistic precedence estimates, then filters them into task graphs that support reordered execution.
- Motivation: Imitation-learning methods often require demonstrations to execute every subtask in the same order, which becomes difficult for longer tasks.Fruit-salad preparation illustrates that some subtasks can be reordered while others must precede later actions.
- Background: Task Precedence Graphs represent mandatory precedence as paths in a DAG while leaving unconnected task steps independent.Prior work explicitly identifies independent subtasks and incorporates semantic information from action predicates.
- Approach: TaPeR reduces prerequisite supervision by using kinematic changes and relative object-pose distributions instead of explicit symbolic action predicates.The method derives precedence probabilities from these sub-symbolic observations and distills them into a precedence graph.
- Contributions: TaPeR fuses temporal, topological, and spatial evidence into pairwise precedence probabilities before constructing a sparse task precedence graph.Its graph pipeline is designed for few, reordered, and noisy demonstrations.
- Contributions: The paper evaluates TaPeR on an existing benchmark and introduces a dataset of longer, more complex manipulation tasks.The stated contributions include releasing the code and dataset upon acceptance.
II. RELATED WORK
Prior work models task ordering through precedence graphs, hierarchical structures, action graphs, or learned action prediction. TaPeR instead infers a probabilistic precedence graph from kinematic events and relative poses using few reordered demonstrations.
- Precedence modeling: Earlier approaches recover ordering from contact-relation transitions, visual action sequences, or manipulation-segment precedence graphs.These methods synthesize robot programs or infer independence from observed execution orders.
- Alternative structures: Hierarchical and action-graph methods represent interchangeable subtasks, sequential chains, or valid subsequences rather than TaPeR’s flat precedence structure.Other approaches learn task structure from large video corpora or instructional videos.
- TaPeR’s representation: TaPeR’s nodes are scene-kinematic changes occurring at single moments, rather than manipulation segments spanning time intervals.This representation enables pairwise precedence estimation without interval algebra over actions.
- TaPeR’s representation: TaPeR uses kinematic-graph membership and relative-pose distributions as supervision, avoiding a classifier for categorical spatial relations.It constructs precedence probabilistically from a few reordered, noisy demonstrations and explicitly resolves contradictory orderings.
- Problem formulation: The task abstraction is a DAG in which a path from si to sj means si must precede sj in every valid execution.Each step represents an object-control transition, either activation or deactivation.
- Method: TaPeR aggregates temporal, interaction, and spatial dependencies into path-probability estimates that guide pruning of a fully connected precedence graph.The objective is to preserve permissible temporal variation and spatial dependencies while maintaining manipulation semantics.
A. Trajectory Preprocessing and Step Extraction
TaPeR preprocesses demonstrations by converting evolving object-kinematic graphs into matched atomic events. These events identify task steps and provide pose observations that can be compared across demonstrations.
- Graph construction: The extractor identifies kinematic connections over time and decomposes each graph into manipulator-specific components plus a residual component.This produces a sequence of graph representations for the demonstrations.
- Event detection: An event is detected when a connected component increases in cardinality, with newly added objects treated as predicted objects and remaining members as landmarks.The event representation separates objects newly incorporated into a component from the objects already connected to it.
- Cross-demonstration matching: Topologically compatible events are matched across demonstrations using consistent object identities and a compatibility relation.Multiple candidate matches may exist within one demonstration, so the matching is not necessarily unique.
- Step representation: Each task step is associated with an event collection, possible cross-demonstration matches, and relative-pose observations between predicted and landmark objects.These observations support estimation of step-level pose distributions.
B. Temporal Dependency
TaPeR treats observed execution order as a soft probabilistic signal for pairwise precedence. A beta-binomial formulation estimates confidence from demonstrations in which both steps occur.
- Temporal evidence: For each pair of steps, TaPeR records which step appeared first in demonstrations where both steps co-occurred.The method compares both possible orders under a null hypothesis of no directional temporal preference.
- Probabilistic formulation: The temporal signal is a posterior probability Tij that si precedes sj, estimated with a beta conjugate prior.This soft prior grows in confidence as the number of observations increases.
- Comparison with prior temporal methods: TaPeR uses temporal evidence as one supervision signal rather than a hard discriminator or ordinal count with a confusion zone.The beta-prior formulation is presented as an alternative to those earlier temporal treatments.
C. Topological Dependency
TaPeR estimates topological and spatial dependencies between task steps from object activations, deactivations, interactions, and relative-pose distributions. These dependencies augment temporal evidence with geometric priors about which placements or landmarks constrain later steps.
- Topological dependence: Deactivation steps are constrained to follow activation steps whose predicted objects cover the deactivated objects.This prior permits multiple activations and joint deactivations rather than requiring identical object sets.
- Topological dependence: Tool-use dependencies arise when an activation step manipulates an object later required by another activation step.The relation is detected through overlap between the later step’s landmark objects and the earlier step’s predicted objects.
- Combining evidence: The resulting dependency probabilities regularize temporal precedence, preserving uncertainty when no object overlap supports a dependency.Background priors αD and αS are used when the corresponding topological or spatial dependency is not observed.
- Spatial dependence: Spatial dependence links deactivation steps when one places an object serving as a landmark for another step’s placement.The model uses predicted-object and landmark overlap rather than a binary temporal switch.
- Spatial dependence: Relative-pose distributions estimate landmark relevance, treating low covariance determinant as evidence of tighter spatial coupling.The method computes empirical relative-pose distributions across matched demonstrations and aggregates object–landmark covariance matrices.
E. Forming a Task Graph
TaPeR converts pairwise precedence probabilities into a sparse, stable task precedence graph through conflict resolution, direct-edge estimation, iterative pruning, cycle removal, and weight-aware reduction. The pipeline accounts for alternative execution paths and avoids arbitrary choices among similarly weak cycle edges.
- Resolving path conflicts: Contradictory execution orders produce opposing precedence probabilities that TaPeR resolves through contrastive normalization.For example, different demonstrations may place the pot or lid first, making both directions relevant but weaker.
- Deriving edge probabilities: Direct-edge probabilities estimate whether a precedence relation is immediate by discounting higher-probability intermediate paths of length 2 or 3.The method assumes an immediate predecessor has no intervening task step and approximates marginalization over alternative graphs.
- Graph processing pipeline: The graph pipeline starts fully connected, removes low-probability edges, cuts cycles using strongly connected components, and iterates until topology stabilizes.Cycle removal ranks edges using inverse probability and betweenness centrality, then considers equally capable edge-removal sets.
- Graph processing pipeline: Ordered contrastive pruning removes weak incoming edges in topological order, while later evaluations are affected by earlier removals.The pipeline normalizes incoming probabilities and applies the filter from roots toward leaves.
- Task-graph examples: The dataset examples include independent coffee-making steps whose shared delivery action depends on all three cups being completed.Other examples depict prerequisite tool pickup and sequential muffin transport stages.
- Graph processing pipeline: A limited transitive reduction removes a direct edge only when an indirect path offers at least as strong a weakest-edge probability.This yields a stable task precedence graph without discarding weight-supported direct connections.
V. EXPERIMENTAL EVALUATION
The evaluation compares semantic supervision with temporal supervision, examines individual signals and graph-processing stages, and extends an existing benchmark with longer, more complex manipulation tasks. Performance is measured primarily by graph edge-existence F1 because task-graph sparsity biases other metrics toward false negatives.
- Evaluation setup: TaPeR is evaluated against temporal baselines on both the HANDSOME benchmark and a newly introduced longer-task dataset.The evaluation also isolates the utility of individual supervision signals and graph-processing stages.
- Dataset: 8 new tasks contain sequences of up to 14 steps, averaging 9.6 steps per task, extending HANDSOME’s shorter and largely linear or independent tasks.The original dataset has 16 tasks with 25 demonstrations each, while the new tasks include transportation and longer pick-and-place sequences.
- Metrics: Graph edge-existence F1 is the primary quantitative metric because the inferred graphs are sparse and other metrics are heavily biased toward false negatives.Task models are generated from 2–7 sampled demonstrations and compared with ground-truth task graphs.
A. Comparison with Temporal Supervision
TaPeR’s semantic supervision is most valuable with few demonstrations and under execution bias, while temporal baselines are brittle to imbalanced observations. Its combined supervision improves over temporal signals, whereas individual signals can reduce quality.
- On HANDSOME-COMPLEX, semantic supervision performs best with 2–3 training demonstrations, after which the counterexample heuristic achieves higher scores and lower variance.
- Ordinal temporal supervision is brittle because it overcommits to imbalanced observations, while the β-prior performs better, especially with few samples.
- Execution bias harms all temporal methods, whereas semantic supervision declines only slightly.
- Matching noise negatively affects both TaPeR and counterexample-based supervision, with an approximately twofold performance gap between the methods.
- The combined supervision signal always improves over the temporal baseline, whereas individual signals reduce model quality.
B. Analysis of Method
The method analysis shows that TaPeR’s supervision signals are complementary rather than independently reliable, and that graph-processing stages contribute unevenly depending on graph connectivity. Annealing is beneficial mainly when paired with transitive reduction on highly connected graphs.
- Impact of supervision signals: Individual supervision signals often reduce F1-score, but their combined use always yields a significant improvement because they affect separate edge sets.Interaction dependence decays edges involving S+, while spatial dependence scores edges involving S−, so using either alone biases the graph toward unscored edges.
- Impact of graph processing stages: The evaluation measures F1-score after successive graph-processing stages, using the first two DAG-producing stages as the baseline.
- Impact of graph processing stages: Each graph-processing stage provides approximately equal improvements in graph quality.
- Impact of graph processing stages: Annealing alone reliably degrades quality, but followed by transitive reduction it gives the highest performance by a small margin and the lowest variance.
- Impact of graph processing stages: Annealing helps only when soft cycle removal leaves graphs highly connected and contrastive pruning cannot remove further edges in one iteration.
C. Robotic Validation
TaPeR’s inferred task models are integrated into a robotic execution system that samples permissible orders according to each task’s precedence constraints. The validation covers tasks ranging from strictly ordered to partially ordered and multi-stage workflows.
- Execution sampling produces different permissible orders because the three validation tasks have different degrees of order strictness.
- The tasks include a coffee cup visiting three strict stations, a shopping-bag cube visiting three shops arbitrarily, and three cups followed by tray transport to a goal.
- The robotic system drives executions by maximizing the probabilities of object poses given the current scene.Object poses are observed using Aruco markers, and relative end-effector–object poses are recorded at activation steps.
VI. DISCUSSION AND CONCLUSION
TaPeR extracts task precedence graphs from sub-symbolic object-pose observations and uses them to support dependency recovery with few or biased demonstrations. The inferred models also support sampling linear robotic executions, although they use contradictory observations less effectively than the baseline.
- TaPeR extracts Task Precedence Graphs from multiple demonstrations using sub-symbolic object-pose observations rather than only temporal or high-level symbolic features.
- The approach is especially useful with fewer than a handful of demonstrations or when demonstrators are biased in execution order.
- TaPeR’s supervision signals must be used together, and its graph-processing pipeline highlights the relative benefits of individual stages.
- The inferred models can sample linear robotic executions, but TaPeR does not capitalize as much on contradictory observations as its baseline.