Integrating actions and state constraints: A closed-form solution to the ramification problem (sometimes)

AbstractIntegrating actions and state constraints is a central problem in knowledge representation. State constraints are commonly used to represent the relationship between objects in the world. When a representation of action is integrated, state constraints implicitly define indirect effects of actions and impose further preconditions on the performance of actions. Thus, a semantically correct integration of actions and state constraints must address the ramification and qualification problems, as well as the frame problem. In this paper we achieve such an integration for a syntactically restricted class of situation calculus theories.This paper presents two major technical contributions. The first contribution is an axiomatic closed-form solution to the frame, ramification and qualification problems for a common class of theories. The solution is presented in the form of an automatable procedure that compiles a syntactically restricted set of situation calculus ramification constraints and effect axioms into a set of successor state axioms. The second major contribution of this paper is an independent semantic justification for this closed-form solution. In particular, we present a semantic specification for a solution to the frame and ramification problems in terms of a prioritized minimization policy, and show that the successor state axioms of our closed-form solution adhere to this specification. Observing that our minimization policy is simply an instance of prioritized circumscription, we exploit results of Lifschitz (1985) on computing circumscription to show that computing the prioritized circumscription yields our successor state axioms. In the special case where there are no ramification constraints, computing the circumscription yields Reiter's (1991) earlier successor state axiom solution to the frame problem