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.
We consider a goal (e.g., a variable which we need to find a value for) like:
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
Private sType As String
Private sQuestion As String
Private bQuestionAsked As Boolean
Private collPossibleValues As Collection
Private collRulesIF As Collection
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
Private sOperator As String
Private sWord2 As String
Private bWord2IsVariable As Boolean
Private sKey As String
Private iValue As Integer
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
Private collIF As cExpressions
Private collTHEN As cExpressions
Private bCanBeFired As Boolean
Private bActivated As Boolean
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:
- 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:
- 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:
- 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:
- 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