EECS 3401 3.0
Introduction to Artificial Intelligence and Logic Programming
Winter 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
- Apr 12: The final exam will be held on Apr 20 at 2pm in DB 0007.
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 AI material seen in Weeks 7 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.
- Apr 5: If you have not yet filled out the course evaluation survey,
please do so at
http://courseevaluations.yorku.ca. The site will be open until Apr 6.
- March 27: Assignment 4 is out; it is due
April 11 at 23:59 (extended!).
- March 14: Assignment 3 is out; it is due
March 28 at 23:59.
- March 10: There will be a special office hour today at 14:00 in LAS 3052A where students can pick up their midterm tests and ask questions about Assignment 2.
- Feb 21: Assignment 2 is out; it is due
March 13 at 23:59 (extended again!).
Note that Clocksin & Mellish Section 7.9 covers "searching graphs".
- Feb 20:This week is reading week and there are no classes or labs.
The instructor office hours will exceptionally be held Feb. 22 at 11:30 and
Feb 24 at 11am.
- Feb 12: As announced in class, the midterm test will be
held on Feb 15 during the lecture. It covers everything we
have seen up to Feb 8 inclusively (both representation and reasoning
in first-order logic and Prolog programming).
This week, the instructor is away. On Feb 13, there will
be a review tutorial during the lecture by the TA Vitaliy Batusov.
The office hours on Feb 13 and 15 are cancelled;
you can ask questions at the tutorial or by emailing the instructor.
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.
- Jan 25: Assignment 1 is out; it is due Feb. 10 at 23:59.
- Classes start January 9.
Instructor
Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca
Lectures
Monday and Wednesday from 17:30 to 19:00 in ACW 106 (ACW is Accolade West).
Instructor Office Hours
Monday 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 required; they are available at the York University
Bookstore.
Prerequisites
General prerequisites; LE/EECS2011 3.00, SC/MATH1090 3.0.
Evaluation
Assignements (4 @ 6% each) |
24% |
Midterm test | 26% |
Final exam | 50% |
Total | 100% |
Tentative Schedule
- Week 1 (Jan 9) Introduction & intelligent agents.
Logical representations, first-order logic syntax and semantics,
use in knowledge representation.
(R&N ch. 1, 2, 7, 8).
- Week 2 (Jan 16) 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 3 (Jan 23) Inference in first order logic, unification, resolution.
(R&N ch. 9).
- Week 4 (Jan 30) 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)
- Week 5 (Feb 6) Prolog control flow, negation as failure, cut,
2nd order features, tail recursion(C&M ch. 3, 4, 6, & 10).
Assignment 1 due.
- Week 6 (Feb 13) Prolog programming techniques, recursion, divide
and conquer, text proessing (C&M ch. 7 & 9). Midterm test.
- Feb 20-24 Reading Week - No Classes.
- Week 7 (Feb 27) Uninformed search (R&N ch. 3, sec. 1 to 4).
- Week 8 (Mar 6) Uninformed search continued (R&N ch. 3, sec. 1 to 4).
- Week 9 (Mar 13) Informed search (R&N ch. 3, sec, 5 to 7).
- Week 10 (Mar 20) Game/Adversarial Search (R&N ch. 5).
- Week 11 (Mar 27) Constraint satisfaction and backtracking search (R&N ch. 6)
- Week 12 (Apr 3) Uncertain Reasoning (R&N ch. 13-14).
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, Part 1 (Jan 9) Introduction & intelligent agents
Required Readings: Russell & Norvig Chapter 1 & 2.
Lecture transparencies.
- Week 1 Part 2 (Jan 11) Knowledge Representation & First-Order Logic
Required Readings: Russell & Norvig Chapter 8 (Chapter 7 is optional).
Lecture transparencies.
- Weeks 2 & 3 (Jan 16 & 23) 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 (Jan 30) Inference in First-Order Logic
Required Readings: Russell & Norvig Chapter 9.
Lecture transparencies.
- Week 5 (Feb 6) 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.
- Weeks 6 & 7 (Feb 13 and Feb 27) 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 (Mar 6) Uninformed Search
Required Readings: Russell & Norvig Chapter 3, Sec 1-4.
Lecture transparencies.
- Week 9 (Mar 13) Informed Search
Required Readings: Russell & Norvig Chapter 3, Sec 5 & 6 and Chapter 4 Section 1.
Lecture transparencies.
- Week 10 (Mar 20) Game Tree Search
Required Readings: Russell & Norvig Chapter 5, Sec 1-3 and 7.
Lecture transparencies.
- Week 11 (Mar 27) Constraint Satisfaction Problems and Backtracking Search
Required Readings: Russell & Norvig Chapter 6.
Lecture transparencies.
- Week 12 (Apr 3) 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