Skip to: Site menu | Main content

Drools

Java Rules Engine

Publications Print

Papers

Rete: A fast algorithm for the many pattern/many object pattern match problem

by Charles L. Forgy

Artificial Intelligence, Volume 19, Issue 1, September 1982, Pages 17-37

Abstract

The Rete Match Algorithm is an efficient method for comparing a large collection of patterns to a large collection of objects. It finds all the objects that match each pattern. The algorithm was developed for use in production system interpreters, and it has been used for systems containing from a few hundred to more than a thousand patterns and objects. This article presents the algorithm in detail. It explains the basic concepts of the algorithm, it describes pattern and object representations that are appropriate for the algorithm, and it describes the operations performed by the pattern matcher.

Production Matching for Large Learning Systems (Rete/UL)

by Robert B. Doorenbos

PhD thesis, Carnegie Mellon University, January 31, 1995

PDF

One of the central results of AI research in the 1970's was that to achieve good performance, AI systems must have large amounts of knowledge. Machine learning techniques have been developed to automatically acquire knowledge, often in the form of if-then rules (productions). Unfortunately, this often leads to a utility problem - the "learning" ends up causing an overall slowdown in the system. This is because the more rules a system has, the longer it takes to match them against the current situation in order to determine which ones are applicable.

RETE*, A Faster RETE with TREAT as a Special Case

by Ian Wright, James Marshall

PDF

Some behaviour of computer game agents can be naturally expressed as collections of rules and knowledge bases. General purpose rule-based languages provide high-level constructs for expressing complex conditional behaviour. We examine the runtime kernel of RC++, a rule-based language developed for game AI, to explore the costs associated with adopting general-purpose, rule-based approaches for computer game production. The kernel of RC++ is the RETE* algorithm, an extension of the RETE algorithm with better time characteristics, but also able to exhibit the beneficial properties of TREAT (a low memory cost alternative to RETE) when required.

The LEAPS Algorithms

by Don Batory

Technical Report 94-28, Department of Computer Sciences, University of Texas at Austin, 1994

PDF

LEAPS is a state-of-the-art production system compiler that produces the fastest sequential executables of OPS5 rule sets. The performance of LEAPS is due to its reliance on complex data structures and search algorithms to speed rule processing. In this paper, we explain the LEAPS algorithms in terms of the programming abstractions of the P2 data structure compiler.

Articles

An Introduction to the Drools Project

by N. Alex Rupp

HTML

Part one of this article revisits an old concept and introduces a new technology for the Java Enterprise developer's utility belt. I'll discuss how Rules Engines can improve the agility of your business by helping you isolate the "logic of the bottom line" from the technical logic of your software applications. I'll also introduce the JSR-94 Rules Engine API and an Open Source product called Drools, the forerunner implementation of this up-and-coming technology. In part two, we'll revisit our examples in greater depth and take a closer look at some of the intricacies of both the Drools engine and its JSR-94 extensions.

Application Validation Strategies

by Mike Dietz

HTML

This article discusses a strategy for data validation within a software application. It addresses the complex interactions often required between the UI and business (domain) layers of an application. The decision of whether to use a Rule Engines is also discussed.

Presentations

Drools Javapolis 2004

by Mark Proctor

PPT.zip | PDF

The PowerPoint slides for the drools presentation given at Javapolis 2004.

Extending JADE for Agent Grid Applications

by Agustino Poggi, et al.

PDF

Discusses using Drools within an agent environment.

Blogs, etc.

TREAT or RETE, neither, LEAPS is best

Professor Daniel P. Miranker

HTML

In the debate concerning the use of the RETE or TREAT it commonly lost that David Brant and I developed a lazy evaluation scheme, (LEAPS), for the evaluation of rule-based systems. This algorithm collapses the space complexity of this problem to linear. In a scaling study we demonstrated polynomial improvements in time and space. Tom Hetherington has done some further extensions to the algorithm which result in asymptotic improvement in time-complexity as well.

Drools?

by Ted Neward, February 22, 2003

HTML

A student in my class this week pointed me to a most interesting resource. In this case, I had mentioned Jaxen, an XPath utility library that layers on top of a number of different hierarchical data sources (such as, but not limited to, an XML DOM or JDOM document node), and he found that Jaxen has been "taken over" by another company, The Werken Company. In of itself, this isn't worthy of note, but he noticed that The Werken Company also maintains a couple of other open-source projects, including one that caught his eye --and mine, when he mentioned it to me--called drools, a rule-based inference engine, much as tools like ILog Rules and Jess are. (Two others I hadn't heard of before but are mentioned in the drools documentation are Haley Eclipse and CLIPS.) Naturally, having been interested in Jess long before this and having consulted for a company that was deeply involved in the whole business rules concept, I had to take a look. After about ten minutes' worth of looking and experimentation, I figured I'd blog about it.