TaPeR: Probabilistic Recovery of Sparse Task Precedence Graphs from a Handful of Demonstrations

Adrian Röfer; Karla Stepanova; Abhinav Valada

cs.ROAug 21, 2026

TaPeR: Probabilistic Recovery of Sparse Task Precedence Graphs from a Handful of Demonstrations

Authors: Adrian Röfer, Karla Stepanova, Abhinav Valada

Organizations: Department of Computer Science, University of Freiburg, Germany · Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University, Czech Republic

Abstract

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.

Figures & tables

Fig. 1: TaPeR identifies independent subtasks in a demonstrated task based on atomic steps identified by an extractor that derives manipulation graphs from demonstrations. TaPeR takes these steps, which represent actions such as picking up a tray , and extracts three supervision signals from their grouped observations across multiple demonstrations, which are integrated into precedence probabilities. These serve as edge weights in an initially fully connected graph, which is iteratively reduced to yield a task precedence graph (TPG). From this graph, we can synthesize multiple possible execution sequences of the task and deploy them on a real robot.

Fig. 2: Graphical Depiction of the stochastic cycle removal and ordered contrastive pruning . Left : The graph contains a cycle, with its SCC highlighted in blue, edge thickness indicates weight. Cutting any of the edges between the blue nodes would resolve the cycle. The diagonal edges are equally weak. Our algorithm removes both of them instead of arbitrarily cutting just one. Right : The nodes are traversed by their depth in the DAG, indicated by their number in the figure. As the edge

(1b,2)

is weaker than

(1a,2)

, it is removed. This removal blocks the subsequent evaluation of

(1b,3)

, without re-evaluation of the successor probabilities for

1b

Panel of Figure 3 — Fig. 3: Qualitative impression of HANDSOME-COMPLEX tasks. Top: Moving sausages onto the lower grill using tongs. Picking up the tongs is a prerequisite for manipulating the sausages. Middle: Making and delivering muffins. The muffin cups are moved to a baking tray, which is then placed in an oven. After removal from the oven, the muffin cups are moved to a tray, which is moved to a delivery location. Bottom: Making three coffees and delivering them on a tray. The order of coffee making is independent, but the tray’s movement depends on all three cups being made.

Fig. 4: We compare our method against pure temporal supervision across the HANDSOME [ 13 ] dataset and our HANDSOME-COMPLEX (HC) extension. We uniformly sample 2-7 demonstrations for a task and use their matched events for our method, pure temporal observation, and the counterexample-based method proposed in [ 11 ] . We report the F1-score over edge predictions in the final TPG. We find that our Semantic supervision performs best in the settings with few demonstrations, where temporal evidence is sparse. While the counterexample becomes the strongest in HC, we note that this is not the case in HANDSOME. We can reproduce the same pattern by sampling demos in HC with a preference towards one particular execution order. Semantic supervision can ignore this bias, while all temporal methods decline. Across all datasets and demo counts, we find our

\beta

-prior to be better than an ordinal temporal signal. We use [ 11 ] as temporal prior for its late model improvement, but find the effect to be slightly negative.

		Event Mismatch Chance
Dataset	Config	$0\%$	$5\%$	$10\%$	$20\%$	$30\%$
HANDSOME- COMPLEX	TaPeR	0.95	-0.01	-0.03	-0.05	-0.07
HANDSOME- COMPLEX	Counter- Example	0.95	-0.02	-0.07	-0.15	-0.20
HANDSOME- COMPLEX- BIASED	TaPeR	0.92	-0.00	-0.02	-0.04	-0.06
HANDSOME- COMPLEX- BIASED	Counter- Example	0.82	-0.01	-0.04	-0.10	-0.14
HANDSOME	TaPeR	0.99	-0.00	-0.00	-0.00	-0.01

TABLE I: We measure the impact of events being matched wrongly across demonstrations. We report the F1-score for edge predictions with a perfect event match and the delta from this baseline across different noise levels. While both our method and the counterexample-based supervision from [ 11 ] are negatively impacted by matching noise, we observe a wide gap (

\approx 2x

) between the two methods.

Dataset	Config	2	3	5	7
HANDSOME- COMPLEX	Topological ( $D_{ij}$ )	-3.6%	-3.7%	-2.6%	-1.7%
	Spatial ( $S_{ij}$ )	-3.8%	-3.4%	-2.5%	-1.4%
	Combined	4.3 %	0.8 %	2.5 %	3.5 %
HANDSOME- COMPLEX- BIASED	Topological ( $D_{ij}$ )	-1.5%	1.0%	0.9%	-0.9%
	Spatial ( $S_{ij}$ )	-1.5%	-0.8%	2.6%	3.0%
	Combined	11.3 %	10.9 %	14.0 %	13.3 %

TABLE II: Relative improvement of individual TaPeR’s supervision signals over temporal signal. Values are reported as percentage change in F1-score produced by the temporal baseline. The combined signal always yields an improvement, whereas the individual signals reduce model quality.

	Dataset
Pipeline Stages	H-C	H-CB	H
Low probabilities +Cycle removal	0.81	0.76	0.99
+Contrastive Pruning	+0.10	+0.11	+0.00
+Transitive Reduction	+0.13	0.15	+0.00
+Annealing	-0.02	-0.00	-0.01
+Annealing +Transitive Reduction	+0.14	0.16	+0.00

TABLE III: We study the impact of our different pipeline stages on model quality. We report the F1-scores for the first two stages required to obtain a DAG from the initial model. For each consecutive stage, we report its delta to the previous one.

Panel of Figure 8 — Fig. 5: We pick three tasks from our datasets and use the extracted model to drive a robotic execution. The strictness of possible execution orders varies by task, so our execution sampling produces different permissible orders. Top : The robot has to move a coffee cup through three strict stations. Middle : The robot has to move a cube symbolizing a shopping bag to three shops in an arbitrary order. Bottom : The robot has to move three coffee cups to the coffee machine and then to a tray. Finally, the tray is pushed towards a goal location.

Learning from Demonstration

Learning from Demonstration teaches agents and robots new behaviors by extracting actions, goals, and task structure from examples.

See all 145 papers

SparTa: Sparse Graphical Task Models from a Handful of Demonstrations
Feb 18, 2026Adrian Röfer, Nick Heppert, Abhinav ValadaRobot Learning Learning from Demonstration
University of Freiburg, Germany · Zuse School ELIZA
Semantic-Geometric Task Representations for Bimanual Manipulation from Human Demonstrations to Robot Action Planning
Jan 16, 2026Franziska Herbert, Vignesh Prasad, Han Liu +2Bimanual Robotic Manipulation Object-Centric Representation Learning
Interactive Robot Perception & Learning (PEARL) Lab, Computer Science Dept., TU Darmstadt, Germany. · Hessian.AI, Darmstadt, Germany. · Robotics Institute Germany (RIG). +2
Knowledge-Guided Manipulation Using Multi-Task Reinforcement Learning
Mar 25, 2026Aditya Narendra, Mukhammadrizo Maribjonov, Dmitry Makarov +2Robotic Manipulation Multi-Task Robotic Manipulation
MIRAI, Moscow, Russia and MBZUAI, Abu Dhabi, UAE · MIRAI, Moscow, Russia and Innopolis University, Russia · MIRAI, Moscow, Russia +1

Feb 18, 2026J/K move · Enter open · S save

SparTa: Sparse Graphical Task Models from a Handful of Demonstrations

Adrian Röfer, Nick Heppert, Abhinav Valada

University of Freiburg, Germany · Zuse School ELIZA

Robot Learning Learning from Demonstration Long-Horizon Robotic Manipulation Data-Efficient Robot Learning Graph Representation Learning

Open paper AskPDF arXiv

Learning long-horizon manipulation tasks efficiently is a central challenge in robot learning from demonstration. Unlike recent endeavors that focus on directly learning the task in the action domain, we focus on inferring what the robot should achieve in the task, rather than how to do so. To this end, we represent evolving scene states using a series of graphical object relationships. We propose a demonstration segmentation and pooling approach that extracts a series of manipulation graphs and estimates distributions over object states across task phases. In contrast to prior graph-based methods that capture only partial interactions or short temporal windows, our approach captures complete object interactions spanning from the onset of control to the end of the manipulation. To improve robustness when learning from multiple demonstrations, we additionally perform object matching using pre-trained visual features. In extensive experiments, we evaluate our method's demonstration segmentation accuracy and the utility of learning from multiple demonstrations for finding a desired minimal task model. Finally, we deploy the fitted models both in simulation and on a real robot, demonstrating that the resulting task representations support reliable execution across environments.

Abstract

Learning from Demonstration

Explore similar work

SparTa: Sparse Graphical Task Models from a Handful of Demonstrations

Semantic-Geometric Task Representations for Bimanual Manipulation from Human Demonstrations to Robot Action Planning

Knowledge-Guided Manipulation Using Multi-Task Reinforcement Learning