On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture

Stavros Vassos, Hector J. Levesque

In a seminal paper, Lin and Reiter introduced a model-theoretic definition for the progression of the initial knowledge base of a basic action theory. This definition comes with a strong negative result, namely that for certain kinds of action theories, first-order logic is not expressive enough to correctly characterize this form of progression, and second-order axioms are necessary. However, Lin and Reiter also considered an alternative definition for progression which is always first-order definable. They conjectured that this alternative definition is incorrect in the sense that the progressed theory is too weak and may sometimes lose information. This conjecture, and the status of first-order definable progression, has remained open since then. In this paper we present two significant results about this alternative definition of progression. First, we prove the Lin and Reiter conjecture by presenting a case where the progressed theory indeed does lose information. Second, we prove that the alternative definition is nonetheless correct for reasoning about a large class of sentences, including some that quantify over situations. In this case the alternative definition is a preferred option due to its simplicity and the fact that it is always first-order.

Subjects: 11. Knowledge Representation; 17. Robotics

Submitted: Apr 14, 2008


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.