A Basic Rules Engine in Excel VBA

• Download ExcelRules.zip - 199.7 KB

Introduction

Most of the expert systems available in open source are in Java, Prolog, etc. - I have not found any in VBA. I wanted a rudimentary rules engine mainly for prototyping prior to implementing a robust one. The syntax is very simple and rules can be written by virtually anybody - that is what I wanted.

The example shows rules to define what methodology to use when starting a project.

The Excel workbook contains a self explanatory help.

Background

The principle of a rule engine functioning in forward chaining is simple:

We consider a set of rules like :

• IF temperature < 32 THEN water_state = "ice"
• IF water_state = "ice" THEN skating_possible = "TRUE"

Each rule being made of conditions and conclusions.

Each one being made of variable operator variable or constant.

We consider a set of facts like:

• temperature = 23
• weather = "SUNNY

Each one being made of variable = variable or constant.

• Is skating possible ?

We want to determine if the variable skating_possible is TRUE or not.

The rule engine will try to apply rules based on the known facts. When a rule is fired, all the conclusions of the rule become new facts, which will make the facts table grow until either the goal is found or there is no rule to be fired.

Consult the literature for more details on expert systems.

Using the Code

Structure

The program handles the following structures: variable, expression and rule. A variable is a basic object manipulated (like X, Temperature, Age), an expression is a logical expression using variables (like X = 3 or Temperature > 32). A rule groups expressions together: the expressions which are part of the conditions of the rules and the ones which are part of the conclusions of the rule.

To manipulate these objects easily, I created classes:

The cVariable Class

Private sName As String                 'Name of the variable.
Private sType As String                 'String, Integer, Boolean, Date
Private sQuestion As String             'Question being asked to get the value of the variable.
Private bQuestionAsked As Boolean       'To prevent asking several times the same question.
Private collPossibleValues As Collection
Private collRulesIF As Collection       'Rules names where this variable appears in the condition.

Notes

• Some variables are restricted to only some values (a boolean variable is actually a string variable that can only contain "TRUE" or "FALSE" for example). The collPossibleValues collection will help to implement these restrictions.
• The collRulesIF collection contains the name of all the rules which have this variable in the condition part. So when the variable is given a value, it is easy to fetch all rules that have to be revisited.
• The value of the variable (when it exists) is kept in the fact table.
• Sometimes, the engine can't fire any rule and needs additional information by asking user about the value of some variables: that is the reason for sQuestion.
• If the user does not know the answer to the question, it is useless to ask a second time: that is the reason for bQuestionAsked.

Occurrences of cVariable are kept within cVariables class (collection).

The cExpression Class

A logical expression consists in:

• a variable
• followed by 0 or 1 operator
• if one operator, it is followed by a variable or a constant.

Examples:

• WEATHER = "NICE" (variable WEATHER and constant NICE)
• TEMPERATURE = 32 (variable TEMPERATURE and constant 32)
• TEMP1 <> TEMP2 (variable TEMP1 and variable TEMP2)
• NOT (NEW STUFF) (negation of variable NEW STUFF)

Private sWord1 As String            'Always a declared variable.
Private sOperator As String         'Nothing or a valid operator.
Private sWord2 As String            'Nothing or a declared variable or a constant
Private bWord2IsVariable As Boolean
Private sKey As String              'Concatenation sWord1&sOperator&sWord2
Private iValue As Integer           '0 = Unknown / 1 <=> True / -1 <=> False

Notes:

• An expression always has a variable as first element.
• Actually we could retrieve every time if the second word is a variable or not by looking in the cVariables but recording it as part of the expression saves time.
• The key is used to ensure unicity of the expression within either conditions or conclusions.
• As indicated, the value records if the expression is true, false or not yet assessed.

Occurrences of cExpression are kept within cExpressions class (collection).

The cRule Class

A rule consists in:

• a name to identify the rule (unique)
• the conditions (e.g. expressions, e.g. the IF part of the rule)
• the conclusions (e.g. expressions, e.g. the THEN part of the rule)

Private sRuleName As String         'Rule name.
Private collIF As cExpressions      'Conditions within the rule.
Private collTHEN As cExpressions    'Conclusions within the rule.
Private bCanBeFired As Boolean      'True <=> all conditions are true.
Private bActivated As Boolean       'Rule has been fired already.

Notes:

• Conclusions of a rule are expressions that assign a value to a variable (like X = 3). Conclusions can't be expressions like X <> 0.
• The boolean bCanBeFired is used to easily determine if the rule can be executed (e.g. all the conditions are TRUE).
• The boolean bActivated prevents a rule from being fired multiple times.

Occurrences of cExpression are kept within cExpressions class (collection).

Algorithm

Pretty simple:

• Load the variables
• Load the rules
• Get the goal (e.g. the variable for which the engine must find a value)
• Get the initial facts
• While (some rules can be fired) AND (goal not found)
• Fire the "best" rule.
• Add all conclusions to the facts table
• If the goal is reached, then stop
• Wend
• If the goal is found, then display its value else display "no solution"

Selecting the "best" rule to fire.

That is a touchy point. Here is the selection method used:

1. Identify all the rules which have not been fired yet and which have all their condition met and which have the goal within their conclusion and pick one at random. If there are no candidates:
2. Identify all the rules which have not been fired yet and which have all their condition met - even if the goal is not within their conclusions and pick one randomly. If there are no candidates:
3. Identify all the rules which have not been fired yet, have the goal within their conclusion but have some conditions unknown. Then ask the user about the value of the variable within the conditions. If one rule can be fired, select it. If there are no candidates:
4. Identify all the rules which have not been fired yet, but have some conditions unknown. Then ask the user about the value of the variable within the conditions. If one rule can be fired, select it. If there are no candidates... no rule can be fired.

Trick

Once a fact becomes true (e.g. AGE = 33 for example) and is stored in the fact table, immediately revisit all the rules having the corresponding variable (e.g. AGE) in one of their conditions and reassess.

Points of Interests

There are probably some bugs here and there and the engine could be optimized. Some useful additions could be added like:

• Adding backward chaining
• Adding probability of conclusion (similar to MYCIN)
• Being able to handle functions in conclusions like X = X + Y...

History

• Version 2.0 - Article being rewritten after rejection