First-Order Strong Progression for Local-Effect Basic Action Theories

Stavros Vassos, Gerhard Lakemeyer, Hector J. Levesque

In a seminal paper Lin and Reiter introduced the notion of progression for basic action theories in the situation calculus. The idea is to replace an initial database by a new set of sentences which reflect the changes due to an action. Unfortunately, progression requires second-order logic in general. In this paper, we introduce the notion of strong progression, a slight variant of Lin and Reiter that has the intended properties, and we show that in case actions have only local effects, progression is always first-order representable. Moreover, for a restricted class of local-effect axioms we show how to construct a new database that is finite.


Subjects: 11. Knowledge Representation; 5. Common Sense Reasoning

Submitted: Jun 17, 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.