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?

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. 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. 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. 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,. 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. 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. 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 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. 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. 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. 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. 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.