EECS 3401 3.0
Introduction to Artificial Intelligence and Logic Programming
Fall 2018
Department of Electrical
Engineering & Computer Science,
York University
Course Description
Artificial Intelligence (AI) deals with how to build systems that can
operate in an intelligent fashion. In this course, we examine
fundamental concepts in AI: knowledge representation and reasoning,
search, constraint satisfaction, reasoning under uncertainty, etc. The
course also introduces logic programming, a programming paradigm based
on predicate logic, where one specifies problems in a declarative way
and one can use the language to search for a solution. Students will
learn how to develop programs in Prolog to solve AI problems.
The course covers the following topics:
- Introduction to Artificial Intelligence, intelligent agents.
- Logical representations, first-order logic syntax and semantics,
use in knowledge representation.
- Basics of logic programming and Prolog, syntax, backchaining procedure, artithmetic, lists.
- Inference in first order logic, unification, resolution.
- Reasoning with Horn theories, SLDNF resolution, Prolog control
flow, backtracking, cut, 2nd order features, closed world assumption, negation as failure, default reasoning.
- Uninformed search.
- Informed search.
- Constraint satisfaction and backtracking search.
- Supervised learning.
- Reasoning about Action and Planning.
- Uncertain reasoning, Bayes Nets.
- Planning under Uncertainty, Markov Decision Processes.
- Reinforcement learning.
Learning Outcomes
- Define the main objectives of artificial intelligence.
- Describe how first-order predicate logic forms the basis of logic programming.
- Write logic programs in Prolog.
- Use and modify heuristic state-space search algorithms such
as A*, RTA* and IDA*.
- Represent knowledge in a small domain using predicate logic
and use the representation to build a logical database for a
knowledge-based expert system.
- Describe and use some other AI techniques including backward
and forward chaining, Bayesian networks, game search and constraint satisfaction, grammars for natural language processing.
What's New
- Dec. 7: There will be a special office hour at noon today Dec 7.
Also on Dec 10, the office hour will be at 11am instead of 5pm.
- Dec. 4: The final exam will be held on December 7 at 2pm in DB
0010. The exam covers all the material that was seen in the course
this term. There will be some questions on Prolog and material seen in
Weeks 1 to 6, but more emphasis on the material seen in Weeks 7 to
13. Make sure you understand the different search algorithms and how
they work on concrete examples. We have seen many such examples in
class. To practice, you can do can do the following exercises in
Russell and Norvig: Chapter 3, exercies 3 and 9, and Chapter 6
exercise 2 (another good exercise for Chapter 6 is to apply
backtracking search to the Australia map colouring, with and without
forward checking), Chapter 10, exercises 3 and 15, Chapter 14,
exercise 1, Chapter 17, exercise 1, Chapter 18, exercise 6; see also
the practice exercises given for the midterm test.
-
Dec 4: Assignment 3 may be submitted without penalty until Dec 10
at noon. To hand in your report for this assignment, submit your
answers to question 1 as a pdf file and your code and test results for
question 2 electronically; see the
updated Assignment 3 handout. You may
also submit your answers to question 1 on paper. In this case, use the
EECS 3401 drop box in the LAS building.
- Nov 22: Links to audio recordings of the make up lecture on 9 Nov
2018 have been posted; they can be found in the Readings and Lecture
Transparencies section below under Week 8 and Week 9.
- Nov 21: The deadline for submitting Assignment 2 had been extended to
November 24 at 09:00.
-
Nov 21: Assignment 3 is out; it is due
on December 4 at 23:59; however it can be submitted without penalty until Dec 10 at noon.
It refers to problem 10.4 in the Russell and Norvig textbook,
which can be found here.
Use this Golog interpreter.
See also this elevator controller
example Golog program.
Note that you should change the extensions from .swipl to .pl
before you load the files into SWI Prolog.
- Nov 15: Solutions to the Midterm Test are now available
here
(you must login using your EECS/Prism account to access the file).
- Nov 9: Assignment 2 is out; it is due
November 24 at 09:00 (extended!).
- Nov 8: The midterm test grades are available
here. The average is 42.96/75. Midterm grades will be increased by 8 marks out of 75 when course grades are calculated.
Students can pick up their midterms at the lectures on Nov 9 and Nov 12.
- Nov 7: Feedback on Assignment 1 has been emailed. It was pointed
out that the assignment handout does not explicitly ask for testing
data to be submitted. Consequently the grade received on question 1
will be increased by 5 marks for everyone who submitted, so that no
marks are deducted for lack of testing.
- Nov 7: The make up lectures to replace the cancelled lectures on
Oct 29 and 31 will take place on Friday Nov 9 from 13:30 to 16:30 in
HNE 034 and Monday Nov 12 from 10:00 to 13:00 in LAS 3033. The
material covered will be the same in both make up lectures so you
should only attend one. A recording of the make up lecture will be made available.
- Oct 28: The instructor is away at a confrence this week so the lectures
on Oct 29 and 31 are cancelled. Please read the lecture slides for
Weeks 7 & 8 posted below. Additional material may be posted later.
The office hours on Oct 29 and 31 are also cancelled.
Send your questions to the instructor by email.
- Oct 23: Exceptionally, the office hour on Oct. 24 will be held from 11:00 to 12:00 in LAS 3052A.
Solutions to Assignment 1 are available here (you must login using your EECS/Prism account to access the file).
- Oct 19: As announced in class, the midterm test will be held on
Oct. 24 during class. The test covers everything we have seen up to
Oct. 17 inclusively (both representation and reasoning in first-order
logic and Prolog programming). To practice for the midterm, you can do
the following exercises in Russell and Norvig: Chapter 8 exercises 2,
6, and 10, and Chapter 9 exercises 4, 20, and 23. If you want to
practice further, have a look at Chapter 8 exercises 3, 8, 9, 19, 23,
and 24, and Chapter 9 exercises 19, 21, and 24. See also the added
alides on entailment in Lecture Transparencies for Week 2 below.
- Oct 9: The office hour on Oct 10 is cancelled. Email the instructor if you have questions.
- Sept 26: Assignment 1 is out; it is due
Oct. 19 at 23:59 (extended again!).
- Classes start Sept. 5.
Instructor
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Lectures
Monday and Wednesday from 13:00 to 14:30 in LSB 105 (LSB is Life Sciences Building).
Instructor Office Hours
Monday 17:00 to 18:00 and Wednesday from 15:00 to 16:00, in LAS 3052A.
Textbooks
Russell, S.J. and Norvig, P.,
Artificial Intelligence: A Modern Approach, 3rd edition
Prentice Hall, 2010.
Authors' web site,
Publisher's web site.
Clocksin, W.F. and Mellish, C.S.,
Programming in Prolog, (5th edition), Springer Verlag, New York, 2004.
The textbooks are strongly recommended; they are available at the York University Bookstore.
Prerequisites
General prerequisites; LE/EECS2011 3.00, SC/MATH1090 3.0.
Evaluation Scheme
Assignements (3 @ 8% each) |
24% |
Midterm test | 26% |
Final exam | 50% |
Total | 100% |
Tentative Schedule
- Week 1 (Sept 5) Introduction & intelligent agents,
common sense reasoning
(R&N ch. 1, 2).
- Week 2 (Sept 10)
Logical representations, first-order logic syntax and semantics,
use in knowledge representation, description logic and ontologies
(R&N ch. 7, 8).
- Week 3 (Sept 17)
Basics of logic programming and Prolog,
syntax, backchaining procedure, arithmetic, lists, I/O, recursive definitions,
constraints solving, debugging
(C&M ch. 1, 2, 3.1-3.3, 5, and 8).
- Week 4 (Sept 24) Inference in first order logic, unification, resolution
(R&N ch. 9).
- Week 5 (Oct 1) Reasoning with Horn theories, SLDNF resolution
(R&N ch. 9 & C&M ch. 4 & 10).
- Reading Week (Oct 8 - No classes)
- Week 6 (Oct 15) Prolog control flow, backtracking, cut,
2nd order features,
closed world assumption, negation as failure, tail recursion, default reasoning
(C&M ch. 3, 4, 6, & 10).
Assignment 1 due.
- Week 7 (Oct 22) Uninformed Search
(R&N ch. 3).
Midterm test.
- Week 8 (Oct 29) Informed Search
(R&N ch. 3, & ch. 4 sec. 1).
- Week 9 (Nov 5) Constraint satisfaction and backtracking search
(R&N ch. 6).
- Week 10 (Nov 12) Reasoning about Action and Planning.
Assignment 2 due.
- Week 11 (Nov 19) Uncertain Reasoning, Bayes Nets
(R&N ch. 13-14).
Assignment 2 due.
- Week 12 (Nov 26) Planning under Uncertainty, Markov Decision Processes, Reinforcement Learning.
- Week 13 (Dec 3) Supervised Learning.
Assignment 3 due.
Academic Honesty
It is important that you look at the
departmental guidelines on academic honesty. Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.
Readings and Lecture Transparencies
- Week 1 (Sept 5) Introduction & intelligent agents
Required Readings: Russell & Norvig Chapter 1 & 2.
Optional Readings: Poole and Mackworth Chapter 1 & 2.
Lecture transparencies.
- Week 2 (Sept 10) Knowledge Representation & First-Order Logic
Required Readings: Russell & Norvig Chapter 8 (Chapter 7 is optional).
Optional Readings: Poole and Mackworth Chapter 13 (and Chapter 5 as needed).
Lecture transparencies (updated!),
additional slides on entailment from Brachman and Levesque (new!).
- Week 3 (Sept 17) Prolog Core Concepts and Notation
Required Readings: Clocksin & Mellish Chapters 1, 2, 3.1 to 3.3, 5, and 8.
Lecture transparencies,
zebra.swipl zebra logic puzzle example code (the zebra.pl file has been renamed zebra.swipl so that our web server will let you download it).
- Week 4 (Sept 24) Inference in First-Order Logic
Required Readings: Russell & Norvig Chapter 9.
Lecture transparencies.
- Week 5 (Oct 1) Reasoning with Horn Theories and Procedural Control of Reasoning
Required Readings: Russell & Norvig Chapter 9 and Clocksin & Mellish Chapter 4 & 10.
Optional Readings: Brachman and Levesque, Knowledge Representation and Reasoning, Chapters 5 & 6.
Lecture transparencies from Brachman and Levesque (the final two slides, 101 & 102, can be skipped).
- Week 6 (Oct 15) Prolog control flow, negation as failure, cut, 2nd order features, tail recursion.
Required Readings: Clocksin & Mellish Chapters 3, 4, 6, and 10.
Lecture transparencies.
- Week 7 (Oct 22) Uninformed Search
Required Readings: Russell & Norvig Chapter 3, Sec 1-4.
Lecture transparencies.
- Week 8 (Oct 29) Informed Search
Required Readings: Russell & Norvig Chapter 3, Sec 5 & 6 and Chapter 4 Section 1.
Lecture transparencies.
An audio recording of a lecture that covers slides 14 to 30 of this
material is available
here;
it was made during the first part of the make up lecture of Nov 9, 2018.
- Week 9 (Nov 5) Constraint Satisfaction Problems and Backtracking Search
Required Readings: Russell & Norvig Chapter 6.
Lecture transparencies.
An audio recording of a lecture that covers this material is available
here;
it was made during the second part of the make up lecture of Nov 9, 2018.
- Week 10 (Nov 12) Reasoning about Action and Planning
Required Readings: Russell & Norvig Chapter 10, Sec 1, 2, 4 and 5.
Lecture transparencies from Brachman and Levesque Ch 14-15,
lecture transparencies on planning as heuristic search.
- Week 11 (Nov 19) Reasoning under Uncertainty
Required Readings: Russell & Norvig Chapter 13 and Chapter 14 Sec. 1 and 2..
Lecture transparencies on reasoning under uncertainty from Brachman and Levesque Chapter 12.
- Week 12 (Nov 26) Sequential Decision Making Under Uncertainty and Reinforcement Learning
Required Readings: Russell & Norvig Chapter 17 Sec. 1 to 3 inclusively and Chapter 21 Sec. 1 to 3 inclusively.
Lecture transparencies from Russell & Norvig Chapter 17.
For the Reinforcement Learning lecture, I went over slides 23 to 38 of
Prof. Picard's lecture transparencies on Russell & Norvig Chapter 21.
- Week 13 (Dec 3) Learning from Examples
Required Readings: Russell & Norvig Chapter 18 Sec. 1, 2, 3, 6, and 7
(the rest of the chapter is optional).
Lecture transparencies from Russell & Norvig Chapter 18 Sec 1 to 3,
Lecture transparencies from Russell & Norvig Chapter 18 Sec 6 and 7.
Optional Readings on Text Processing in Prolog:
Clocksin & Mellish Chapter 9.
Lecture transparencies on Text Processing in Prolog (optional material).
Additional References
Other good AI textbooks:
Poole, D. and Mackworth, A.
Artificial Intelligence, Foundations of Computational Agents, 2nd edition,
Cambridge University Press, 2017.
On knowledge representation:
Ronald J. Brachman and Hector J. Levesque,
Knowledge Representation and Reasoning,
Elsevier/Morgan Kaufmann 2004, ISBN 1-55860-932-6
Baral, C.
Knowledge representation, reasoning, and declarative problem solving.
Cambridge University Press, Cambridge/New York, 2003.
Genesereth, M.R. and Nilsson, N.J.
Logical foundations of artificial intelligence.
Morgan Kaufmann, Los Altos, CA, 1987.
On reasoning about action:
Reiter, R.,
Knowledge in Action: Logical Foundations for Specifying and Implementing
Dynamical Systems,
MIT Press, 2001.
York Library eCopy,
Book home page.
On Prolog:
Bratko, I. Prolog Programming for Artificial Intelligence 4th Edition,
Pearson Education Canada, 2012.
Sterling, L.S. and Shapiro, E.Y.
The Art of Prolog, Second Edition,
MIT Press, 1994.
|
Running SWI-Prolog in the Prism Lab
|
-
To run Prolog execute the command pl. To exit enter
<CTRL>-D
at the prompt.
-
Documentation is available
on the web.
Getting Prolog
About Prolog