Learning Symbolic Models of Stochastic Domains

Hanna M. Pasula, Luke S. Zettlemoyer, Leslie Pack Kaelbling

TL;DR

Learning accurate models of the real world is challenging because physical interactions are inherently noisy, complex, and nondeterministic. This paper introduces Noisy Deictic Rules (NDRs), a probabilistic relational representation that models stochastic dynamics while handling unmodeled chaotic events via a dedicated "noise" outcome and referencing unnamed objects through deictic pointers. Combined with greedy rule induction and relational concept invention, the system learns compact, predictive models from raw transitions that enable effective planning in a realistic 3D rigid-body physics simulator.

What Problem Does This Paper Address?

To plan flexible courses of action toward changing goals, autonomous agents need a predictive model of world dynamics. Traditional AI planning models (like deterministic STRIPS or early probabilistic extensions) break down in physical settings for several reasons:

  1. Unmodeled Complexity and Chaos: In a physical domain (such as a robotic arm stacking blocks), actions occasionally produce chaotic outcomes (e.g., an entire tower toppling into an irregular heap) that are too rare and complex to enumerate explicitly.
  2. Rigid Action Signatures: Classical models require all affected objects to be explicit arguments in the action definition, making it awkward when an action indirectly affects surrounding objects.
  3. Missing High-Level Vocabulary: Perceptual systems typically supply raw, low-level relations (such as "object $A$ exerts downward force on $B$"), lacking the abstract concepts (such as "height of stack" or "top-of-stack") required to predict whether an action will succeed.

Methods

The authors introduce Noisy Deictic Rules (NDRs), which extend probabilistic first-order planning rules:

  • Deictic References: Rules can define auxiliary variables bound to specific contextual objects using unique existential restrictions (e.g., "let $Y$ be the unique block directly on top of $X$"). If a deictic reference fails to resolve uniquely, the rule simply does not apply.
  • Explicit Noise Outcomes: Rather than forcing the model to explain every edge-case transition, each rule includes a catch-all noise outcome ($\Psi'_{\text{noise}}$) paired with a worst-case lower-bound probability ($p_{\text{min}}$). A background default rule models unhandled events as noise.
  • Concept Invention (LearnConcepts): Extends the primitive language by applying structural operators—including conjunction, quantifiers ($\exists, \forall$), counting ($\#$), and transitive closure (Kleene star)—to invent derived concepts (such as above, topstack, and height) that feed back into rule learning.
  • Hierarchical Greedy Learning (LearnRules):
  • Outermost level: Searches the space of proper rule sets using search operators (dropping literals, splitting on variables, adding deictic references, explaining uncovered examples).
  • Middle level (InduceOutcomes): Generates minimal sets of state changes observed in training transitions.
  • Innermost level (LearnParameters): Uses a conditional gradient ascent algorithm with the Armijo line-search rule to maximize the penalized log-likelihood over outcome probabilities.
  • Planning: Evaluated via an MDP sparse sampling planner adapted to scale down estimated values when traversing noisy outcome branches.
       Raw Transitions (s, a, s')
                   │
                   ▼
      ┌─────────────────────────┐
      │  LearnConcepts Search   │◄──── Invent predicates (transitive closure,
      └────────────┬────────────┘      counting, quantification)
                   │
                   ▼
      ┌─────────────────────────┐
      │  LearnRules Set Search  │◄──── Greedy operators (AddRefs, DropLits, etc.)
      └────────────┬────────────┘      starting from default noise rule
                   │
                   ▼
      ┌─────────────────────────┐
      │     InduceOutcomes      │◄──── Identifies proper outcome conjunctions
      └────────────┬────────────┘
                   │
                   ▼
      ┌─────────────────────────┐
      │     LearnParameters     │◄──── Solves concave likelihood via
      └─────────────────────────┘      conditional gradient ascent

Datasets

The authors evaluate their approach on three simulated environments:

  • Slippery Gripper: An abstract, symbolic benchmark based on Draper et al. (1994) where blocks are manipulated, but painting blocks can wet the gripper and reduce future pickup reliability.
  • Trucks and Drivers: A logistics domain adapted from the 2002 AIPS International Planning Competition, involving trucks, drivers, locations, and packages, including a stochastic "walk" action where pedestrians can arrive at random adjacent nodes.
  • 3D Simulated Blocks World: Built using the Open Dynamics Engine (ODE) rigid-body physics simulator. Unlike abstract blocks worlds, blocks vary in size and color, stacks can topple, and gripper actions are physical motors that apply downward force and pinch grasps. States are represented purely with Skolem constants (arbitrary object IDs without intrinsic persistent identity) and the force-based primitive relation $\text{on}(X,Y)$.

Key Insights and Ideas

  • Abstracting Away Object Identity Prevents Overfitting: Forcing models to use deictic references and variables rather than object-specific constants creates an inductive bias that enables rapid generalization from fewer training samples.
  • Treating Chaos as Noise Preserves Tractability: Forcing an agent to fit every rare, catastrophic physical outcome balloons hypothesis complexity. Providing a bounded noise outcome lets the model focus learning capacity on predictable transitions without breaking the probabilistic semantics.
  • Invented Concepts Bridge the Gap to Physics: Basic physics engines produce local contact relations. Relational operators like transitive closure and counting allow the learner to invent concepts like height and topstack autonomously, which are critical for recognizing when an action (e.g., placing on a tall stack) is likely to fail.

Key Results

  • Sample Efficiency in Symbolic Benchmarks: In the Slippery Gripper and Trucks & Drivers domains, the deictic learner consistently achieved lower variational distance to the true dynamics than relational (with constants) and propositional learners as training sample size varied from 100 to 1,000 examples.
  • Human-Level Task Performance in Realistic Physics: In the ODE 3D blocks world (evaluating cumulative reward for maximizing stack height):
  • Full NDR learner (with learned concepts): Reached an average reward around 15.0 to 15.5 at 1,000 training examples, closely approaching an expert human teleoperating the gripper (16.2).
  • Hand-engineered concepts: Achieved nearly identical performance (~15.0).
  • Ablations: Removing noise outcomes or restricting the relational concept language dropped performance down to baseline levels (~6.5 to 9.2), matching the reward of taking no actions at all (9.2).
  • Speedup: Learning compact NDR models took minutes on a standard desktop PC, whereas traditional rules attempting to model all transitions took hours.

Limitations and Future Work

  • Full Observability Assumption: The framework assumes an unambiguous, noise-free perceptual state is delivered at each step; real robot sensors suffer from partial observability and occlusion.
  • Mutual Exclusivity Constraint: Exactly one rule is assumed to cover each transition. The formalism cannot easily express independent concurrent effects acting in parallel.
  • Quantifiers in Outcomes: Actions that stochastically pick among an unbounded set of targets (like the random-destination walk action) currently cannot be represented by a single outcome and require enumerating destination rules.
  • Batch Greedy Search: The algorithm operates offline on pre-collected batches. The authors note the need to extend this framework to online, active exploration where an agent gathers its own experience in a reinforcement learning setup.

Summary updated

Abstract

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.
BibTeX
@article{pasula2007learning,
  author = {Hanna M. Pasula and Luke S. Zettlemoyer and Leslie Pack Kaelbling},
  title = {{Learning Symbolic Models of Stochastic Domains}},
  journal = {J. Artif. Intell. Res.},
  year = {2007},
  url = {https://openreview.net/forum?id=X1UCaRIZYUX},
}

Loading related content...

Figure