Intelligent Systems: 2010-2011
Lecturer | |
Degrees | Schedule B2 — Computer Science |
Term | Michaelmas Term 2010 (16 lectures) |
Overview
This is an introductory course into the field of artificial intelligence. The course focuses mainly on various search-based methods for problem solving. Emphasis is put on the design of heuristics that help dealing with large search spaces.Learning outcomes
By attending the course the students should acquire a firm grasp of various search techniques and should be able to apply search 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
This course assumes that the students are familiar with the basics of propositional logic. Undergraduate students are expected to acquire the relevant expertise in the Logic and Proof course. MSc students are expected to have completed an equivalent course during their undergraduate education.
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.