Learning Action Models with Conditional and Quantified Effects via Uncertainty-Guided Exploration

Motivation

• Context-dependent outcomes and effects on nearby objects require expressive conditional and quantified action models, but their combinatorial hypothesis space limits scalability and noise robustness.Noisy state estimates can obscure the true action dynamics during deployment.Source: Introduction · p. 1
• Existing methods largely learn unconditional STRIPS effects or restrict learnable conditions to control the complexity of conditional-model learning.These restrictions limit applicability to complex environments.Source: Introduction · p. 1

OHCAM

• OHCAM maintains a belief over candidate models, uses soft consistency for noisy observations, and expands from simple hypotheses only when data support greater complexity.Branch-and-bound search avoids exhaustive reasoning over the combinatorial hypothesis space.Source: Introduction · p. 1
• OHCAM selects actions that maximize disagreement among plausible hypotheses, making exploration sample efficient.The approach actively gathers interactions that reduce uncertainty about competing models.Source: Introduction · p. 1

Evaluation

• Across six benchmark domains and two Kinova Gen3 tasks, OHCAM achieves higher task completion, improved sample efficiency, and practical online learning in noisy environments.The benchmark and hardware evaluations support its applicability beyond simulation.Source: Introduction · p. 1

Action Model Learning

• Most AML methods infer STRIPS models with unconditional effects restricted to action parameters, limiting representation of conditional behaviors and effects on additional objects.Logical induction can also eliminate the ground-truth formula after a single noisy observation.Source: Related Works · p. 2

Conditional and Quantified Effects

• Methods for conditional and quantified effects include deictic references, clustering, LAMP, and Conditional-SAM, but face permissive conditions, rapidly growing hypothesis spaces, or restrictions on quantified variables.The cited approaches trade expressiveness against tractability or noise robustness.Source: Related Works · p. 2

Capability Comparison

• Table 1 compares action-model learning approaches across capabilities required for real-world environments.The table is framed around capability comparison rather than a single performance metric.Source: Table 1 · p. 2

Online AML

• Online AML selects actions and incrementally updates models from observed outcomes, making sample-efficient active exploration important when executions are time consuming.Recent work distinguishes competing hypotheses through multi-step plans rather than purely myopic exploration.Source: Related Works · p. 2

Setting

• A planning domain consists of predicates describing object attributes and relations, parameterized actions, and action models specifying preconditions and effects.Preconditions determine applicability, while effects describe state changes.Source: Problem Formulation · p. 2
• The agent knows available macro-actions and their parameters but must learn how those actions affect the environment online.This setting reflects robotics scenarios where exact action consequences are unknown before deployment.Source: Problem Formulation · pp. 2–3

Conditional and Quantified Effects

• Conditional effects apply only when their context condition is satisfied, while quantified effects can influence objects outside the action parameters through universally quantified variables.Quantified effects apply to all objects satisfying the corresponding condition.Source: Problem Formulation · p. 3

Online Learning

• The learning objective is to infer action preconditions and effects from observed state transitions and success indicators using actively selected actions under budget B and noisy observations.The agent observes states before and after execution together with whether the action succeeded.Source: Problem Formulation · p. 3

Hypothesis Scoring

• OHCAM factorizes model learning into hypothesis sets for preconditions and potential effect literals, estimating each hypothesis from predicted versus observed state changes.Execution-literal comparisons yield true-positive, true-negative, false-positive, and false-negative counts.Source: Dynamic Hypothesis Expansion · p. 3
• A soft-consistency likelihood reduces but does not eliminate hypotheses after incorrect predictions, while a simplicity prior penalizes complex antecedents.The score balances predictive fit with model complexity.Source: Dynamic Hypothesis Expansion · p. 3

Search Challenge

• Finding the MAP hypothesis is difficult because candidate sets grow combinatorially with the number of literals and possible conditional effects.The computational challenge motivates structured search rather than exhaustive evaluation.Source: Dynamic Hypothesis Expansion · p. 3

Dynamic Hypothesis Expansion

• Dynamic expansion starts with simple hypotheses and incrementally adds antecedent literals using best-first branch-and-bound search.The search refines only hypotheses with sufficient potential to improve the current best score.Source: Dynamic Hypothesis Expansion · pp. 3–4

Belief-Guided Exploration

• In the blocks example, OHCAM selects actions with high predictive disagreement, shifts posterior weight after observations, and replaces a hypothesis with a more complex one to preserve diversity.The figure illustrates belief updates and adaptive hypothesis expansion during interaction.Source: Figure 2 · p. 4

Dynamic Hypothesis Expansion

• Admissible upper bounds prioritize refinements that could surpass the current best hypothesis, and termination occurs when no frontier bound exceeds that score.This procedure returns a MAP hypothesis while controlling explored candidates.Source: Dynamic Hypothesis Expansion · p. 4
• Restricting refinement literals to those with promising score bounds and sufficient true negatives reduces branching relative to considering every bound literal.The refinement set contains literals that plausibly correlate with the effect and offset the simplicity penalty.Source: Dynamic Hypothesis Expansion · p. 4

• Trajectory rollouts are imagined as part of the procedure.Source: §4 · p. 4
• The rollout process connects imagined trajectories to an action-selection step.Source: §4 · p. 4
• The procedure selects the first action of the best rollout.Source: §4 · p. 4

Dynamic quantified hypotheses

• Quantified effects explain impacts on objects outside action parameters using universally quantified variables and locality relationships.Affected objects are connected to action-parameter objects through observed state relationships.Source: Quantified Effects · pp. 4–5
• OHCAM forms candidate UQV sets from state-graph trees connecting affected objects to action-parameter objects, starting with the simplest trees.Tree nodes become UQVs and edges become antecedent conditions.Source: Figure 3 · p. 5, Quantified Effects · p. 5

Dynamic hypothesis expansion

• The simplicity prior penalizes hypotheses with more conditions and UQVs, while dynamic expansion adds complexity only when existing hypotheses cannot explain effects.The quantified-hypothesis prior includes a penalty factor β^|Q| for additional UQVs.Source: Quantified Effects · p. 5

Belief-guided exploration

• BALD selects actions expected to reduce posterior uncertainty by maximizing disagreement among plausible hypotheses.Disagreement may concern action applicability or the resulting state and effects.Source: Belief-Guided Exploration · p. 5
• The exploration utility accounts for applicability uncertainty because effects are observed only when actions execute successfully.Predictive entropy decomposes into uncertainty about applicability and individual effects.Source: Belief-Guided Exploration · p. 5

Online learning

• OHCAM scores receding-horizon imagined rollouts by cumulative information gain, executes the selected action, and reweights or expands hypotheses until budget B is exhausted.The final output is the MAP action model M′.Source: Belief-Guided Exploration · pp. 5–6

• OHCAM is evaluated on six benchmark planning domains and two real-world tasks using a Kinova Gen3 robot.Source: Experiment Setup · p. 6

Baselines

• The baselines include offline learners of conditional and quantified effects and OLAM, an online active learner limited to STRIPS effects.Conditional-SAM is evaluated with three maximum antecedents and ground-truth UQV type.Source: Experiment Setup · p. 6

Data collection

• Three data regimens are compared: OHCAM-collected active data, uniformly random actions, and expert demonstrations with 20% random actions.Source: Experiment Setup · p. 6

Domains

• The simulation domains are Satellite, Briefcase, Miconic, Maintenance, CityCar, and Nurikabe; two additional domains support hardware evaluation.Source: Experiment Setup · p. 6

Training and evaluation

• Each domain uses ten training and ten harder evaluation problems, and every method receives up to one hour for learning.Evaluation problems contain more objects or longer plans.Source: Experiment Setup · p. 6

Metrics

• Task completion rate measures the average fraction of evaluation tasks solved by open-loop plans without failed actions, while sample efficiency is evaluated at 10-action intervals.Offline methods are evaluated on increasing data subsets.Source: Experiment Setup · p. 6

Task completion

• >95% of tasks were completed by OHCAM on five of six domains, whereas the next-best approach reached that level on only two domains with expert data.OHCAM consistently performed better than or similarly to the baselines.Source: Simulation Results and Discussion · p. 6
• Conditional-SAM learned overly restrictive conditions in larger domains because its strict safety threshold required more data than the budget allowed.Source: Simulation Results and Discussion · p. 6
• LAMP often exceeded the one-hour training limit because it exhaustively enumerated hypotheses.Source: Simulation Results and Discussion · p. 6
• Cluster&Intersect failed to generalize to additional evaluation objects because it learned an action for each training-observed object combination.Source: Simulation Results and Discussion · p. 6

Sample efficiency

• Within 100 actions, OHCAM trained on its actively collected data recovered expert-demonstration performance without prior domain knowledge.OHCAM-collected data also enabled higher problem-solving rates for other baselines than random data.Source: Simulation Results and Discussion · p. 6

Robustness to noise

• With noise increasing from zero to 40%, OHCAM degraded gracefully, while baselines declined sharply; under 10% noise, its simplicity prior prevented false effects.OHCAM-collected data was more robust to noise than expert data.Source: Simulation Results and Discussion · p. 7

Hardware and setup

• The setup uses a Kinova Gen3 7 DoF arm and an Intel RealSense D435i camera for tabletop manipulation.Actions are implemented as manipulation skills parameterized by object locations.Source: Robot Hardware Results · p. 7

Evaluation

• Figure 6 reports task completion rates across 10 MagnetBlocks evaluation tasks and five SpongeWorld tasks.The figure also shows example start and goal configurations.Source: Robot Hardware Results · p. 7, Figure 6 · p. 7

Results

• OHCAM solves all evaluation tasks in both domains using online-collected data despite perception noise.The baselines fail because they cannot address noise in the data.Source: Robot Hardware Results · p. 7
• The naïve model without conditional effects solves only 20% of MagnetBlocks tasks and 40% of SpongeWorld tasks.In MagnetBlocks, the baselines learn a model incapable of finding a plan for any task.Source: Robot Hardware Results · p. 7

Conclusion

• OHCAM combines dynamic hypothesis expansion and belief-guided exploration to learn expressive action models from limited interactions under noisy observations.The framework targets conditional effects and quantified variables.Source: Conclusion · p. 7
• Experiments on benchmark planning domains and a Kinova Gen3 robot report higher sample efficiency and downstream planning performance than state-of-the-art baselines.The evaluation spans both simulated planning domains and physical robot tasks.Source: Conclusion · p. 7
• Future work will address partially observable settings and scaling OHCAM to larger relational domains.Source: Conclusion · p. 7

MAP correctness

• Dynamic hypothesis expansion returns a MAP hypothesis under a finite literal set and best-first branch-and-bound search.The proof shows the MAP hypothesis remains refinable, is eventually generated, and is preserved by the termination criterion.Source: Appendix A · p. 9

Search bounds

• The search automatically bounds generated hypothesis depth by the MAP hypothesis rather than a predefined maximum-depth hyperparameter.Only hypotheses with potential exceeding the current best score are refined, and refinement can be restricted to a thresholded literal set.Source: Appendix A · p. 9
• The complexity-to-noise ratio ζ represents the minimum prediction errors that must be eliminated to justify adding one literal.The proof uses ζ to show that removing a MAP-condition literal decreases true negatives sufficiently for that literal to remain in the refinement set.Source: Appendix A · p. 9

Noiseless complexity bound

• In the noiseless case, the MAP hypothesis complexity satisfies |Cmap| ≤ |C∗|, so generated hypotheses have depth no greater than the true conditional effect.Thus dynamic expansion does not search beyond the complexity of the simplest true effect that perfectly predicts the environment.Source: Appendix A · p. 10

Likelihood and prior

• The simplicity prior α and noise parameter ϵ jointly control how conditional hypotheses are penalized and how missed predictions are tolerated.The paper sets α = 0.1 for sparse conditional effects and uses ϵ = 0.1 for hardware experiments, corresponding to 11% noise.Source: Appendix B.1 · p. 10

Predictive power

• Predictive power measures how accurately learned models predict action applicability and effects, complementing task success evaluation.Applicability and effect precision and recall are averaged over applicable states and actions.Source: Appendix B.2 · p. 11
• Cluster&Intersect could not be reliably evaluated because non-mutually-exclusive action branches let planners choose among outcomes, unlike the deterministic environment.Conditional-SAM also timed out on multiple domains despite predicting 100% of the evaluation dataset, because its quantified preconditions were complex.Source: Appendix B.2 · p. 11

Number of hypotheses expanded

• OHCAM expands hypotheses according to the true conditional-effect depth instead of enumerating every hypothesis up to a fixed antecedent depth.The analysis motivates minimizing hypothesis enumeration as domains and effect complexity increase.Source: Appendix B.2 · p. 11
• 637 thousand hypotheses were generated by Conditional-SAM at d = 3 on Nurikabe, while OHCAM generated fewer hypotheses than Conditional-SAM in every domain.OHCAM learned a depth-3 conditional effect on Nurikabe while still producing fewer hypotheses than Conditional-SAM at d = 1.Source: Appendix B.2 · p. 11, Figure 7 · p. 12

Benchmark domains

• The benchmark suite spans six domains with varying action, predicate, conditional-effect, and quantified-effect complexity.The domains are Satellite, Briefcase, Miconic, Maintenance, CityCar, and Nurikabe.Source: Appendix C.2 · p. 12
• CityCar was the most challenging domain because a quantified effect required a rare interaction involving a destroyed road and a car on it.The analysis also observed that overly complex preconditions affected task completion.Source: Appendix C.2 · p. 12

Noise considerations

• Robot-collected data contained perception and execution noise, including object misidentification, depth-map errors, and occasional sponge slippage.These observations required the learning algorithms to distinguish noise from genuine conditional effects; approximately 5% of action failures during data collection resulted from perception noise.Source: Appendix D.1 · p. 15

Data Collection

• All hardware experiments used a human supervisor because irreversible conditional effects could apply unsafe torque to the robot.One example is placing a block over another with a magnet block between them.Source: Appendix D.2 · p. 15
• 250 skill executions were collected in each of MagnetBlocks and SpongeWorld, with data collection taking approximately 45 minutes to 1.25 hours.Most time was spent executing skills and resetting the environment rather than selecting actions.Source: Appendix D.2 · p. 15

Robot Evaluation

• Learned PDDL models were evaluated with Fast Downward on ten MagnetBlocks tasks and five SpongeWorld tasks.Seven MagnetBlocks tasks and four SpongeWorld tasks required knowledge of conditional effects.Source: Appendix D.2 · p. 15
• Each task was run once per learned model, with reruns only when perception or execution noise caused failure.The evaluation targeted online learning under noisy observations and sample efficiency, rather than robot execution accuracy.Source: Appendix D.2 · p. 15