Artificial Intelligence: 2025-2026
Lecturer | |
Degrees | Schedule A2(CS&P) — Computer Science and Philosophy Schedule B1 (CS&P) — Computer Science and Philosophy Schedule A2 — Computer Science Schedule B1 — Computer Science |
Term | Hilary Term 2026 (16 lectures) |
Overview
How do you get an intelligent system to “think”? One of the most powerful answers in AI is: Search. From Google Maps finding a route across a city, to a robot deciding its next move, to a program choosing the best play in a game, AI repeatedly comes down to exploring vast spaces of possibilities efficiently and intelligently.
This course is an accessible, hands-on introduction to Artificial Intelligence, centred on search as a unifying idea across many classic and still highly relevant AI problems. We start with familiar navigation tasks, like planning a route on a known road map, and quickly see why “just try everything” is hopeless: the number of possibilities explodes. The exciting part is learning the tools that make these problems tractable.
You will learn the core search algorithms that form the backbone of AI: depth-first search, breadth-first search, and iterative deepening, and you will see how heuristics turn blind exploration into targeted reasoning. In particular, we study A*, a landmark algorithm that can transform an intractable problem into one that is solved quickly by prioritising the most promising paths and avoiding wasted work.
Search is not only about finding a solution, it is also about finding the best one. The course therefore explores optimisation, through problems like the n-queens variant where the goal is to minimise conflicts rather than simply eliminate them. You will see how AI tackles optimisation with practical methods such as hill climbing, simulated annealing, and genetic algorithms, techniques that underpin many modern approaches to difficult, high-dimensional problems.
We then move to planning: how an agent can choose a sequence of actions to achieve goals in the world. Think of coordinating deliveries to multiple destinations, or generating a plan for a robot that must move safely through a geometric environment. You will learn how to model problems in a standard language, STRIPS, and how planners solve them using search-based techniques such as forward search, backward search, and partial-order planning.
Another major AI paradigm covered is constraint satisfaction, which captures problems where solutions must satisfy a set of rules, like map colouring, timetabling, and resource allocation. You will learn how backtracking and constraint propagation can solve large instances efficiently by exploiting structure rather than brute force.
Games bring all of these ideas to life. Since the earliest days of AI, game playing has been a proving ground for intelligent decision-making. You will study minimax and alpha–beta pruning, learning how a program can reason strategically about an opponent and search deeply while keeping computation under control.
Finally, we tackle a key ingredient of real-world intelligence: acting under uncertainty. If a robot explores an unknown maze, it must continuously update what it believes about the world as it gathers information. You will see how such problems can be solved by searching in belief space, the space of all possible world models consistent with what the agent has observed.
By the end of the course, you will have a toolkit of foundational AI methods, a clear sense of why they work, and the ability to recognise the same ideas, search, heuristics, optimisation, planning, constraints, and strategic reasoning, reappearing across AI systems in the wild.
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.Related research
Themes |
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.