CSE352 (Spring `03)
Artificial Intelligence

[ General Information | Course Outline | Lectures | Handouts | Other Pointers | Requirements ]
[ Announcements ]


General Information

Course description: This course is for students interested in learning some unifying as well as diversifying cutting-edge technologies and applications of computer science, centered around the idea of intelligent agents. The main topics include problem solving and search, knowledge representation and inference, planning, uncertainty reasoning, and learning; we will also discuss natural language processing, computer vision, and robotics. | Prerequisites: CSE 214 and 303; or permission of the instructor. | Credits: 3.

Instructor: Annie Liu | Email: liuATcsDOTsunysbDOTedu | Office: Computer Science 1433 | Phone: 632-8463.

Hours: TueThu 8:20-9:40AM, in Computer Science 2129. | Office hours: TueThu 9:40-11, in CS 1433.

Textbook: Artificial Intelligence: A Modern Approach, 2/E, by Stuart Russell (UC Berkeley) and Peter Norvig (Google), Prentice Hall, 2003. ISBN: 0-13-790395-2.

Grading: 20% for weekly or bi-weekly programming or written assignments, 20% for a project, and 30% each for two exams. Programming assignments and project are to be done in pairs, the rest individually. Written assignments given as practice for exams will not be graded, but solutions will be provided and each one not turned in will receive -5%. No credit for late submissions.

Course homepage: http://www.cs.sunysb.edu/~liu/cse352/, containing all course-related information.


Course Outline

We will start with an overview of the scope, problems, approaches, and applications of artificial intelligence and present the view of AI as the enterprise of designing intelligent agents.

We will then study two most basic topics of AI: (i) problem solving and search, which includes problem description, exhaustive and heuristic search, constraint satisfaction, and game playing, and (ii) knowledge representation and inference, which includes propositional logic, first-order logic, and inference methods and systems. We will also discuss additional techniques for the topic of planning. This will be followed by the first exam.

We will then introduce two important distinguished areas of AI: (i) uncertainty reasoning, which includes uncertainty and probability, Bayesian networks and reasoning, temporal probabilistic reasoning and speech recognition, and decision making, and (ii) learning, which includes inductive learning, decision tree learning, and neural networks. This will be followed by the second exam.

Finally, we will discuss topics on agents communicating, perceiving, and acting, which include natural language processing (grammars, syntax analysis, etc), vision (image formation, object recognition, etc), and robotics (robots, configuration spaces, motion planning).

Assignments will be given mostly before the spring break, and each one will be due in class on the due date, usually when the next course work is given. The project will be given after the spring break and due immediately after the last class. See detailed schedules below, but there might be small changes based on the pace of the lectures.


Lectures

Lecture 1 (01/23/03): Overview: course, AI problems, approaches, history, state of art. Reading: Ch.1. Assign 1.
Lecture 2 (01/28/03): Intelligent agent: agents & environments, rationality & performance, types. Reading: Ch.2.
Lecture 3 (01/30/03): Problem solving and search: problem formulation, state space, exhaustive search strategies. Reading: Ch.3. Assign 2: programming.
Lecture 4 (02/04/03): Heuristic search: best-first, A*, heuristics; local search, hill-climbing, simulated annealing. Reading: Ch.4.
Lecture 5 (02/06/03): Constraint satisfaction problems: CSP, backtracking, efficiency improvements; local search. Reading: Ch.5. Assign 3: programming.
Lecture 6 (02/11/03): Game-playing: game tree, minmax; evaluation function, cut off; alpha-beta pruning; with chance, with unknowns. Reading: Ch.6.
Lecture 7 (02/13/03): Knowledge representation and inference: knowledge base; Wumpus world; basics of logic; propositional logic; inference; forward & backward chaining, resolution. Reading: Ch.7:1-5.
Lecture 8 (02/18/03): University classes canceled due to snow storm.
Lecture 9 (02/20/03): First-order logic: objects, relations; constants, functions, predicates, equality, quantifications; examples, Wumpus world; idea of situation calculus. Reading: Ch.8. Assign 4: for Exam 1.
Review week: Feb 24-28.
Lecture 12 (03/04/03): Inference in first-order logic: reducing to propositional inference; unification, generalized Modus Ponens; forward chaining. Reading: Ch.9:1-3.
Lecture 13 (03/06/03): Inference in first-order logic: backward chaining, logic programming; resolution. From ontology to nonmonotonic logic. Review for Exam 1. Reading: Ch.9:4-6. Assign 5: programming.
Exam 1 (03/11/03): In-class exam: intelligent agent, problem solving and search, knowledge rep and inference.
Lecture 15 (03/13/03): Planning: vs search and inference; STRIPS actions, precondition and effect; partial order planning; conditional planning; execution monitoring and replanning. Reading: Ch.11-12.
Spring break: March 17-22.
Lecture 16 (03/25/03): Uncertainty reasoning: uncertainty, probability, prior and conditional, inference by enumeration, independence. Reading: Ch.13:1-5. Project.
Lecture 17 (03/27/03): Bayes rule, Bayesian networks, semantics, construction, compact conditional distributions. Reading: Ch.13:6-8,Ch.14:1-3.
Project week: April 1-3.
Lecture 20 (04/08/03): Inference in Bayesian networks: exact inference by enumeration, variable elimination; approximate inference by stochastic simulation, Markov chain Monte Carlo. Reading: Ch.14:4-5,8.
Lecture 21 (04/10/03): Hidden Markov models and speech recognition: Time and uncertainty, Markov processes/chains, hidden Markov models; speech as probabilistic inference, sounds, phones, words, word sequences. Reading: Ch.15:1,3,6.
Lecture 22 (04/15/03): Decision making: rational preferences, maximizing expected utilities; utilities, money, multiattribute utilities, decision networks; value of information. Reading: Ch.16. Assign 6: for Exam 2.
Another break: April 16-18.
Lecture 23 (04/22/03): Learning: basics; inductive learning: consistency, simplicity; decision tree learning: expressiveness, choosing attributes, performance measurement. Reading: Ch.18:1-3.
Lecture 24 (04/24/03): Neural networks: brains and neurons, neural net units, network structures; perceptrons, multilayer perceptrons, expressiveness, learning; applications. Reading: Ch.20:5,7.
Exam 2 (04/29/03): In-class exam: planning, uncertainty reasoning, learning.
Lecture 26 (05/01/03): Interfacing: Languages: communication, grammar, syntax analysis, problems. Project presentations: Common sense DJ, Intelligence using NARIA, Vacuum cleaner Roomba. Reading: Ch.22.
Lecture 27 (05/06/03): Vision: perception, image formation, 2D to 3D, object recognition. Project presentations: Board game Connect 4, Board game using AIP, Game Counter-Strick. Reading: Ch.24.
Lecture 28 (05/08/03): Robotics: robots, effectors, sensors; localization, mapping; motion planning. Project presentations: Email filter Bogofilter, Chatbot Anna, Computer poet, Composing music using NN. Project due. Reading: Ch.25.

Handouts

Handout Q: Questionnaire

Slides for Ch.1: Artificial Intelligence
Slides for Ch.2: Intelligent Agents

Slides for Ch.3: Solving Problems by Searching
Slides for Ch.4: Informed Search and Exploration (pdf)
Slides for Ch.5: Constraint Satisfaction Problems (pdf)
Slides for Ch.6: Adversarial Search (pdf)

Slides for Ch.7: Logical Agents (pdf)
Slides for Ch.8: First-Order Logic (pdf)
Slides for Ch.9: Inference in First-Order Logic (pdf)

Slides for Ch.11: Planning (pdf)
Slides for Ch.12: Planning and Acting in the Real World (pdf)

Slides for Ch.13: Uncertainty (pdf)
Slides for Ch.14: Probabilistic Reasoning /Part 1 (pdf) | /Part 2 (pdf)
Slides for Ch.15: Probabilistic Reasoning over Time /Part 1 (pdf) | /Part 2 (pdf)
Slides for Ch.16: Making Simple Decisions (pdf)

Slides for Ch.18: Learning and Observations (pdf)
Slides for Ch.20: Statistical Learning Methods /Part on Neural Networks (pdf)

Slides for Ch.22: Communication (pdf)
Slides for Ch.24: Perception (pdf)
Slides for Ch.25: Robotics (pdf)

Handout A1: Assignment 1: Intelligent Agent

Handout A2: Assignment 2: Programming Recursion and Symbolic Manipulation

Handout A3: Assignment 3: Programming A* Search

Handout A4: Assignment 4: Exercise Problems for Exam 1

Handout A5: Assignment 5: Programming with Logical Relations and Rules

Handout A6: Assignment 6: Exercise Problems for Exam 2

Handout E1: Exam 1
Handout E1S: Exam 1 Solution

Handout E2: Exam 2
Handout E2S: Exam 2 Solution

Handout P: Project: An Artificial Intelligence System


Other Pointers

Ghostscript, Ghostview and GSview: Ghostview and GSview are for viewing and printing Postscript documents (some of the handouts for this course will be in this format). If you use Linux, then this software is already installed on your machine. On Windows, you need to download both Ghostview and Ghostscript (and also some fonts). Unzip Ghostview and run setup.exe. It will unpack and install the rest.

The gzip homepage: GNU zip for compression.


Requirements

Some programming assignments will be in Java, others in a language that you choose and can justify. Knowledge of Lisp would be useful. We will also learn some Prolog. Basic ideas of data structures and complexity are needed. Calculus comes in handy in one or two places.

You should learn all information on the course homepage. Check the homepage periodically for Announcements.

Do all course work. The homeworks and projects are integral parts of the course as they provide concrete experiences with the abstract ideas covered in the class.

Your handins, whether on papers or in electronic forms, should include the following information at the top: your name, course number, homework/project number, and due date.

Your work should be submitted in a neat and organized fashion; for handins on papers, if your handwriting is hard to read, then your work needs to be typed.

Your approach to solving problems is as important as your final solutions; you need to show how you arrived at your solutions and include appropriate explanations.

If you feel your grade was assigned incorrectly, please bring it up no later than two weeks after the assignment was returned to the class.

You are encouraged to discuss with others and look up references, but you should write up your own solutions independently and credit all sources that you used. Any plagiarism or other forms of cheating will result in an F or worse.

Disability: If you have a physical, psychological, medical or learning disability that may have an impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133 Humanities, 632-6748/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.


Annie Liu