70077

Introduction to Symbolic Artificial Intelligence

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, and SAT solvers (at least DP and DLL) as an application of propositional logic for automated reasoning in A.I.; the fundamentals of logic programming for knowledge representation (unification, resolution, logic programs, SLD); a variety of search algorithms widely used in A.I. for both uninformed (depth and breadth-first, iterative deepening) and informed search ( greedy BFS, A*); adversarial search in games (Minimax, alpha-beta pruning); search in in partially-observable domains; and basic planning algorithms (planning graphs, GraphPlan, PDDL).

Learning outcomes

After the module, you will be able to:
1. Formalise knowledge in propositional and first-order logic.
2. Apply and appraise fundamental SAT-solving algorithms.
3. Represent knowledge in logic programs through the application of unification, resolution and SLD.
4. Search for 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.               

Module syllabus

The module will divide into 4 topics.

A. Logic
- Propositional logic: syntax and semantics.
- SAT solvers: basic algorithms.
- First-order logic: syntax and semantics.

B. Knowledge Representation
- Minimal models of definite logic programs; SLD.
- Negation-by-failure; stratified and locally stratified logic programs.
- Applications in KR.

C. 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.

D Planning
- Algorithms for planning as state-space search.
- Planning graphs with applications to GraphPlan.
- Planning Domain Description Language (PDDL).           

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

There will be two pieces of assessed coursework, each contributing 10% of the final grade for the module.  Your first piece of coursework concerns logic, and consists of written exercises.  The second piece of assessed coursework covers material on search and planning, and typically involves the implementation of a search algorithm and its application to a planning problem.

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 both pieces of your assessed coursework. Feedback on the formative exercises will be given in class. You will receive cohort feedback for the examination.               

Module leaders

Dr Robert Craven
Dr Francesco Belardinelli