CPSC322 - Introduction
to Artificial Intelligence - 1999
CPSC322 will be taught in 12 modules, each lasting one week (three lectures).
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?
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.
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 2: Symbols and Semantics
In this module we see how to compute proofs. We show two different ways
to compute logical consequences.
What you should know: soundness, completeness, bottom-up proof procedure,
consequence set, SLD resolution, derivation, unification.
Module 3: Reasoning with Symbols
In this module we consider fundamental search algorithms for finding paths
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 4: Searching Basics
In this module we consider advanced issues in searching, including handling
loops in graphs, multiple path pruning,.
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 5: Search issues: loops,
directions, space/time tradeoffs, dynamic programming.
Constraint Satisfaction Problems.
In this module we consider solving constraint satisfaction problems
via search, consistency methods and hill climbing.
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,
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.
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,
In this module we consider knowledge engineering and how to implement
representation languages as well as how to implement knowledge-level
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.
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
What you should know: equality; unique names assumption; state space;
actions; static, dynamic, derived and primitive relations; STRIPS
representation; situation calculus.
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.
What you should know: what is a plan; forward planner; planner as
resolution; STRIPS planner; protecting and reachieving subgoals;
regression planner; weakest precondition.
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.
What you should know: bias, overfitting,
what is a decision tree, top-down induction of decision trees, bias of
decision trees, handling overfitting.
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.
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.
Copyright © David Poole 1999.