Learning Symbolic Models of Stochastic Domains

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

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.

Introduction

Traditional AI planning often relies on highly idealized models. In the classic "Blocks World," blocks are perfectly cubical, stacks never wobble, and actions like pickup(A) always succeed. However, real-world environments—and even high-fidelity physics simulators—are significantly more complex. Piles topple, grippers slip, and the number of objects affected by an action can vary unpredictably.

To address this, we identify two core challenges in developing autonomous agents:

  1. Representation: Developing a compact way to describe rules that are both relational (generalizing across objects) and stochastic (handling uncertainty).
  2. Learning: Automatically inducing these rules from raw execution data without human intervention.

Methods: Noisy Deictic Rules (NDRs)

We propose Noisy Deictic Rules (NDRs), a framework that combines first-order logic with probabilistic outcomes to model complex world dynamics.

Representation

NDRs utilize variables to generalize across objects and assign probabilities to various outcomes. A key feature is the use of deictic references (e.g., "the object currently in the gripper"), which allows rules to maintain a simple action interface while affecting the surrounding context.

Crucially, we introduce a "noise" outcome. Rather than attempting to model every rare, complex event—such as the exact final position of every block in a collapsed tower—the rule includes a catch-all for unmodeled effects. This prevents the learner from overfitting to rare "freak" events and focuses the representational budget on predictable dynamics.

Learning Algorithm

The system learns from $(state, action, next\_state)$ triples using a three-tiered greedy search:

  1. Parameter Learning: Gradient ascent optimizes probabilities for rule outcomes.
  2. Outcome Induction: Searches for the best logical changes to describe action effects.
  3. Rule Set Search: An outer loop that manages the rule set to maximize a scoring metric balancing likelihood against complexity.

Furthermore, a Concept Learning layer allows the agent to "invent" higher-level concepts (e.g., above, clear) from basic primitives using a grammar of logical operators, making the resulting rules significantly more accurate.

Experimental Setup

The approach was evaluated across three distinct domains:

  1. Slippery Gripper: An abstract domain where painting blocks affects gripper reliability.
  2. Trucks and Drivers: A logistics domain with complex movement dynamics.
  3. 3D Simulated Blocks World: A challenging environment using the Open Dynamics Engine (ODE), featuring realistic physics, varying block sizes, and a physically simulated gripper.
A 3D simulated blocks world environment with a blue gripper and various white and red blocks, demonstrating the noisy physics domain.

Key Results and Insights

The experiments yielded several critical insights into the effectiveness of NDRs:

  • The Utility of Noise Modeling: By explicitly modeling a "noise" outcome, the agent becomes more robust, treating rare events as background noise rather than trying to find complex logical explanations for them.
  • Deictic Bias as Regularization: Forcing the use of relative pointers prevents the agent from memorizing specific object identities, encouraging the learning of general principles that apply across different scenarios.
  • Predicate Invention: The agent successfully rediscovered concepts like above (the transitive closure of on) and height (counting blocks in a stack) purely from data.

In the 3D physics simulator, the full NDR algorithm achieved a planning reward of ~14-15, approaching human performance (16.2) and significantly outperforming baselines that lacked noise modeling or concept learning. Despite the NP-hard nature of rule learning, the greedy algorithm typically converged in under 50 steps, taking minutes on standard hardware.

Conclusion and Future Work

While NDRs effectively model noisy, relational domains, several challenges remain. The current model assumes full observability, which is often unrealistic in physical settings. Additionally, while greedy search performed well here, it remains susceptible to local optima. Future work will explore scaling concept search to more diverse environments and integrating continuous states (e.g., coordinates and velocities) directly into the symbolic rule representation.

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