Proceedings

Reasoning with Incomplete Initial Information and Nondeterminism in Situation Calculus

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Temporal Reasoning. Pages 1434-1439.

© 1997 International Joint Conferences on Artificial Intelligence

Abstract

Situation Calculus is arguably the most widely studied and used formalism for reasoning about action and change. The main reason for its popularity is the ability to reason about different action sequences as explicit objects. In particular, planning can be formulated as an existence problem. This paper shows how these properties break down when incomplete information about the initial state and nondeterministic action effects are introduced, basically due to the fact that this incompleteness is not adequately manifested on the object level. A version of Situation Calculus is presented which adequately models the alternative ways the world can develop relative to a choice of actions.

  1. [AAAI96, 1996] Proceedings of the Thirteenth National Conference on Artificial Intelligence. AAAI Press, Menlo Park, California, 1996.
  2. [Baker, 1989] Andrew B. Baker. A simple solution to the Yale shooting problem. In Principles of Knowledge Representation and Reasoning: Proceedings of the First International Conference.
  3. Morgan Kaufmann, 1989.
  4. [Davis, 1994] Ernest Davis. Knowledge preconditions for plans. Journal of Logic and Computation, 4(5):721- 766, October 1994.
  5. [Doherty, 1994] Patrick Doherty. Reasoning about ac- tion and change using occlusion. In Proceedings of the Eleventh European Conference on Artificial Intel- ligence. John Wiley & Sons, 1994.
  6. [Fikes and Nilsson, 1971] Richard E. Fikes and Nils J. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial In- telligence, 2:189-208, 1971. IJCAI
  7. [Kowalski and Sergot, 1986] R. A. Kowalski and M. Ser- got. A logic-based calculus of events. New Generation Computing, 4:67-95, 1986.
  8. [Levesque, 1996] Hector J. Levesque. What is planning in the presence of sensing? In AAAI96 [1996].
  9. [Lifschitz, 1985] Vladimir Lifschitz. Computing circum- scription. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pages 121- 127.
  10. Morgan Kaufmann, 1985.
  11. [Lifschitz, 1988] Vladimir Lifschitz. Pointwise circum- scription. In M. Ginsberg, editor, Readings in Non- monotonic Reasoning.
  12. Morgan-Kauffmann, 1988.
  13. [Lin, 1996] Fangzhen Lin. Embracing causality in speci- fying the indeterminate effects of actions. In AAAI96 [1996].
  14. [Manna and Waldinger, 1987] Zohar Manna and Richard Waldinger. A theory of plans. In M.P. Georgeff and A.L. Lansky, editors, Reason- ing about Actions and Plans: Proceedings of the 1986 Workshop. Morgan Kaufmann, 1987.
  15. [McCarthy and Hayes, 1969] John McCarthy and Patrick J. Hayes. Some philosophical problems from the standpoint of artificial intelligence. Machine Intelligence, 4:463-502, 1969.
  16. [McCarthy, 1979] John McCarthy. First order theories of individual concepts and propositions. Machine In- telligence, 9, 1979. 1440
  17. T EMPORAL R EASO NIN G [Moore, 1985]
  18. Robert C. Moore. A formal theory of knowledge and action. In J.R. Hobbs and R.C. Moore, editors, Formal Theories of the Commonsense World, chapter 9. Ablex, Norwood, New Jersey, 1985.
  19. [Peot and Smith, 1992] M. Peot and D. Smith. Con- ditional nonlinear planning. In Proceedings of the First International Conference on Artificial Intelli- gence Planning Systems. Morgan Kaufmann, 1992.
  20. [Pratt, 1976] V. Pratt. Semantical considerations on Floyd-Hoare logic. In Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, 1976.
  21. [Reiter, 1991] Ray Reiter. The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. In V. Lifs- chitz, editor, Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John Mc- carthy, pages 359-360. Academic Press, 1991.
  22. [Reiter, 1996] Ray Reiter. Natural actions, concurrency and continuous time in the situation calculus. In Principles of Know ledge Representation and Reason- ing: Proceedings of the Fifth International Confer- ence. Morgan Kaufmann, 1996.
  23. [Rosenschein, 1981] Stanley J. Rosenschein. Plan syn- thesis: A logical perspective. In Proceedings of the Seventh International Joint Conference on Artificial Intelligence, pages 331-37. IJCAI
  24. Morgan Kaufmann, 1981.
  25. [Sandewall, 1994] Erik Sandewall. Features and Fluents. Oxford Press, 1994.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards