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

## ELEC60004 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

Decalrative Programming. Search: search space, problem formulation, generic 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 gamesL minimax and alpha-beta search; reinforcement learning and potential fields for path planning. Knowledge representation and reasoning; propositional logic, predicate logic and modal logic: semantic proof and syntactic proof; soundness and completeness; automated reasoning with proof system KE; modal logic and practical reasoning with boxKE; temporal reasoning with the Event Calculus.
Assessment
Exam Duration: 3:00hrs
Exam contribution: 80%
Coursework contribution: 20%

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: