You don't need an expert system shell for rule-based programming—you can write rules in plain old vanilla C
Despite what you've been told, you don't necessarily need a fancy expert system shelf to enjoy the advantages of rule-based programming, one of the most useful and widely used ideas to come out of AI. In this month's column, we'll learn how to write rules in plain vanilla C, look at some programming examples, and discuss forward chaining and simple control structures. By the time we're done, you should have a clear idea of how to use rule-based programming techniques in a conventional programming language.
Rules allow us to represent certain kinds of knowledge that are difficult to employ n a conventional procedural program. Rule-based programs also separate the knowledge from the rest of the program in such a way that a change in the knowledge base is not propagated throughout the program like a change in a procedural program can be.
This flexibility allows you to defer some kinds of decisions or reconsider them halfway through the program without completely rebuilding it. Rules are ideal for expert systems, where the process the program is to perform is very imperfectly understood, at least at the outset.
Rule-based programs can be written several ways. Some languages, such as OPS-5, are intended for this purpose. There are also expert systems shells of many kinds, prices, and capabilities. Either approach can offer a great deal of power in rule-based programming and should be considered for an expert system or any program that will have a great many rules. However, in some cases these approaches sacrifice the capability of the procedural programming on such prosaic areas as I/O and screen control.
In any case, you are required to learn new ways to do old things. For a program with just a few rules or for experimenting, you might consider writing a rule-based program in C.
In a rule-based program, the function is embodied in a set of rules written in something resembling English. A rule has a condition or set of conditions called the IF part and a result or set of results called the THEN part. The THEN part of the rule usually consists of actions to be performed. If the IF part of the rule is satisfied the rule can fire. If the rule fires, actions in the THEN part are performed
IF there is rain
AND you must walk
THEN umbrella is necessary
In this case the THEN portion doesn't look like an action. It could also be written umbrella = necessary, and in either case could have the effect of assigning the string necessary to the variable umbrella or giving the Boolean umbrella a value of TRUE or whatever your program requires. The IF part could also be rewritten as IF rain is true, which would look more like a normal program.
RULES IN C
In most rule-based systems the rules are written in a language resembling English, like the rule in the previous example, and the rule interpreter converts them into language the machine can deal with. To dispense with the rule interpreter, we are going to write our rules directly in C. To someone familiar with the language these rules will be easy to read, and judicious use of the preprocessor can make them even clearer. (Similar techniques could be used in many programming languages.) Here is the first rule from Listing 1.
if (av_speed > 60)
fly =1:
When the function rules() is called, the global variable av_speed has a value calculated from the numbers entered by the user. The variable fly has its initial value, which is 0. If av_speed is less than or equal to 60, the rule does not fire and fly keeps the value of 0.
Nothing here is different from a normal C program. We are just using different names and structuring things a bit differently.
CONTROL
Simply encoding the rules is not enough, we must also have control over them. Since it is impossible to fire all of the currently valid rules simultaneously, there must be a conflict-resolution strategy. This is more important in very large programs where rule sequencing can have a great effect on the speed of execution, but even the smallest program must have a means of choosing the next rule to fire.
The simplest way to use rules like these in a program is to start with the data and allow the rules to work toward a solution through a process called forward chaining. This can be done by checking each rule in turn to see if the available data (the environment or context) satisfies the IF portion and, if it does, performing the action in the THEN part. When you reach the end of the rules, you have made all the deductions that can be made on the basis of the initial data.
This is the simplest kind of a rule-based system. The rule module is called and it looks at some global variables and draws certain conclusions. These conclusions result in changes in the global database. Then the module returns.
Listing 1 is an example of forward chaining. It is a toy system to help decide what means of transportation to use for a trip. The main program begins by gathering all the necessary data and filling some of the global variables. It then calls the rule module that processed the data and fills in some more of the global variables with its results. (In the interest of simplicity, all these variables are Booleans.) Finally, the main program reports its conclusion to the user.
You have probably been taught to avoid global variables (and for good reason) but using them simplifies a small system like this one. For larger programs, it is better to pass structures to the rule modules and avoid global variables.
Notice that some of the rules produce data used by other rules. The order in which the rules are written insures that the data is ready when needed. The rules are checked one at a time in the order they are written and each of them fires if it’s IF part is satisfied. This is control, even though it is so simple.
Listing 2 is modified so the rules may appear in any sequence. For the rules function be independent of rule order, it must go through the rules more than once. If you continue to loop through the rules until none of them fires, you are assured of drawing all the conclusions the data supports.
This can be done with a flag to indicate the firing of a rule. In Listing 2 this flag is called done. Each rule makes done false if it fires. This insures that the module will repeat until it exhaust all changes. Within each iteration the rules are tested in order, just as in Listing 1.
It is necessary to prevent rules that have fired in a previous iteration from firing again, which would have no effect on the data but would cause the function to loop endlessly. This can be accomplished several ways, one of which is shown in Listing 2: the variables are three-valued and initialized to 2, which represents UNKNOWN.
The rules have a new check in the IF part that keeps the rule from firing unless the variable to be changed is UNKNOWN. For example, the first rule shown in Listing 2 is
if (av_speed > 60
&& fly == UNKNOWN) }
fly = TRUE:
done = false
When the function rules is called and this rule is tested for the first time, the variable fly will have its initial value of UNKNOWN or 2. If the global variable av_speed is greater than 60, this rule will fire and change the value of fly to TRUE. This rule cannot fire again in a future iteration of rules because fly is now TRUE and the rule cannot fire unless fly is UNKNOWN.
But this strategy introduces another order dependency. If two rules of this form affect the same variable, the final value of the variable depends on the order of the rules. The one that fires first prevents the other from firing. This is not necessarily bad, but you must be aware of it.
It is possible to accomplish nearly the same result by preventing rules from firing unless they will change the value of some variable. The previous example could be rewritten
if (av_speed > 60
& & fly ! = TRUE{
fly = TRUE
done = FALSE
}
This prevents the rule from firing when it would have no effect. However,
it is now possible for two rules to change a variable back and forth to another.
These strategies may be mixed. You might write a rule that will fire and give
a value to a variable only if that variable is UNKNOWN. Then a later rule, if
otherwise satisfied, might fire and give a new value to the same variable if
it does not already have that value:
if (av_speed > 60
& & fly UNKNOWN) {
fly = TRUE;
done = FALSE;
}
if (hate_flying)
& & fly ! = FALSE){
fly = FALSE;
done = FALSE;
}
This has the effect of allowing the hate_flying rule to override the av_speed rule regardless of the order on which they occur. Also, two or more rules can give different values to the same variable without creating an endless loop.
Yet another way to control the execution of the rules is to break them into several modules that are called as needed by the main program. Listing 3 is an example of this technique. The first function, air_land, decides between driving and flying and returns to the main program. The main program then calls either fly_rul() or drive_rul() to choose a specific vehicle. The module to call next is chosen by the main program on the basis of the information on the global variables.
As always, this sort of modularity improves the clarity of a program. It also increases speed by eliminating sections of rules from consideration.
In the module air_land(), the first rule causes a return form the module if it fires. This is valid because the average speed cannot satisfy both of the rules in the module. It is desirable because we gain a bit of speed by not considering the second rule of the first one fires.
Another method of accomplishing almost the same thing as separately called modules is to include a state requirement in the IF portion of each rule. Some means must be provided for changing to the next state, typically a line in the THEN portion is some of the rules
Not every rule will need to cause a state change. For example
if(state== air_land
& & av_speed < 60) {
drive = TRUE
state = choose_ground_veh;
}
It is also possible to change states at a certain point in the execution of a rule module without reference to the data. In that case, a rule such as this one would be used:
if (state == air_land)
state = choose_ground_veh;
This rule would probably be used at the end of a section of rules, organized so that it could not be reached until the state change was appropriate.
GOING FURTHER
The ideas here are best used for simple jobs or as a foundation for a study of more complex cases. However, do not overlook the fact that the techniques demonstrated in these examples can be used for a very large but uncomplicated jobs. They could be embedded in a C program to solve a classification problem or replace a complex decision tree.
To learn more about the subject, see the references. You might also want to experiment with the demonstration programs offered by several of the companies that sell expert systems shells. I found the EXSYS demo useful.
Lynwood Wilson is a programmer, teacher, and writer specializing in small computers. In addition to his freelance work, he is a founder and vice president of Mandarin Systems, an expert system house in North Carolina.
REFERENCES
Schildt, Herbert. Artificial Intelligence Using C. New York, N.Y.: Osborne McGraw-Hill, 1987.
Winston, Patrick Henry. Artificial Intelligence. Reading, Mass: Addison-Wesley, 1984.
