Characterizing causal action theories and their implementations in answer set programming

Abstract

In logic-based AI, formal reasoning about action has been a central topic. The main challenges have been the frame and the ramification problems. To solve them, there has been much work on causal action theories and several action languages for these theories have been proposed. We propose a new approach to characterize action languages in form of postulates. We first consider a language for writing causal action theories, and postulate several properties for the state transition models of these theories. We then consider their implementations in logic programs with answer set semantics. In particular, we propose to consider what we call permissible translations from these causal action theories to logic programs. First, for a small language, we use a computer program to systematically examine all causal theories, and identify a minimal set of postulates that yields a unique permissible mapping under strong equivalence. We then prove that the result holds in the general case for any language as well. This approach is quite general and can be used to evaluate and to compare action languages. And we use this approach to give characterizations of three representative action languages, B, C and BC, and to compare them based on our new characterization.

Date of Award	2016
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology