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 course is to provide the students with several computational concepts and tools that have been developed in logic programming to support symbolic reasoning.
The material covered in the course will interleave the computational concepts of logic programming with applications of the concepts in knowledge representation and problem solving.

The students will have the opportunity to:

  • Learn the general framework of Answer Set Programming (ASP) that interprets logic programs under the Answer Set Semantics
  • Learn to use ASP for:
    • Defeasible reasoning
    • Solving combinatorial problems
    • Solving optimisation problems using preferences
    • Reasoning about actions and change
  • Put in practice the topics learned in class by solving simple problems using an ASP environment
  • Learn about Datalog+/-, an extension of logic programming to deal with the Open World semantics of the Semantic Web.

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.Translate these planning environments into ASP programming to solve different types of planning tasks
6.Analyse the role of Open World in Semantic Web Ontologies
 

Module syllabus

  • Week 1: Logic Programming (Jorge)
    • Introduction to / recap of first-order logic
      • We shall teach syntax and semantics, but not inference rules (nor soundness nor completeness)
    • Definite logic programs
    • Intro to negation & stratified logic programs
  • Week 2: Answer Set Semantics (Richard) [IOL 1]
    • Normal logic programs
    • Stable model & answer set semantics
    • Integrity constraints & choice
    • Defeasible reasoning in ASP
  • Week 3: Modelling and solving problems in ASP (Richard) [IOL 2]
    • How to model NP problems using generate and test
    • Practical examples including: Hamiltonian circuits, navigating mazes, fault diagnosis using abduction, generating haiku, understanding conversational implicature using abduction
    • Grounding and solving of ASP programs
    • How to optimize grounding and solving
  • Week 4: Modelling preferences in ASP (Richard) [IOL 3]
    • How weak constraints are represented
    • How optimization is performed
    • Practical examples: shortest path, maze generation
  • Week 5: Reasoning about actions and change (Jorge) [IOL 4]
    • Causal reasoning
    • Action description languages and ASP
    • Plan verification: regression, progression
    • Planning with incomplete information
    • Explaining observations through action occurrences  
  • Week 6: The Semantic Web (Jorge) [IOL 5]
    • Light intro to Description Logic and ontologies
    • Datalog+/-
  • Week 7: Emerging topics (Jorge) [non-examinable]. Possible topics include:
    • Probabilistic logic programming
    • Neural Networks and symbolic reasoning
      • modelling propositional logic operations in neural networks
      • an introduction to hybrid neural-symbolic architectures

Relevant reading:

  • Knowledge representation, reasoning and declarative problem solving (Baral)
  • Answer Set Programming (Liftschitz)
  • Knowledge Representation, Reasoning, and the Design of Intelligent Agents (Gelfond)
  • Answer Set Solving in Practice (Gebser et al)
  • Commensense Reasoning Using Answer Set Programming (Mueller)

Teaching methods

7 weeks of 3 hours of lectures + 1 hour of tutorial
Coursework will start during tutorial hours and will be completed out of the class
2 hours at the end of the course will be dedicated to (1) do a quick overview of probabilistic logic programming and (2) make connections between symbolic computation to Neural Networks. This will include: modelling propositional logic operations in neural networks, modelling first-order logic operations in neural networks, an introduction to hybrid neural-symbolic architectures.

Assessments

There will be two coursework exercises during weeks 4 and 7, each contributing 10% of the total mark for the module. They will be programming exercises that should take at most 10 hours each. These exercises will be backed up by unassessed exercises designed to reinforce the material as it is taught. Coursework exercises will be similar to the unassessed exercises. Most of the exercises will be covered in tutorials.

  • The first coursework exercise will be on defeasible inference and modelling NP problems (e.g. graph coloring).
  • The second coursework exercise will be on modelling actions and change.

The coursework will be take-home programming problems and will consist of several simple exercises that can be solved in a few hours. The students will be given one week to do the exercises.

Module leaders

Mr Richard Evans
Professor Jorge Lobo