CS4341 Introduction to Artificial Intelligence 
Project 2 - C 2002

DUE DATES:

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

• Project Goal
• Project Assignment
• Input Specifications
  • Sample Input Files
    • proj2_rulebase1.txt
    • proj2_rulebase2.txt
    • proj2_rulebase3.txt
• Output Specifications
• Your Code
• Project Submission
• Grading
• Graduate Credit Problem

Project Goal:

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:
   • (5 points) Forward Chaining Use forward chaining to derive ALL assertions that are derivable from this knowledge base (that is, from the set of rules together with the assertions in the working memory). Construct all trees showing the steps followed by forward chaining and show when and how the working memory is updated during the process.
   • (5 points) Backward Chaining Use backward chaining to determine the truth value of each of the conjetures in the file (i.e. weather or not each conjecture is true or false). Construct a tree showing the steps followed by backward chaining and show when and how the working memory is updated during the depth 1st search.
2. Part II: (90 points) Implement a rule based system.
   • Your program must run on the CCC Unix machines
   • You may use any high-level language (Java, Lisp, Prolog, C, C++, ...).
   • Your program must adhere to the Input and Output Specifications.
   • Your program must demonstrate the following inference modes:
     • Backward Chaining.
     • Forward Chaining.
       Conflict resolution technique: Use the rules in the order in which they appear in the input file.
     Your program must use the algorithms described in the textbook to implement these reasoning modes.
   • Your program must use the depth-1st search code that you implemented for Project 1.

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

        IF
        precondition-1
        precondition-2
        ...
        precondition-n
        THEN
        postcondition
        

   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:

       WM
       #####
       

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:

BACKWARD CHAINING
is hobbes tiger
yes
R1 R3 R4
is tweety mammal
no
FORWARD CHAINING
hobbes is a mammal
hobbes is a carnivore
hobbes is a tiger

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:

   • proj2_readme.txt: Containing:
     • the names of the members of your group
     • code documentation following the Departmental Documentation Standard
     • instructions on compiling and running your program
   • proj2_script.scr: A capture script of your program working on the sample file
   • The source code for your program
   • Any ancillary files that your program requires

Grading:

• Part I: 10 points.
• Part II: 90 points.
  • Test Input Files
    • proj2_grading_test1.txt
    • proj2_grading_test2.txt
    • proj2_grading_test3.txt
  Note that below we don't assign points to each of the test cases but to the process that they are following to construct the answer. Hence the test cases should be used to give the grader an idea of what your program does right or wrong.

  • Documentation: 10 points

  • Forward Chaining: 40 points
    "following the right procedure":
    • for all rules (one at a time):
      • branching out correctly: 10 points
        i.e. finding all instantiations of the current assertion in the working memory and keeping track of variable bindings
      • constructing each branch correctly: 10 points
        i.e. checking all the assertions (until done or one assertion is false) in the antecedents of the rules
      • right termination condition for each rule: 5 points
        stopping the construction of a tree when no more branches can be explored
    • right termination condition for the whole forward chaining process: 10 points
      i.e. stopping only after none of the rules have produced any new assertions during a full "epoch".
    • updating working memory correctly: 5 points
      

  • Backward Chaining: 40 points
    "following the right procedure":
    • starting the backward chaining from the conjecture: 2 points
      
    • for all assertion that needs to be proven (one at a time):
      • checking working memory to see if assertion is true: 3 points
        
      • branching out correctly: 15 points
        i.e. in case that assertion is not found in WM, finding all rules whose consequents match the assertion and creating a "branch" for each one and exploring them in a depth-1st manner
      • constructing each branch correctly: 10 points
        i.e. checking all the assertions (until done or one assertion is false) in the antecedents of the rules and keeping track of variable bindings
    • right termination condition for the whole backward chaining process: 10 points
      i.e. stopping only after the conjecture is proven (i.e.when a derivation branch succeeds) or all the branches in the derivation tree fail.
    • updating working memory correctly: 5 points
      

  • Extra Credit: 10 points for using their depth-1st search code from Proj. 1

• Total: 100 points + 10 extra-credit points.

Graduate Credit Problem:

Consider a commutative relation like for instance

married ?x ?y 

IF
married ?x ?y
THEN 
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.