Building a Simple Rule-Based Reasoner

Laboratory Exercise 9


Artificial Intelligence Laboratory

Fall Semester 2001

[ Goals | Background | Pre-Lab | In-Lab | Post-Lab | More Info ]

Goals for the Laboratory Exercise

The goal of this lab is for you to understand some of the programming issues in building an inference engine for a system that reasons using modus ponens over a rule base.


We spent a couple of weeks in class discussing the use of logic as a tool for representing knowledge and reasoning about the world. In order to build a truly intelligent agent in this way, we need to develop more sophisticated logical languages and more sophisticated inference systems. That is a hard task at which many AI researchers are working.

It turns out that, for a large number of problems, a much simpler representation and reasoning scheme based on logical ideas will suffice. During the 1980s, a small industry based on the idea of a "rule-based system" flourished. Rule-based systems were essentially propositional logic systems extended to handle very simple variables, which used modus ponens for inferring new facts.

These systems used modus ponens in one of two ways. The most common was backward chaining, in which you asked the system if a specific assertion were true. The backward chainer would first see if the assertion was in its database of facts. If so, it could answer "yes". If not, it would try to find a rule that could infer the fact. It would then recurse on the preconditions of the rule because, if all the preconditions of the rule were true, then the specific assertion was true.

For example, we might ask (backward-chain 'eugene-is-cool)? If 'eugene-is-cool was in the database, then the function would return true immediately. If not, it would look for a rule that could infer 'eugene-is-cool, for example, ((eugene-teaches-AI eugene-plays-chess) eugene-is-cool). The system would then call itself recursively with 'eugene-teaches-AI and 'eugene-plays-chess as targets, and if both returned true it would return true for 'eugene-is-cool -- and add it to the database. If this rule failed, it try all other rules that infer 'eugene-is-cool, until it either found one that succeeded or all had failed.

A less common approach was forward chaining, in which the system would simply start with the facts in its database and try to infer every possible conclusion based on its rules. This sort of system would try to find rules whose preconditions matched things in its database. If all the preconditions of a rule were true, then it would add the rule's conclusion to the database. It would keep doing this until it could no longer add any new items to its database.

Building rule-based AI systems requires us to do two kinds of programming: writing an inference engine and writing a rule base. One of the central ideas of this approach is that, once we have written an inference engine, we can reuse it with any rule base. This was the source of seduction in rule-based systems... In principle, this approach makes it possible for "non-programmers" to build rule-based systems! Writing rules is much closer to their experience and abilities than writing a Lisp program to ask as an inference engine. For small rule bases and simple problems, this approach succeeded nicely. Unfortunately, it doesn't scale well to more general problems.

Pre-Lab Activities

Prior to doing the in-lab activity, be sure that you have done the following:

  1. Read this document in its entirety.


None this week.

In-Lab Activities

Assume that we have decided to use variable-free rules of this form:

( name (preconditions...) (conclusions...) )

Here is are a couple of examples:

(2 (c d) (g h))

(eugene-1 (fun cool grades-generously) (eugene))

  1. Implement an abstract data type for rules. This must include at least a set of access functions rule-name, rule-conditions, and rule-conclusions to retrieve the corresponding elements of a rule.

  2. Implement the function (forward-chain database rule-list). forward-chain fires the rules in rule-list until no new data can be concluded. database is a list of facts known to be true at the outset. forward-chain returns a list of all facts known to be true after inferring all that it can.

    Be sure to write and use helper functions where appropriate.

  3. Define a rule base for a domain of your own choice. Select a domain and task with which you have some expertise. Your rule base should have at least 20 rules.

  4. Evaluate your forward chainer and rule base on at least four different databases. Try to create at least one database that demonstrates an interesting feature of your domain, or an interesting feature of forward chaining in general.


Submit an e-mail message containing only a single, gcl-loadable file containing your solutions to the above exercises by Wednesday, October 31, at 4:00 PM. If you forget what "gcl-loadable" means, please review the instructions in Laboratory Exercise 2..

By that same time, submit a print-out of the same file, stapled, to me in person or to the department office.

Post-Lab Exercise

As we learned earlier in the semester, propositional logic restricts us from making and reasoning about some assertions easily ("A is a letter." "B is a letter." ... "Z is a letter.") or at all ("All Romans either loved Caesar or despised him."). The sort of "propositional" rules that we used for this exercise face the same limitations.

Think about the changes you would have to make to your forward chainer to support expressions containing variables. For example, we might want to say:


Send me a description of what you might do to make a forward chainer handle rules of this sort, via e-mail by 4:00 PM on Wednesday.

Further Information

None yet...

Eugene Wallingford ==== ==== October 24, 2001