Lectures on Reasoning about Action in the Situation Calculus

part of Elective in AI - HRI & Reasoning Agents with part 1 on HRI by Iocchi and part 3 Game-theoretic Approach to Planning and Synthesis by De Giacomo
and National PhD Program in AI
April 2024

Dipartamento di Ingegneria informatica, automatica e gestionale,
Sapienza Università di Roma

Brief Description

This short course provides an introduction to reasoning about action in AI. We present the Situation Calculus, a first-order logic framework for reasoning about action. After presenting the language, we discuss how we can address various representational problems (such as the frame problem) and how we can perform reasoning. We also discuss how high-level programs can be defined and reasoned about in the Situation Calculus. Finally, we discuss an extension to represent nondeterministic domains.

What's new

May 29: Class presentations will be on May 30 15:00-19:00 in A5 and A6; see below for the schedule; presentations will be in person; students who are not presenting may attend in person or on Zoom, click here (Meeting ID: 986 7706 9399 Passcode: 157135)
May 14: Class presentations will be on May 27 and/or May 30 during class times.
April 23: There is no class on April 25 due to the Festa della Liberazione holiday. The next and final class is on April 29, when we will discuss how to represent and reason about nondeterministic domains in the situation calculus and wrap up the course..
April 8: The first lecture will be on April 11 15:00-17:00 in A5&6.

Instructor

Prof. Yves Lespérance
Office: B213
Email: lesperan at eecs.yorku.ca

Lectures

Monday 17:00-19:00 in A2 and Thursday 15:00-17:00 in A5&6.

Evaluation

If you are taking the course for credit, see the instructors to arrange evaluation. See suggestions for presentations at the bottom of this page.

Schedule

Lecture 1 (Hour 1 and Hour 2)(April 11): Introduction to Reasoning about Action in the Situation Calculus
Lecture 2 (Hour 3 and Hour 4)(April 15): Reasoning abourt Action in the Situation Calculus (cont.)
Lecture 3 (Hour 5 and Hour 6)(April 18): High-Level Programming in the Situation Calculus: Golog and ConGolog
Lecture 4 (Hour 7 and Hour 8)(April 22): High-Level Programming in the Situation Calculus: Golog and ConGolog (cont.)
Lecture 5 (Hour 9 and Hour 10)(April 29): The Nondeterministic Situation Calculus

Readings and Lecture Transparencies

Lecture 1 (Hour 1 and Hour 2)(April 11) and Lecture 2 (Hour 3 and Hour 4)(April 15): Introduction to Reasoning About Action in the Situation Calculus.
Lecture transparencies (updated!), lecture video recording for April 11, lecture video recording for April 15
Required readings:
Just read the lecture transparencies ahead of time.
References:
Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001, Chapters 1-5, Publisher site, Book home page.

Lecture 3 (Hour 5 and Hour 6)(April 18) and Lecture 4 (Hour 7 and Hour 8)(April 22: High-level Programming in the Situation Calculus: Golog and ConGolog.
Lecture transparencies (updated!), lecture video recording for April 18, lecture video recording for April 22
Required readings:
Just read the lecture transparencies.
References:
Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001, Chapters 1-5, Publisher site, Book home page.
Hector J. Levesque, Raymond Reiter, Yves Lespérance, Fangzhen Lin, Richard B. Scherl: GOLOG: A Logic Programming Language for Dynamic Domains. J. Log. Program. 31(1-3): 59-83 (1997)
Giuseppe De Giacomo, Yves Lespérance, Hector J. Levesque: ConGolog, a concurrent programming language based on the situation calculus. Artif. Intell. 121(1-2): 109-169 (2000)

Lecture 5 (Hour 9 and Hour 10)(April 29) The Nondeterministic Situation Calculus.
Lecture transparencies (updated!), lecture video recording for April 29.
References:
Giuseppe De Giacomo, Yves Lespérance: The Nondeterministic Situation Calculus. KR 2021:, 216-226.

References and Links

Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001. Publisher site, Book home page.

Hector J. Levesque, Raymond Reiter, Yves Lespérance, Fangzhen Lin, Richard B. Scherl: GOLOG: A Logic Programming Language for Dynamic Domains. J. Log. Program. 31(1-3): 59-83 (1997)

Giuseppe De Giacomo, Yves Lespérance, Hector J. Levesque: ConGolog, a concurrent programming language based on the situation calculus. Artif. Intell. 121(1-2): 109-169 (2000)

Ronald J. Brachman and Hector J. Levesque, Knowledge Representation and Reasoning, Elsevier/Morgan Kaufmann, 2004.

Russell, S.J. and Norvig, P., Artificial Intelligence: A Modern Approach, 4th edition Prentice Hall, 2020. ISBN 978-0134610993.
Authors' web site, Publisher's web site.

Wooldridge M., An Introduction to Multiagent Systems - Second Edition, Wiley, 2009.

Clocksin, W.F. and Mellish, C.S., Programming in Prolog, Springer Verlag, New York, 1987. Third edition.

Presentation Schedule on May 30 (tentative)

15:00-16:00 Francesco Petri, Flavio Maiorana, and Charlotte Primiceri
Richard B. Scherl, Hector J. Levesque: Knowledge, action, and the frame problem. Artificial Intelligence 144(1-2): 1-39 (2003). [link to paper]

16:00-16:40 Amine Ahardane and Syrine Enneifer
Giuseppe De Giacomo, Yves Lespérance, Adrian R. Pearce: Situation Calculus Game Structures and GDL. ECAI 2016: 408-416 [link to paper]

16:50-17:50 Luigi Gallo, Montella, and Ricci
Chapter 7 "Time, Concurrency, and Processes" of Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001 [link to paper]

17:50-18:10 Andrea Gervasio
Craig Boutilier, Raymond Reiter, Mikhail Soutchanski, Sebastian Thrun: Decision-Theoretic, High-Level Agent Programming in the Situation Calculus. AAAI/IAAI 2000: 355-362 [link to paper]

18:10-18:50 Giovanni D'Amico and Lorenzo Pante
Weinan He, Canming Huang, Zhanhao Xiao, Yongmei Liu: Exploring the Capacity of Pretrained Language Models for Reasoning about Actions and Change. ACL (1) 2023: 4629-4643 [link to paper] and
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, Animesh Garg: ProgPrompt: program generation for situated robot task planning using large language models. Auton. Robots 47(8): 999-1012 (2023) [link to paper]