Computer Laboratory – Course material 2010–11: Artificial Intelligence I

Course material 2010–11

Artificial Intelligence I

Lecturer: Dr S.B. Holden

No. of lectures: 12

Prerequisite courses: Algorithms I. In addition the course requires some mathematics, in particular some use of vectors and some calculus. Part IA Natural Sciences Mathematics or equivalent, and Discrete Mathematics I + II, are likely to be helpful although not essential. Similarly, elements of Algorithms II are likely to be useful.

This course is a prerequisite for the Part II courses Artificial Intelligence II and Natural Language Processing.

Aims

The aim of this course is to provide an introduction to some basic issues and algorithms in artificial intelligence (AI). The course approaches AI from an algorithmic, computer science-centric perspective; relatively little reference is made to the complementary perspectives developed within psychology, neuroscience or elsewhere. The course aims to provide some basic tools and algorithms required to produce AI systems able to exhibit limited human-like abilities, particularly in the form of problem solving by search, representing and reasoning with knowledge, planning, and learning. Historically this corresponds roughly to the era prior to when probability became the standard method for dealing with the crucial concept of uncertainty. More recent material on uncertain reasoning is covered in Artificial Intelligence II.

Lectures

Introduction. What is it that we’re studying? Why is something that looks so easy to do actually so difficult to compute? Theories and methods: what approaches have been tried? Agents as a unifying view of AI systems. The basic structure of an agent. Interaction of an agent with the environment. Assessment of agents. What does this course cover, and what is left out? [1 lecture]
Search I. How can search serve as a fundamental paradigm for intelligent problem-solving? Simple, uninformed search algorithms. Tree search and graph search. More sophisticated heuristic search algorithms. The $\mbox{A}^{\star}$ algorithm and its properties. Improving memory efficiency: the $\mbox{IDA}^{\star}$ and recursive best first search algorithms. [2 lectures]
Search II. Search in an adversarial environment. Computer game playing. The minimax algorithm and its shortcomings. Improving minimax using $\alpha$ - $\beta$ pruning. [1 lecture]
Constraint satisfaction problems (CSPs). Standardising search problems to a common format. The backtracking algorithm for CSPs. Heuristics for improving the search for a solution. Forward checking, constraint propagation and arc consistency. Backtracking, backjumping using Gaschnig’s algorithm, graph-based backjumping. [2 lectures]
Knowledge representation and reasoning. How can we represent and deal with commonsense knowledge and other forms of knowledge? Semantic networks, frames and rules. How can we use inference in conjunction with a knowledge representation scheme to perform reasoning about the world and thereby to solve problems? Inheritance, forward and backward chaining. Knowledge representation using first order logic. The frame, qualification and ramification problems. The situation calculus. [3 lectures]
Planning. Methods for planning in advance how to solve a problem. The STRIPS language. Achieving preconditions, backtracking and fixing threats by promotion or demotion: the partial-order planning algorithm. [1 lecture]
Learning. A brief introduction to supervised learning from examples. Learning as fitting a curve to data. The perceptron. Learning by gradient descent. Multilayer perceptrons and the backpropagation algorithm. [2 lectures]

Objectives

At the end of the course students should:

Appreciate the distinction between the popular view of the field and the actual research results.
Appreciate different perspectives on what the problems of artificial intelligence are and how different approaches are justified.
Be able to design basic problem solving methods based on AI-based search, reasoning, planning, and learning algorithms.

Recommended reading

* Russell, S. & Norvig, P. (2003). Artificial intelligence: a modern approach. Prentice Hall (3rd ed.).
Cawsey, A. (1998). The essence of artificial intelligence. Prentice Hall.
Poole, D. L. & Mackworth, A. K. (2010). Artificial intelligence: foundations of computational agents. Cambridge University Press.