Knowledge Representation and Reasoning

CMPT 411/721 Course Home Page
Fall 2019

General Information

• Classes:
  • MWF 14:30 - 15:20, AQ 3159

• Instructor: Jim Delgrande,
  • T 9015; Email: jim
  • Office Hours: Tuesday and Thursday 2:00-3:00

• TA: Turash Mosharraf
  • Email: turash_mosharraf
  • Office Hours: Monday 11:00-12:00 and Friday 12:00-1:00 in ASB 9810 (CSIL)

• Midterm Test: 8th week of class, exact date will be given shortly

• Final Exam: 11 Dec, 12:00, AQ 3003
  • You must be able to write the final exam

• Grading
  • 40% - 4 assignments
  • 20% - midterm test;
  • 40% - final exam.

• Letter grades will be assigned as follows:

  A+: >=90, A: 84-89, A-: 80-83,

  B+: 77-79, B: 74-76, B-: 70-73,

  C+: 67-69, C: 64-66, C-: 58-63,

  D: 50-57, F: < 50.

• If you have any questions about the grading, please check first with the TA. Please see me if you disagree with the TA.

Announcements

• Sept 20: Assignment 1 can now be handed in up until noon, Monday Sept 30.
• The midterm test will be on Oct 21.
• Oct 21: Assignment 2 can now be handed in up until noon, Monday Oct 28

Lecture Slides

Topic	Chapter in Text	Week
0. Overview		1
1. Introduction (Text slides)	Ch. 1	1
2. Propositional logic		1
3. First-order Logic	Ch. 2	2
4. Expressing Knowledge	Ch. 3	2
5. Resolution	Ch. 4	3,4
6. Definite Clause Reasoning	(Ch. 5)	4
6. Extended Definite Clause Reasoning	(Ch. 5)	5
7. Abductive Reasoning	Ch. 13	6
7. Answer Set Programming: Introduction		7,8
Answer Set Programming: Modelling		8
Answer Set Programming: ASP Solvers		9
8. Using ASP for Reasoning with Defaults	(Ch 11)	9
9. Description Logics	(Ch 9)	10,11
10. Argumentation		12
Preferences: CP-nets (optional)		13

Assignments

• Assignment 1 (due Sept 27 Sept 30)
• Assignment 2 (due Oct 21 Oct 28)
• Assignment 3 (due Nov 15)
• Assignment 4 (due Dec 2)

Course Materials

Text and related materials

• The text is available online via the SFU library.
• Here are slides based on the text. Note that the slides that I use differ slightly from these.

Datalog reference:

• What You Always Wanted to Know About Datalog (And Never Dared to Ask)
• In addition, almost any current database text will have a section on Datalog. The Ramakrishnan and Gehrke text is good, as that by Ullman and Widom.

Material on answer set programming:

• The User's Guide to the University of Postdam answer set solvers.
• Answer Set Solving in Practice. (The slides are based on material in this text.)
• AI Magazine Special Issue on ASP.
• Examples:
  • Two answer sets: twoas.lp
  • One answer set: oneas.lp
  • No answer set: noas.lp
  • Unsafe program: unsafe.lp
  • Safe program: safe.lp
  • Graph colouring: gc.lp
  • Graph colouring with hidden atoms: gchide.lp
  • N-queens: nqueens.lp
  • Flying birds: birds.lp

Material on Description Logics:

• The following is a good general overview of description logics:

  D. Nardi, R. J. Brachman.
  An Introduction to Description Logics.
  in The Description Logic Handbook,
  edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider,
  Cambridge University Press, 2002, pages 5-44.

• As well there is a recent general text (online access is available through SFU library):

  F. Baader and I. Horrocks and C. Lutz and U. Sattler,
  An Introduction to Description Logic,
  Cambridge University Press, 2017.

• Here is another DL reference that includes a description of ALC.
• There are various downloadable systems. One of the best known and developed is the protégé system.
• Other resources can be found at the DL web site

Argumentation:

• Here is the Besnard and Hunter paper: BesnardHunterTutorial.pdf

Preferences:

• Here is the original CP-nets paper: CPNets.JAIR04.pdf

KR resources

• The Handbook of Knowledge Representation, F. van Harmelen, V. Lifschitz, and B. Porter (eds.), Elsevier Science, 2008

  This is a collection of survey papers by leading researchers on areas of KR. It provides an excellent resource for going into a KR topic in more detail and depth but can be quite technical.

Relevant AI texts

• Artificial Intelligence: A Modern Approach, Stuart Russell and Peter Norvig, Prentice Hall, Third edition, 2010.

  This is the standard AI text; it is detailed, and has good material on logical agents, reasoning, and (particularly) dealing with uncertainty.

• Artificial Intelligence: Foundations of Computational Agents, David Poole and Alan Mackworth, Cambridge University Press, 2010.

  Another nice text, with something of a logic-programming slant. It can be accessed at http://artint.info/index.html.

Logic References

• Introduction to Mathematical Logic, E. Mendelson
• A Mathematical Introduction to Logic, H. Enderton