Provably correct theories of action

ABSTRACT

We investigate logical formalization of the effects of actions in the situation calculus. We propose a formal criterion against which to evaluate theories of deterministic actions. We show how the criterion provides us a formal foundation upon which to tackle the frame problem, as well as its variant in the context of concurrent actions. Our main technical contributions are in formulating a wide class of monotonic causal theories that satisfy the criterion, and showing that each such theory can be reformulated succinctly in circumscription.

REFERENCES

• 1: Andrew B. Baker, Nonmonotonic reasoning in the framework of situation calculus, Artificial Intelligence, v.49 n.1-3, p.5-23, May 1991 [doi>10.1016/0004-3702(91)90004-4 ]
• 2: ~BAKER, m. B., AND GINSBERG, M. L. 1989. Temporal projection and explanation. In Proceedings' ~of the llth h, ternational Joint Conference on Artificial hztelligence (IJCAI-89). Morgan- ~Kaufmann, San Mateo, Calif., pp. 906-911.
• 3: ~CLARK, K. L. 1978. Negation as failure. In Logics and Databases, H. Gallaire and J. Minker, eds. ~Plenum Press, New York, pp. 293-322.
• 4: ~GELFOND, M., L~FSCHrrZ, V., AND RABINOV, A. 1991. What are the limitations of the situation ~calculus? In Working Notes of ttle AAAI Spring Symposium on the Logical Formalizations of ~Comrnonsense (Stanford, Calif.). AAAI Press, Menlo Park, Calif., pp. 59-69.
• 5: ~GEORGEFF, M. P. 1986. The representation of events in multiagent domains. In Proceedings of ~the 5th National Conference on Artificial Intelligence ( AAAI-86) (Philadelphia, Pa.). AAAI Press, ~Menlo Park, Calif., pp. 70-75.
• 6: S. Hanks , D. McDermott, Nonmonotonic logic and temporal projection, Artificial Intelligence, v.33 n.3, p.379-412, Nov. 1987 [doi>10.1016/0004-3702(87)90043-9 ]
• 7: ~HAUGH, B. 1987. Simple causal minimizations for temporal persistence and projection. In ~Proceedings of the 6th National Conference on Artificial Intelhgence (AAAI-87). AAAI Press, ~Menlo Park, Calif., pp. 218-233.
• 8: ~KAUTZ, H. 1986. The logic of persistence. In Proceedings of the 5th National Conference on ~Artificial Intelligence (AAAI-86). (Philadelphia, Pa.). AAAI Press, Menlo Park, Calif.
• 9: ~LIFSCHITZ, V. 1985, Computing circumscription. In Proceedings of the 9th International Joint ~Conference on Artificial Intelligence (IJCA1-85). Morgan-Kaufmann, San Mateo, Calif.
• 10: ~LIFSCHITZ, V. 1986. Pointwise circumscription. In Proceedings of the 5th National Conference on ~Artificial Intelligence (AAAI-86) (Philadelphia, Pa.). AAAI Press, Menlo Park, Calif., pp. ~406-410.
• 11: ~LIFSCHITZ, V. 1987a. Formal theories of action. In Proceedings of the lOth International Joint ~onference on A~:tificial Intelligence (IJCAI-87). Morgan-Kaufmann, San Mateo, Calif., pp. ~966-972.
• 12: V. Lifschitz, On the declarative semantics of logic programs with negation, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 13: Vladimir Lifschitz, Frames in the space of situations (research note), Artificial Intelligence, v.46 n.3, p.365-376, Dec. 1990 [doi>10.1016/0004-3702(90)90021-Q ]
• 14: ~LIFSCH1TZ, V. 1991. Toward a meta-theory of action. In Proceedings of the 2nd International ~Con)~erence on Princtples of Knowledge Representation and Reasoning (KR'91), J. Allen, R. Fikes, ~and E. Sandewall, eds. Morgan-Kaufmann, San Mateo, Calif., pp. 376-386.
• 15: Vladimir Lifschitz , Arkady Rabinov, Miracles in formal theories of action, Artificial Intelligence, v.38 n.2, p.225-237, March 1989 [doi>10.1016/0004-3702(89)90059-3 ]
• 16: ~Louh R. 1987. Response to Hanks and McDermott: Temporal evolution of beliefs and beliefs ~about temporal evolution. Cogn. Sct. 11.
• 17: John McCarthy, Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence, v.28 n.1, p.89-116, Feb. 1986 [doi>10.1016/0004-3702(86)90032-9 ]
• 18: ~MCCARTHY, J., AND HAYES, P. 1969. Some phdosophical problems from the standpoint of ~artificial intelligence. In Machme Intelligence, vol. 4, B. Meltzer and D. Michie, eds. Edinburgh ~Umversity Press, Edinburgh, England, pp. 463-502.
• 19: ~MORGENSTERN, L., AND STEIN, L. A. 1988. Why things go wrong: A formal theory of causal ~reasoning. In Proceedings of the 7th Nattonal Conference on Artificial Intelligence (AAAI-88). ~AAAI Press, Menlo Park, Calif. pp. 518-523.
• 20: Edwin P. D. Pednault, ADL: exploring the middle ground between STRIPS and the situation calculus, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.324-332, December 1989
• 21: David Peleg, Concurrent dynamic logic, Journal of the ACM (JACM), v.34 n.2, p.450-479, April 1987 [doi>10.1145/23005.23008]
• 22: ~RE~TER, R. 1978. On closed world data bases. In Logics and Data Bases, H. Gallaire and J. ~Minker, eds. Plenum Press, New York.
• 23: ~REITER, R. 1982. Circumscription implies predicate completion (sometimes). In Proceedmgs of ~AAAI-82. pp. 418-420.
• 24: Raymond Reiter, The frame problem in situation the calculus: a simple solution (sometimes) and a completeness result for goal regression, Artificial intelligence and mathematical theory of computation: papers in honor of John McCarthy, Academic Press Professional, Inc., San Diego, CA, 1991
• 25: ~SCHUBERT, L. K. 1990. Monotonic solution to the frame problem in the situation calculus: an ~efficient method for worlds with fully specified actions. In Knowledge Representation and ~Defeasible Reasoning, H. Kyberg, R. Loui, and G. Carlson, eds. Kluwer Academic Press, Boston, ~Mass., pp. 23-67.
• 26: Y. Shoham, Chronological ignorance: experiments in nonmonotonic temporal reasoning, Artificial Intelligence, v.36 n.3, p.279-331, October 1988 [doi>10.1016/0004-3702(88)90085-9 ]
• 27: Jay C. Weber, On the representation of concurrent actions in the situation calculus, Proceedings of the eighth biennial conference of the Canadian Society for Computational Studies of Intelligence on CSCSI-90, p.28-32, July 1990, University of Ottawa, Ottawa, Canada
• 28: ~W~NSLETT, M. S. 1988. Reasoning about actions using a possible models approach. In Proceed- ~ings of the 7th National Conference on Artificial Intelligence ( AAAI-88). AAAI Press, Menlo Park, ~Calif.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Human Factors, Theory

Keywords:
concurrent actions, frame problem, reasoning about actions, temporal reasoning