The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. (English) Zbl 0755.68124

Reiter, Raymond

Artificial intelligence and mathematical theory of computation, Pap. in Honor of J. McCarthy, 359-380 (1991).

[For the entire collection see Zbl 0745.00070.]
Ever since it was first pointed out by McCarthy and Hayes in 1969, the frame problem has remainded an obstacle to the formalization of dynamically changing worlds. Despite many attempts, no completely satisfactory solution has been obtained. Without presuming to have solved the frame problem in its full generality, we propose a solution for an interesting special case, and explore some of its consequences. Specifically, we have two objectives:
1. To provide an analysis of two recent proposals for dealing with the frame problem in the situation calculus [E. P. D. Pednault, ADL: Exploring the middle ground between STRIPS and the situation calculus, Principles of knowledge representation and reasoning, Proc. 1st. Int. Conf., Toronto/Can., 324-332 (1989), L. K. Schubert, Monotonic solutions of the frame problem in the situation calculus: an efficient method for worlds with fully specified actions. In H. E. Kyberg, R. P. Loui, and G. N. Carlson, editors, Knowledge representation and defeasible reasoning, Kluwer Academic Press, Boston, Mass., 23-67 (1990)] and to show how they can be combined, under a suitable closure assumption that is appropriate in settings when the effects of all actions on all fluents can be specified.
2. To show how the axioms arising from the analysis of 1. provide a systematic treatment of goal regression [R. Waldinger, Achieving several goals simultaneously. In E. Elcock and D. Michie, editors, Machine Intelligence 8, Ellis Horwood, Edinburgh, Scotland, 94-136 (1977)] for plan synthesis, together with natural conditions under which regression is provably sound and complete.

MSC:

68T15

Theorem proving (deduction, resolution, etc.) (MSC2010)

Keywords:

frame axioms; soundness; completeness; frame problem; situation calculus; goal regression

Citations:

Zbl 0745.00070