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.
Prior to doing the in-lab activity, be sure that you have done the following:
None this week.
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))
Be sure to write and use helper functions where appropriate.
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.
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.
None yet...