CS B552 Knowledge-Based Computation

Homework 2: Creating a Rule-Based System

Due Date: 11:59pm on Wednesday, Feb 8

Assignment Goals

Goals of the assignment are to understand production systems, their implementation, and basic knowledge representation for rule-based systems.

Assignment Task

In this assignment you will write a simple forward-chaining production system in python and test it in the medical domain you coded in hw1.  The assignment may be done individually or in groups of 2.  If you wish to work in a group, please email Eriya the group members by January 27.

Before You Start

Be sure to read the Guidelines for AI programming assignments before starting. All system knowledge should be represented declaratively.

Detailed Description

You will write code to define and manage a working memory, given a set of rules.  Your top-level procedure will be “run-ps”, taking three arguments:

1.    a working memory (a list of facts, abbreviated as wm)

2.    a list of rules

3.    True or False, depending on whether the system is being run in question mode.

Question mode enables the system to ask the user about the truth of conditions it has not been able to infer from other knowledge.  When question mode is turned off, the system must start with all relevant information.   When it is turned on, it can model a physician asking the patient about unknown symptoms while doing a diagnosis. 

For example, the rules in hw1 include:

If a patient has a high fever and congestion, the patient has the flu.

The facts given in hw1 include that Ed has a high fever, but nothing about whether he is congested.  The system will not be able to infer whether Ed is congested from its initial rules and facts.  In "question mode", when the system tries to apply this rule (or any rule whose antecedent has a value it cannot confirm), it will ask the user whether this antecedent should be added to the working memory:

“has-symptom congestion Ed positive” was not in the working memory. Would you like to add it? (Yes / No / Quit)

Function of question mode

In question mode, the system will first run to completion without asking questions, to generate all conclusions it can from the initial facts.  This fills in its background knowledge.  It will then re-run itself with questions enabled. 

It will ask the user a question each time it encounters an antecedent satisfying four conditions:  (1) all variables have been bound, (2) the antecedent is not in the working memory, (3) the system has not yet asked the user about it, and (4) at least one antecedent of the rule has already been found in memory.  The final condition makes questions focus on rules for which there is already some evidence of relevance.

When a question is asked, the system will allow the user to enter “Yes”, “No”, or “Quit”.  If the value is “Yes”, the system adds the assertion to working memory.  We encourage writing your program so it then re-runs itself (not in question mode) to see if this new assertion can enable new rules to fire, filling in more knowledge.  However, you may also have it proceed through all questions if there are unmatched antecedents, and then re-run itself with question mode turned off (to update knowledge), and re-run in question mode (to ask questions based on any rules that became relevant during the update).

If the input value is “No”, the system should set this antecedent aside (to prevent re-asking the user) and continue. “Quit” terminates the inference process.

Notes

You will test this with the rules and facts you encoded in hw1.

Question mode should only ask questions about rules that have two or more antecedents.

Your production system will run its rules repeatedly, outputting a trace of its process. When no new patterns are found on an iteration or when the user enters “Quit” in question mode, it will return the current working memory. Sample output at the end of this assignment shows one possible form for the output description.

You may encode the system as you choose, provided it applies exhaustive depth-first search.  If you wish more detailed guidance, we provide step by step instructions for a basic design, to which you will add the capability for the system to ask questions.

Flow of the program

With Question mode disabled:

1.    The program matches the facts in the working memory against the list of rules to see if any consequents can be generated.

2.    Repeat step 1 until no new inferences can be generated.

With Question mode enabled:

1.    The program matches the facts in the working memory against the list of rules to see if any inferences can be generated.

2.    Repeat step 1 until no new inferences can be generated.

3.    The program is re-run, with the change that:  If the system encounters an antecedent for which (1) all variables have been bound, (2) the antecedent is not in the working memory, (3) the system has not yet asked the user about it, and (4) at least one antecedent of the rule has already been matched, it asks the user whether this antecedent should be added to the working memory or not.

                              i.           If “Yes”, add the assertion to the working memory. Go to step 1.

                             ii.           If “No”, repeat step 3.

                            iii.           If “Quit”, terminate the inference process.

 Sample Output

CYCLE 1

Current WM:

…

Attempting to match rule 1

Failing

Attempting to match rule 2

Match succeeds

Adding assertions to WM:

…

Attempting to match rule 3

Match succeeds

Adding assertions to WM:

...

Attempting to match rule 4

Failing

...

CYCLE 2

Current WM:

...

Attempting to match rule 1

Failing

Attempting to match rule 2

Match succeeds

No new WM assertions

Attempting to match rule 3

Match succeeds

No new WM assertions

Attempting to match rule 4

Failing

Attempting to match rule 5

Match succeeds

Adding assertions to WM:

...

CYCLE 3

...

CYCLE 4

...

NO CHANGES ON LAST CYCLE, HALTING

[Outputs contents of wm]

 ...

 )

> 

Submission

The assignment will be submitted electronically, on Canvas.  For group work, each group should submit only one copy with both names, with a brief comment describing the division of effort/parts done by each member.  You should submit separate files for:

1.    Your code (well documented, with instructions on how to run it), including your rules and facts from hw1, to make a runnable system.

2.    A trace of your system running with your rules on the facts from hw1. Your output should provide the same information illustrated above in an easily readable form, but need not use exactly the same format.

You may submit as many versions as you wish (only the last submission before the deadline will be graded). We recommend submitting a first version before the last minute, to make sure it's in the system. Also, please keep backup copies of all your files.