Characterizing Causal Action Theories and Their Implementations in Answer Set Programming

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Characterizing Causal Action Theories and Their Implementations in 
Answer Set Programming"

By

Mr. Haodi ZHANG


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 many different 
action languages have been proposed. These approaches and semantics basically 
agree when the causal action theories are stratified. However when there is 
some dependency cycle, it is not always clear that what correct and reasonable 
results should be.

We propose a new computer-aided 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. 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. 
With a systematic experiment on a small domain of action theories, we identify 
a minimal set of postulates, under which there is only one unique permissible 
translation under strong equivalence. Last, we prove that for arbitrary causal 
action theory in the language, the set of postulates gives the same unique 
translation. Thus an action language is evaluated by postulates over all 
possible causal action theories, instead of some examples.

This approach is quite general and can be used to evaluate and to compare 
action languages in an intuitive sense. And we use this approach to give 
characterizations of three representative action languages, B, C and BC, and to 
compare them in a brand new perspective. For instance, they solve the 
ramification problem in different levels. We characterize these action 
languages in form of postulates, and all possible action theories in the 
language are included in the conclusion, with our experiment and proof.


Date:			Friday, 22 January 2016

Time:			10:00am - 12:00noon

Venue:			Room 3584
 			Lifts 27/28

Chairman:		Prof. Michael Loy (PHYS)

Committee Members:	Prof. Fangzhen Lin (Supervisor)
 			Prof. Raymond Wong
 			Prof. Nevin Zhang
 			Prof. Xiangtong Qi (IELM)
 			Prof. Michael Gelfond (Comp. Sci., Texas Tech U)


**** ALL are Welcome ****