CPSC322 - Introduction to Artificial Intelligence - 1999

Modules

CPSC322 will be taught in 12 modules, each lasting one week (three lectures).

Module 1. AI, Agents and Intelligence
Module 2. Symbols and Semantics.
Module 3. Reasoning with Symbols.
Module 4. Search, blind and heuristic.
Module 5. Search issues: loops, directions, space/time tradeoffs, dynamic programming.
Module 6. Constraint satisfaction.
Module 7. Knowledge representation issues.
Module 8. Metainterpreters.
Module 9. Action representations.
Module 10. Planning.
Module 11. Learning: decision trees.
Module 12. Learning: neural networks.

Module 1: AI, Agents and Intelligence

In this module we consider the questions: What is AI? What is intelligence? What can be automated? What sorts of AI applications are there? What are intelligent agents? What common features do they have?

Lectures: Lecture 1, Lecture 2 (or pdf (b&w 2-up for printing) or html)
Readings: Computational Intelligence, Chapter 1.
Assignment 1: AI applications and What is Intelligence? (or pdf)
Online resources for assignment 1.
Robot pages: Spinoza The Dynamites Platonic beasts

Module 2: Symbols and Semantics

In this module we see how symbols in a computer can have meaning. Semantics specifies how symbols in the computer can be used to reason about an external world. We separate the specification of what should be computed from how it is computed. We consider this in the context of a simple representation and reasoning system called Datalog.

Lectures: Lecture 1, Lecture 2, Lecture 3 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Sections 2.1-2.6 and 3.1-3.4.
Assignment 2. (or pdf). Here is plumbing.pl . Here is a trace of using CILog .
Here is a solution for the assignment.
Here is the buggy CILog program discussed in class. Try ask wet(floor), and debug it using how, with the intended interpretation given here.

What you should know: Syntax of Datalog. Formal semantics of Datalog. How the formal semantics can be applied to real problems. How to use semantics to debug a knowledge base (without knowing how answers are produced). How to write simple Datalog programs.

Module 3: Reasoning with Symbols

In this module we see how to compute proofs. We show two different ways to compute logical consequences.

Lectures: Lecture 1, Lecture 2, Lecture 3 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Sections 2.7-2.9 and 3.5-3.6.
Assignment 3 (or pdf). Here is plumbing2.pl.
Solution to Assignment 3 (or pdf).

What you should know: soundness, completeness, bottom-up proof procedure, consequence set, SLD resolution, derivation, unification.

Module 4: Searching Basics

In this module we consider fundamental search algorithms for finding paths in graphs.

Lectures: Lecture 1, Lecture 2, Lecture 3 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Sections 4.1-4.5.
Assignment 4 (or pdf). Errata: the neighbours of i should be give by: neighbours(i,[j,g]).
Graph Searching Applet, or run ~cs322/tools/search/search. The last button on the web page loads the graph from assignment 4 (or you can load mod4gr199, also available as ~cs322/tools/search/mod4gr199, using the load button in the application).
as4.pl, a CILog axiomatization for the graph of assignment 4. This can be run with hsearch.pl. These are also available on "~cs322/cilog/". The number of nodes expanded can be determined using "how."
Solution to Assignment 4 (or pdf).

What you should know: graph definitions, generic search algorithm, depth-first search, breadth-first search, lowest-cost-first search best-first search, heuristic depth-first search and A^* search.

Module 5: Search issues: loops, directions, space/time tradeoffs, dynamic programming.

In this module we consider advanced issues in searching, including handling loops in graphs, multiple path pruning,.

Lectures: Lecture (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Section 4.6.
Assignment 5 (or pdf).
Graph Searching Applet, or run ~cs322/tools/search/search. The second last button on the web page loads the graph from assignment 5 (or you can load mod5gr1999, also available as ~cs322/tools/search/mod5gr1999, using the load button in the application).
mod5gr1999.pl, a CILog axiomatization for the graph of assignment 5. This can be run with hsearch.pl. These are also available on "~cs322/cilog/". The number of nodes expanded can be determined using "how."
Solution to Assignment 5 (or pdf).

What you should know: space and time complexity of algorithms, cycle checking, multiple path pruning (and their overhead), iterative deepening, direction of search, bidirectional search, island-driven search, dynamic programming.

Module 6: Constraint Satisfaction Problems.

In this module we consider solving constraint satisfaction problems via search, consistency methods and hill climbing.

Lectures: Lecture 1 Lecture 2 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Section 4.7.
Assignment 6 (or pdf).
Solution to Assignment 6 (or pdf).
Constraint Satisfaction Applet, or run ~cs322/tools/constraint/cspsolver. The last button on the web page loads the first graph from assignment 6 (or you can load mod6cn1999, also available as ~cs322/tools/constraint/mod6cn1999, using the load button in the application).
For a hint on the assignment, look at CI solved problems for Chapter 4 (in particular question 5).

What you should know: variables, domains, hard constraints, soft constraints, generate-and-test, backtracking algorithms, constraint networks, domain consistency, arc consistency, AC-3, domain splitting, hill climbing.

Module 7: Knowledge Representation Issues.

In this module we consider the nature of knowledge representation, mapping from a problem to a solution via a representation and an answer, quality of solutions, choosing a representation language, levels of abstraction, object-attribute-value representation.

Lectures: Lecture 1 Lecture 2 Lecture 3 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Chapter 5.
Assignment 7 (or pdf).
Solution to Assignment 7 (or pdf).

What you should know: optimal solution, satisficing solution, anytime algorithm, knowledge level, symbol level, object-attribute-value representation, semantic networks, primitive versus derived relations, property inheritance,

Module 8: Metainterpreters.

In this module we consider knowledge engineering and how to implement different knowledge representation languages as well as how to implement knowledge-level debugging, ask-the-user

Lectures: Lecture 1 Lecture 2 Lecture 3 Lecture 4 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Chapter 6.
Assignment 8 (or pdf). (Note: the answer in Question 1 should be Val=29.)
Some useful CILog code: simple eval discussed in class. Also vanilla metainterpreter, and delaying metainterpreter.
Solution to Assignment 8 (or pdf).

What you should know: roles for people in knowledge-based systems, base language, metalanguage, vanilla metainterpreter, depth-bounded metainterpreter, delaying metainterpreter, ask-the-user, explanation, how/why, knowledge-level debugging.

Module 9: Action Representations.

In this module we look at two different representations for actions: the situation calculus and the STRIPS representation. We start off with (in)equality as we use the unique names assumption in the action representations.

Lectures: Lecture 1 Lecture 2 Lecture 3 Lecture 4 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Sections 7.2, 8.1, and 8.2 (except the Event Calculus).
Assignment 9 (or pdf). You can start with plumbing.pl, CILog code for the solution of the relevant part of assignment 2.
Solution to Assignment 9 (or pdf). The CILog code is in: plumbing_sitc.pl.

What you should know: equality; unique names assumption; state space; actions; static, dynamic, derived and primitive relations; STRIPS representation; situation calculus.

Module 10: Planning.

Planning is finding a sequence of actions for achieving a goal. In this module we look at a number of different planning algorithms: forward planning, SLD resolution, STRIPs planning and regression.

Lectures: Lecture 1 Lecture 2 Lecture 3 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Section 8.3 (except Partial Order Planning).
Assignment 10 (or pdf). The relevant code is: delrob_strips.pl, strips_strips.pl, back_strips.pl.
Solution to Assignment 10 (or pdf).

What you should know: what is a plan; forward planner; planner as resolution; STRIPS planner; protecting and reachieving subgoals; regression planner; weakest precondition.

Module 11: Learning Decision Trees.

In this module we consider the general problem of learning from examples, in particular the problem of supervised classification, and learning as search through a space of representations. We consider the representation of decision trees.

Lectures: Lecture 1 Lecture 2 (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Sections 11.1, 11.2.
Assignment 11 (or pdf).
The code from the notes: dtlearn_bool.pl, the data from the book: dtlearn_t2, and the data from the assignment: as11data.pl.
Solution to Assignment 11 (or pdf).

What you should know: bias, overfitting, what is a decision tree, top-down induction of decision trees, bias of decision trees, handling overfitting.

Module 12: Learning Neural Networks.

In this module we learn about feed-forward neural networks, how they can represent functions and how that can be learned from data.

Lectures: Lecture (or pdf (b&w 2-up for printing))
Readings: Computational Intelligence, Section 11.2.
Assignment 12 (or pdf).
Neural Network Applet. Or run ~cs322/tools/neuralnet/neuralnet on the undergrad machines.
Solution to Assignment 12 (or pdf).

What you should know: input units, hidden units, output units, how the output of a unit is computed for a given instance, sigmoid function, sum-of-squares error, backpropagation learning, gradient descent, bias of neural network.