EECS 3401 3.0
Introduction to Artificial Intelligence and Logic Programming
Fall 2017
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.
- Inference in first order logic, unification, resolution.
- Reasoning with Horn theories, SLDNF resolution, Prolog control
flow, backtracking, closed world assumption, negation as failure.
- Prolog lists, arithmetic.
- Uninformed search.
- Informed search.
- Constraint satisfaction and backtracking search.
- Game/adversarial search.
- Uncertain reasoning, Bayes Nets.
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 8: The instructor's office hours in the coming week are
Dec 8 at 2pm, Dec 12 at 4pm, and Dec 14 at 11am.
There will be no office hours on Dec 11 and 13.
- Dec. 4:
The final exam will be held on December 14 at 2pm in DB 0005. 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 7,
but more emphasis on the AI material seen in Weeks 8 to 12. 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, exercises 3 and 9, Chapter 5 exercise 9, and
Chapter 6 exercise 2; see also the practice exercises given for the
midterm test. Another good exercise for Chapter 6 is to apply
backtracking search to the Australia map colouring, with and without
forward checking.
- Dec. 4: If you have not yet filled out the course evaluation
survey, please do so at
http://courseevaluations.yorku.ca; today is the last day for this.
- Nov. 27: Assignment 4 is out; it is due
December 11 at 18:00. As agreed in class, the assignment is optional.
If you hand it in,
it will be graded, and the assignments grade will be computed by averaging
the best 3 out of 4 among the assignments submitted
(each counting for 8% of the course grade).
- Nov. 20: Assignment 3 is out; it is due December 4 at 14:30.
- Nov. 5: Assignment 2 is out; it is due Nov. 20 at
14:30 (extended!).
- Oct 15: The midterm test will be held on Oct. 30 during class.
The test covers everything we have seen up to Oct 25 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.
- Oct 15: see added alides on entailment in Lecture Transparencies for Week 2 below.
- Oct. 4: Assignment 1 is out; it is due Oct. 18 at 14:30.
- Classes start Sept. 11.
Instructor
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Lectures
Monday and Wednesday from 14:30 to 16:00 in CB 121 (CB is Chemistry Building).
Instructor Office Hours
Monday and Wednesday from 16:30 to 17:30, 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 11) Introduction & intelligent agents.
Logical representations, first-order logic syntax and semantics,
use in knowledge representation.
(R&N ch. 1, 2, 7, 8).
- Weeks 2 & 3 (Sept 18 & 25) 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)
- Weeks 4 & 5 (Oct 2 & 9) Inference in first order logic, unification, resolution.
(R&N ch. 9).
- Week 6 (Oct 16) Reasoning with Horn theories, SLDNF resolution, Prolog
control flow, backtracking, closed world assumption, negation as failure
(R&N ch. 9 & C&M ch. 4 & 10). Assignment 1 due.
- Week 7 (Oct 23) Prolog control flow, negation as failure, cut,
2nd order features, tail recursion(C&M ch. 3, 4, 6, & 10).
- Week 8 (Oct 30) Uninformed search (R&N ch. 3, sec. 1-4).
- Week 9 (Nov 6) Informed search (R&N ch. 3, sec, 5 & 6 and ch. 4 sec. 1).
- Week 10 (Nov 13) Game/Adversarial Search (R&N ch. 5 sec. 1-3 & 7).
- Week 11 (Nov 20) Constraint satisfaction and backtracking search (R&N ch. 6)
- Week 12 (Nov 27) Uncertain Reasoning (R&N ch. 13-14).
- Week 13 (Dec 4) Review.
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 - Lecture 1 (Sept 11) Introduction & intelligent agents
Required Readings: Russell & Norvig Chapter 1 & 2.
Lecture transparencies.
- Week 1 - Lecture 2 (Sept 13) Knowledge Representation & First-Order Logic
Required Readings: Russell & Norvig Chapter 8 (Chapter 7 is optional).
Lecture transparencies,
additional slides on entailment from Brachman and Levesque (new!).
- Weeks 2 & 3 (Sept 18 & 25) 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).
- Weeks 4 & 5 (Oct 2 & 9) Inference in First-Order Logic
Required Readings: Russell & Norvig Chapter 9.
Lecture transparencies (updated!).
- Week 6 (Oct 16) 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.
- Week 7 (Oct 23) 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 8 (Oct 30) Uninformed Search
Required Readings: Russell & Norvig Chapter 3, Sec 1-4.
Lecture transparencies.
- Week 9 (Nov 6) Informed Search
Required Readings: Russell & Norvig Chapter 3, Sec 5 & 6 and Chapter 4 Section 1.
Lecture transparencies.
- Week 10 (Nov 13) Game Tree Search
Required Readings: Russell & Norvig Chapter 5, Sec 1-3 and 7.
Lecture transparencies.
- Week 11 (Nov 20) Constraint Satisfaction Problems and Backtracking Search
Required Readings: Russell & Norvig Chapter 6.
Lecture transparencies.
- Week 12 (Nov 27) Reasoning under Uncertainty and Text Processing in Prolog
Required Readings: Russell & Norvig Chapter 13 and Chapter 14 Sec. 1 and 2; Clocksin & Mellish Chapter 9.
Lecture transparencies on reasoninge under uncertainty from Brachman and Levesque,
lecture transparencies on text processing in Prolog.
Additional References
Other good AI textbooks:
Poole, D. and Mackworth, A.
Artificial Intelligence, Foundations of Computational Agents,
Cambridge University Press, 2010.
Poole, D., Mackworth, A., Goebel, R.
Computational Intelligence, A Logical Approach,,
Oxford University Press, New York, 1998.
Nilsson, N.J.,
Artificial Intelligence: A New Synthesis,,
Morgan Kaufmann, San Francisco, 1998.
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