When a person shows a planning agent one way to solve a task, the agent can in principle learn a reusable recipe from that single example. It does this by explaining why each step was needed (which earlier step set up the condition a later step relies on) and then throwing away every detail the explanation does not use. Classical work showed how to do this soundly for plans whose steps can be reordered. The catch is that it only works if the agent's model of what actions require and cause is complete and correct. Real models are rarely either. Current systems respond in one of three ways. They give up on generalizing the unexplained step and memorize it verbatim. They repair the model through many rounds of trial and error. Or they use the incomplete model only to guess an observed agent's goal. None of them uses the one demonstration it has to fill the holes in the model and produce a safe, reusable recipe in the same step.
We propose to do both from one demonstration. The agent finds the smallest set of guesses about missing action requirements and effects that would make the demonstration fully explainable. It then generalizes the plan into an order-flexible template. Every causal link in the template is labelled as either known or assumed. Wherever an unknown side effect could undo a needed condition, the template adds a conservative ordering constraint. The claim to be tested is concrete: under 20–80% model incompleteness, these labelled templates should transfer to new problem instances with far fewer silent execution failures than memorizing the unexplained steps. They should also beat a language-model-repair-then-generalize pipeline that ignores what the demonstration itself rules out.
Core Claim
The relevant existing pieces do not talk to each other. Explanation-Based Generalization of Partially Ordered Plans supplies the method. Its algorithms, EXP-MTC and EXP-GEN, use Chapman's Modal Truth Criterion, a test that checks whether a condition is guaranteed to hold at a step in every possible ordering of a plan. From one example they extract every producer–consumer link and every "protection interval" (a span during which a condition must not be deleted), and they do this in $O(n^3)$ time. The resulting template is valid under every ordering of its steps, but only if the action model is complete. Any missing precondition or effect makes the algorithms fail or produce templates that look safe but are not.
Goal Recognition in Incomplete Domain Models and Landmark-Enhanced Heuristics for Goal Recognition in Incomplete Domain Models motivate the setting. They represent incompleteness explicitly, marking preconditions and effects as "possible," and they reason optimistically over them. They show that observed actions reveal "overlooked" bottleneck conditions even when 80% of the model is missing. However, they only recognize goals and never build reusable plans.
Our claim is that the epistemic labels from the second line of work can be carried directly into the truth criterion of the first. A causal link supported only by a possible effect becomes an assumed link. A possible delete effect that lies between a producer and its consumer becomes a possible threat. The template generalizer must then choose between two responses to each possible threat: order the threatening step out of the way, which is safe but less general, or leave it unordered, which is more general but risks failure. That choice is the new technical object. Model repair and template generalization come out of the same single demonstration.
Research Program
The input is a symbolic action model $M$ in a STRIPS-like language with some preconditions and effects marked "possible" and others simply absent. It also includes one demonstrated plan $\pi$ with the observed state before and after each step.
The first stage is minimal abduction. We look for the smallest set $A$ of assumed precondition and effect additions under which the demonstration is fully explained:
$$A^* = \arg\min_{A \subseteq \mathcal{C}(\pi)} |A| \quad \text{s.t. every precondition and goal in } \pi \text{ has an MTC-valid producer under } M \cup A,$$
Here $\mathcal{C}(\pi)$ is a candidate pool. It consists of possible annotations already in $M$, plus new candidates read off observed state changes: a fact that changed across a step with no modelled cause is a candidate effect of that step. The demonstration also prunes candidates. An effect cannot be a delete if the fact visibly persisted. A precondition cannot be required if it was observably false when the step ran. The second kind of pruning is what separates this approach from unconstrained repair. Candidates from a language model can be added to $\mathcal{C}(\pi)$, but each one must pass these consistency checks before it can enter $A$.
The second stage is labelled generalization. We run EXP-GEN over $M \cup A^*$, tagging each causal link as known (supported by a definite effect) or assumed (supported by an element of $A^*$). Each possible delete effect that falls inside a protection interval gets one of two policies. In the conservative policy we add an ordering constraint that keeps it outside the interval. In the optimistic policy we leave it unordered but attach a runtime check before the consumer step.
The third stage, which is optional, is one-failure refinement. If the template later fails on a new instance, the failing step pins down a single assumed link or unguarded threat to retract or confirm. This mirrors how Constructing and Refining Causal Explanations from an Inconsistent Domain Theory refines by layers. The difference is that the new requirement is abduced from observation rather than looked up in a hand-written deeper layer, so the method does not fail when the hand-written layers run out (what that paper calls "bottoming out").
The analysis question is how generality trades against soundness as incompleteness grows. We will also characterize when the minimal abduction is unique and when the demonstration leaves real ambiguity. Ambiguous cases should be flagged rather than silently resolved.
Baselines
The naive reference point is rote replay: re-execute the demonstrated action sequence with objects substituted by type. This is the floor any generalization method must clear on new instances.
The closest one-trial competitor is memorization fallback as in Interactively Learning a Blend of Goal-Based and Procedural Tasks. The Rosie agent applies explanation-based generalization where its model explains a step and compiles an ungeneralized procedural step where it cannot. We reimplement this policy on top of EXP-GEN in the same STRIPS setting, so the two systems differ only in how they treat unexplained steps. Beating it means more transfer across reorderings and new object layouts at equal or lower failure rates.
The strongest repair-based competitor is a repair-then-generalize pipeline built on CLIMB. CLIMB uses GPT-4o to propose missing predicates after execution failures and reports BlocksWorld success rising from 40% after initial model generation to 80% after iterative failure feedback, compared with 12% for direct language-model planning. We give the same language model the same incomplete model and the single demonstration, let it propose a completed model in one shot, and then run EXP-GEN on that model unchanged. The pipeline gets the same language-model calls and the same compute as our candidate-generation step. Beating it means fewer unsound templates at matched coverage. The 80% figure is not directly comparable to our metric, because it uses multiple feedback trials and measures planning success rather than template transfer. We will report both systems on our protocol.
The strongest planner-only reference is replanning from scratch on each new instance. We use FastDownward over the optimistic model, and we also run the GPT-4 prompting method of LLMs Can Plan Only If We Tell Them, which reports 82% accuracy on Blocksworld and 80% on Logistics, against 14% for vanilla GPT-4 on Logistics.
Two ablations isolate the key ingredients. The first removes the demonstration-consistency pruning, so abduction draws from an unfiltered candidate pool. The second removes the known/assumed labelling and treats every abduced element as certain, which tests whether threat handling, rather than repair alone, drives safety.
Why not just…?
Why not just have a language model complete the model and then run the classical generalizer? This is the most serious threat, and it is a baseline above. Its weakness is that a language model's completion is not constrained by what the demonstration showed. The DecoVer study (DecoVer) documents that language-model formalizers omit steps and make causally inconsistent rules, and that errors in the restrictions they generate go uncaught and cause outright "No Solution" failures. An over-strong invented precondition makes the template apply less often. A missing delete effect makes it unsound. The pruning ablation directly measures how much the demonstration's evidence adds. If the gap is negligible, our contribution narrows to the threat labelling, and we will report that.
Why not just memorize unexplained steps? Memorized steps do not generalize to new objects or orderings, as Interactively Learning a Blend of Goal-Based and Procedural Tasks acknowledges. Totally ordered fragments embedded in a partially ordered plan can also be undone by reordered neighbours, the failure mode Explanation-Based Generalization of Partially Ordered Plans was built to prevent. The memorization baseline quantifies this cost.
Why not just replan on every new instance? Replanning avoids templates entirely. Over an incomplete model, however, the planner relies on the same missing facts, so it can produce plans that look valid but fail on execution. Language-model planners still fail on about a fifth of deterministic Blocksworld and Logistics problems (LLMs Can Plan Only If We Tell Them). Replanning also discards the repair the demonstration provided. We report replanning success and cost against template instantiation on identical instances.
Proposed Experiments
The main testbed reuses the controlled-incompleteness protocol of Goal Recognition in Incomplete Domain Models: 15 standard planning-competition domains, including ROVERS, LOGISTICS and SOKOBAN, with 20%, 40%, 60% and 80% of preconditions and effects removed or downgraded to "possible." Those papers report recognition latency of at most 2.7 seconds but give no plan-generalization numbers; no reported result found on Lacuna for template transfer under this protocol.
For each domain and goal type we take one demonstrated plan and generalize it. We then instantiate the template on 50 held-out problems and execute it in the true, complete domain under randomly sampled orderings consistent with the template. The metrics are four:
- Coverage: the fraction of held-out instances to which the template applies.
- Sound-execution rate: the fraction of executions that achieve the goal.
- Silent-failure rate: executions in which the template applied but failed. This is the safety metric.
- Abduction accuracy: precision and recall of $A^*$ against the removed ground-truth model elements.
A second testbed uses CLIMB's BlocksWorld, Grippers, Heavy and BlocksWorld++ domains with the Blocks World 4-block problem from Explanation-Based Generalization of Partially Ordered Plans as a sanity case. Here we add the one-failure refinement stage and count how many executions are needed to reach a sound template, compared with CLIMB's multi-trial repair loop.
Three checks will decide the outcome. First, at 60–80% incompleteness our silent-failure rate should sit well below both memorization fallback and repair-then-generalize at matched coverage. If it does not, the labelling adds nothing. Second, abduction recall should degrade gracefully as incompleteness rises, because observed state changes keep supplying candidates. A collapse to the language model's prior would mean the demonstration is not doing the work. Third, the conservative policy should trade measurable coverage for near-zero silent failures, and the optimistic-with-checks policy should recover most of that coverage. If the two policies are indistinguishable, possible threats rarely matter in practice, and the threat-handling part of the proposal should be dropped.
References
- Explanation-Based Generalization of Partially Ordered Plans
- Goal Recognition in Incomplete Domain Models
- Landmark-Enhanced Heuristics for Goal Recognition in Incomplete Domain Models
- Constructing and Refining Causal Explanations from an Inconsistent Domain Theory
- Interactively Learning a Blend of Goal-Based and Procedural Tasks
- CLIMB: Language-Guided Continual Learning for Task Planning with Iterative Model Building
- LLMs Can Plan Only If We Tell Them
- DecoVer: A Decompose-and-Verify Neuro-Symbolic Framework for Embodied Task Planning with BC+