--> Logic Programming and Artificial Intelligence (LPA) - 2nd year module - CS department - University of York

LPA is a second year CS course in the same clump as TOC. To some degree, this course carries on from TOC.

The Road to LPA

Prequesites, assessment, and further information can be found on the LPA module description page (York access only).

What is LPA about?

The field of Artificial Intelligence (AI) studies processes of intelligence as computational processes. Logic programming is a declarative programming paradigm based on mathematical logic that is well-suited to building AI systems. The LPA course introduces students to both AI and Logic Programming, with particular emphasis on the common foundations: search spaces, search and planning, declarative representation and deduction.

By the end of the LPA module, students will have:

  1. gained an understanding of the main principles of logic programming and will have learnt how to apply them in various logic programming environments.
  2. become familiar with some of the foundations of artificial intelligence and with how to apply them in the design of application systems.
  3. learnt programming skills using the Prolog language, with an emphasis on recursion, list processing and AI programs.
  4. got to grips with the basics of first-order logic including: syntax, semantics, entailment, proof (soundness, completeness) and its use in formalising a domain.

News and other announcements

The LPA forum can be found here Check often to see what discussions have been going on. Announcements about LPA will also make it to the forum pages.

Your can view your mini exam marks here. These marks are provisional, subject to ratification by the Board of Examiners.

Course content

The LPA course is split into a series of units. Some of these are independent of the others and some are closely linked. These units and the approximate number of lectures per unit are outlined below:

  1. General introduction: (2 lectures) Overview of the module. Introduction to declarative programming and artificial intelligence. Anatomy of an AI system. Introduction to intelligent agents.
  2. Introduction to problem solving and search: (3 lectures) Problem solving and problem representations. Uninformed search methods.
  3. Introduction to first-order logic: (5 lectures) Logical arguments and entailment. Review of propositional logic. Syntax and semantics. Formulating a domain.
  4. Deduction with Horn clauses: (6 lectures) The Horn-clause subset of logic. SLD resolution and the SLD search space. Soundness and completeness. Answer extraction.The limitations of Horn clauses.
  5. Programming with logic: (8 lectures) The PROLOG programming language. Recursive programs and recursive data types, especially lists. Controlling search, arithmetic, input/output and negation as failure.
  6. Advanced problem solving and search: (4 lectures) Informed search methods. Constraint satisfaction.
  7. Reasoning about change: (3 lectures) Using situation calculus to represent dynamic domains. The STRIPS representation of the planning problem. From situation space planning to partial-order planning.
  8. Intelligent Agents: (3 lectures)  Reactive vs. Logic-based AI. Hybrid Agents. Multi-Agent Systems.  

Books and other material

The main textbook for this course is the second edition of "Artificial Intelligence: A Modern Approach (Third Edition)" by Stuart Russell and Peter Norvig. This is a book that all students should buy and read. The textbook will be of use again in enough modules of the CS degree to make it worth buying. However, as it is quite expensive, students are advised to make use of the library where there are 12 copies of the second edition (11 one-week loan, 1 ordinary loan).

Download course materials

Unit 1: General Introduction
  • Guide to Unit 1 (18 Jan 2011)
  • Lecture slides: Module Introduction (18 Jan 2011)
  • Lecture slides: Introduction to AI and Agents (19 Jan 2011)
    • Unit 2: Introduction to Problem Solving and Search
  • Guide to Unit 2 (20 Jan 2011)
  • Lecture slides: Problem Representation (20 Jan 2011)
  • Lecture slides: The Lighthill debate (21 Jan 2011)
  • Reading: David J. Chalmers. The Conscious Mind. Introduction: Taking Consciousness Seriously. Oxford Paperbacks (1998).
  • Lecture slides: Uninformed Search (25 & 27 Jan 2011)
    • Unit 3: Introduction to First-Order Logic
  • Lecture Slides: Introduction to Logic (28 Jan 2011).
  • Lecture Notes: Introduction to Logic (28 Jan 2011).
  • Lecture Slides: Propositional Logic (1 Feb 2011).
  • Lecture Notes: Propositional Logic (1 Feb 2011).
  • Lecture Notes: More Semantic Definitions (1 Feb 2011).
  • Lecture Slides: First-Order Logic (3 Feb 2011).
  • Lecture Slides: Building a representation with first-order logic (8 Feb 2011).
    • Unit 4: Deduction with Horn Clauses
  • Lecture Slides: SLD Proofs for Propositional Logic (10 Feb 2011).
  • Lecture Slides: SLD Proofs for First-Order Predicate Calculus (11 Feb 2011).
  • More reading: Summary of FOL terminology (in Sections 2.1.2 - 2.1.3, pp.17-22) Note additional LP naming conventions and variation in substitution notation.
    • Unit 5: Programming with Logic
  • Lecture slides: Introduction to Prolog (22 Feb - 03 Mar)
  • Lecture slides: Advanced Prolog Concepts (03 Mar - )
    • Unit 6: Advanced Problem Solving and Search
  • Lecture slides: Informed Search
  • Lecture slides: Local Search Algorithms
  • Lecture slides: Constraint Satisfaction Problems
    • Unit 7: Reasoning about Change
  • Lecture Notes: Representing the Dynamic Blocks World
  • Lecture slides: Planning
  • Example: Solving the Sussman Anomaly with POP
    • Unit 8: Reactive Agents and Multi-Agent Systems
  • Lecture slides