Logic and Symbolic AI

Module aims

This module aims to give you skills and techniques used pervasively in the design and implementation of symbolic AI systems along with basic knowledge of several central areas of symbolic AI.

The module presents the syntax and semantics of propositional and first-order logic; definite and normal logic programs as a knowledge representation formalism; Herbrand models and stable model semantics; fundamentals of answer-set programming as an implementation of logic programming; a variety of search algorithms widely used in AI for both uninformed (depth and breadth-first, iterative deepening) and informed search (greedy BFS,  A*); adversarial search in games (Minimax, alpha-beta pruning); as well as basic planning frameworks (PDDL) and tools (planning.domains).

Learning outcomes

After the module, you will be able to:

1. Formalise statements in propositional and first-order logic.
2. Reason about the effects of specific formalisations in approaches to logic programming.
3. Represent problem-domains as answer-set programs, and calculate models, and use current implementations.
4. Find solutions by applying standard searching algorithms.
5. Critically evaluate the strengths and weaknesses of search algorithms.
6. Formalise planning problems and use search algorithms to solve them, including some basic online planning tools.        

Module syllabus

Outline syllabus:

A. Logic
- Propositional logic: syntax, semantics, translation into and out of the logic.
- First-order logic: syntax, semantics, translation into and out of the logic.

B. Foundations of KR
- Definite logic programs, Herbrand models
- Normal logic programs, stratification
- Stable model semantics

C. ASP
- ASP as an implementation of normal logic programming
- Features of ASP language to optimise knowledge representation tasks

D. Search
- Methods for Searching Solutions (time and space complexity).
- Uninformed and Informed Search Strategies (breadth- and depth-first search, iterative deepening, best-first search, A*).
- Adversarial Search (Minimax, alpha-beta pruning).
- Heuristic Functions.

E. Planning
- Algorithms for planning as state-space search.
- Planning Domain Description Language (PDDL). planning-domains as an online planning tool.

Teaching methods

You will learn using a combination of lectures, and tutorials with written and computer-based exercises.  Tutorials will cover both the theoretical content of the module as well as give you practice in the application of algorithms covered, and the practical representation of problems.  This also applies to the assessed coursework exercises.  An online Q&A forum will be used to supplement the opportunity for questions in the lectures and tutorials.            

Assessments

Coursework will contribute 20% of the module.  It will be a combination of written exercises (theory, and also working-through of algorithms by hand) and practical programming (involving the representation of a problem-domain or implementation of a key algorithm), covering multiple sections of the syllabus.

The remainder of the marks, 80%, will come from a final written examination. Formative assessments include unassessed exercises.
            
You will be provided with individual written feedback for assessed coursework. Feedback on the formative exercises will be given in class. You will receive cohort feedback for the examination.

Reading list

Core reading

Supplementary reading

Module leaders

Dr Robert Craven
Dr Francesco Belardinelli

Reading List

View the module reading list (Leganto)