PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Symbolic Models of Stochastic Domains

L. P. Kaelbling, H. M. Pasula, L. S. Zettlemoyer

arXiv:1110.2211v1cs.LGcs.AI

TL;DR

The paper asks how agents can learn compact action-dynamics models for complex, noisy worlds without hand-crafted models. It develops a probabilistic relational rule representation and learning algorithm, then evaluates them through planning in simple domains and a physically simulated blocks world. The results show effective learned modeling, while the approach remains limited by planning difficulty and scalability to more complex domains.

  • Problem

    Agents need models of complex, nondeterministic world dynamics, but hand-crafting accurate relational models is difficult, especially with numeric parameters.

  • Method

    The paper learns probabilistic relational planning rules, including structure, parameters, noise effects, and derived relational concepts, from example action executions.

  • Results

    The learning algorithm effectively learns models usable for planning in simple domains and a physically simulated blocks world.

  • Takeaways & Limitations

    A probabilistic action-model representation can compactly describe action effects in a physically simulated blocks world as a step toward learning in more complex worlds.

  • Takeaways & Limitations

    The approach does not solve hard combinatorial planning problems and is expected to become prohibitively expensive as domains grow more complex.

Abstract

from arXiv · show

In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.

1. Introduction

The paper targets agents that act in complex, noisy environments by learning compact models of action effects rather than relying on hand-crafted dynamics. It develops and evaluates a probabilistic, relational approach in planning domains and a realistic simulated blocks world.

  • Motivation: Agents need world models because everyday object-manipulation tasks have variable, sometimes unreliable physical effects.Examples include piles slipping, drawers sticking, and objects usually remaining intact when moved in boxes.
  • Approach: The paper learns probabilistic, relational action-effect rules from supervised action executions.Learning jointly selects model structure, parameters, and newly defined relational concepts using likelihood and complexity.
  • Evaluation setting: The simulated blocks world introduces varying block sizes and colours, untidy piles, possible toppling, and an unreliable gripper.These properties require models to handle noisy, nondeterministic effects and nontrivial dynamics.
  • Evaluation setting: The paper uses a three-dimensional rigid-body simulator as a less-idealized planning domain than traditional neatly stacked blocks worlds.It presents the domain as a simplified proxy for more complex real-world activity.
  • Validation: The learned models are validated by planning with them and demonstrating their utility in the tested domains.The paper describes planning and empirical validation as subsequent steps after developing the modeling language and learning algorithm.

2. Structured Stochastic Worlds

The paper adapts probabilistic first-order dynamics representations for realistic domains by adding references to indirectly affected objects, explicit noise, and learnable relational concepts. These extensions address stochastic effects and representation limits that arise in a physical blocks world.

  • Structured stochastic worlds: Traditional first-order representations compactly generalize action effects over object identities, but realistic domains require additional uncertainty and complexity.The paper takes probabilistic first-order world-dynamics representations as its starting point.
  • Action parameterization: Deictic references let rules identify affected objects that are absent from an action’s parameter list.This avoids varying the number of action arguments when an action can affect different sets of objects.
  • Modeling noise: Noise outcomes allow models to represent unmodeled changes and unusual physical effects, including outcomes that violate a small-outcome assumption.The mechanism is intended for complex domains where actions may have varied effects.
  • Language extension: The language supports complex quantification and construction of new concepts beyond predefined observable predicates.In the blocks world, concepts such as height can be defined from on, supporting rules about toppling and non-clear pickups.
  • Language extension: Hand-engineering useful predicates for each new problem is difficult, time consuming, and error prone, motivating concept learning.The paper reports that traditional blocks-world predicates alone were insufficient for its noisier setting.

3. State and Action Representation

The representation describes fully observable world states and actions in a first-order logical vocabulary, using constants, predicates, and functions. It supports intrinsic or arbitrary object identifiers and grounds representations during learning, inference, and planning.

  • Core representation: States encode configurations of object properties and relations, while actions are positive literals over predicates and world-associated constants.The representation is grounded during inference, learning, and planning.
  • Core representation: The primitive language contains constants, predicates, and traditional, discrete-valued, and integer-valued functions.The paper assumes these primitives are directly observable in a completely observable environment.
  • Object identification: The formalism currently permits any number of objects in a configuration but cannot model object creation or deletion through dynamics.This is an explicit scope boundary of the state representation.
  • State representation: State descriptions are conjunctive specifications listing truth values or function assignments for all possible groundings.Arity determines argument-list length, predicates may be negated, and functions may take values in their ranges.
  • Object identification: Intrinsic constants consistently identify particular objects, whereas Skolem constants are arbitrary identifiers without inherent meaning.Skolem constants are useful when perception cannot assign meaningful object identities.
  • Object identification: The techniques apply to both intrinsic and Skolem constants, while Skolem constants require stronger abstraction from object identity and may improve learned-model quality.The paper presents this as both a perceptual motivation and a consequence for learning algorithms.

4. World Dynamics Representation

The paper represents probabilistic transition dynamics with relational rules that generalize across objects, model multiple outcomes, and extend to deictic references and noise. These extensions support partial modeling of complex stochastic worlds while preserving useful planning behavior.

  • Probabilistic Dynamics: Probabilistic rules represent Pr(s′|s, a) through relational variables, action contexts, and multiple possible successor-state outcomes with associated probabilities.Logical variables abstract object identities, while each outcome constructs a possible next state.
  • Rule Semantics: Mutually exclusive rule contexts ensure that each state-action pair is covered by at most one rule; otherwise the state remains unchanged with probability 1.0.This avoids conflicting rule predictions and supplies a default transition when no rule applies.
  • Deictic Reference: Deictic references let rules constrain objects affected by an action without requiring every such object to appear in the action’s argument list.Standard representations add arguments merely to bind changed objects, which can create many rejected ground action instances during planning.
  • Partial Models: The representation can use a partial model that ignores unlikely or overly complex transitions while still learning and acting effectively.The probability model remains well-defined only when pmin times the number of possible states does not exceed 1.0.
  • Adding Noise: Noise outcomes extend rules to model unusual physical effects, including changes that violate the assumption that actions have only a small number of simple effects.A default noise rule can assign background noise when no specific rule applies.
  • Action Models: Action models combine concept definitions with rule sets, and restricting learned models to exclude constants can improve generalization with small training sets.The paper discusses both intrinsic and skolem constants and uses restrictions as a useful learning bias.

5. Learning Action Models

The learning algorithm searches for an action model that explains observed state-action transitions, jointly addressing rule construction and discovery of useful concept predicates.

  • Learning Objective: The algorithm learns an action model from training examples represented as (s, a, s′) triples by maximizing the likelihood of observed action effects while penalizing complexity.This objective favors models that explain the examples without unnecessary representational complexity.
  • Learning Procedure: Learning separates rule-set construction from concept discovery: it first assumes a fixed predicate set, then identifies new useful concept predicates.The rule language combines discovered concepts with directly observable primitive predicates.

5.1 Learning Rule Sets

The paper learns probabilistic rule sets by decomposing an NP-hard search into greedy subproblems for outcomes, parameters, and rules. Scoring balances example likelihood against model complexity, while outcome induction and parameter learning handle overlapping noisy effects.

  • Hierarchical search: Learning rule sets is NP-hard, so the method uses three hierarchical greedy searches: LearnRules, InduceOutcomes, and LearnParameters.The levels search rule sets, outcome sets, and outcome distributions, respectively.
  • Scoring metric: The scoring metric favors rule sets that maximize the likelihood bound on training data while penalizing overly complex rules.Complexity is measured using the number of literals, with α set to 0.5 in the experiments.
  • Parameter learning: LearnParameters estimates outcome probabilities by maximizing the rule’s log likelihood, using outcome coverage percentages when each example has a unique outcome.With overlapping outcomes, it instead solves a concave optimization problem using conditional gradient ascent, which converges to the global maximum.
  • Outcome induction: InduceOutcomes begins with outcomes representing observed sets of changed atoms, then greedily adds conjunctions or removes redundant overlapping outcomes.Each candidate outcome set is evaluated with LearnParameters, and the search is restricted to proper outcome sets.
  • Representation constraints: Variables are introduced by reversing action substitutions, but without constants, changes involving unreferenced constants must be assigned to the noise outcome.This restriction limits which object-specific changes the rule language can express.
  • Search properties: The heuristic search operators are complete in construction space, but greedy scoring provides no guarantee of reaching the global maximum.The operators were consistently used during learning.

0.5 : on(Y, Z)

The displayed rule fragment identifies Y as the object in hand and T as the table.

  • Y is associated with the inhand predicate.
  • T is associated with the table predicate.
  • The fragment uses Y and T as named variables in the rule representation.

0.33 : on(Y, X)

The greedy search builds a rule set by proposing rules that explain training examples, scoring alternatives, and iteratively retaining score-improving changes. In the example, specialized rules progressively replace default noise explanations, while generalization remains limited by the available examples.

  • Rule-set search: LearnRuleSet starts with a default rule and uses ExplainExamples to propose compact rules covering training examples with high probabilities.At initialization, observed changes are assigned to noise; ExplainExamples then proposes rules intended to avoid unnecessary noise outcomes.
  • Rule-set search: The greedy search selects the highest-scoring candidate rule set, choosing r2 with score −10.443 over r1 at −16.101 and r3 at −15.5.The default-only rule set scores −21, so all three candidates improve on initialization, but r2 is best.
  • Rule-set search: After specialization, the search improves the score from −10.443 to −10.102 and then to −4.602 by reducing noise while reallocating example coverage.One refinement leaves e3 to the default rule; adding r3 subsequently removes all noise for the remaining examples.
  • Learned rules: The learned rules describe putting a block on a clear block and putting it on a block with another block above it.Further generalization to higher stacks would require training examples containing higher stacks.
  • Model variants: Propositional, relational, and deictic variants are obtained by controlling whether constants, variables, noise, and deictic references are allowed.These variants support evaluation of how representation choices affect learned action models.

5.2 Learning Concepts

LearnConcepts expands the modeling language by constructing derived predicates from existing literals and testing whether they improve learned rule sets. A complexity penalty discourages overfitting from excessive concept invention.

  • Concept learning: LearnConcepts constructs increasingly complex derived predicates and evaluates them by running LearnRuleSet and checking their use in learned rules.Candidate concepts are generated by operators applied to literals in the original language and subsequent concept sets.
  • Concept learning: A derived predicate can capture relational structure unavailable from primitive predicates, such as identifying a clear block at the top of a stack.The example builds topstack through successive definitions based on on and clear.
  • Controlling overfitting: The rich concept language creates a serious risk of overfitting, including concepts that identify individual examples.The paper addresses this risk with a penalty based on the number of distinct concepts used.
  • Controlling overfitting: The adjusted score S′(R) = S(R) − α′c(R) favors rule sets using fewer derived predicates.Here c(R) counts distinct concepts and α′ is a scaling parameter.

5.3 Discussion

The discussion frames learning as simultaneous induction of rule structure, outcome parameters, and derived predicates, with experiments supporting LearnConcepts. The approach is effective in tested domains but computationally expensive and ultimately non-scalable without further algorithmic development.

  • Discussion: Learning must recover rule structure, numeric outcome parameters, and definitions of derived predicates for the modeling language.This makes rule-set learning a joint structural and parametric problem.
  • Discussion: LearnConcepts performs this simultaneous learning effectively in the experiments reported in Section 7.2.The claim is explicitly tied to the paper’s experimental evaluation.
  • Computational cost: The search is expensive, although its operators attempt to keep the current rule set small.The number of candidate rule sets depends on the current rules; ExplainExamples creates d candidates, while other operators can create O(rm).
  • Computational cost: Because scores increase at every step, the algorithm converges to a usually local optimum, but convergence speed is not guaranteed.In tested domains, LearnRuleSet took at most 50 steps and LearnConcepts at most 5 outer-loop cycles.
  • Computational cost: The complete algorithm took no more than six hours on one processor in the reported implementation.The implementation relied substantially on caching intermediate computations.
  • Scope and future work: The authors expect the approach to become prohibitively expensive in more complex domains and leave online, more directed search for future work.The proposed future direction would learn concepts, rules, and parameters online.

6. Planning

The paper evaluates learned models through MDP planning when relational ground-truth dynamics are unavailable. Its sparse-sampling planner approximates action values under noisy outcomes, enabling comparison of models on relatively simple reward functions but not hard combinatorial planning problems.

  • Planning setup: For complex actions without relational ground-truth models, learned models are evaluated by planning and executing actions using MDP planning.The rule set defines the transition model, while the reward function is specified by hand.
  • Planning setup: An MDP represents states, actions, transition dynamics, and rewards, and planning seeks a policy maximizing reward over time.The optimal policy can be characterized through Bellman equations.
  • Sparse sampling: The sparse-sampling planner builds a finite state tree by forward sampling, estimates node values with the Bellman equation, and selects the highest-valued action.Tree depth and branching factor are predefined approximations to exact Bellman-equation solving.
  • Sparse sampling: For noisy outcomes, the planner estimates unknown next-state value by sampling as if the agent stayed in the same state and scaling the result by 0.75.The reported depth and branching factor are both four.
  • Planning limitations: The noisy-outcome value estimate is only a guess because partial noisy rules do not specify the next state explicitly.The value of an outcome such as a fallen tower depends on the current goal.
  • Planning limitations: The planner does not solve hard combinatorial planning problems but can maximize relatively simple reward functions well enough to distinguish good from poor models.This capability supports the paper’s model evaluation strategy.

7. Evaluation

The evaluation tests learned probabilistic action models across symbolic domains and a physically simulated blocks world. Variable abstraction, deictic references, noise outcomes, and learned concepts are associated with stronger planning performance.

  • Evaluation: Experiments evaluate rule learning in low-noise domains and an intrinsically noisy simulated blocks world.The domains include slippery gripper, trucks and drivers, and a rigid-body physics blocks world.
  • 7.1.1 Slippery Gripper: The slippery gripper domain models probabilistic manipulation involving wet-gripper failures and drying.Its relational rules include pickup, puton, painting, and wetness-related outcomes.
  • 7.1.2 Trucks and Drivers: The trucks-and-drivers domain includes stochastic walking, where drivers sometimes arrive at randomly chosen connected locations.Its representation requires a separate rule for each origin location and outcomes for linked destinations.
  • 7.2.1 Learning Rule Sets with No Noise: Relational learning consistently outperforms propositional learning, while deictic learning performs best except when the walk action cannot be represented efficiently.The results indicate that variable abstraction helps, but overly restrictive or mismatched representations can limit performance.
  • 7.2.2 Learning in the Blocks World Simulator: In the simulated blocks world, learned concepts approach human-expert performance and slightly outperform hand-engineered concepts on small training sets.The concept learner rediscovered predefined predicates and discovered additional useful predicates such as onclear.
  • 7.2.2 Learning in the Blocks World Simulator: Ablated variants received rewards comparable to doing nothing, showing that noise outcomes, extended concepts, and deictic references are all important.The human-directed gripper averaged reward 16.2, while the full learned system performed near human levels.
  • 7.2.2 Learning in the Blocks World Simulator: Noisy deictic models were faster to learn and plan with than traditional rules because they were more compact.Learning NDRs took minutes on one desktop, compared with hours for traditional rules.

8. Discussion

The discussion frames the representation as a first step toward learning probabilistic action models in physically simulated worlds. It highlights new search and concept-learning components while identifying representational and scalability limitations.

  • 8. Discussion: The paper develops a probabilistic action-model representation rich enough for planning in a physically simulated blocks world.The authors present this as a first step toward learning in more complex worlds.
  • 8.1 Related Work: Unlike earlier probabilistic approaches, the representation addresses complex noisy dynamics and supports learned concepts.Earlier methods were described as insufficiently robust for complex noisy environments, while TRAIL lacked mechanisms for learning new predicates.
  • 8.1 Related Work: Initializing greedy rule-set search with a noise rule avoids hand-selecting an initial rule set and works in more complex environments.The paper reports this search strategy as a new approach that works well in practice.
  • 8.2 Future and Ongoing Work: The approach may require adaptation for additional domains, including more realistic robotics and dialogue systems.Proposed extensions include parallel rule application, quantified outcomes, and handling partial observability.
  • 8.2 Future and Ongoing Work: Future work includes incremental online learning to reduce dependence on training sets that adequately sample relevant worlds.Such methods would require techniques for exploring the world while learning.
Loading 1110.2211v1…