Learning Partially Observable Action Models: Efficient Algorithms

Dafna Shahaf, Allen Chang, Eyal AmirAAAI 2006

Abstract

Learning action models in partially observable environments is a fundamental challenge in artificial intelligence. Traditional approaches often struggle with computational intractability or rely on imprecise approximations. This paper presents Simultaneous Learning and Filtering (SLAF), a framework for exact learning of deterministic action models. By utilizing Directed Acyclic Graphs (DAGs) and Conjunctive Normal Form (CNF) representations, the proposed algorithms maintain compact knowledge bases even in high-dimensional state spaces. Experimental results demonstrate that these methods scale to environments with over 1,000 features while maintaining millisecond-level processing times.

Introduction

In classical AI planning, agents are typically provided with complete action models. However, in real-world scenarios, agents must often learn these models through interaction. This task is significantly complicated by partial observability, where the agent cannot perceive the full state of the environment. For example, an agent must infer that an object moved inside a container even after it is no longer visible.

Previous research in this area has faced a trade-off between accuracy and efficiency. Approximate methods may fail to capture exact dynamics, while exact logical methods often suffer from state-space explosion. This work addresses these limitations by introducing efficient algorithms that maintain exact belief states using clever logical data structures.

Methodology

The core of the proposed approach is the Simultaneous Learning and Filtering (SLAF) framework. SLAF maintains a belief state representing all action models consistent with the observed action-observation sequence.

DAG-SLAF

The DAG-SLAF algorithm represents logical formulas as Directed Acyclic Graphs. This allows for the reuse of shared sub-formulas, preventing the exponential growth typically associated with logical progression. The algorithm ensures that the representation size remains polynomial relative to the number of environment features.

The DAG-SLAF algorithm for efficient action model learning.

CNF-SLAF

Alternatively, knowledge can be represented in Conjunctive Normal Form (CNF), which is compatible with high-performance SAT solvers. The authors prove that under certain observability conditions—specifically, if features are observed periodically—the CNF representation remains indefinitely compact.

Successor-State Axioms

The framework adapts successor-state axioms from the Situation Calculus to update the agent's knowledge base. After each action, the algorithm progresses the belief state by incorporating the action's effects and filtering it against new observations.

DAG representation of the belief state over time, showing how explanations point to shared transition rules and initial states.

Experimental Evaluation

The algorithms were tested on standard International Planning Competition (IPC) domains, including Blocks World, Briefcase World, and Driverlog. Notably, the tests included synthetic domains with over 1,000 features, representing a state space of $2^{1000}$.

Key Results

  • Scalability and Speed: DAG-SLAF processed actions in under 2 milliseconds, even in large-scale domains.
  • Learning Efficiency: Agents learned the majority of transition rules within a few dozen steps, even with only 60% observability.
  • Feature Support: Unlike previous state-of-the-art learners like AE-STRIPS, the CNF-SLAF approach successfully learns action preconditions.

Conclusion

This work demonstrates that exact logical deduction for learning action models is computationally tractable in deterministic, partially observable worlds. By leveraging DAGs to prevent logical explosion, the SLAF framework provides a robust foundation for autonomous model acquisition. Future research will focus on extending these methods to stochastic environments and relational action schemas to improve generalization across objects.

Summary updated

BibTeX
@inproceedings{shahaf2006learning,
  author = {Dafna Shahaf and Allen Chang and Eyal Amir},
  title = {{Learning Partially Observable Action Models: Efficient Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure