AAAI Publications, Workshops at the Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Towards an Expressive Decidable Logical Action Theory
Wael Yehia, Mikhail Soutchanski

Last modified: 2012-07-15


In the area of reasoning about actions, one of the key computational problems is the projection problem: to find whether a given logical formula is true after performing a sequence of actions. This problem is undecidable in the general situation calculus; however, it is decidable in some fragments. We consider a fragment P of the situation calculus and Reiter’s basic action theories (BAT) such that the projection problem can be reduced to the satisfiability problem in an expressive description logic ALCO(U) that includes nominals (O), the universal role (U), and constructs from the well-known logic ALC. It turns out that our fragment P is more expressive than previously explored description logic based fragments of the situation calculus. We explore some of the logical properties of our theories. In particular, we show that the projection problem can be solved using regression in the case where BATs include a general “static” TBox, i.e., an ontology that has no occurrences of fluents. Thus, we propose seamless integration of traditional ontologies with reasoning about actions. We also show that the projection problem can be solved using progression if all actions have only local effects on the fluents, i.e., in P, if one starts with an incomplete initial theory that can be transformed into an ALCO(U) concept, then its progression resulting from the execution of a ground action can still be expressed in the same language. Moreover, we show that for a broad class of incomplete initial theories progression can be computed efficiently.


Description Logics; Situation Calculus; Projection Problem

Full Text: PDF