Rete Algorithm

The Rete Algorithm was invented by Dr. Charles L. Forgy of Carnegie Mellon University in 1979 and is widely regarded as the breakthrough that made rule-based inference efficient enough to be practical. It is an efficient pattern matching algorithm for implementing rule-based (“expert”) systems. Rete has become the basis for many popular expert systems, including JRules, OPS5, CLIPS, JESS, Drools, Soar and LISA.

A naive implementation of an expert system might check each rule against the known facts in the Knowledge base, firing that rule if necessary, then moving on to the next rule (and looping back to the first rule when finished). For even moderate sized rules and facts knowledge-bases, this naive approach performs far too slowly.

The Rete algorithm (usually pronounced either ‘REET’ or ‘REE-tee’, from the Latin ‘rete’ for net, or network) provides the basis for a more efficient implementation of an expert system. A Rete-based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left-hand-side of a rule. The path from the root node to a leaf node defines a complete rule left-hand-side. Each node has a memory of facts which satisfy that pattern.

As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered.

The Rete algorithm is designed to sacrifice memory for increased speed. In most cases, the speed increase over naive implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system). In very large expert systems, however, the original Rete algorithm tends to run into memory consumption problems. Other algorithms, both novel and Rete-based, have since been designed which require less memory.

The animations of Rete available here follow the descriptions of the implementation of Rete in the Jess system described in Ch 8, Jess In Action, by Dr. Ernest Friedman-Hill. A copy of Jess can be obtained at: http://herzberg.ca.sandia.gov/jess/index.shtml. A copy of the book, Jess in Action, can be obtained at: http://www.manning.com/friedman-hill/index.html . Besides, Jess reference manual contains Rete algorithm in Ch 19,

Drools is an open source rules engine implementation Rete information on Drools.org.

There are flash animations to describe Rete:

• Rete Network, the corresponding Jess rules, Test1
• Rete Mismatch the corresponding Jess rules, Test2
• Rete Chaining the corresponding Jess rules, Test3

External Links

• Charles Forgy, “Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem”, Artificial Intelligence, 19, pp 17-37, 1982
• Robert B. Doorenbos Production Matching for Large Learning Systems, Chapter 2 (Detailed and accessible description of Rete), 1995.

JESS and JADE

JESS Agent

1. University of Technology Aachen, Germany. The Jess Agent is constructed in a way that allows an easy access to the JESS via an agent.
2. (JessAgent) JADE example. A simple sample JADE Agent that embeds a Jess engine. It instantiates and adds only one behaviour. This behaviour is BasicJessBehaviour that only asserts messages when they arrive and use Jess as a reasoning tool This agent executes the Jess code in the file examples/jess/JadeAgent.clp
3. (JadeJessProtege) JADE example. Examples for a closer integration of JADE with JESS, optionally also with protege. Aspects are starting a JADE agent from a running JESS engine, interactively developing JADE agent behaviour from a JESS console, and protege ontology support for JADE agents in JESS rules.

Getting Started with Jess 6.1p8

Compiling Jess source files

You can compile Jess by typing a few commands yourself.

cd "c:\Program Files\Jess61p8"
javac -d . jess*.java
javac -d . jessawt*.java
javac -d . jessfactory*.java

would work just fine, given that c:\Program Files\Jess61p8 is your current directory.

NOTE: Jess works fine with JDK 1.4, but you will get warnings during the compilation about a conflict between the new Java keyword "assert" amd the Jess function jess.Rete.assert(). These are just warnings, and they don't stop the compilation. This function is now deprecated in Jess and will be phased out over the next few versions.

If you have problems, be sure the CLASSPATH environment variable includes the current directory '.'. Don't try to compile from inside the Jess61p8/jess/ directory; it won't work. You must use a Java 2 compiler to compile Jess. The resulting code will run on any Java 2 or later VM. Jess works great with JDK 1.3. There are a number of optional example source files in the subdirectories Jess61p8/jess/examples/ that aren't compiled if you follow the instructions above. You can compile the examples one at a time. For example, to compile the example named pumps using the JDK on a Windows system, you can use the command

javac -d . jessexamplespumps*.java

---

Again, don't set your current directory to, for example, Jess61p8/jess/examples/pumps/ to compile the pumps example: it will not work. The compiler will report all sorts of errors about classes not being found and the jess package not being found. Compile everything from the Jess61p8 directory. I can't stress this enough: this is by far the most common problem people have in getting started with Jess!

---

Create jess.jar

Jess API will need the Jess.jar file. The following command will create a jar file.

cd "c:\Program Files\Jess61p8"
jar cvf jess.jar jess\*.class jess\awt\*.class jess\factory\*.class

JESS and Prolog

Difference between Jess and Prolog

• Jess is different than some Rete-based systems in that it includes both a kind of backwards chaining and a construct called defquery which lets you make direct queries of the working memory. Both of these help Jess a better fit for some Prolog applications, but they don’t make Jess into a Prolog-like system.

• Prolog is optimized, in a sense, for space, at the cost of speed. Jess (and its Rete algorithm) is optimized for speed at the cost of space.

• The Rete algorithm is all about computing things -once- so they never need to be recomputed, and then reusing them. Prolog’s approach is targeted at exploring large numbers of possibilities once, while Rete is aimed at exploring medium-sized numbers of possibilities repeatedly.