WPI Worcester Polytechnic Institute

Computer Science Department

CS4341 Introduction to Artificial Intelligence 
Project 2 - C 2002

  1. Part I: Thursday, Jan. 31 at 10 am. 
  2. Part II: Wednesday, Feb. 6 at 9 pm. 

Project Goal:

The purpose of this project is to implement a rule based system. This rule based system will consist of three parts: a rule base, a working memory, and an inference engine.

Project Assignment:

  1. Part I: Follow by hand on a piece of paper the inference procedure used by a rule based system when applied to the rule base proj2_rulebase2.txt under each of the two reasoning modes:
  2. Part II: (90 points) Implement a rule based system.

Input Specifications:

The input file consists of 3 different parts (see the test files listed above for illustration):

  1. A list of IF THEN rules. Each rule is written in the following format
    Each condition (pre or postcondition) consists of three parts: one relational symbol and two arguments. We hereby call these conditions "relational statements". Examples of relational statements are:
         shape ?x square
         siblings ?x ?y
         older bob mark
         smart ?x nil
    Identifiers that start with a question mark denote variables. The first relational statement above states that ?x's shape is a square. The second relational statement states that ?x and ?y are sibblings. The third relational statement states that bob is older than mark. The fourth relational statement states that ?x is smart. Note that in this last case, the second argument is not needed (being smart is a "unary" condition :-) hence "nil" is used there as a placeholder for the second argument.

    Rules are separated by lines that contain the string "#####"

  2. A list of initial facts in the working memory. This section of the file starts with a line containing the string "WM" Each fact follows the same format described for relational statement above. This section of the file ends with a line containing the string "#####".

    In the case of an initial empty working memory, this section of the file will look like:


  3. A list of conjectures This section of the file starts with a line containing the string "CONJECTURES". Each conjecture follows the same format described for relational statements above.

Output Specifications:

Your output should consist of two parts: the results of the backward chaining and the results of the forward chaining.

  1. Results of the backward chaining mode.

    This section should start with a line containing the string "BACKWARD CHAINING" For each of the conjectures that appear at the end of the test file, output a line containing the conjecture followed by a line containing the string "yes" if the conjecture can be inferred from the set of rules, and "no" if the conjecture cannot be inferred from the set of rules. In case that the answer is "yes" print out in a new line the sequence of rule numbers (R1, R2, R3, ...) that were used (in the order in which the rules were applied/fired) to prove the conjecture.

  2. Results of the forward chaining mode.

    This section should start with a line containing the string "FORWARD CHAINING". Then, on separate lines, print out the list of ALL the relational statements that were inferred during the forward chaining in the order in which they were deduced and stored in the working memory. This list should not contain any repetitions nor relational statements that were already present in the initial working memory.

As an illustration, here is the output that your program should produce for proj2_rulebase1.txt:

is hobbes tiger
R1 R3 R4
is tweety mammal
hobbes is a mammal
hobbes is a carnivore
hobbes is a tiger
For a description of the process followed to obtain these results and the trees contructed, see Solutions CS4341 Exam 1 D01.

Your Code:

Your program (or an accompanying script, as described in your program documentation) must accept the name of the file to read the rulebase from.

Your code must contain two separate functions called backward_chaining and forward_chaining that implement the corresponding inference modes. In addition to them, your code must have functions that handle the working memory and the set of rules, as well as functions that construct the trees needed during the inference process. The code used for performing the search during the inference, must be the code that you implemented for project 1.

Although you are welcome to look at other code to guide the design of your program, you MUST submit your own original code.

Project Submission:

  1. Project 2 Part I is due on Thursday, Jan. 31 at 10 am. Please bring your solutions on a piece of paper and hand them in at the beginning of the class.

    Project 2 Part II is due at 9 pm on February 3,2002.  One (and only one) member of your group should submit the following files using the turnin program:


Graduate Credit Problem:

Due on Wednesday, Feb. 6 at 9 pm. 

Consider a commutative relation like for instance

married ?x ?y 
If say, married bob mary, then it also holds that married mary bob. Hence, the following rule is valid:
married ?x ?y
married ?y ?x
  1. (5 points) Discuss problems of including a rule like the one above in a regular rule based system (Hint: add it to proj2_rulebase2.txt and run your system over it with conjecture married dave donna.) Describe the problems you observe and explain in detail using the trees constructed during the process the cause of the problems.
  2. (5 points) Describe solutions to the problems above. Explain in detail how your solutions would be implemented and why they would avoid the problems observed.