Action-centered reasoning for probabilistic dynamic domains

This dissertation focuses on modeling stochastic dynamic domains, using representations and algorithms that combine logical AI ideas and probabilistic methods. We introduce new tractable and highly accurate algorithms for reasoning in those complex domains. Furthermore, we apply these algorithms to tasks of narrative understanding and web page monitoring. We model stochastic dynamic domains with a factored logical representation that uses a graphical model to represent a prior distribution over initial states. Our representation uses sequences of actions (represented in logical form) to represent transitions. We introduce an algorithm for reasoning in stochastic dynamic domains (in propositional and relational fashions) based on subroutines for reasoning in deterministic substructure of the domain. Our algorithm takes advantage of the factored logical representation and efficient subroutines for logical progression and regression. The tractability of the algorithm results from the tractability of these underlying subroutines. Our theoretical and empirical results show significant improvement of our algorithm over previous approaches for reasoning. Our novel algorithm for reasoning in probabilistic dynamic domains samples sequences of deterministic actions corresponding to an observed sequence of probabilistic actions. This algorithm is built upon a novel exact and tractable algorithm to reason about deterministic dynamic domains with a probabilistic prior. We apply the dynamic domain representation and our algorithms to the understanding of narratives. For that, we introduce a label-free iterative learning approach which outperforms the state- of-the-art that uses labeled data. We also apply dynamic domains and reasoning about them in the problem of monitoring change in webpages to direct crawlers. For that, we introduce a greedy algorithm that outperforms the state-of-the-art algorithms