Project 4: Logic Programming

Overview

Implement the Rete Algorithm for logical inference. Once the algorithm works, create two domains with two problem instances apiece to demonstrate it in action. Then refine the algorithm to allow prohibitions of unwanted conditions.

Setup

Clone the Github repository logic_programming. Push your own copy to your Github account as a private repository and add the instructor as a collaborator.

Programming Assignment

Complete the following functions and methods in logical.py:

  • Predicate.unify()
  • HornClause.bound_from_precondition()
  • Rete.add_clause()
  • Rete.clauses_for()
  • KnowledgeBase.add_facts()
    • Most of this is written - the part for you to complete is the else clause for parsing a Horn clause.
  • KnowledgeBase.propagate_forward()
    • For Level 1 credit, ignore negative constraints.
    • For Level 3 credit, take negative constraints into account.

Developing domains

Develop two problem domains. Each problem domain is specified as a series of Horn clauses. For each problem domain, also write a domain_main.py program to enable the user to interact with the knowledge base.

Two example domains are provided that may be useful as inspiration. The first example is a model for completing the Hendrix Computer Science major:

can_take CSCI_150
can_take MATH_130
can_take MATH_240

can_take CSCI_151 <- taken CSCI_150
can_take CSCI_235 <- taken CSCI_150
can_take CSCI_270 <- taken CSCI_150
can_take CSCI_285 <- taken CSCI_150; taken MATH_130
can_take CSCI_320 <- taken CSCI_151
can_take CSCI_322 <- taken CSCI_151
can_take CSCI_335 <- taken CSCI_151
can_take CSCI_340 <- taken CSCI_151
can_take CSCI_352 <- taken CSCI_151
can_take CSCI_360 <- taken CSCI_151
can_take CSCI_365 <- taken CSCI_150; taken MATH_240
can_take CSCI_370 <- taken CSCI_151
can_take CSCI_380 <- taken MATH_240
can_take CSCI_382 <- taken CSCI_151; taken MATH_240
can_take CSCI_410 <- taken CSCI_151

took_math <- taken CSCI_285
took_math <- taken CSCI_365
took_math <- taken CSCI_380
took_end_user <- taken CSCI_340
took_end_user <- taken CSCI_352
took_end_user <- taken CSCI_370
took_complex <- taken CSCI_335
took_complex <- taken CSCI_360

A predicate line consists of the name of the predicate followed by any parameters it has. A Horn clause line consists of the consequent of the Horn clause followed by a <-, after which are listed the preconditions, which in turn are separated by a ;.

Each domain is intended to be used with some case-specific facts. Here is one example of a facts file:

taken CSCI_150
taken CSCI_151
taken CSCI_380
taken CSCI_335
taken CSCI_370

In the next example, heroes_domain.txt, we have some free variables:

allies ?a ?c <- allies ?a ?b; allies ?b ?c
allies ?a ?b <- allies ?b ?a
enemies ?a ?c <- enemies ?a ?b; allies ?b ?c
enemies ?a ?b <- enemies ?b ?a
uncertain ?a ?b <- allies ?a ?b; enemies ?a ?b

!allies ?a ?a
!enemies ?a ?a
!uncertain ?a ?a

We have some negative constraints in this example, on the lines starting with !. Those are predicates that are not allowed to be true. If a Horn clause implies one of them, it will not be added as a true fact.

Here is an example facts file for that domain:

allies spider-man iron-man
allies daredevil spider-man
enemies kingpin daredevil

Paper

In your paper, discuss each of your domains informally. Then discuss the aspects of those domains you were able to encode in the domain-logic file and facts files.

Submission

  • Post your code on Github in your private repository. Make sure the instructor is added as a collaborator.
  • Upload your paper to Microsoft Teams.

Assessment

  • Level 1
    • Rete algorithm implementation passes all of the Level 1 tests.
  • Level 2
    • For each of two problem domains:
      • There is a domain file describing the basic logic of the domain.
      • There is a domain_main.py file that enables a user to interact with the domain’s knowledge base.
      • There are two problem files describing different situations in the domain.
      • The paper describes the intuition behind the domain.
      • The paper assesses how well the logic encoding models the domain, including a discussion of its strengths and limitations.
  • Level 3
    • The Rete algorithm passes all of the tests that employ negative constraints.
    • At least one domain has been augmented with at least one negative constraint.
    • The paper discusses the role and utility of this negative constraint.