Lecturer	Bernardo Cuenca Grau
Degrees	Schedule S1(CS&P)(3rd years) — Computer Science and Philosophy Schedule S1(3rd years) — Computer Science Schedule S1(M&CS)(3rd years) — Mathematics and Computer Science Schedule A — MSc in Advanced Computer Science
Term	Hilary Term 2019  (16 lectures)

Overview

MSc students will be assessed by invigilated exam lasting approximately 3 hours in week 0 of TT.

This is an introductory course into the field of artificial intelligence (AI), with particular focus on search as the fundamental technique for solving AI problems.

The problem of navigating a road map with a known layout is a typical example of a problem studied in this course. Problems such as this one can be solved by enumerating all possible sequences of moves until a solution is found. Such a naive idea, however, is rarely applicable in practice because the size of the search space is typically vast. This course will introduce basic AI search techniques, such as depth‐first, breadth‐first, and iterative deepening search, and it will discuss heuristic techniques such as A* search that improve efficiency by pruning the search space.

This course also deals with optimization problems. For example, the optimization version of the n‐queens problem is to arrange n queens on an n x n chessboard while minimizing the number of pairs of queens that are under attack. Such problems can be effectively solved by search techniques introduced in the course such as hill climbing, simulated annealing, and genetic algorithms. Planning is a special kind of optimization problem. A typical planning problem is finding a sequence of actions for delivering ten packages to ten different destinations. This course will introduce a standardized language called STRIPS for modelling planning problems, and it will discuss how to solve planning problems using search techniques such as forward chaining, backward chaining, and partial order planning. This course will also show how to apply these techniques to the problem of planning a robot’s path through an environment while taking into account the geometry of the environment and the robot.

Constraint satisfaction problems (CSPs) constitute another important class of AI problems, a typical example of which is the map colouring problem: colour each country on a map with red, green, or blue, but in a way so that no two adjacent countries have the same colour. This course will introduce search techniques such as backtracking and constraint propagation that can efficiently solve many CSP problems in practice.

Developing programs for playing board games such as chess has played a central role in AI since the very inception of the field. Game playing can be conceived as yet another kind of search problem, in which the objective is to find a winning strategy. This course will introduce the basic game‐playing techniques such as minimax search and alpha‐beta pruning.

Dealing with unknown or incompletely specified environments is a form of intelligent behaviour that is critical in many intelligent systems. For example, consider a robot in maze that has no prior knowledge about the maze layout. To solve the problem, the robot needs to represent and update its knowledge about the maze as it moves through the maze. This course will show how to solve such problems via search in the belief space – the space of all possible beliefs the robot may have about the maze layout.

The  lectures for this course are not going to be recorded in Hilary Term 2019.

Learning outcomes

By attending the course the students should acquire a firm grasp of various search techniques and should be able to select an appropriate search technique and apply it in practice. Since search is such a fundamental technique in computer science, the material taught in the course is relevant in contexts other than artificial intelligence.

Prerequisites

Familiarity with propositional logic would be beneficial but is not a requirement.

Students are expected to use Java in practicals. This course does not cover any aspects of Java programming: the students are expected to have learned Java elsewhere. No knowledge of Java or any other programming language is required in order to pass the exam: all programming (in Java or any other language) is limited to practicals.

Synopsis

1	Introduction to Artificial Intelligence: definition of AI; Turing test; brief history of AI.
2 - 3	Problem solving and search: problem formulation; search space; states vs. nodes; tree search: breadth-first, uniform cost, depth-first, depth-limited, iterative deepening; graph search.
4	Informed search: greedy search; A* search; heuristic function; admissibility and consistency; deriving heuristics via problem relaxation.
5	Local search: hill-climbing; simulated annealing; genetic algorithms; local search in continuous spaces.
6 - 7	Planning: the STRIPS language; forward planning; backward planning; planning heuristics; partial-order planning; planning using propositional logic; planning vs. scheduling.
8 - 9	Dealing with geometry of physical agents: basic issues in robotics; degrees of freedom; Dijkstra’s shortest path algorithm; configuration spaces; Voronoi diagrams; skeletonization; potential field planning.
10	Constraint satisfaction problems (CSPs): basic definitions; finite vs. infinite vs. continuous domains; constraint graphs; relationship with propositional satisfiability, conjunctive queries, linear integer programming, and Diophantine equations; NP-completeness of CSP; extension to quantified constraint satisfaction (QCSP).
11 - 12	Solving CSPs: constraint satisfaction as a search problem; backtracking search; variable and value ordering heuristic; degree heuristic; least-constraining value heuristic; forward checking; constraint propagation; dependency-directed backtracking; independent subproblems; tree-like CSPs; acyclic CSPs; CSPs of bounded treewidth.
13 - 14	Playing games: game tree; utility function; optimal strategies; minimax algorithm; alpha-beta pruning; games with an element of chance.
15 - 16	Beyond classical search: searching with nondeterministic actions; searching with partial observations; online search agents; dealing with unknown environments.

Syllabus

Problem solving via search. Uninformed, informed, and local search. Planning. Dealing with geometry of physical agents. Constraint satisfaction. Adversarial search. Searching with nondeterministic actions and partial observations.

Reading list

S.J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach (3rd edition), Prentice-Hall, 2010.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.