Rule-based expert systems proved to be a successful AI technology in a number of areas. Building such systems requires creating a rulebase, as well as providing an effective inference mechanism that fires rules appropriate in a given context. The paper briefly discusses main rule inference algorithms Rete, TREAT and Gator. Since large rulebases often require identifying certain rule clusters, modern inference algorithms support inference rule groups. In the paper the case of the new version of Drools, introducing the RuleFlow module is presented. These solutions are contrasted with a custom rule representation method called XTT2. It introduces explicit structure in the rulebase based on decision tables linked in an inference network. In this case, the classic Rete-based solutions cannot be used. This is why custom inference algorithms are discussed. In the paper possible integration of the XTT2 approach with that of RuleFlow is discussed.
Rules constitute a cardinal concept of the rule–based
expert systems (RBS for short) [
The main problem discussed in this paper concerns inference methods in structured rule-bases. A rule-base can contain thousands or even milions rules. Such large rule-bases cause many problems: 1) Maintenance of the large set of rules. 2) Inference inefficiency – the large number of rules may be unnecessary processed. The modularization of the rule-base that introduces structure to the knowledge base can be considered as the way to avoid these problems. The rules can be grupped in the modules, what can facilitate the maintenance of the large set of rules. What is more, the inference algorithm may be integrated with structured rule-base. The integration can influence the inference performance.
The main focus of this paper is the inference in
the structured rule bases. The Section 2 presents the
well-known expert system shells such as CLIPS [
ation of complete expert systems. Usually, they have most of the important functionalities built-in such as: rule-base, inference algorithm, explanation mechanism, user interface, knowledge base editor.
Such system must be adopted to the domain-specific problem solving. This can be done by creation of the knowledge base. The knowledge engineer must codify the captured knowledge according to the formalism.
The knowledge can be captured in a several ways, but this issue is not discussed in this paper.
CLIPS is an expert system tool that is based on
Rete algorithm. It provides its own programming
language that supports rule-based, procedural and
objectoriented programming [
CLIPS has been written in C language. This makes the actions in the RHS of the selected production(s). the tool very efficient and platform independent. How- 4) Goto 1. The first step is a bottleneck of inference ever, the integration with other existing systems is not process. The algorithms, which are presented in this as easy as it is in case JESS. section, try to alleviate this problem.
JESS is a rule engine and scripting environment The Rete algorithm [
Jess uses a very efficient method known as the Rete tation of the pattern matching algorithm might check algorithm. In the Rete algorithm, inefficiency of the each production against each working element. The combinatoric explosion of rules analysis is alleviated main advantage of the Rete algorithm is that it tries to by remembering the past test results across the itera- avoid iterating over production and working memory. tions of a rule loop. Only new facts are tested against Rete can avoid iterating over working memory by each rule conditional part, but still all rules must be storing the information between cycles. Each pattern taken into consideration. stores the list of the elements that it matches. Due to
Jess supports both forward-chaining and backward this fact, when working memory is changed only the chaining. The default is forward-chaining. As the knowl- changes are analysed. edge representation JESS uses rules as well as XML- Rete also can avoid iterating over production set. based language called JessML. JESS uses LISP-like This is done by forming a tree-like structure (network) syntax, which is the same as in CLIPS. The JessML is that is compiled from the patterns. The network comnot convenient to read by human. It contains more de- prise of two types of nodes: intra–elements that involve tails, what makes this representation suitable for parsers. only one working element and inter–elements that in
Drools 5 introduces the Business Logic integration volve more than one working element. At first, the Platform which provides a unified and integrated plat- pattern compiler builds a linear sequence of the intraform for Rules, Workflow and Event Processing. Drools elements. This part of the network is called alpha memis now split up into 4 main sub projects: 1) Drools Gu- ory and contains only the one-input nodes. After that, vnor (BRMS/BPMS) – centralised repository for Drools the compiler builds the beta memory from the interKnowledge Bases. 2) Drools Expert (rule engine). 3) elements. The beta memory consists of the two-input Drools Flow (process/workflow) provides workflow or nodes. Each two-input node (except the first one) joins (business) process capabilities to the Drools platform. one two-input node and one one-input node. The first 4) Drools Fusion (event processing/temporal reason- two-input node joins two one-input nodes. ing) – the module responsible for enabling event processing capabilities. Drools Expert is a rule engine ded- R1(a > 17; d(X)); icated for the Drools 5 rule format. R2(d(X); e(Y ); g(Z));
Drools 5 implements only forward-chaining engine, R3(c = on; g(Z)); (1) using a Rete-based algorithm – ReteOO. In the future, R4(e(Y ); f (W )); Drools 5 is promised to support a backward-chaining. R5(b = F riday; f (W ))
ements, that has been changed, are let int to the network. Each node of the network tries to match the given working element. If it matches, then the copy of the element is passed to all the successors of the node. The R1 R2
R1 R2 R3
R1 R2 R3 R4
R1 R2 R3 R4 R5 two-input nodes joins the elements from the two different paths of the network into bigger one. The last twoinput element (terminal element) is the output from the algorithm and contains the information about changes, which must be applied to the conflict set.
Rete algorithm has been invented by Charles L. Forgy of Carnegie Mellon University. At first, Rete has been assumed as the most efficient algorithm for this problem. The literature did not contain any comparative analysis of the Rete with any other algorithm. Nowadays, other algorithms such as Treat, A-Treat, Gator are known. Some of them are discussed in this paper.
TREAT algorithm. State saving mechanism implemented in Rete is not very efficient. The structure of the Rete network often stores redundant information and number of elements stored in beta-memory nodes may be combinatorially explosive. Moreover cost of join operation in beta-memory are very expensive when many addition and deletion operations are preformed. To address these problems new version of Rete algorithm called TREAT was proposed.
Rete algorithm is based on two concepts: Memory support that creates and maintains alpha–memory and Condition relationship that join operations in beta– memory. TREAT also uses Memory support, but does not use Condition relationship. Instead Conflict set support and Condition membership are used. Absence of Condition relationship implies fact that in TREAT network structure there is no beta memory. Hence, the structure of TREAT network is flat.
R1 R2 R3 R4 R5
R1 R2 R3 R4 R5
The main idea of the TREAT algorithm is to
exploit the conflict set support for temporarily redundant
systems. The conflict set is explicitly retain across
production system cycles which allows for the following
advancements comparing to Rete [
each rule called rule-active that determines weather each of the rule condition elements is partially matched. The match algorithm ignores then rules that are non-active during production system cycles.
Gator algorithm. Both Rete and TREAT offer static networks, which structures are defined arbitrary by the design engineer (Rete) and looks mostly the same for all kinds of knowledge databases (Rete and TREAT). This very often leads to the creation of networks that are not optimal for some knowledge bases.
To address this problem a new discrimination
network algorithm called Gator was proposed. It is based
on Rete, but additionally implements mechanisms for
optimizing network structure according to specific
knowledge base characteristic. It can be said that Rete and
TREAT are special cases of Gator and as reported in [
Every rule in production system can be represented by a condition graph with nodes for rule condition elements and edges for join conditions.
Gator networks are general tree structures. They consist of alpha–memory elements (leaves), optional beta-memory elements (internal nodes, that can have multiple inputs) and a P–node which is a root of the tree representing a complete RHS of the rule.
R1
R2
R3
R4
R5 R1 R2 R3
R4 R5
R1 R2 R3 R4 R5
Fig. 3. Gator network for rule 1
networks of size one (which are basically alpha–memory elements) and combine them into larger optimal networks. There is a constraint which states that every newly created network have to be optimal. That ensures that the final network would also be optimal.
The network is built and optimize according to the following rules:
Gator networks unless there is an explicit connection between them in connectivity graph.
works unless their respective sets of rule condition elements do not overlap.
work that covers the same set of condition as the new network, and the existing network cost (ac- Each rule can decide which module should be focused cording to the cost function) no more than the as the next one. To accomplish that, the operation of new one, discard new network. the focus changing should be included in the rule conclusion part. This leads to the structured rulebase, but
More detailed information about cost functions and still all rules are checked against the facts. In terms of
rules for combining Gator networks can be found in [
Drools RuleFlow. It is a workflow and process en4. KNOWLEDGE MODULARIZATION gine that allows advanced integration of processes and rules. It provides a graphical interface for processes Most of the well–known expert systems have a flat knowl- and rules modelling. Drools have built-in a functionedge base. In such case, the inference mechanism have ality to define the structure of the rulebase which can to check each rule against each fact. When the knowl- determine the order of the rules evaluation and exeedge base contains a large number of rules and facts cution. The rules can be gruped in a ruleflow–groups this process becomes inefficient. This problem can be which defines the subset of rules that are evaluated and solved by providing a structure in the knowledge base executed. The ruleflow–groups have a graphical repthat allows for checking only a subset of rules. This resentation as the nodes on the ruleflow diagram. The Section describes the three well–known expert system ruleflow–groups are connected with the links what deshells CLIPS, JESS and Drools and knowledge base or- termines the order of its evaluation. A ruleflow diagram ganisation implementen in them. is a graphical description of a sequence of steps that the
CLIPS Modules. CLIPS offers functionality for rule engine needs to take, where the order is important. organising rules into so called modules. Modules al- Rules grouping in Drools 5 contributes to the effilows for restriction of access to their elements from ciency of the ReteOO algorithm, because only a subset other modules, and can be compared to global and local of rules are evaluated and executed. However there is scoping in other programming languages. Modulariza- no policy which determines when a rule can be added tion of knowledge base helps managing rules, and im- to the ruleflow-group. Due to this fact, the rules grupproves efficiency of rule-based system execution. Mod- ping can provide a muddle in the rule base especially ules in CLIPS are defined with defmodule command. in case of large rulebases.
In CLIPS each module has its own pattern-matching network for its rules and its own agenda. When a run 5. XTT–BASED EXPERT SYSTEMS command is given, the agenda of the module which is the current focus is executed. Rule execution contin- Knowledge bases in expert system shells described in ues until another module becomes the current focus, no Section 2 are flat and do not have any internal structure. rules are left on the agenda, or the return function is To create a conflict set the entire knowledge base have used from the RHS of a rule. Whenever a module that to be searched, and an intelligent inference control in was focused on runs out of rules on its agenda, the cur- such unstructuralised system is very difficult. Knowlrent focus is removed from the focus stack and the next edge representation languages are not formal neither in module on the focus stack becomes the current focus. Drools, Jess, nor in CLIPS and as a consequence there Before a rule executes, the current module is changed are not formalized methods for verifying and analysing to the module in which the executing rule is defined systems designed with those tools. To solve these prob(the current focus). The current focus can be dynami- lems a new knowledge representation method called cally switched in RHS of the rule with focus command. XTT2 (Extended Tabular Trees) was proposed which
JESS Modules. Jess provides modules mechanism is part of the HeKatE [
Main goals of XTT2 knowledge representation was 1) to provide an expressive formal logical calculus for rules, 2) allow for advanced inference control and formal analysis of the production systems, 3) provide structural and visual knowledge representation. XTT2 incorporates extended attributive table format, where similar rules are grouped within separated tables, and the system is split into such tables linked by arrows representing the control strategy. Each table consist of two parts representing condition and decision part of the rule.
grams provide the conceptual design. This stage is
supported by VARDA tool that generates XML file (called
HML in HeKatE methodology) with specification of
types, domains, attributes and dependencies between
them. Based on this file a XTT2 skeleton is created in
HQEd editor, and the tables are filled with rules [
Rules representation in XTT2 is based on
attributive logic called ALSV(FD) [
The logical rule representation is mapped to the HMR language (Hekate Meta Representation) which is an internal rule language for XTT. Following example shows HMR the notation and its pseudocode representation. xrule tab_4/1: [today eq workday,
hour in [9 to 17]] ==> [operation set bizhours]. xrule tab_4/4: [today eq workday,
hour gt 17] ==> [operation set not_bizhours].
IF today=workday AND hour>=9 AND hour<=17 THEN operation := bizhours IF today = workday AND hour > 17 THEN operation := not_bizhours
Described in section 5.1 XTT2 knowledge
representation allows for more efficient inference control during
rule-based system execution. The inference control is
assured thanks to firing only rules necessary for
achieving the goal. It is achieved by selecting the desired
output tables and identifying the tables necessary to be
fired first. The links between tables representing the
partial order assure that when passing from a table to
another one, the latter can be fired since the former one
prepares an appropriate context knowledge. There are
four algorithms based on XTT2 notation that control
the inference. They were successfully implemented in
HeaRT (HeKatE RunTime) inference engine [
[FOI] The simplest algorithm consists of a hardcoded order of inference, in such way that every table is assigned an integer number; all the numbers are different from one another. The tables are fired in order from the lowest number to the highest one. This inference algorithm is usefull when a reasoning path is well defined and does not change over rule-based system cycles. [DDI] A data-driven inference algorithm identifies start tables, and put all tables that are linked to the initial ones in the XTT network into a FIFO queue. When there is no more tables to be added to the queue, algorithm fires selected tables in order they are poped from the queue. This inference mode s especially useful for diagnosis systems, where a lot of symptoms are given as an input that can lead to multiple diagnosis. Choosing apropriate reasoning path by the system saves time and memory. [GDI] A goal-driven approach works backwards with respect to selecting the tables necessary for a specific task, and then fires the tables forwards so as to achieve the goal. One or more output tables are identified as the ones that can generate the desired goal values and are put in LIFO queue. As a consequence only those tables that leads to desired solution are fired, and no rules are fired without purpose. This inference algorithm works best in hypotesisproving systems, where value of attribute from particular table is wanted. [TDI] This approach is based on monitoring the partial order of inference defined by the network structure with tokens assigned to tables. A table can be fired only when there is a token at each input. A token at the input is a kind of a flag signalling that the necessary data generated by the preceding table is ready for use. This inference mode was designed to support systems where a lot of dependencies between tables and rules are denoted that would require many redundant conditions XTT tables. Tokens allow to omit those unnecessary conditions, which saves time and memory and makes the system more readable.
The highly modularised knowledge representation that is used in XTT2 was one of the reasons why inference engine – HeaRT – implemented for XTT2 approach does not use matching algorithm based on Rete. Due to the fact that HeaRT was implemented entirely in Prolog, fast and efficient unification algorithm that is implemented in Prolog interpreter was used instead.
Considering the differences between the XTT2 approach and the classic Rete-based solutions, at least two meanings of the notion „structure of the rule base” can be given. The first one is related the previously discussed modules in classic expert system shells. There a physical structure of the rule base is introduced using modules. The global set of rules is partitioned by the system designer into several parts in an arbitrary way. This is a technical solution, similar to source code partitioning methods such as packages is programming languages. Practically, these partitions are often merged during the inference process. Therefore, the partitioning process itself does not support in optimizing the design and inference. The second one is realized in the XTT2 representation. Here rules working in the same context, i.e. having the same conditional attributes are grouped into tables (forming simple rule sets) during the design process. This forms a logical structure of the rule base.
All of the common expert system shells described in this paper use Rete or its variants as a matching algorithm. This is so, because Rete algorithm is very efficient on flat and not structured knowledge base. Once knowledge base becomes modularized, Rete loses its assets. Although idea of modules as sets of not related in any way rules was introduced in CLIPS, the core inference algorithm – Rete – remained the same. Such partial modularisation slightly increases performance of the system, but still did not solve efficient design and verification problems. Most of solutions presented in CLIPS or Jess are just modifications of existing approaches that have their own historical drawbacks.
To address these problems a new knowledge representation called XTT2 was proposed that is a part of newly designed methodology for designing, implementing and verifying expert systems, called HeKatE. It provides visual representation of the knowledge base, formal verification of the rule–based systems and intelligent inference control. XTT2 knowledge base are highly modularized and hence its internal structure allows for more advanced reasoning. Modularisation in XTT is not partial as in CLIPS. XTT tables are not only a mechanism for managing large knowledge bases, but they also allow for context reasoning, due to the fact that each XTT table groups rules that belongs to the same context (have similar LHS and RHS). Moreover, rules in XTT2 are based on attributive logic which allows for formal verification of knowledge base. Table 1 contains the comparison of the expert system shells described in this paper and XTT2 approach. DDI DDI
formal, modular knowledge representation. Since DroolsFlow diagrams may contain other DroolsFlow diagrams, relations between XTT tables would not be limited to relation table to table, but may also be considered as realtion system to system. Integrating DroolsFlow and XTT can be done by invoking HeaRT from within DroolsFlow blocks directly, using the SWI JPL package for Java integration, or via TCP/IP protocol.