A note on situation calculus
Keywords:
Situation calculus , LTS model , Modal logic, Knowledge representationAbstract
Situation calculus is a logical language for expressing change. Situations, actions, and fluents are the three core ideas of situation calculus. As agents perform actions, the dynamic environment changes from one situation to another. Fluents are functions that change with the situations and describe the effects of actions. They can be seen as properties of the world that come into existence when an action is initiated and disappear when another action ends. While situation calculus is powerful, it often struggles with complexity and verbosity when modeling dynamic systems, which can make it challenging to manage and reason about in large-scale settings. To address these limitations, we propose using Labelled Transition Systems (LTS). The LTS model, based on graph models of modal logic, offers a more concise and formal representation of system behaviors. The LTS-based method aims to provide a simpler and more intuitive framework for modeling dynamic settings, thereby improving system representation clarity and efficiency. This allows for higher scalability and more efficient verification and validation processes, which are critical in complex systems. Finally, the LTS model seeks to bridge the theoretical expressiveness of situation calculus with the practical requirements of system design and analysis.
References
[1] Mccarthy, j, & Hayes, P. . (1969). Some philosophical problems from standpoint of artificial intelligence. In Readings in artificial intelligence (pp. 463–502). Elsevier.
[2] Farinelli, A., Finzi, A., & Lukasiewicz, T. (2007). Team programming in golog under partial observability. IJCAI international joint conference on artificial intelligence, 6(12), 2097–2102.
[3] Ferrein, A., Fritz, C., & Lakemeyer, G. (2005). Using golog for deliberation and team coordination in robotic soccer. AI - artificial intelligence, 19(1), 24–31.
[4] Ghaderi, H., Levesque, H., & Lespérance, Y. (2007). Towards a logical theory of coordination and joint ability. Proceedings of the international conference on autonomous agents (pp. 544–546). Association for Computing Machinery. DOI: 10.1145/1329125.1329223
[5] Reiter, R. (1991). The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. Artificial and mathematical theory of computation, 3, 359–380. DOI:10.1016/b978-0-12-450010-5.50026-8
[6] Sardina, S., De Giacomo, G., Lespérance, Y., & Levesque, H. J. (2004). On the semantics of deliberation in IndiGolog - From theory to implementation. Annals of mathematics and artificial intelligence, 41(2–4), 259–299. DOI:10.1023/B:AMAI.0000031197.13122.aa
[7] Scherl, R. B. (2022). A situation-calculus model of knowledge and belief based on thinking about justifications. CEUR workshop proceedings, 3197, 104–114.
[8] De Giacomo, G., Felli, P., Logan, B., Patrizi, F., & Sardiña, S. (2022). Situation calculus for controller synthesis in manufacturing systems with first-order state representation (extended abstract). IJCAI international joint conference on artificial intelligence (pp. 5722–5726). Elsevier. DOI: 10.24963/ijcai.2022/798
[9] De Giacomo, G., Ternovska, E., & Reiter, R. (2020). Non-terminating processes in the situation calculus. Annals of mathematics and artificial intelligence, 88(5–6), 623–640. DOI:10.1007/s10472-019-09643-9
[10] Baier, J. A., & McIlraith, S. A. (2022). Knowledge-based programs as building blocks for planning. Artificial intelligence, 303, 103634. DOI:10.1016/j.artint.2021.103634
[11] Knight, S., Mardare, R., & Panangaden, P. (2011). An epistemic logic for labelled transition systems. McGill University. https://www.cs.mcgill.ca/~prakash/Pubs/completeness_paper.pdf
[12] Tretmans, J. (2008). Model based testing with labelled transition systems. In Lecture notes in computer science (Vol. 4949 LNCS, pp. 1–38). Springer. DOI: 10.1007/978-3-540-78917-8_1
[13] Baier, C., & Katoen, J.-P. (2008). Principles Of model checking (Vol. 950). MIT Press.
[14] Giannakopoulou, D., & Magee, J. (2003). Fluent model checking for event-based systems. Proceedings of the acm sigsoft symposium on the foundations of software engineering (pp. 257–266). IEEE. DOI: 10.1145/940071.940106
[15] Hughes, G. E., & Cresswell, M. J. (2012). A new introduction to modal logic. Routledge.
[16] Zadeh, L. A. (2014). A note on modal logic and possibility theory. Information sciences, 279, 908–913. DOI:10.1016/j.ins.2014.04.002
[17] Russell, S., & Norvig, P. (2020). Artificial intelligence: A modern approach. Pearson.
Metrics
