Back to TOC Features

Decision-Making with Production Systems

Dwayne Phillips

Computers still can't think, but they can do a respectable job of carrying out policy.

Introduction

Software is often used to make complex decisions. Commonly used techniques employ levels of if-then-else statements, switch-case structures, Boolean operations on bit strings, etc. An excellent decision-making tool from the field of Artificial Intelligence (AI) is the production system. In contrast to hard-coded decision-making structures, production systems store decision-making knowledge in a set of external production rules.

Production systems were first proposed in the 1940s. They have taken many forms and have been applied to many problems. The development of production systems has come primarily at the hands of AI and expert-system researchers. The resulting applications are typically used to support difficult decision-making situations, for example, a doctor diagnosing a patient. But a production system can also make a valuable decision-making tool for programmers.

If it's written as a self-contained module (see [1]), the production system can be used in many different situations. The production system eliminates the need for stacks of if-then-else statements, which must be unique for every program, and which the programmer must create from scratch. The source code for a production system does not change; only the production rules change, depending on the situation. Programmers can enter the production rules in easily understood text (IF is_odd AND gt_zero THEN-CALL routine_x).

In this article I discuss the basics of production systems. I present a couple of examples, along with source code that implements a simple production system. I also suggest ways the sample production system might be extended.

How Production Systems Work

The basis for all production systems is the condition-action pair known as a production rule: IF condition THEN take action. Production systems consist of three parts: (1) a rule base of production rules, (2) a buffer, known as the context, and (3) an interpreter that controls the system. These parts are represented schematically in Figure 1.

A production system reaches a decision through one or more iterations. The algorithm applied in each iteration is as follows:

1. Search through the production rules; find all the rules whose conditions are satisfied by the context buffer. The context buffer is basically a list of all the conditions which are currently "true." Place all the production rules whose conditions are satisfied in a hit list.

2. Remove any hit from the hit list whose action (that is, output) is already contained in the context buffer.

3. If no production rules are left in the hit list, quit.

4. Otherwise, find the rule on the hit list with the lowest number.

5. Fire the rule found in step 4, adding its action (or output) to the context buffer.

6. Reset the hit list and go back to 1.

When the interpreter finds a satisfied condition in the production rules, it fires or activates the action. Activation consists of adding that action to the context. The context, sometimes called a data buffer or short-term memory, is what the interpreter uses to pick which production rule to fire. The original context contains the initial conditions of the production system, that is, the conditions which hold in the problem environment at the beginning of the decision-making process. As the interpreter works through the situation, the context grows with the addition of actions. The actions added to the context become new conditions.

This iterative process is what gives the production system its power. Thus, a production system is more than just a list of if-then pairs. This algorithm cycles repeatedly until there are no production rules that can fire. Each cycle comprises (1) matching, (2) conflict resolution, and (3) action phases. Matching occurs in step 1 above. Conflict resolution occurs in steps 2 and 4. It is the norm for more than one production rule to hit on the current context. The interpreter should only fire one rule, so it must decide which. The algorithm presented here will fire the production rule with the lowest number. (There are many other schemes for determining which rule should fire; I list a few near the end of this article.) The action phase is step 5. It fires the single production rule that both hit in the current context and was chosen via conflict resolution.

A Simple Example

A simple example from [2] will illustrate how the three parts of a production system work together to make a decision. The production rules are as follows.

Rule
Number
1:    IF green THEN produce
2:    IF small THEN delicacy
3:    IF refrigerated OR produce THEN perishable
4:    IF 15-lbs AND inexpensive AND NOT perishable THEN staple
5:    IF 15-lbs AND produce
THEN watermelon

Now start with the original context:

(green 15-lbs)

The interpreter finds a rule that hits on the conditions in rule 1. It fires that rule, and the context becomes:

(produce green 15-lbs)

The action produce becomes a new condition in the context. During the next cycle, the interpreter hits on rules 1, 3, and 5. The action of rule 1 (produce) is already on the context, so rule 1 is deactivated. The interpreter chooses to fire rule 3 because it has a lower number than rule 5. The context becomes:

(perishable produce green 15-lbs)

During the next cycle, the interpreter again hits on rules 1, 3, and 5. The actions of rules 1 and 3 are already in the context, so the interpreter deactivates those. The only rule left on the hit list is 5, so the interpreter fires it producing the context:

(watermelon perishable produce green 15-lbs)

The interpreter runs through another cycle and hits on rules 1, 3, and 5 once more. The actions of all these rules are on the context, so they are all deactivated. The interpreter stops cycling because the hit list is empty.

From the start, the obvious conclusion of this example is watermelon. The production system, however, cycled through the rules and fired on the actions produce and perishable. These extra side effects can produce interesting and useful results. Programming these side effects into hard-coded if-then logic would be very difficult. It would be even more difficult for someone else who came along two years later to read, understand, and modify. The hard-coded programming method would work for only one application, while the production system would work for any application.

Production System Source Code

Listings 1 through 3 show source code that will implement a basic production system. The goal in developing the code was to have a reusable subroutine that can be called from any program.

Listing 1 shows the include file that defines the constants and function prototypes. The context of the production system is implemented as a simple string. The CONTEXT string will be the original context in the program. The production rules will be stored in a text file (RULES_FILE).

Listing 2 shows a main and a calling function. These are wrappers for the example. main calls a_user_function, which then calls the production system. This illustrates how the production system can be a reusable subroutine.

Listing 3 shows the production system functions. production_system implements the interpreter algorithm described above. The while(interpreting_context) section cycles through the system until no more rules can fire. The while(reading_rules) section searches for any production rules that will hit on the context. read_a_rule reads and returns a single rule from the production rules file. is_a_hit determines if the condition in the rule matches the context. This is a key subroutine and is discussed further below. All hits are placed on the hit list (the hits array).

The next section of code (if(!no_hits)) performs the conflict resolution phase. It deactivates any rules that would add a duplicate to the context (is_a_duplicate) and finds the rule on the hit list with the lowest number (lowest_number). Finally, the code fires the rule selected by calling fire_rule.

The other functions in Listing 3 implement the operations called by production_system. They are straightforward, so I won't describe them here.

The key function is is_a_hit. This function decides if the context satisfies the condition part of each production rule. Following is a list of the types of rules is_a_hit can interpret:

IF a THEN z
IF NOT a THEN z
IF a AND b THEN z
IF a AND b AND c THEN z
IF a AND b AND_NOT c THEN z
IF a AND_NOT b THEN z
IF a OR b THEN z
IF a OR b OR c THEN z
IF a OR b OR_NOT c THEN z
IF a OR_NOT b THEN z

This is not an exhaustive or all inclusive list. It would be best if is_a_hit could interpret all combinations of AND, OR, and NOT, or if it was a full-powered regular expression processor. The design of the example code permits programmers to add all the power they want in this one place. The remaining functions wil not be affected.

A Bigger Example

Another example illustrates the power of production systems for programmers. This example handles a scheduling problem. In a scheduling problem there are typically limited resources, and many requests for service. The system must make a decision to determine how best to respond to all the current requests. Many types of software have to deal with this situation, from email servers to compilers.

Suppose you have written a software system for a delivery company that performs the usual business functions (finance, customer records, etc.). In addition, this software system must help schedule which drivers make a given delivery. This example also assumes that purchasing a standalone AI system to handle this problem is not acceptable (perhaps too expensive). The scheduling process must therefore be part of the big system.

The company runs three shifts of drivers each day, and there are different numbers of drivers on each shift. The weekend also has three shifts, but these are different drivers from the weekday drivers.

A set of if-then constructs can solve this problem. That code, however, would be one-of-a-kind and would not solve any other decision-making problem. That code could also be very difficult for another programmer to understand.

Figure 2 shows a portion of the 68 production rules developed to solve this problem. At first glance, these rules may seem perplexing. The large number of rules is a consequence of the limited types of rules is_a_hit can interpret, and of the conflict-resolution scheme (lowest number) it uses. A programmer could extend the capability of the system, and with it the scope of the problem it can solve, by adding more rules.

As illustration of how these rules work, consider an original context:

(friday dt6 shift3 wedds1d1-busy)

This context says that the third shift on Friday has a delivery to make, the delivery time is greater than six hours, and the first driver of the first shift on Saturday is already busy.

The production system cycles through the production rules, yielding the series of contexts shown in Figure 3. The production system's final answer is to assign this delivery to the second driver of the first weekend shift on Saturday.

There are several changes to the original context that would make the problem more realistic. For example, the context could contain initial conditions that indicated all the drivers that were busy. This would make the original context much longer and harder to read but would not hinder the production system.

Improving the Basic Production System

There are a number of ways to improve the basic production system discussed here. I've already mentioned improving the is_a_hit routine to add power and flexibility to the production rules. Two other types of possible changes include conflict resolution and taking action when firing a production rule.

The conflict resolution in the sample code simply chooses the production rule with the lowest rule number. This strategy forces the person entering the rules to take great care in the order they are listed. An alternative strategy could be to assign points to each rule and fire on the rule with the most points. Another strategy would fire the rule with the most words in its condition. Yet another strategy is to fire the rule that refers to the most recently added word in the context. The alternatives go on and on and include firing all matching rules simultaneously or using a random number to select the rule.

Also, in the current production system, any action taken only adds a word to the context. A powerful enhancement would be to call functions based on the action part of the production rule. This change would permit the production system to take direct action immediately as well as affect the final decision. Another very useful way to enhance the system would be to enable it to delete words from the context. If you've just started working with the sample system, this ability may not seem useful. But working with the system a while will show how important deletion can be.

Summary

Software can make complex decisions, and production systems are excellent decision-making tools. Production systems store knowledge in production rules; the user presents a situation in a context (statement or list), and the interpreter cycles the context through the production rules. If written as a self-contained module, programmers can reuse the production system in many different situations. This contrasts with complex if-then logic that is unique for every situation.

I encourage experimentation with the production system presented here. Create a new problem and enter rules one by one. (Please go slowly at first.) Run the system after entering each new rule to understand how the rules interact. After experimenting with the system, try implementing some of the improvements suggested earlier. I think you'll find that production systems are powerful and useful software tools. o

References

[1] Dwayne Phillips. "Information Hiding in C," C/C++ Users Journal, January 1998.

[2] The Handbook of Artificial Intelligence. Edited by Avron Barr and Edward A. Feigenbaum (William Kaufmann, Inc., 1981).

Dwayne Phillips works as a software, systems, and computer engineer with the United States Government. He has a Ph.D. in Electrical and Computer Engineering from Louisiana State University. His interests include computer vision, artificial intelligence, software engineering, and programming languages.