ORIGINAL DRAFT

XML provides a vehicle for representing virtually any kind of data collection. Organized structures can be thought of as languages that may be interpreted, such as a collection of business rules. In this column, we’ll look at simple Java-based tools that help you get more mileage out of both Java and XML. In this installment, we’ll develop a simple, extensible expert system shell that supports backward-chaining inference.

Expert systems are use heavily in diagnostic scenarios, such as determining what’s wrong with a person or a machine. They are also useful because they tend to be declarative rather than procedural. You can specify a set of rules and the inference engine will apply them appropriately and provide an answer if enough information is available. Of course, the inference process is hardly magical. It relies on simple principles which are fairly easy to express.

The algorithm for a backward-chaining inference engine requires the specification of a set of rules and a goal to resolve. To make things interactive, we’ll also specify questions that can be asked of the user to determine the value of a given variable. To resolve a goal, we check to see if the variable already has a value. We ask a question if we can when we don’t already know the answer. Finally, we look for rules that have the variable in their conclusion and try to prove the conditions using the same process. When the goal variable is given a value, we are done and we display the results.

Here’s an example session with an animal-guessing rule set:

Does your animal have a backbone?
 1) yes
 2) no
Select: 2
Does your animal live primarily in soil?
 1) yes
 2) no
Select: 1
Does your animal have a flat body?
 1) yes
 2) no
Select: 1
I think your animal is a flatworm

The engine is capable of showing it’s progress if you turn the trace facility on, so you can see each subgoal, it’s variables, rules and any questions being processed. Let’s take a quick look at the goal for this rule base. You’ll notice that the text is used in the conclusion message. Resolving the variable ‘type-animal’ is the stated objective of the inference process.

<GOAL>
  <VARIABLE>type-animal</VARIABLE>
  <TEXT>I think your animal is a </TEXT>
</GOAL>

The rule that was fired last in this trace is shown below. You see that a rule is made up of an IF and THEN clause. The IF section includes one or more conditions, which are specified by name, with both a variable and a value. The THEN section includes one or more conclusions, which are specified by name, with both a variable and a value as well. The name of each condition and conclusion is important and we’ll take a closer look at these in a moment.

This rule gets fired because it contains our goal variable, ‘type-animal’, in its conclusion. To succeed, the two conditions must be met, so the inference engine tries to find a value for the ‘phylum’ variable. That stimulates the firing of other rules and the asking of the first two questions. Once ‘phylum’ is determined, we need to find the value for ‘flat-bodied’, which leads us to the question.

<QUESTION>
  <VARIABLE>flat-bodied</VARIABLE>
  <TEXT>Does your animal have a flat body?</TEXT>
  <CHOICES>
    <CHOICE>yes</CHOICE>
    <CHOICE>no</CHOICE>
  </CHOICES>
</QUESTION>

As you can see, a question is defined by it’s variable, the text we want to present to the user and the choices we can present for selection. Having seen an example of each type of element in our knowledge base, we can define the DTD and write the code we’ll need to make this work.

Listing 1 shows the code for RuleBase.DTD. A RULEBASE is a collection of zero or more RULE and QUESTION elements, and at least one GOAL. You’ll notice that we defined the DTD so that these elements don’t have to be in a specific sequence, although rules near the beginning of the file will be considered first if they’re relevant to a subgoal, so the order is not completely arbitrary. Questions are asked only when necessary, so the order in which they are declared is not important.

You’ve seen examples of a GOAL, RULE and QUESTION, so I won’t elaborate much on the DTD. A few elements have a single name attribute. The RULEBASE and RULE names are never used by the code. They’re there primarily for documentation reasons. The CONDITION and CONCLUSION names are important. At least one CONDITION must be included in an IF statement, at least one CONCLUSION must be in a THEN statement and at least one CHOICE must be included in a question.

Now we’re ready to write some code. Figure 1 shows the classes we’ll put together. The InferenceEngine is designed to be extensible, so we create Predicate and Command interfaces to handle condition and conclusion elements. This is where the names come in. We can add as many named Predicate and Command classes as we like to the InferenceEngine, so long as they implement these interfaces. We’ll implement an EqualsPredicate and an AssignCommand to run our example.

Figure 1: InferenceEngine classes.

The RuleBase class is the internal representation of a rule base. It uses supporting classes to translate between DOM Elements and a representation more suitable for inference. These classes mimic the objects in our DTD fairly closely, with a RuleBase containing a list of Rule and Question objects and a Goal. A Rule contains a list of Condition and Conclusion elements. The only other object we use is a Console, which decouples the user interface from the InferenceEngine as much as possible, providing methods to read user input and write any output to a console.

Let’s take a look at a couple of the more important classes. You can find the rest of the code online at www.xmlmag.com, including the Java classes, DTD and XML rule base information.We’ll take a quick look at the RuleBase class, which reflects the same basic structure as the Goal, Question, Rule, Condition and Conclusion classes, with the added benefit that it ties all the latter classes together. We’ll also take a quick look at the InferenceEngine class, which is the main class in this project.

Listing 2 shows the code for the RuleBase class. We use a couple of List instance variables to store the collection of questions and rules, as well as an instance of a Goal to store the single goal we expect to find. We provide a getGoal method to get this goal and a pair of methods for getting the rule and question count.

The readRuleBase method uses JDOM to read the XML document. We set validation to true to make sure we have a valid document. With a reference to the Document in hand, we get a list of children and start processing each depending on it’s tag. If the tag is QUESTION, we delegate handling to the convertQuestion method in the Question class. The same is true for a Rule and the Goal elements.

In each case, the Element object is passed into the static convert[type] method and the element is broken into it’s constituent objects by looking at the attributes and subtags available, following the syntax we specified in the DTD. The the case of a Rule, additional conversions are made, delegating them to respect Condition and Conclusion objects, as necessary.

We also provide two other convenience methods that seek out questions and rules for a given variable. The findQuestionFor method is fairly straight forward, calling the getVariableName method on each Question object in the rule base until it finds a suitable question or runs out of entries. The findRuleFor method collects all the rules that have the variable in their conclusion and so must traverse the rules in the rule base, testing each conclusion for the requisite variable. The last step converts the List into a Rule array to make it easier to work with.

Listing 3 shows the code for the InferenceEngine class. We use a number of instance variables to store maps of variable/value pairs, name/predicate and name/command assignments. The later two are used to route processing to appropriate Predicate and Command instances, based on the name attribute in the CONDITION and CONCLUSION tags, respectively. We also store a reference to a RuleBase and Console object, as well as a trace flag so that we can flip between terse and verbose modes for tracing.

The setTrace method lets you set the state of the trace variable. We provide a pair of accessors for setting and retrieving Command, Predicate and variable/value assignments to and from the previously mentioned maps. The test method delegates it’s boolean test to the assigned Predicate instance for a given name. The exec method delegates execution to the assigned Command instance for a given name.

The ask method is a convenience call that delegates writing a question and retrieving a response to the Console object. The trace method writes output to the Console, if the trace flag is set to true, ignoring the text if the trace flag is false. The readRuleBase method loads the rule base, delegating most of the work to the RuleBase object, reporting rule and question count information after the rule base is loaded.

The actual inference code is encapsulated in the three variants of the resolve method. The resolveGoal method is the high-level call that tries to resolve the goal variable and prints out the goal text with the resolved value to the console. The first variant of the resolve check whether we already have a value for the variable in the environment by calling the getValue method. If we do, that value gets returned. If not, we try to find a suitable question and ask it, returning the response and storing it by calling setValue.

If we cannot resolve a variable from the environment or by asking a question, we try to fire suitable rules. To do this, we call the testRulesFor method, after which we check the variable in the environment and return the result. The testRulesFor method gets a list of rules that contain the named variable in their conclusion and tries to resolve each condition. To support this, we provide a variant to resolve that takes a Condition as it’s argument.

If all the Conditions for a given rule are met, the Conclusion list is activated, which in turn calls the exec method to run each associated Command. In our example rule base, we only use the AssignCommand, so the results are simply placed in the environment map, but the kinds of actions you can take include any extension you like, so this is not a limitation of the engine.

I’ve left the main method in the InferenceEngine, though strictly speaking it belongs in another class that’s more specific to the AnimalRuleBase. After creating an instance of a InferenceEngine, we turn off the trace and assign the AssignCommand and the EqualsPredicate mappings to “Assign” and “Equals” strings, respectively. Finally, we call readRuleBase to load the rule base and the resoveGoal method to kick things off.

If you answer the questions consistently when prompted, the system will provide a suitable answer for the animal you were thinking of. The rule base reflects most common animals and hyphenates alternative guesses. It was converted from an example knowledge base that served as an example for an existing expert system shell. If you see inappropriate results, they may be attributable to errors I may have introduced in the conversion process.

In expert systems, there are two major types of reasoning, forward and backward-chaining. Forward-chaining involves firing each rule and asserting valid conclusions in the knowledge base. This process is repeated until a complete pass can be made in which no rules are fired. Backward-chaining tries to prove a goal by firing rules that include required conclusions, attempting to prove their conditions in the same way. This process is more like deductive reasoning than forward-chaining.

While our implementation is fairly simple, it represents a good foundation to build on. Named predicates and commands can easily be added. New predicates can test more complex relationships or data types, reach into databases or read sensors on-the-fly. New commands can operate on databases, interact more effectively with users or even trigger actuators.

This solution represents what’s often referred to as data-driven programming, where the static data, in this case XML, is driving processing and minimizing the amount of programming necessary to function. Different groups of people are better suited to different jobs. In this case, domain experts who know the rules and questions to ask don’t need to understand Java to be effective. Programmers can be called in to extend the engine with relative ease, when necessary, and everyone benefits from the resulting specialization.

Listing 1

<?xml version="1.0" encoding="ISO-8859-1"?>

<!ELEMENT RULEBASE ((RULE | QUESTION)*, GOAL)>
<!ATTLIST RULEBASE name CDATA #REQUIRED>

<!ELEMENT VARIABLE (#PCDATA)>
<!ELEMENT VALUE (#PCDATA)>

<!ELEMENT RULE (IF, THEN)>
<!ATTLIST RULE name CDATA #REQUIRED>

<!ELEMENT IF (CONDITION+)>
<!ELEMENT THEN (CONCLUSION+)>

<!ELEMENT CONDITION (VARIABLE, VALUE)>
<!ATTLIST CONDITION name CDATA #REQUIRED>

<!ELEMENT CONCLUSION (VARIABLE, VALUE)>
<!ATTLIST CONCLUSION name CDATA #REQUIRED>

<!ELEMENT TEXT (#PCDATA)>
<!ELEMENT CHOICE (#PCDATA)>

<!ELEMENT QUESTION (VARIABLE, TEXT, CHOICES)>
<!ELEMENT CHOICES (CHOICE+)>

<!ELEMENT GOAL (VARIABLE, TEXT)>

Listing 2

import java.io.*;
import java.util.*;
import org.jdom.*;
import org.jdom.input.*;

public class RuleBase
{
  protected List questions = new ArrayList();
  protected List rules = new ArrayList();
  protected Goal goal;
  
  public Goal getGoal()
  {
    return goal;
  }
  
  public int getQuestionCount()
  {
    return questions.size();
  }
  
  public int getRuleCount()
  {
    return rules.size();
  }
  
  public void readRuleBase(String filename)
  {
    try
    {
      DOMBuilder builder = new DOMBuilder();
      builder.setValidation(true);
      Document doc = builder.build(new File(filename));
      List children = doc.getRootElement().getChildren();
      for (int i = 0; i < children.size(); i++)
      {
        Element element = (Element)children.get(i);
        if (element.getName().equals("QUESTION"))
        {
          Question question = Question.convertQuestion(element);
          questions.add(question);
        }
        if (element.getName().equals("RULE"))
        {
          Rule rule = Rule.convertRule(element);
          rules.add(Rule.convertRule(element));
        }
        if (element.getName().equals("GOAL"))
        {
          goal = Goal.convertGoal(element);
        }
      }
    }
    catch (JDOMException e)
    {
      e.printStackTrace();
    }
  }

  public Question findQuestionFor(String variable)
  {
    for (int i = 0; i < questions.size(); i++)
    {
      Question question = (Question)questions.get(i);
      String name = question.getVariableName();
      if (name.equals(variable))
        return question;
    }
    return null;
  }
  
  public Rule[] findRulesFor(String variable)
  {
    List list = new ArrayList();
    for (int i = 0; i < rules.size(); i++)
    {
      Rule rule = (Rule)rules.get(i);
      Conclusion[] conclusions = rule.getConclusionList();
      for (int j = 0; j < conclusions.length; j++)
      {
        String var = conclusions[j].getVariableName();
        if (var.equals(variable)) list.add(rule);
      }
    }
    Rule[] rules = new Rule[list.size()];
    for (int i = 0; i < list.size(); i++)
    {
      rules[i] = (Rule)list.get(i);
    }
    return rules;
  }
}

Listing 3

import java.io.*;
import java.util.*;

public class InferenceEngine
{
  protected boolean trace = true;
  protected Map commands = new HashMap();
  protected Map predicates = new HashMap();
  protected Map environment = new HashMap();
  protected RuleBase ruleBase = new RuleBase();
  protected Console console = new Console();
  
  public void setTrace(boolean trace)
  {
    this.trace = trace;
  }
  
  public void setCommand(String name, Command command)
  {
    commands.put(name, command);
  }
  
  public Command getCommand(String name)
  {
    return (Command)commands.get(name);
  }
  
  public void setPredicate(String name, Predicate predicate)
  {
    predicates.put(name, predicate);
  }
  
  public Predicate getPredicate(String name)
  {
    return (Predicate)predicates.get(name);
  }
  
  public String getValue(String variable)
  {
    return (String)environment.get(variable);
  }
  
  public void setValue(String variable, String value)
  {
    environment.put(variable, value);
  }
  
  public boolean test(Condition condition)
  {
    String name = condition.getName();
    String variable = condition.getVariableName();
    String value = condition.getValue();
    Predicate predicate = getPredicate(name);
    return predicate.test(environment, variable, value);
  }
  
  public void exec(Conclusion conclusion)
  {
    String name = conclusion.getName();
    String variable = conclusion.getVariableName();
    String value = conclusion.getValue();
    Command command = getCommand(name);
    command.exec(environment, variable, value);
  }

  public String ask(Question question)
  {
    try
    {
      String text = question.getText();
      String[] choices = question.getChoiceList();
      return console.ask(text, "Select: ", choices);	
    }
    catch (IOException e)
    {
      e.printStackTrace();
      return null;
    }
  }
  
  public void trace(String text)
  {
    if (trace) console.say(text);
  }
  
  public void readRuleBase(String filename)
  {
    trace("Loading rulebase...");
    ruleBase.readRuleBase(filename);
    StringBuffer buffer = new StringBuffer();
    buffer.append("Rulebase loaded [");
    buffer.append(ruleBase.getRuleCount());
    buffer.append(" rules, ");
    buffer.append(ruleBase.getQuestionCount());
    buffer.append(" questions]");
    trace(buffer.toString());
  }
  
  public void resolveGoal()
  {
    Goal goal = ruleBase.getGoal();
    String variable = goal.getVariableName();
    String result = resolve(variable);
    String text = goal.getText();
    console.say(text + result);
  }
  
  protected String resolve(String variable)
  {
    trace("Try to resolve " + variable);
    if (getValue(variable) != null)
    {
      String value = getValue(variable);
      trace("Variable: " + variable + " is " + value);
      return value;
    }
    Question question = ruleBase.findQuestionFor(variable);
    if (question != null)
    {
      String value = ask(question);
      setValue(variable, value);
      trace("Question: " + variable + " is " + value);
      return value;
    }
    else
    {
      testRulesFor(variable);
    }
    String value = getValue(variable);
    if (value == null) value = "[unknown]";
    trace("Proven: " + variable + " is " + value);
    return value;
  }

  protected String resolve(Condition condition)
  {
    String var = condition.getVariableName();
    if (var == null) return null;
    String value = resolve(var);
    if (value != null) setValue(var, value);
    return value;
  }
  
  protected void testRulesFor(String variable)
  {
    // Get list of rules with this variable in the conclusion
    Rule[] rules = ruleBase.findRulesFor(variable);
    for (int i = 0; i < rules.length; i++)
    {
      trace("Test rule " + rules[i].getName());
      Condition[] conditions = rules[i].getConditionList();
      boolean truth = false;
      for (int j = 0; j < conditions.length; j++)
      {
        Condition condition = conditions[j];
        // Try to resolve variable before testing
        resolve(condition);
        // Ready to test condition
        truth = test(condition);
        if (!truth) break;
      }
      if (truth)
      {
        Conclusion[] conclusions = rules[i].getConclusionList();
        for (int j = 0; j < conclusions.length; j++)
        {
          exec(conclusions[j]);
        }
      }
    }
  }
  
  public static void main(String[] args)
    throws Exception
  {
    InferenceEngine engine = new InferenceEngine();
    engine.setTrace(false);
    engine.setCommand("Assign", new AssignCommand());
    engine.setPredicate("Equals", new EqualsPredicate());
    engine.readRuleBase("AnimalRuleBase.xml");
    engine.resolveGoal();
  }
}