Course pages 2015–16
Artificial Intelligence I
Lecturer: Dr S.B. Holden
No. of lectures: 12
Suggested hours of supervisions: 3
Prerequisite courses: Algorithms. 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 are likely to be helpful although not essential. Similarly, elements of Mathematical Methods for Computer Science, 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, game-playing, representing and reasoning with knowledge, planning, and learning.
Lectures
- Introduction. Alternate ways of thinking about
AI. Agents as a unifying view of AI systems. [1 lecture]
- Search I. Search as a fundamental paradigm for
intelligent problem-solving. Simple, uninformed search
algorithms. Tree search and graph search. [1 lecture]
- Search II. More sophisticated heuristic search
algorithms. The A* algorithm and its properties. Improving memory
efficiency: the IDA* and recursive best first search
algorithms. Local search and gradient descent. [1 lecture]
- Game-playing. Search in an adversarial
environment. 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. [1 lecture]
- Backjumping in CSPs. Backtracking, backjumping using
Gaschnig’s algorithm, graph-based backjumping. [1 lecture]
- 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. [1 lectures]
- Planning I. 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]
- Planning II. Incorporating heuristics into partial-order
planning. Planning graphs. The GRAPHPLAN algorithm. Planning using
propositional logic. Planning as a constraint satisfaction
problem. [1 lecture]
- Neural Networks I. A brief introduction to supervised
learning from examples. Learning as fitting a curve to data. The
perceptron. Learning by gradient descent. [1 lecture]
- Neural Networks II. Multilayer perceptrons and the
backpropagation algorithm. [1 lecture]
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;
- 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.