Fiora Pirri
Abstract
We focus on a rich axiomatization for actions in the situation calculus that includes, among other features, a solution to the frame problem for deterministic actions. Our work is foundational in nature, directed at simplifying the entailment problem for these axioms. Specifically, we make four contributions to the metatheory of situation calculus axiomatizations of dynamical systems:
(1) We prove that the above-mentioned axiomatization for actions has a relative satisfiability property; the full axiomatization is satisfiable iff the axioms for the initial state are.
(2)We define the concept of regression relative to these axioms, and prove a soundness and completeness theorem for a regression-based approach to the entailment problem for a wide class of queries.
(3) Our formalization of the situation calculus requires certain foundational axioms specifying the domain of situations. These include an induction axiom, whose presence complicates human and automated reasoning in the situation calculus. We characterize various classes of sentences whose proofs do not require induction, and in some cases, some of the other foundational axioms.
(4)We prove that the logic programming language GOLOG never requires any of the foundational axioms for the evaluation of programs.
- ALLEY, J.F. 1984. Towards a general theory of action and time. Artif. Int. 23, 2, 123-154. Google Scholar
- BERTOSSI, L., ARENAS, M., AND FERRETTI, C. 1998. SCDBR: An automated reasoner for specifications of database updates. J. Int. Inf. Syst. 10, 3. Google Scholar
- BURGARD, W., CREMERS, A. B., FOX, D., HAHNEL, D., LAKEMEYER, G., SCHULTZ, D., STEINER, W., AND THRUM, S. 1998. The interactive museum tour-guide robot. In Proceedings of the National Conference on Artificial Intelligence (AAAI'98). AAAI Press/MIT Press, Cambridge, Mass., pp. 11-18. Google Scholar
- DAVIS, E. 1990. Representations of Commonsense Knowledge. Morgan-Kaufmann, San Francisco, Calif. Google Scholar
- DE GIACOMO, G., LESPERANCE, Y., AND LEVESQUE, U. J. 1997. Reasoning about concurrent execution, prioritized interrupts, and exogenous actions in the situation calculus. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (Nagoya, Japan). pp. 1221-1226. Google Scholar
- ENDERTON, H.B. 1972. A Mathematical Introduction to Logic. Academic Press, Orlando, Fla.Google Scholar
- FUNGE, J. 1998. Making them behave: Cognitive models for computer animation. Ph.D. dissertation. Dept. Comput. Sci. Univ. Toronto, Toronto, Ont., Canada. Google Scholar
- GELFOND, M., AND LIFSCHITZ, V. 1998. Action languages. Linkdping Electronic Articles in Computer and Information Sciences, 3, www.ep.liu.se/ea/cis/1998/016/.Google Scholar
- GELFOND, M., LIFSCHITZ, V., AND RABINOV, A. 1991. What are the limitations of the situation calculus? In Working Notes, AAAI Spring Symposium Series on the Logical Formalization of Commonsense Reasoning. AAAI Press, Reston, Va., pp. 50-69.Google Scholar
- GOLDBLATT, R. 1987. Logics of time and computation. In CSLI Lecture Notes No. 7. Center for the Study of Language and Information, Stanford Univ. Stanford, Calif. Google Scholar
- GALEN, C.C. 1969. Theorem proving by resolution as a basis for question-answering systems. In Machine Intelligence, vol. 4, B. Meltzer and D. Mitchie, eds. American Elsevier, New York, pp. 183-205.Google Scholar
- HAAS, A.R. 1987. The case for domain-specific frame axioms. In The Frame Problem in Artificial Intelligence. Proceedings of the 1987 Workshop, Los Altos, Calif., F. M. Brown, ed. Morgan- Kaufmann, San Francisco, Calif., pp. 343-348.Google Scholar
- HANKS, S., AND MCDERMOTT, D. 1986. Default reasoning, nonmonotonic logics, and the frame problem. In Proceedings of the National Conference on Artificial Intelligence (AAAI'86). AAAI Press, Reston, Va., pp. 328-333.Google Scholar
- JENKIN, M., LESPt#RANCE, Y., LEVESQUE, H. J., LIN, F., LLOYD, J., MARCU, D., REITER, R., SCHERL, R. B., AND TAM, K. 1997. A logical approach to portable high-level robot programming (Invited paper). In Proceedings of the lOth Australian Joint Conference on Artificial Intelligence (/t1'97) (Perth, Australia).Google Scholar
- KOWALSKI, R. A., AND SERGOT, M.J. 1986. A logic-based calculus of events. New Gener. Comput. 4, 67-95. Google Scholar
- LESPt#RANCE, Y., LEVESQUE, H. J., AND REITER, R. 1997. A situation calculus approach to modeling and programming agents. In Foundations and Theories of Rational Agency, A. Rao and M. Wooldridge, eds. in press.Google Scholar
- LEVESQUE, H.J. 1996. What is planning in the presence of sensing? In Proceedings of the National Conference on Artificial Intelligence (AAAI'96). AAAI Press, Reston, Va., pp. 1139-1146. Google Scholar
- LEVESQUE, H. J., REITER, R., LESPt#RANCE, Y., LIN, F., AND SCHERL, R. 1997. GOLOG: A logic programming language for dynamic domains. J. Logic Prog. Special Issue on Actions, 31, 1-3, 59-83.Google Scholar
- LIFSCHITZ, V. 1991. Toward a metatheory of action. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR'91) (Los Altos, Calif.). J. Allen, R. Fikes, and E. Sandewall, eds. Morgan-Kaufmann, San Francisco, Calif., pp. 376-386.Google Scholar
- LIN, F., AND REITER, R. 1994. State constraints revisited. J. Logic Comput. Special Issue on Actions and Processes, 4, 655-678.Google Scholar
- LIN, F., AND REITER, R. 1997. How to progress a database. Artifi Int. 92, 131-167. Google Scholar
- MCCARTHY, J. 1968. Situations, actions and causal laws. In Semantic Information Processing, M. Minsky ed. HIT Press, Cambridge, Mass., pp. 410-417.Google Scholar
- MCCARTHY, J. 1977. Epistemological problems of artificial intelligence. In Proceedings of the 5th International Joint Conference on Artificial Intelligence (Cambridge, Mass.). pp. 1038-1044.Google Scholar
- MCDERMOTT, D. 1982. Non-monotonic logic. II. Nonmonotonic model theories. J. ACM, 29, 1 (Jan.), 33-57. Google Scholar
- MCILRAITH, S.A. 1997. Towards a formal account of diagnostic problem solving. Ph.D. thesis, Dept. Comput. Sci. Univ. Toronto, Toronto, Ontario, Canada. Google Scholar
- PEDNAULT, E. P.D. 1986. Toward a Mathematical Theory of Plan Synthesis. Ph.D. dissertation. Dept. Electrical Engineering, Stanford Univ. Stanford Calif. Google Scholar
- PEDNAULT, E. P.D. 1989. ADL: Exploring the middle ground between STRIPS and the situation calculus. In Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR'89). R. J. Brachman, H. Levesque, and R. Reiter, eds. Morgan-Kaufmann, San Francisco, Calif., pp. 324-332. Google Scholar
- PINTO, J.A. 1994. Temporal reasoning in the situation calculus. Ph.D. dissertation. Dept. Comput. Sci., Univ. Toronto, Toronto, Ont., Canada. Google Scholar
- PINTO, J. 1999. Occurrences and narratives as constraints in the branching structure of the situation calculus. J. Logic Comput., to appear, URL = ftp://lyrcc.ing.puc.cl/pub/jpinto/jlc.ps.gz.Google Scholar
- REITER, R. 1999. Knowledge in action: Logical foundations for describing and implementing dynamical systems. In preparation. Draft available at http://www.cs.toronto.edu/#cogrobo/.Google Scholar
- REITER, R. 1991. The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. In Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, Vladimir Lifschitz, ed. Academic Press, San Diego, Calif., pp. 359-380. Google Scholar
- REITER, R. 1993. Proving properties of states in the situation calculus. Artifi Int. 64, 337-351. Google Scholar
- REITER, R. 1995. On specifying database updates. J. Logic Prog. 25, 25-91.Google Scholar
- REITER, R. 1996. Natural actions, concurrency and continuous time in the situation calculus. In Principles of Knowledge Representation and Reasoning: Proceedings of the 5th International Conference (KR'96). L. C. Aiello, J. Doyle, and S. C. Shapiro, eds. Morgan-Kaufmann, San Francisco, Calif., pp. 2-13.Google Scholar
- REITER, R. 1998. Sequential, temporal GOLOG. In Principles of Knowledge Representation and Reasoning: Proceedings of the Sixth International Conference (KR'98). A. C. Cohn and L. K. Schubert, eds. Morgan-Kaufmann, San Francisco, Calif., pp. 547-556.Google Scholar
- SANDEWALL, E. 1994. Features and Fluents: The Representation of Knowledge about Dynamical Systems. Oxford University Press, Oxford, England. Google Scholar
- SCHUBEaT, L. K. 1990. Monotonic solution of the frame problem in the situation calculus: An efficient method for worlds with fully specified actions. In Knowledge Representation and Defeasible Reasoning. H. E. Kyberg, R. P. Loui, and G. N. Carlson, eds. Kluwer Academic Press. pp. 23-67.Google Scholar
- SHANAHAN, M.P. 1997. Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia. MIT Press, Cambridge, Mass. Google Scholar
- STOY, J.E. 1977. Denotational Semantics. MIT Press, Cambridge, Mass.Google Scholar
- WALDINGER, R. 1977. Achieving several goals simultaneously. In Machine Intelligence 8. E. Elcock and D. Michie, eds. Ellis Horwood, Edinburgh, Scotland, pp. 94-136.Google Scholar
Index Terms
- Some contributions to the metatheory of the situation calculus
Recommendations
On knowledge-based programming with sensing in the situation calculus
Special issue devoted to Robert A. KowalskiWe consider a class of knowledge-based Golog programs with sense actions. These programs refer explicitly to an agent's knowledge, and are designed to execute on-line, and under a dynamic closed-world assumption on knowledge. On-line execution of sense ...
Inductive situation calculus
Temporal reasoning has always been a major test case for knowledge representation formalisms. In this paper, we develop an inductive variant of the situation calculus in ID-logic, classical logic extended with inductive definitions. This logic has been ...
The Situation Calculus: A Case for Modal Logic
The situation calculus is one of the most established formalisms for reasoning about action and change. In this paper we will review the basics of Reiter's version of the situation calculus, show how knowledge and time have been addressed in this ...
Comments