Learning Partially Observable Deterministic Action Models

Eyal AmirIJCAI 2005

Introduction

Autonomous agents operating in unknown environments must learn the underlying "physics" of their world—the preconditions and effects of their actions—to plan and act intelligently. This task is particularly challenging in partially observable domains, where the agent cannot see the entire state of the world. In such settings, hidden states obscure the direct consequences of actions, and the number of possible transition models grows double-exponentially with the number of environmental features.

This paper presents SLAF (Simultaneous Learning and Filtering), a breakthrough online algorithm that provides the first tractable and exact method for learning action models in partially observable, deterministic worlds. By representing the set of all possible world models as a logical formula and updating it efficiently, SLAF transforms a traditionally intractable problem into one that scales linearly with the number of features.

The SLAF Framework

The core innovation of SLAF is treating the learning process as a logical filtering problem. Instead of attempting to guess a single model, SLAF maintains a logical formula that represents every transition model consistent with the sequence of actions and observations seen so far. This approach combines the concept of "Version Spaces" from classic machine learning with logical filtering techniques.

The authors represent transition rules using a propositional language where a term like $a^F_G$ signifies: "If condition $G$ holds, then action $a$ causes effect $F$." While a naive implementation of this filtering is computationally heavy, the authors introduce Factored-SLAF to achieve tractability. They prove that if actions follow STRIPS-like rules—where each action affects only a small number of features ($k$)—the global logical formula can be decomposed into independent factors. This ensures that update times remain polynomial, specifically $O(T \cdot n^k)$, where $n$ is the number of features.

The AE-STRIPS-SLAF procedure for learning action models.

Experimental Evaluation

To validate the algorithm, the authors conducted experiments using standard AI planning benchmarks, including the Blocks-World domain. They generated random action-observation sequences of up to 4,000 steps. The testing covered a wide range of environmental complexities, with the number of features (fluents) varying from 31 to 157. Additionally, the algorithm was tested in virtual adventure-game environments featuring arbitrary rooms and objects to ensure its robustness across different types of deterministic rules.

Key Results and Performance

SLAF demonstrated the ability to learn exact STRIPS models in domains with over 100 features. This is a significant achievement; for comparison, a standard Hidden Markov Model (HMM) would require a transition matrix with $(2^{100})^2$ entries, making it physically impossible to store or process.

The empirical results highlight the algorithm's efficiency. In the blocks-world experiments, the time taken per update step was extremely low—less than 9 milliseconds.

Computational performance of SLAF across different feature counts and steps.

As shown in the performance graph, the time per step scales linearly with the number of features and remains stable as the number of steps increases. This confirms that the factored approach successfully manages the potential "model explosion" that plagues other learning methods. The authors note that while probabilistic approaches like Dynamic Bayesian Networks (DBNs) often struggle with unbounded errors in discrete deterministic domains, SLAF's use of logical pruning allows it to maintain exact knowledge efficiently.

Conclusion

SLAF proves that the strictness of determinism, often seen as a limitation, can be leveraged as a computational strength. By using observations to definitively prune inconsistent hypotheses, the algorithm maintains an exact belief state of possible world models. While currently limited to deterministic environments with discrete features, the SLAF framework provides a powerful "skeleton" for future research into stochastic domains and more complex conditional effects.

Summary updated

BibTeX
@inproceedings{amir2005learning,
  author = {Eyal Amir},
  title = {{Learning Partially Observable Deterministic Action Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure