TDDA16: Knowledge Representation in AI

Latest Information

• The monday, 8-10, week 9 seminar is cancelled.
• (98/02/11) Some slides now on-line. Beware, there are some bugs, some refer to articles you have not read.
• (98/02/07) Readings notes added. Schedule for weeks 7-8 added!
• (98/01/12) First Seminar: Friday, Jan 23, kl 10-12, GG31 (G-Hus/IDA)
• All course material is free and will be distributed on friday

This course provides an introduction to formal knowledge representation in AI. More specifically, we consider the problem of reasoning about action and change and its formal characterization in logic. Conceptually, the course consists of three parts:

1. In part one, we consider knowledge representation in general and a methodology for constructing reasoners for computing inferences from a knowledge base.
2. In part two, we focus on a particular application domain, that of reasoning about action and change. We consider the historical development of the frame, qualification, and ramification problems which arise when reasoning about dynamical systems. We also introduce a number of approaches to temporal reasoning and introduce the notion of preferential entailment and its characterization in terms of circumscription. We conclude this part of the course with a number of case studies which propose solutions to the frame problems.
3. In part three, we question the methodological practice used in the case studies and consider a proposal by Sandewall, described in the book

   Features and Fluents: A Systematic Apporach to the Representation of Knowledge about Dynamical Systems,
   Erik Sandewall,
   Oxford University Press, 1994.

   We introduce a systematic approach for studying the knowledge representation of dynamical systems. It is used for analyzing much of the work considered in part two of the course, and for constructing new logics of action and change which correct various anomalies in the case studies.

Module 1 - Laying the Foundations

1. First Order Logic, M. Davis
2. The Role(s) of Logic in Artificial Intelligence, D. Israel
3. Some Philosophical Problems from the Standpoint of AI, J. McCarthy and P. Hayes
4. Epistemological Problems in Artificial Intelligence, J. McCarthy

• Slides: Introduction.
• Slides: Introduction to KR.
• Notes on KR.

Module 2 - Tools and Techniques

1. Temporal Logics in AI: Semantical and Ontological Considerations, Y. Shoham
2. A Non-Reified Temporal Logic, F. Bacchus, J. Tenenberg, J. A. Koomen
3. Application of Theorem Proving to Problem Solving, C. Green
4. Circumscription, G. Brewka, Chapter 4 in Nonmonotonic Reasoning: Logical Foundations of Commonsense, 1991, Cambridge University Press.

• Notes on Temporal Logic.
• Notes on Circumscription.
• Slides: Temporal Logic, BTK.
• Slides: Temporal Logic, STL, SitCalc.
• Slides: Temporal Logic, Green.
• Slides: Circumscription I.
• Slides: Circumscription II.
• Exercises on formalisms.
• Exercises on circumscription.

Module 3 - Nonmonotonic Temporal Reasoning

1. Default Reasoning, Nonmonotonic Logics, and the Frame Problem, S. Hanks, D. McDermott
2. The Logic of Persistence, H. Kautz
3. Formal Theories of Action, V. Lifschitz
4. Monotonic Solution of the Frame Problem in the Situation Calculus, L. Schubert
5. The Frame Problem in the Situation Calculus: A Simple Solution (Sometimes) and a Completeness Result for Goal Regression, R. Reiter

• Notes on Approaches (I).
• Notes on Approaches (II).
• Slides: NM Temporal Logic I, Lifschitz, Kautz, Shoham.
• Slides: NM Temporal Logic II, Lifschitz, Haugh.

Module 4 - Back to the Future

1. The Problem with Solutions to the Frame Problem, L. Morgenstern
2. Nonmonotonic Temporal Reasoning, E. Sandewall, Y. Shoham

• Notes

Module 5 - The TAL Family of Logics

1. Reasoning about Action and Change using Occlusion, P. Doherty, Proceedings of the 11th European Conference on Artificial Intelligence, pp. 401-405, 1994.
2. Embracing Occlusion in Specifying the Indirect Effects of Actions, J. Gustafsson, P. Doherty
3. Reasoning about Actions in a Multi-Agent Environment, L. Karlsson, J. Gustafsson
4. Tackling the Qualification Problem using Fluent Dependency Constraints, P. Doherty, J. Kvarnström

• Notes
• Exercises on simple, sequential scenarios.
• Exercises on ramification, qualification and concurrency.

Module 5 - Features and Fluents

1. Features and Fluents, E. Sandewall

Schedule

Week 04

Friday, 10-12, GG31, patdo

Sem1. -- An overview of the course topics is provided, course material is distributed, and administrative details are discussed.

Week 07

Monday, 10-12, GG31, patdo

Sem2. -- We discuss knowledge representation in broad terms, the role of logic in AI, and different methodologies used in knowledge representation.

Reading: Module 1

Tuesday, 13-15, GG31, patdo

Thursday, 08-10, GG32, patdo

Sem3-4. -- In the third and fourth seminars, we will discuss temporal reasoning in general, including a number of techniques used to represent temporal facts. We will then study three existing temporal logics in detail that use these techniques. The techniques studied more or less cover the spectrum of logics used for temporal reasoning in AI.

Friday, 10-12, GG32, larka

Lek1. -- In this session, Lars will discuss the three temporal logics more concretely, do a number of exercises that involve representing action scenarios, and discuss the take-home exercises.

Reading: Module 2

Week 08

Monday, 08-10, GG31, patdo

Sem5. -- We will discuss the frame, qualification and ramification problems in terms of how they arose in attempting to do planning with monotonic versions of the situation calculus. We will consider the Monkey and Bananas problem used by Green and extend it iteratively until we have a reasonable syntactic representation of the problem, but still lack an essential element: nonmonotonic inference.

Tuesday, 08-10, GG32, patdo

Wednesday, 10-12, GG31, patdo

Sem6-7. -- In these sessions, we will discuss nonmonotonic reasoning and we will study a number of different forms of Circumscription in detail. We will also discuss logics of preferential entailment.

Thursday, 15-17, G33, larka

Lek2. -- In this session, Lars will do a number of practical exercises pertaining to Circumscription and preferential entailment. Take-home exercises will also be distributed.

Friday, 15-17, GG32, patdo

Sem8. -- In this session, we will discuss the Yale Shooting problem and approaches to its solution using chronological minimization and causal minimization.

Week 09

Tuesday, 15-17, GG33, larka

Sem9. -- In this session, we will discuss explanation closure as a solution to the frame problems.

Wednesday, 08-10, GG32, larka

Lek3. -- In this session, Lars will consider a number of scenarios using the methods discussed in the previous three sessions.

Wednesday, 15-17, GG32, patdo

sem10. -- In this session, we will discuss Features and Fluents and introduce the concept of inhabited dynamic systems and its associated underlying semantics. In addition, we will discuss the conceptual space of ontological and epistemological assumptions.

Friday, 13-15, GG32, patdo

Sem11. -- In this session, we will discuss Discrete Feature Logic, the temporal logic used in Features and Fluents to reason about action and change.

Week 10

Monday, 08-10, GG32, patdo

Sem12. -- PMON and the TAL family of Logics

Wednesday, 13-15, GG32, larka, joagu, jonkv

Sem13. -- TAL-C, TAL-R, TAL-Q

Thursday, 10-12, GG32, larka

Lek4. -- Lars will provide exercises for TAL-C, TAL-R, TAL-Q

Some useful Links

• The DLS algorithm is an algorithm for reducing second-order formulas to logically equivalent first-order formulas. You can test the experimental interactive implementation and try to reduce some of the circumscription axioms described in the course!
• The VITAL action scenario reasoning tool is a program written in Java which can be used to study action scenarios. You may create your own and analyze other scenarios.
• The European Colloquium for Spatial and Temporal Reasoning (ECSTER) is organized by the Compulog SIG for Spatial and Temporal Reasoning and it's web page contains a plethora of useful information relating to spatial and temporal reasoning.
• The reasoning about actions link has been compiled by Rob Miller and contains links to a large number of researchers actively working in the area of reasoning about actions and time.
• Electronic Transactions on Artificial Intelligence (ETAI) actions is a new on-line journal specializing in research in Artificial Intelligence. The most developed part of the transactions is currently the action and change research domain.

Additional Information

Patrick Doherty (Course Leader)
Department of Computer and Information Science
University of Linköping
S-581 83 Linköping, SWEDEN
Phone: +46 13 28 24 26
Telefax: +46 13 28 26 06
Room: FOA A1.291

Lars Karlsson (Course Assistant)
Department of Computer and Information Science
University of Linköping
S-581 83 Linköping, SWEDEN
Phone: +46 13 28 24 28
Telefax: +46 13 28 26 06
Room: FOA A1.287

Gunilla Norbäck (Course Administrator)
Department of Computer and Information Science
University of Linköping
S-581 83 Linköping, SWEDEN
Phone: +46 13 28 22 97
Telefax: +46 13 28 44 99
Room: G 1tr G1.208