A mathematical investigation of reasoning about actions
G. Kartha · 1995
Reasoning about actions is a central area of research in artificial intelligence, related to the study of common sense and nonmonotonic reasoning, knowledge representation, planning and theorem proving. The methodology of research in this area has not been quite satisfactory; typically, a new proposal for reasoning about actions is illustrated by way of a few examples that have been known to be challenging to formalize, and then claims are made that the method works in general. This is not very satisfactory since minor modifications of the examples might prove (indeed, have proven, in many cases) to be difficult or impossible for the new proposal to handle correctly. Such an example-oriented methodology also makes it difficult to compare various formalisms and thus to synthesize new ones. In this dissertation, we present a systematic study of reasoning about actions. The shortcomings of the example-oriented methodology are avoided as follows. First, declarative languages for describing actions are introduced and their semantics defined in such a way as to capture the underlying commonsense intuitions. Different methods of reasoning about actions are presented as translations from these languages and then the adequacy of the different formalizations is established by proving the soundness and completeness of the translations. The new declarative languages we propose are capable of representing rich action domains, such as those where actions can have indirect effects. In addition, we introduce a new approach to reasoning about actions and show its adequacy in formalizing a large class of action domains. We show that, in conjunction with this approach, symbolic methods can often be employed for automating reasoning about actions. Finally, we point out some limitations of proposed methods of reasoning about actions and suggest ways to overcome these limitations.