Knowledge Representation

Module aims

Knowledge representation and reasoning are essential components of an intelligent system and are at the core of Artificial Intelligence research. The aim of this module is to provide the students with several computational concepts and tools that have been developed in logic-programming or otherwise symbolic reasoning, to support the knowledge representation and inference.

The material covered in the module will interleave the computational concepts of logic programming with applications of the concepts in knowledge representation and problem solving.
More specifically, the module will:

• Recap basic definitions from first-order logic as a necessary preliminary.
• Define definite logic programs, normal logic programs, core semantics for each and stratification. Define stable models, answer-set semantics and splitting sets.
• Present the syntax of Answer Set Programming (ASP), and their use for:
  • Defeasible reasoning
  • Solving combinatorial problems
  • Solving optimisation problems using preferences
• Define the action language C+ and its use for reasoning about action and change, causal reasoning, and planning.
• Present fundamental work on properties of non-monotonic reasoning formalisms, and give a view of the way in which different formalisms satisfy or fail to satisfy these properties.

Learning outcomes

Upon successful completion of this module a student will be able to:

1. write ASP programs that use constraints and choice operators
2. represent and solve NP-hard combinatorial problems in ASP
3. solve optimisation problems using preferences
4. model complex planning environments using logic-based action description languages
5. prove properties of the underlying semantics for ASP and the action language C+ using the appropriate mathematical tools.
6. reason about the more abstract desirable properties of non-monotonic formalisms in general.

Module syllabus

• Logic Programming
  • Recap of FOL
  • definite logic programs
  • Intro to negation & stratified logic programs
• Answer Set Semantics
  • normal logic programs
  • stable model & answer set semantics
  • integrity constraints & choice
• Defeasible reasoning in ASP
• Modelling and solving problems in ASP
  • Practical examples include: Hamiltonian circuits, navigating mazes, fault diagnosis using abduction, generating haiku, understanding conversational implicature using abduction
• Modelling preferences in ASP
• Reasoning about actions and change
  • causal reasoning
  • the action language C+
  • Action description languages and ASP
  • Plan verification: regression, progression
  • Planning with incomplete information
  • Explaining observations through action occurrences
  • Diagnosis - repairing plans
• Non-monotonic consequence relations
  • Desirable properties of non-monotonic logics
  • Different formalisms for non-monotonic reasoning (e.g., Default Logic, Autoepistemic Logic). The satisfaction by ASP, action languages, and these other formalisms of the aforementioned properties.

Teaching methods

7 weeks of 4 hours, divided between lectures, paper-based tutorials and lab sessions. The precise division between lectures, labs, paper exercises, will vary depending on the needs of each topic. 2hrs at the end of the module for wrap-up and revision.

An online service will be used as a discussion forum for the module.

Assessments

There will be two assessed coursework exercises, each contributing 10% of the total mark for the module. The first will be set in week 3 and will be a programming exercise using ASP; the second will be set in week 5 and will be a mixture of programming and paper-based exercises, on action languages.

20 hours (10 hrs for each assessed coursework).

Coursework 1 will be submitted as code and marked by the instructor.

Coursework 2 will be submitted as code, and as an electronic written submission and will be written by the instructor.

Module leaders

Dr Richard Evans
Dr Robert Craven