Skip to main content
SpringerLink
Log in

The Situation Calculus: A Case for Modal Logic

  • Published:
Journal of Logic, Language and Information Aims and scope Submit manuscript

Abstract

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 framework, and point to some of the weaknesses of the situation calculus with respect to time. We then present a modal version of the situation calculus where these problems can be overcome with relative ease and without sacrificing the advantages of the original.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bacchus F., Kabanza F. (2000) Using temporal logics to express search control knowledge for planning. Artificial Intelligence 116(1–2): 123–191

    Article  Google Scholar 

  • Bacchus F., Halpern J.Y., Levesque H. (1999) Reasoning about noisy sensors and effectors in the situation calculus. Artificial Intelligence 111(1–2): 171–208

    Article  Google Scholar 

  • Baltag, A., Moss L. S., & Solecki, S. (1998). The logic of public announcements, common knowledge, and private suspicions. In Proceedings of the 7th conference on theoretical aspects of rationality and knowledge (TARK-VII) (pp. 43–56).

  • Bienvenu, M., Fritz, Ch., & McIlraith, S. A. (2006). Planning with qualitative temporal preferences. In Proceedings of the tenth international conference on principles of knowledge representation and reasoning (KR’2004) (pp. 134–144). AAAI Press.

  • Blackburn P., Kamps J., Marx M. (2001) Situation calculus as hybrid logic: First steps. In: Brazdil P., Jorge A. (eds) Progress in artificial intelligence. Lecture notes in artificial intelligence 2258. Springer, New York, pp 253–260

    Google Scholar 

  • Boutilier, C., Reiter, R., Soutchanski, M., & Thrun, S. (2000). Decision-theoretic, high-level agent programming in the situation calculus. In Proceedings of AAAI-00 (pp. 355–362). AAAI Press.

  • Burgard W., Cremers A.B., Fox D., Hähnel D., Lakemeyer G., Schulz D. et al (1999) Experiences with an interactive museum tour-guide robot. Artificial Intelligence 114(1–2): 3–55

    Article  Google Scholar 

  • Carbone, A., Finzi A., Orlandini, A., Pirri, F., & Ugazio, G. (2005). Augmenting situation awareness via model-based control in rescue robots. In Proceedings of IROS-2005. Edmonton, Canada.

  • Castilho M. A., Gasquet O., Herzig A. (1999) Formalizing action and change in modal logic I: The frame problem. Journal of Logic and Computation 9(5): 701–735

    Article  Google Scholar 

  • Classen, J., & Lakemeyer, G. (2008). A logic for non-terminating Golog programs. In Proceedings of the eleventh conference on principles of knowledge representation and reasoning (KR 2008) (pp. 589–599). AAAI Press.

  • Demolombe, R. (2003). Belief change: From Situation Calculus to Modal Logic. Journal of Applied Non-Classical Logics, 13(2).

  • De Giacomo G., Lesperance Y., Levesque H. J. (2000) Congolog, a concurrent programming language based on the situation calculus. Artificial Intelligence 121: 109–169

    Article  Google Scholar 

  • Demolombe R., Herzig A., Varzinczak I. (2003) Regression in modal logic. Journal of Applied Non-Classical Logics 13(2): 165–185

    Article  Google Scholar 

  • Emerson E., Halpern J. Y. (1986) “Sometimes” and “not never” revisited: On branching versus linear time temporal logic. Journal of the ACM 33(1): 151–178

    Article  Google Scholar 

  • Fagin R., Halpern J., Moses Y., Vardi M. (1995) Reasoning about Knowledge. MIT Press, Cambridge, MA

    Google Scholar 

  • Ferrein A., Fritz C., Lakemeyer G. (2004) On-line decision-theoretic Golog for unpredictable domains. In: Biundo S., Frhwirt T., Palm G. (eds) KI2004: Advances in artificial intelligence. Springer, New York

    Google Scholar 

  • Fikes, R., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. In Proceedings of the second international joint conference on artificial intelligence (IJCAI-71) (pp. 608–620).

  • Gabaldon, A. (2004). Precondition control and the progression algorithm. In Proceedings of the ninth international conference on principles of knowledge representation and reasoning (KR’2004) (pp. 634–664). AAAI Press.

  • Grosskreutz H., Lakemeyer G. (2003) cc-Golog—An action language with continous change. Logic Journal of the IGPL 11(2): 179–221

    Article  Google Scholar 

  • Green, C. (1969). Application of theorem proving to problem solving. In Proceedings of the 1st international joint conference on artificial intelligence (IJCAI-69) (pp. 219–240). Washington, DC.

  • Harel D. (1984) Dynamic logic. In: Gabbay D., Guenther F. (eds) Handbook of philosophical logic. D. Reidel, LK, pp 497–604

    Google Scholar 

  • Herzig, A., Lang, J., Longin, D., & Polacsek, T. (2000). A logic for planning under partial observability. In Proceedings of AAAI-2000. AAAI Press.

  • Hintikka J. (1962) Knowledge and belief. Cornell University Press, Ithaca

    Google Scholar 

  • Hughes G., Cresswell M. (1968) An introduction to modal logic. Methuen, London

    Google Scholar 

  • Kripke S. A. (1963) Semantical considerations on modal logic. Acta Philosophica Fennica 16: 83–94

    Google Scholar 

  • Lakemeyer, G., & Levesque, H. J. (2004). Situations si, situation terms no. In Proceedings of the ninth international conference on principles of knowledge representation and reasoning (KR 2004) (pp. 516–526). AAAI Press.

  • Lakemeyer, G., & Levesque, H. J. (2005). A useful fragment of the situation calculus. In Proceedings of the nineteenth international joint conference on artificial intelligence (IJCAI-05) (pp. 490–496).

  • Lakemeyer, G., & Levesque, H. J. (2009). A semantic characterization of a useful fragment of the situation calculus with knowledge. In L. Morgenstern, V. Lifshitz & S. McIlraith (Eds.), Special issue in honor of John McCarthy, artificial intelligence. Elsevier (to appear).

  • Levesque H. J., Lakemeyer G. (2001) The logic of knowledge bases. MIT Press, Cambridge, MA

    Google Scholar 

  • Levesque H. J., Lakemeyer G. (2008) Cognitive robotics. In: Harmelen F., Lifschitz V., Porter B. (eds) Handbook of knowledge representation. Elsevier, Amsterdam, pp 869–886

    Chapter  Google Scholar 

  • Levesque H. J., Reiter R., Lespérance Y., Lin F., Scherl R. B. (1997) Golog: A logic programming language for dynamic domains. Journal of Logic Programming 31: 59–84

    Article  Google Scholar 

  • Lutz, C. (2006). Complexity and succinctness of public announcement logic. In Proceedings of the fifth international joint conference on autonomous agents and multiagent systems (pp. 137–143).

  • McCarthy, J. (1968). Situations, actions and causal laws. Technical report, Stanford University, 1963 [also in M. Minsky (Ed.), Semantic information processing (pp. 410–417). Cambridge, MA: MIT Press].

  • McIlraith, S., & Son, T. C. (2002). Adapting Golog for composition of semantic web services. In Proceedings of the eighth international conference on principles of knowledge representation and reasoning (pp. 482–493). San Francisco: Morgan Kaufmann.

  • Moore R. C. (1985) A formal theory of knowledge and action. In: Hobbs J. R., Moore R. C. (eds) Formal theories of the commonsense world. Ablex, Norwood, NJ, pp 319–358

    Google Scholar 

  • Pinto J. (1998) Integrating discrete and continuous change in a logical framework. Computational Intelligence 14(1): 39–88

    Article  Google Scholar 

  • Prior A. (1967) Past, present and future. Oxford University Press, Oxford

    Google Scholar 

  • Reiter, R. (1991). The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. In V. Lifschitz (Ed.), Artificial intelligence and mathematical theory of computation (pp. 359–380). Academic Press.

  • Reiter R. (2001a) Knowledge in action: Logical foundations for describing and implementing dynamical systems. MIT Press, Cambridge, MA

    Google Scholar 

  • Reiter, R. (2001b). On knowledge-based programming with sensing in the situation calculus. ACM Transactions on Computational Logic, 433–457.

  • Scherl R. B., Levesque H. J. (2003) Knowledge, action, and the frame problem. Artificial Intelligence 144(1–2): 1–39

    Article  Google Scholar 

  • Shanahan M. (1997) Solving the frame problem: A mathematical investigation of the common sense law of inertia. MIT Press, Cambridge, MA

    Google Scholar 

  • van Benthem, J. (2009). Situation calculus meets modal logic. In L. Morgenstern, V. Lifshitz & S. McIlraith (Eds.), Special issue in honor of John McCarthy, artificial intelligence. Elsevier (to appear).

  • van Ditmarsch, H., Herzig, A., & de Lima, T. (2007). Optimal regression for reasoning about knowledge and actions. In Proceedings of the twenty-second conference on artificial intelligence (AAAI-07) (pp. 1070–1075).

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, RWTH Aachen University, Aachen, Germany

    Gerhard Lakemeyer

Authors
  1. Gerhard Lakemeyer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gerhard Lakemeyer.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lakemeyer, G. The Situation Calculus: A Case for Modal Logic. J of Log Lang and Inf 19, 431–450 (2010). https://doi.org/10.1007/s10849-009-9117-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10849-009-9117-6

Keywords

Search

Navigation