Learning Partially Observable Deterministic Action Models

Abstract

e present the first tractable, exact solution for the problem of identifying actions’ effects in partially observable STRIPS domains. Our algorithms resemble Version Spaces and Logical Filtering, and they identify all the models that are consistent with observations. They apply in other deterministic domains (e.g., with conditional effects), but are inexact (may return false positives) or inefficient (we could not bound the representation size). Our experiments verify the theoretical guarantees, and show that we learn STRIPS actions efficiently, with time that is significantly better than approaches for HMMs and Reinforcement Learning (which are inexact). Our results are especially surprising because of the inherent intractability of the general deterministic case. These results have been applied to an autonomous agent in a virtual world, facilitating decision making, diagnosis, and exploration.