CPSC 522 --- Artificial Intelligence II
Reasoning and Acting under Uncertainty

Course Overview -- Spring 2006

Instructor: David Poole

Time: Tuesdays & Thursdays, 11:00-12:30 room DMP 201.
First class: Tuesday January 10.
The Schedule will be updated as term goes on.
See the 522 WebCT page for the bulletin board, textbook and grades.
Please read the newsgroup: ubc.courses.cpsc.522
Online resources that may be useful for the project.

One of the primary goals of AI is the design, control and analysis of agents or systems that behave appropriately in various circumstances. Such intelligent agents require not only the ability to act but also to decide how to act as circumstances vary. In turn, good decision making requires that the agent have knowledge or beliefs about its environment and its dynamics, about its own abilities to observe and change the environment, and its goals and preferences.

This course builds on the foundations of dynamical systems, decision theory, knowledge representation and machine learning all of which will be presented in enough detail to understand the rest of the course.

In this course, we will overview some of the techniques for and issues that arise in representing, reasoning about and learning the knowledge required for acting. The emphasis will be on appropriate representations of knowledge, and how they impact on computational models and related issues.

We will begin by studying representations of belief and reasoning methods. We will move on to examine representations for action and change. We then discuss preferences and single-step decision making, and spend some time on the issues that arise in multi-stage decision processes and planning and learning for acting. Time permitting, we will consider complications that arise in multi-agent decision problems. Throughout, we will pay special attention to the open problems and outstanding issues that exist in these areas or in the attempt to bring them together. Some familiarity with propositional and first-order logic will be assumed.

Formal prerequisites

Some background in some aspect of AI (e.g., an undergraduate course, CPSC 502 or CPSC 540) or permission of instructor.

Assignments

Assignment 0 (Student info)
Assignment 1 or pdf. Here is subtraction.xml subtraction belief network (you need to autoscale after loading it).
Assignment 2 or pdf
Assignment 3
Assignment 4
Project (or pdf) (proposal due February 23)

Topics Covered

A list of topics that will likely be covered:

Agents, knowledge representation and AI - overview of the big picture.

The components of decision making and rational action.

Belief

Probabilistic semantics for belief.
Representation of probabilities: belief (Bayesian) networks.
Inference in belief networks: exact and approximate (variable elimination, clique-tree propagation, stochastic simulation, particle filters, variational methods)
Context-specific independence, causal independence, other parametric forms
Learning belief networks: learning probabilities, unobserved variables (EM), learning structure
Integrating belief and dynamics: Markov chains, hidden Markov models, Kalman filters, dynamic belief networks
Causality
Spatial Reasoning
First-order representations

Acting and deciding

Preferences and utilities. Multi-attribute utility theory.
Rational decision-making.
Multi-stage decision making; decision networks (influence diagrams).
Solving decision networks (dynamic programming, search)
Value of information and control
Bounded Rationality

Processes

Acting continually: Markov decision processes.
Learning how to act; reinforcement learning, supervised learning.
Partial observability, sensing the environment. (POMDPs)
Multi-agent systems; applications of game theory to cooperative and competitive decision making.

The topics covered (and especially the emphasis) will depend on the interests of the participants.

Organization

The class will meet twice per week. Some some classes will be devoted to the presentation of background material, and others will be centered around the discussion of a particular research article. All participants are expected to have read (at some marginal level of detail) the articles before the class and contribute to the discussion. Once during the term, each participant will be required to (very informally) present one such article in class and lead the discussion.

Participants will also be expected to complete a small course project. The project will be decided in consultation with the instructor and may consist of an implementation of a particular reasoning, decision-making or planning theory (or theories), a short research paper on problem related to a course topic, or a critical literature survey. You are encouraged to collaborate with other students to find complementary synergistic projects (e.g., sharing the same code to test different hypotheses), but your written project must be the your own. You will be required to hand in a short proposal in the middle of the term, and then 4 copies of your project in the last week of classes. You will be expected to peer review three other projects and give a conference-style presentation of your project. You will have a chance to revise your project based on the reviews and feedback from your presentation.

Evaluation for the course will be based on class participation (including presentations), the course project (including reviewing) and three plus or minus two homework assignments.

Text and Readings

While this is not a required text, we will use Poole, Mackworth and Goebel, Computational Intelligence (OUP, 1998) as well as selected chapters from the second edition we are writing, and Russell and Norvig, Artificial Intelligence : A Modern Approach, 2nd edn (Prentice-Hall, 2003) as the basis for certain background material in planning, decision theory, etc. Research articles to be discussed in class will form the bulk of the class reading. More comprehensive references in specific areas will be provided for those who find themselves especially interested in particular topics. Research articles for class, as well as background and optional material, will be made available in the Reading Room for easy access.

David Poole 2005-08-23.

CPSC 522 --- Artificial Intelligence II Reasoning and Acting under Uncertainty