CAREER: Causal Theories of Action for AI Planning

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

In the last few years a greater emphasis on causality has enhanced the expressiveness of logic-based action representations. An example of this is the "causal theories" formalism of McCain and Turner, which can be used to conveniently describe action domains in which: (a) actions have indirect, nondeterministic, and/or delayed effects; (b) things change by themselves; and (c) concurrent actions have interacting effects. Although causal theories are nonmonotonic, they are mathematically simple. In fact, in their most commonly used form they have a concise translation into classical propositional logic. This last fact is particularly significant in light of the remarkable success of the satisfiability planning method of Kautz and Selman, which has greatly influenced recent AI planning research. While most current work on satisfiability planning involves propositional encodings of STRIPS-like action descriptions, the expressiveness of causal theories will support satisfiability planning in relatively complex action domains. For example, there has been little progress in AI planning for action domains in which concurrently executed actions may have interacting effects. Causal theories can be used to describe them, and the resulting descriptions can be used for planning by the satisfiability method. A unifying goal of the current research is to broaden the applicability of AI planning by means of contributions in the following areas: (a) mathematics of causal theories and related formalisms; (b) representations of complex action domains as causal theories; and (c) automated planning and reasoning about actions.