EE Department Intranet - intranet.ee.ic.ac.uk

## ELEC70068 Machine Reasoning

Lecturer(s): Prof Jeremy Pitt

### Aims

The overall aim of the course is to provide a foundational introduction to two essential elements of machine reasoning studied in Artifical Intelligence: planning and inference. Therefore the course focuses on algorithms for solving two types of question usually considered the domain of human intelligence and requiring some form of symbolic (rather than numerical or sub-symbolic) representation or reasoning: firstly, planning: suppose I am at (or in situation) X, and I want to get to Y: how do I do that And secondly, inference: suppose I know (or believe) that X is true, and I want to know if Y is true (or not), how do I do that?

In answering these questions, the more specific aims of the course are to: (1) learn declarative specification and programming in Prolog; (2) introduce efficient formulation of a problem space, a declarative notation for describing it, and algorithms for searching it; (3) introduce aspects of knowledge representation using propositional, predicate and modal logics, and algorithms for automated reasoning with those logics; and (4) introduce the concept of temporal reasoning using the Event Calculus.

### Learning Outcomes

Upon successful completion of this module, you will be able to: 1. use and evaluate different algorithms for searching a graph as a basis for planning and problem-solving 2. use and evaluate algorithms for automated reasoning in propositional, predicate and modal logics 3. apply formal languages for knowledge representation and reasoning through symbolic computation 4. write algorithms for planning and reasoning in Prolog (logic programming language)

### Syllabus

Search: search space, problem formulation, general graph search algorithm, graph theory; uninformed search strategies - depth first, breadth first, uniform cost, iterative deepening; informed search strategies - best first, A*, iterative deepening A*; analysis of algorithms - completeness, complexity, optimality; 2-player games: minimax, minimax to fixed ply, alpha-beta search; reinforcement learning and potential fields for path planning. Knowledge representation and reasoning: knowledge acquisition, knowledge engineering; propositional logic, predicate loigc, modal logic; semantic proof, syntactic proof, soundness and completeness of proof systems; resolution, unification; automated reasoning with calculus KE in propositional, predicate and modal logic; Event Calculus and reasoning about actions and events.
Assessment
Exam Duration: 3:00hrs
Exam contribution: 70%
Coursework contribution: 30%

Term: Autumn

Closed or Open Book (end of year exam): Closed

Coursework Requirement:
Assessed problem sheets

Oral Exam Required (as final assessment): no

Prerequisite module(s): None required

Course Homepage: http://www.iis.ee.ic.ac.uk/~j.pitt/Teaching.html

Book List: