Computer Laboratory

Course pages 2011–12

Artificial Intelligence I

Principal lecturer: Dr Sean Holden
Taken by: Part IB
Past exam questions
Information for supervisors (contact lecturer for access permission)

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, Mathematical Methods for Computer Science, Probability, Logic and Proof, Prolog and Complexity Theory 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 fundamental 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 fundamental 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. Alternate ways of thinking about AI. 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 A* algorithm and its properties. Improving memory efficiency: the A* and recursive best first search algorithms. Local search and gradient descent. [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 I. 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. [1 lectures]

  • Knowledge representation and reasoning II. Knowledge representation and reasoning using first order logic. The frame, qualification and ramification problems. The situation calculus. [2 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 the fact that the computational complexity of most AI problems requires us regularly to deal with approximate techniques;

  • 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, knowledge representation, reasoning, planning, and learning algorithms.

Recommended reading

The recommended text is:

* Russell, S. & Norvig, P. (2010). Artificial intelligence: a modern approach. Prentice Hall (3rd ed.).

There are many good books available on artificial intelligence; one alternative is:

Poole, D. L. & Mackworth, A. K. (2010). Artificial intelligence: foundations of computational agents. Cambridge University Press.

For some of the material you might find it useful to consult more specialised texts, in particular:

Dechter, R. (2003). Constraint processing. Morgan Kaufmann.

Cawsey, A. (1998). The essence of artificial intelligence. Prentice Hall.

Ghallab, M., Nau, D. & Traverso, P. (2004). Automated planning: theory and practice. Morgan Kaufmann.

Bishop, C.M. (2006). Pattern recognition and machine learning. Springer.