Drools - Business Logic integration Platform

James Taylor to Keynote for Drools Meeting in San Diego on April 19th

noreply@blogger.com (Mark Proctor) — Wed, 17 Mar 2010 22:26:00 +0000

James Taylor, Smart Enough Systems, is going to keynote for us on Wednesday at our Drools meeting starting April 19th, as blogged here. The talk will be titled "Smarter systems for uncertain times". I'll blog more details in a few hours.

April 19th Boot Camp to be open to all

noreply@blogger.com (Mark Proctor) — Mon, 15 Mar 2010 16:28:00 +0000

We will now be opening the boot camp up to all, for the last 3 days. The boot camp was previously announced here. The over all schedule is below. I'll be putting up a registration wiki page up on line in the next day or two, like last years which you can fine here. Keep an eye on the blog for more info soon.

We are looking for people that would like to present, take a focus group or workshop. The topics can be on drools, or how drools is applied, or on projects that use drools, or just general interesting topics for rules, workflow, event processing and ontologies - anything you think the people there would be interested in. Email me if you would like to present

Where - San Diego, CA (meeting place tbc)
Date - Monday the 19th of April to Friday the 23rd of April

Schedule

Mon-Tue (medical only) The the first two days are exclusive to the medical community and only people from medical organisations or with a medical background will be allowed to attend.
Wed (medical focus - open to all) The third day will still maintain a medical theme, wrapping up the last two days, but we will open it up for those that want to observe or participate. We will try and cover topics that will be interesting to all there, even if not from medical background, just be aware that medical discussions take priority.
Thu-Fri (general topics - open to all) The last two days is open to all and will have no specific topic

CHR 2010 (Constraint Handling Rules)

noreply@blogger.com (Mark Proctor) — Fri, 12 Mar 2010 13:43:00 +0000

I'll be a guest speaker at this years CHR 2010.

CHR 2010 - The Seventh International Workshop on Constraint Handling Rules.

"The CHR 2010 Workshop will be held July 20, 2010 in Edinburgh (Scotland) at the occasion of ICLP 2010 (part of FLoC 2010), the premier international venue for presenting research in logic programming.

The Constraint Handling Rules (CHR) language has become a major declarative specification formalism and implementation language for constraint reasoning algorithms and applications. Algorithms are often specified using inference rules, rewrite rules, sequents, proof rules, or logical axioms that can be directly written in CHR. Its clean semantics facilitates program design, analysis, and transformation. See the CHR website for more information.

...

Invited Speaker

We are privileged to announce a distinguished invited speaker this year: Mark Proctor, lead of the thriving, innovating JBoss Drools project. He will be introducing the Drools Business Logic integration Platform, a fully featured business rule engine and management system that seamlessly integrates powerful Complex Event Processing and workflow capabilities."

Drools Open Source Healthcare Conference, 19th of April, San Diego

noreply@blogger.com (Mark Proctor) — Tue, 09 Mar 2010 23:28:00 +0000

The Drools Open Source Healthcare conference, mentioned previous here, has the go ahead. 19th of April, San Diego. Will blog more details soon.

Nurse Rostering Competition 2010

noreply@blogger.com (Geoffrey De Smet) — Wed, 03 Mar 2010 18:09:00 +0000

The International Timetabling Competition 2007 has a follow up: the Nurse Rostering Competition 2010.
So expect a Drools Planner nurse rostering example soon :)

Building on the success of the two timetabling competitions, this competition on the nurse rostering problem aims to further develop interest in the general area of rostering and timetabling while providing researchers with models of the problems faced which incorporate an increased number of real world constraints.

The competition is composed of three tracks, called after the Olympic disciplines sprint, middle distance running and long distance running. These tracks represent distinct problem settings in practice and algorithm performance is often tuned to the available running time. The organisers do welcome researchers to trial their techniques on more than one track. The winner of each track receives a prize of €535 and free registration to PATAT in Belfast 2010.

Who's up for some competition? Bring it on!

Best score over time graphs

noreply@blogger.com (Geoffrey De Smet) — Sat, 27 Feb 2010 17:38:00 +0000

It's easy to create different Drools Planner configurations, but it's sometimes hard to determine which configuration is the best for your automated planning problem.

The benchmarker allows you to play out different configurations against each other and it ranks the configurations, but you can easily make a scalability misjudgment: just because config A is better than config B when given 5 minutes, doesn't mean that A will be better then B when given 60 minutes. Sometimes the opposite is true.

It's not only interesting to see what best score a configuration has after the given time, but also how it got there. And that's why the benchmarker now supports outputting a graph with the best score over time.

Graph examples

Above we see that the green configuration wins. But less then 50 seconds (= 50 000 milliseconds) earlier, the red configuration would have won.

Not all datasets have the same curve. Some datasets are harder because they are more compact (not necessarily bigger), making it harder to move resources around. Harder dataset can separate the weak from the strong configurations more clearly.

Above we can see that the green and yellow configurations take less than half the time of the other configurations to achieve the same score.

Lies, damned lies and statistics

Now, before you start drawing conclusions from the above diagrams, take these things into consideration:

The 4 configurations shown are almost identical and differ only in tabu type. They don't differ in the important things, such as the move factory implementations or absolutionSelection/relativeSelection size. They are already the best out of many inferior configurations.

400 000 milliseconds is only 7,5 minutes. Many of the algorithms don't "flatline" yet in that time. Their ROI time (return on invested time) is still high.

In an upcoming blog/article I 'll demonstrate the effect of giving Drools Planner more time and the importance of using a real-world time limitation.

Thanks to the excellent JFreeChart library for making it so easy to turn data into a graph. It's a pity though that out-of-the-box it uses yellow as the 4th line's color, making it hard to see on the default white background.

Collection-oriented Match for massively parallel Drools 6

noreply@blogger.com (Mark Proctor) — Mon, 22 Feb 2010 19:19:00 +0000

With multi-cores becoming ever cheaper the desire to push Drools into parallel processing is increasing. We've already added rulebase partitioning, which helps throughput for CEP type problems, but that doesn't solve the parallel matching.

I've followed ParaOPS5, but wasn't comfortable enough that the design would deliver universal speed improvements compared to the complexity it brings. With ParaOPS5 each partial match when propagated to a node for evaluation was submitted to a queue for evaluation as a "task". This produces something that is very fine grained, and as a node, or potentially the index in a node is a locking point, there is a lot of waiting around for very small units of work.

A while back I stumbled across this paper "Collection-Oriented Match by Anurag Acharya and Milind Tambe". The paper is well written and relatively easy to understand. Here it proposes instead of propagating the partial match once it's created, it instead stays in the node and produce all partial matches which are stored in a collection, it's this collection we then propagate. This propagated collection is submitted as a "task" to the queue. This allows for larger units of work, as more is done in the node itself. The approach is not without it's problems, particularly around left indexing, as partial matches in the same propagated collection could be in different indexes for the node.

However we feel that this shows a lot of promise and have decided to explore this as the underlying algorithm for Drools 6. We'll hopefully have a basic prototype working this summer, and then we'll have some ideas on advantages and disadvantages.

Versatile Benchmarking for Concurrent Production System Architectures

noreply@blogger.com (Mark Proctor) — Sun, 21 Feb 2010 19:43:00 +0000

Found this paper which I thought might interest people:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.9392&rep=rep1&type=pdf

"The shortage of adequate benchmarking is a major problem in the evaluation of novel production system machine organisations. This paper presents a survey of benchmark programs used in published research for improvement of production systems. We offer a new benchmark problem that allows independent variation in the size of the database, the number of productions, the ratio between local and global data, and the variance in the size of the local data clusters."

Automated planning problems are cursed with NP completeness

noreply@blogger.com (Geoffrey De Smet) — Fri, 19 Feb 2010 12:11:00 +0000

Drools Planner (formerly known as Drools Solver) optimizes automated planning. Real world planning problems are almost always NP complete. But what does NP complete mean? And why is it so annoying? And how does Drools Planner deal with it?

Let's take a look at the bin packaging use case. In this simple 2D bin packaging example we have to put 5 items of different sizes into a 4 by 8 container:

There are 3 solutions presented, but only the last solution is feasible:

The first algorithm puts in the items with the largest size first. It starts with the purple item of size 9. In the end, the blue item doesn't fit.

The second algorithm puts in the items with the largest side first. It starts with the blue item which has a side of 5. In the end, the green item doesn't fit.

The last algorithm, one of Drools Planner's algorithms, manages to fit in all the items and generate a feasible solution.

Why does the yellow item has to be at the bottom (or the top) in a feasible solution for this problem instance? Let's take a look at 3 more problem instances and a feasible solution for each of them:

The yellow item is in a different location in each of those problem instances. It's location depends upon the size of the container, all of the items involved and the constraints. They call this phenomenon NP complete:

It is easy to verify a feasible solution,

But it is hard to find a feasible solution.

Only by trying many (or all) of the solutions, we find a feasible solution. Actually, we can't even easily prove if there even is a feasible solution:

Even though the total size of the items is 14 and the container is size 18, we
humans can easily see that there's no feasible solution for this tiny planning problem.
But what if the planning problem is bigger?

Real world bin packaging has thousands of items, multiple containers, different container sizes and many more other constraints.

So, how do we make the computer automate it? Brute force?
No, because brute force takes too long. Instead, Drools Planner optimizes it with metaheuristic algorithms, such as tabu search and simulated annealing.

In a upcoming blog, I 'll prove that brute force takes billions of years even for small planning problems.

Enterprise Space Invaders !

noreply@blogger.com (Michael Neale) — Tue, 16 Feb 2010 21:43:00 +0000

Here is a a great article on using declarative rules (drools in this case) in game programming (versus loops within loops).

CHEF: A Model of Case-based Planning

noreply@blogger.com (Mark Proctor) — Tue, 09 Feb 2010 05:03:00 +0000

The original CHEF application for Case Based Reasoning (CBR) makes for an interesting read and is covered in the Expert Systems book (Peter Jackson) . I just found the original paper online, so I thought I'd share it. Maybe someone could start doing a CHEF implementation on top of Drools?
https://www.aaai.org/Papers/AAAI/1986/AAAI86-044.pdf

"CHEF is a case-based planner that builds new plans out of its
memory of old ones. CHEF’s domain is Szechwan cooking and its
task is to build new recipes on the basis of a user’s requests. CHEF’s
input is a set of goals for different tastes, textures, ingredients and
types of dishes and its output is a single recipe that satisfies all of its
goals. Its output is a single plan, in the form of a recipe, that satisfies
all of the users goals.

Before searching for a plan to modify, CHEF examines the goals in
its input and tries to anticipate any problems that might arise while
planning for them. If a failure is predicted, CHEF adds a goal to avoid
the failure to its list of goals to satisfy and this new goal is also used
to search for a plan. Because plans are indexed in memory by the
problems they avoid, this prediction can be used to find a plan that
solves the predicted problem. Much of CHEF’s planning power lies
in this ability to predict and thus avoid failures it has encountered
before."

JUG Lille video's: Drools and Drools Planner plus other Presentations

noreply@blogger.com (Geoffrey De Smet) — Thu, 04 Feb 2010 18:44:00 +0000

Last month Mark and I gave a presentation in Lille for Ch'ti JUG. The video's are now online:

Drools video of Mark Proctor at Ch'ti JUG.
Mark shows an overview of Drools and in-depth examples of the rule engine.

Drools Planner video of Geoffrey De Smet at Ch'ti JUG.
I show several planning problem use cases (n queens, bin packaging, shift rostering, examination scheduling) and explain the deterministic and meta-heuristic algorithms to tame them.

Here are links to more presentations:
RuleML2009
Lille2010
Fosdem2010

Open Source Healthcare Event (last week of March)

noreply@blogger.com (Mark Proctor) — Mon, 01 Feb 2010 20:36:00 +0000

Last November I bloggged about the great news for collaboration on Drools between the US Navy and OSDE (Argentinian health care). This is with a focus of potentially enabling Drools as an important component for the Open Source Healthcare Connect project, which provides a gateway into NHIN.

Since then we've had other heath care organisations show an interest in getting involved at some level. So it made sense that we should potentially organise another event, similar to last years boot camp, but specifically for the healthcare community.

The event will cover the usual intro into Drools, along with additional talks on the recent developments of Drools; such as our simulation/testing frameworks and service frameworks. We would ideally like to keep this industry and academic research focused. That means we will need as many third party industry and academic research talks as possible and break out sessions to discuss requirements and potential collaborations.

So whether you want to come along and tell the world about your research projects, requirements and ideas or just see what others are up to, or just find out what Drools is about, this should be a useful event for anyone in the healthcare industry.

If this interests you, either as an attendee or a presenter, then please let me know. The date is quite soon, tentatively last week of March and at the Duke University in North Carolina for 3 days.

Mark
mproctor at codehaus d0t org

New Drools Planner website

noreply@blogger.com (Geoffrey De Smet) — Mon, 01 Feb 2010 17:21:00 +0000

The new Drools Planner website is up:
http://www.jboss.org/drools/drools-planner.html
It features diagrams of some use cases, to explain them more clearly.

With the upcoming release of 5.1 milestone 2,
this will complete the rename from Drools Solver to Drools Planner.

Drools Inference and Truth Maintenance for good rule design and maintenance

noreply@blogger.com (Mark Proctor) — Fri, 22 Jan 2010 21:19:00 +0000

Back in November I did a blog on inference and how it can be useful for rule authoring.
What is inference and how does it facilitate good rule design and maintenance

The summary of this was:

De-couple knowledge responsibilities
Encapsulate knowledge
Provide semantic abstractions for those encapsulations

For my JUG in Lille I extended this example by including truth maintenance, to demonstrate self maintaining systems.

The previous example was issuing ID cards to over 18s, in this example we now issue bus passes, either a child or adult pass.

rule "Issue Child Bus Pass" when
  $p : Person( age < 16 )
then
  insert(new ChildBusPass( $p ) );
end

rule "Issue Adult Bus Pass" when
  $p : Person( age >= 16 )
then
  insert(new AdultBusPass( $p ) );
end

As before the above example is considered monolithic, leaky and providing poor separation of concerns.

As before we can provide a more robust application with a separation of concerns using inference. Notice this time we don't just insert the inferred object, we use "logicalInsert":

rule "Infer Child" when
  $p : Person( age < 16 )
then
    logicalInsert( new IsChild( $p ) )
end
rule "Infer Adult" when
  $p : Person( age >= 16 )
then
    logicalInsert( new IsAdult( $p ) )
end

A "logicalInsert" is part of the Drools Truth Maintenance System (TMS). Here the fact is logically inserted, this fact is dependant on the truth of the "when" clause. It means that when the rule becomes false the fact is automatically retracted. This works particularly well as the two rules are mutually exclusive. So in the above rules if the person is under 16 it inserts an IsChild fact, once the person is 16 or over the IsChild fact is automatically retracted and the IsAdult fact inserted.

We can now bring back in the code to issue the passes, these two can also be logically inserted, as the TMS supports chaining of logical insertions for a cascading set of retracts.

rule "Issue Child Bus Pass" when
  $p : Person( )
       IsChild( person =$p )
then
  logicalInsert(new ChildBusPass( $p ) );
end

rule "Issue Adult Bus Pass" when
  $p : Person( age >= 16 )
       IsAdult( person =$p )
then
  logicalInsert(new AdultBusPass( $p ) );
end

Now when the person changes from being 15 to 16, not only is the IsChild fact automatically retracted, so is the person's ChildBusPass fact. For bonus points we can combine this with the 'not' conditional element to handle notifications, in this situation a request for the returning of the pass. So when the TMS automatically retracts the ChildBusPass object, this rule triggers and sends a request to the person:

rule "Return ChildBusPass Request "when
  $p : Person( )
       not( ChildBusPass( person == $p ) )
then
    requestChildBusPass( $p );
end

Drools : Towards computerizing intensive care sedation guidelines:design of a rule-based architecture for automated execution of clinical guidelines

noreply@blogger.com (Mark Proctor) — Wed, 20 Jan 2010 20:21:00 +0000

Towards computerizing intensive care sedation guidelines:design of a rule-based architecture for automated execution of clinical guidelines

"The aim is to close the gap in communication between the IT and the medical domain. This leads to a less time-consuming and error-prone development phase and a shorter clinical evaluation phase.

Methods: A framework is proposed that semi-automatically translates a clinical guideline, expressed as an XML-based flow chart, into a Drools Rule Flow by employing semantic technologies such as ontologies and SWRL."

Drools JUG Lille 21st of Jan

noreply@blogger.com (Mark Proctor) — Wed, 20 Jan 2010 11:53:00 +0000

I'm going to be at the Ch’ti JUG tomorrow the 21st of January doing a Drools talk:
http://chtijug.org/rendez-vous-le-21-janvier-drools-avec-cylande-et-luniversite-de-lille-1/

Update: Geoffrey will do a Drools Planner talk too.

Drools - OSGi Ready!

noreply@blogger.com (Mark Proctor) — Mon, 18 Jan 2010 18:02:00 +0000

I've spent some time getting Drools OSGi ready, which was harder than I expected, especially as OSGi is new to me. Last night I finally got OSGi Declarative Services working with Drools. When you combine this with our Spring work, http://blog.athico.com/2009/12/drools-spring-improvements.html, it's great timing for the recent Spring DM announcement, http://blog.springsource.com/2010/01/12/dm-server-project-moves-to-eclipse-org.

For those that don't know. OSGi is a dynamic module system for declarative services. So what does that mean? Each jar in OSGi is called a bundle and has it's own Classloader. Each bundle specifies the packages it exports (makes publicly available) and which packages it imports (external dependencies). OSGi will use this information to wire the classloaders of different bundles together; the key distinction is you don't specify what bundle you depend on, or have a single monolithic classpath, instead you specify your package import and version and OSGi attempts to satisfy this from available bundles.

It also supports side by side versioning, so you can have multiple versions of a bundle installed and it'll wire up the correct one. Further to this Bundles can register services for other bundles to use. These services need initialisation, which can cause ordering problems - how do you make sure you don't consume a service before its registered?

OSGi has a number of features to help with service composition and ordering. The two main ones are the programmatic ServiceTracker and the xml based Declarative Services. There are also other projects that help with this; Spring DM, iPOJO, Gravity.

Each of the Drools factories is now also available as a FactoryService interface. You can either have OSGi inject those into a pojo, or retrieve them yourself from OSGi. I'll cover injection here. The below example injects the KnowledgeBuilderFacotryService, KnowledgeBaseFactoryService and ResourecFactoryService into the TestComponent pojo.

<scr:component xmlns:scr="http://www.osgi.org/xmlns/scr/v1.1.0">
<implementation class="testosgi.TestComponent"/>

<reference bind="setKnowledgeBaseFactoryService"
           unbind="unsetKnowledgeBaseFactoryService"
           interface="org.drools.KnowledgeBaseFactoryService"
           />
         
<reference bind="setResourceFactoryService"
           unbind="unsetResourceFactoryService"
           interface="org.drools.io.ResourceFactoryService"
           />           
         
<reference bind="setKnowledgeBuilderFactoryService"
           unbind="unsetKnowledgeBuilderFactoryService"
           interface="org.drools.builder.KnowledgeBuilderFactoryService"
           target="(org.drools.compiler.DecisionTableProvider=true)"  />           
</scr:component>

The TestComponent will only be activated when all of the referenced services are available and injected into the pojo. You'll also notice the "target" attribute for the KnowledgeBuilderFactoryService. The reason for this is that OSGi DS has no built in way to declaratively say which optional services must be present to satisfy your component. As a work around I made any Drools service that has optional services set a property if/when the optional service is available. Filters can then be applied, via the target attribute, to make sure the Service is in a desired state before consuming it. And that is pretty much it :)

Getting there wasn't so easy. The first step was in automating the build and packaging. To automate the build I used Peter Krien's BND tool. I found that BND would only automate the maven transitive dependencies by embedding them, so I did this first. This built a single Drools jar with all Drools jars and dependencies inside it. This straight away triggered ClassLoader issue, forcing me to rework how the Drools ClassLoader framework is configured. The issue here was that Drools uses the ClassLoader that you provide it when compiling DRLs, that means any runtime class loading is resolved against the ClassLoader the user provides. Because of the way OSGi works if the user was to provide a ClassLoader from their bundle, that ClassLoader would not be able to see internal classes to Drools itself. This meant I'd have the Drools bundles giving me ClassNotFoundExceptions for classes in it's own Bundle. The answer was to make a CompositeClassLoader that takes the provided user ClassLoader and combines it with the ClassLoaders of the Drools bundle's.

With that now working the next issue was the monolithic bundle we now had. I first tried to separate drools-api, to give real api separation. This then triggered "split packages". This is one of those things that you wish the OSGi people would shout from the roof tops about to anyone hoping to be OSGi compatible in the future, as I had them all over the place. A split package is where you have the same package namespace used in different jars. drools-api and drools-core both have classes in the "org.drools" namespace. There is very little documentation on resolving split packages and the solution proposed in BND didn't seem to do anything for me. I read that I can use a "mandatory" setting with my exports, which should make my imports work, but I couldn't get that working either. Instead I moved away from "Package-Import" to "DynamicPackage-Import *" and "Require-Bundle", where I tied the Drools impl bundles to the api bundle and re-exported interfaces. This seemed to do the job, although the later are frowned upon, see here. "Require-Bundle" couples your bundle to a specific version, which means you aren't making the most of the more declarative nature of OSGi and "DynamicPackage-Import *" just sucks everything in, which apparently can lead to inefficiencies in OSGi, something called a "fan out". I have to admit this gets too low level for me, so if anyone wants to add more light on this in the comments, please do and I'll paste it into the end of this blog.

The next step was to split up my monolithic Drools bundles back to their original jars and not to embed their dependencies. Variations on the following for the Drools modules seemed to work for me:

<configuration>
   <manifestLocation>META-INF</manifestLocation>
   <instructions>
       <_removeheaders>Ignore-Package</_removeheaders>                   
       <Require-Bundle>org.drools.api;visibility:=reexport;bundle-version="${pom.version}"</Require-Bundle>
       <Import-Package>!org.drools.*, *</Import-Package>
       <Export-Package>org.drools.*</Export-Package>    
       <DynamicImport-Package>*</DynamicImport-Package>
       <Bundle-Activator>org.drools.osgi.core.Activator</Bundle-Activator>
   </instructions>
</configuration>

Because many of the Drools dependencies are not OSGi ready I turned to the Spring repository, which repackages many projects with OSGi ready manifests in a Maven consumerable repository.

The Activator element specifies the class to be called when each Bundle is loaded in OSGi. The Activator registers services and where optional services need to be tracked configures a ServiceTracker that updates the properties that the target attribute can filter on. This is the programmatic way to setup services in OSGi, compared to DS.

I'm now in the process of OSGi-ifying the other Drools modules and trying to make it more robust. Thanks to Peter Kriens and the people on the #eclipse and #osgi irc channels for their patience with my questions.

Rete and "True Modify"

noreply@blogger.com (Mark Proctor) — Mon, 04 Jan 2010 20:19:00 +0000

The first commit for "true modify" is in, although we'll need to think of a better name for it. The branch doesn't fully compile, so you can't use maven. But it does compile enough to run examples that use just joins, not and exist nodes. Such as manners and waltz. And we've been extending the rete testing harness, http://blog.athico.com/2009/11/rete-dsl-testing-harness.html, to provide more thorough testing of these nodes. I'll blog this algorithm in more detail later:
http://fisheye.jboss.org/browse/JBossRules/branches/true_modify_20100104

The crux of it is that a modify no longer is a stateless retract+assert. I use the term stateless here as all state is lost in the retract and all state is recreated in the assert, it's not easy to know the state changes between these two in a stateful manner.

As an example of work arounds we have had to do, to determine those state changes, take the event model for activations. Drools has always provided activation normalisation, to make the events seem correct and for truth maintenance. When a modify happens we put all cancelled activations in a map, that happened as part of the retract, and remove all activations that are in the map that happaned as part of the assert. This way we can know what was really cancelled, stayed the same and added. While it creates a system users can more easily understand, it adds considerable overhead (about 10%) and complexity, to my knowledge Drools is the only PRD system that does this.

The new algorithm does not do two propgations, a retract + assert, it instead does a single modify propagation. This propagation applies the constraint and determines what to do and how to continue:
false before, true now = continue as assert
true before, false now = continue as retract
true before, true now = continue as modify
false before, false now = do nothing

Tradditional symetrical Rete implementations, such as in Drools 4, would not be able to do this http://blog.athico.com/2008/10/symmetrical-and-asymmetrical-rete.html. Because there is not enough state in the network to avoid the retract + assert. Drools 5.0 implements asymetrical Rete for tree based removal as mentioned in the Doorenbos's papers and based on the work of Gary Riley in Clips. In this algorithm every Tuple (Jess calls Tokens and Clips calls PartialMatch) knows which Tuples it was joined to and all resulting children, likewise each child knows it's parents. The implementation alone in Drools 5.0 was not enough to move straight to true modify and the data structures had to be changed, mostly around deterministic iteration. For perf Drools 5 and Clips would just reference the head of a list, we would iterate from the head and add to the head. For true modify the opposite node iterations must be in the same order as the child tuple iterations. To achieve that we need to keep a reference to both the head and the tail, we add to the tail and iterate from the head. Along with a few other additions that means we can now implement modify methods, as illustrated in the JoinNode modifyLeft


public void modifyLeftTuple(final LeftTuple leftTuple,
                            final PropagationContext context,
                            final InternalWorkingMemory workingMemory) {
    final BetaMemory memory = (BetaMemory) workingMemory.getNodeMemory( this );

    // Add and remove to make sure we are in the right bucket and at the end
    // this is needed to fix for indexing and deterministic iteration
    memory.getLeftTupleMemory().remove( leftTuple );
    memory.getLeftTupleMemory().add( leftTuple );

    this.constraints.updateFromTuple( memory.getContext(),
                                      workingMemory,
                                      leftTuple );
    LeftTuple childLeftTuple = leftTuple.firstChild;

    RightTupleMemory rightMemory = memory.getRightTupleMemory();

    RightTuple rightTuple = rightMemory.getFirst( leftTuple );

    // first check our index (for indexed nodes only) hasn't changed and we are returning the same bucket
    if ( childLeftTuple != null && rightMemory.isIndexed() && rightTuple != rightMemory.getFirst( childLeftTuple.getRightParent() ) ) {
        // our index has changed, so delete all the previous propagations
        this.sink.propagateRetractLeftTuple( leftTuple,
                                             context,
                                             workingMemory );

        childLeftTuple = null; // null so the next check will attempt matches for new bucket
    }

    // we can't do anything if RightTupleMemory is empty
    if ( rightTuple != null ) {
        if ( childLeftTuple == null ) {
            // either we are indexed and changed buckets or
            // we had no children before, but there is a bucket to potentially match, so try as normal assert
            for ( ; rightTuple != null; rightTuple = (RightTuple) rightTuple.getNext() ) {
                final InternalFactHandle handle = rightTuple.getFactHandle();
                if ( this.constraints.isAllowedCachedLeft( memory.getContext(),
                                                           handle ) ) {
                    this.sink.propagateAssertLeftTuple( leftTuple,
                                                        rightTuple,
                                                        context,
                                                        workingMemory,
                                                        this.tupleMemoryEnabled );
                }
            }
        } else {
            // in the same bucket, so iterate and compare
            for ( ; rightTuple != null; rightTuple = (RightTuple) rightTuple.getNext() ) {
                final InternalFactHandle handle = rightTuple.getFactHandle();

                if ( this.constraints.isAllowedCachedLeft( memory.getContext(),
                                                           handle ) ) {
                    if ( childLeftTuple != null && childLeftTuple.getRightParent() != rightTuple ) {
                        this.sink.propagateAssertLeftTuple( leftTuple,
                                                            rightTuple,
                                                            context,
                                                            workingMemory,
                                                            this.tupleMemoryEnabled );
                    } else {
                        // preserve the current LeftTuple, as we need to iterate to the next before re-adding
                        LeftTuple temp = childLeftTuple;
                        childLeftTuple = this.sink.propagateModifyChildLeftTuple( childLeftTuple,
                                                                                  rightTuple,
                                                                                  context,
                                                                                  workingMemory,
                                                                                  this.tupleMemoryEnabled );
                        // we must re-add this to ensure deterministic iteration
                        temp.reAddLeft();
                    }
                } else if ( childLeftTuple != null && childLeftTuple.getRightParent() == rightTuple ) {
                    childLeftTuple = this.sink.propagateRetractChildLeftTuple( childLeftTuple,
                                                                               rightTuple,
                                                                               context,
                                                                               workingMemory );
                }
                // else do nothing, was false before and false now.
            }
        }
    }

    this.constraints.resetTuple( memory.getContext() );
}

The first thing you'll notice is that this is about third more code than retract+assert together, and there are additional logic tests to determine the before and after states. This combined with a small overhead addition in the data structures means that actually we aren't reducing the executed code statements, but increasing. What you'll notice though is that if there are no state changes, true before and true now, unlike retract+assert it avoids a Tuple creation. So for large conflict sets, where none or only a small proportion of the set changes we get much less or even no object creation and thus reduced load on the GC. In the past large systems with millions of facts using gigabytes of memory have had GC problems, where Drools is creating objects faster than standard GC can keep up with, causing OOME. The answer then was to tune the GC, to make it run more aggressively and more often. For those systems true modify should hopefully be a real advantage. Waltz and manners are small applications and are only marginally faster, most likely only due to the removal of the activation normalisation.

But is it only large systems that will benefit? Not at all. Now that we have stateful modifications it opens up lots of new opportunities for optimisation. The biggest initial gain will be from the more functional programming aspects of Drools. When you use 'from' to nest and chain conditional elements and patterns you are using Drools in a functional way. Accumulates are like left folds, it iterates a set of data and produces a derived object which we filter with patterns or other conditional elements.


$p : Person( location == "london" )
accumulate( CashFlow( person == $p, type == "DEBIT", $v : value ).
            sum( $v ) )

If the Cashflows are all inserted first, the accumulation is triggered by the insertion of a Person. What happens if we change a field on the person, but not the location? In the functional world changes in values for a field are known as side effects. With the traditional Rete approach we have no way of knowing if the side effect can impact the results of the function, more than that the results are wiped away during the retract. With the modify we still have the result, we can then determine if the modified object or field can impact the accumulation, if it doesn't we can use the result as is, no need to recalculate. Some applications can chain many accumulations in a single rule, the savings in performance here are orders of magnitudes, Drools Planner (was solver) is such an application that will make big gains from this.

Range optimisations, age > $v, normally use BTrees for indexing. If every modify is a retract+assert this would send the BTree rebalancing into over drive, negating any benefits. Now that we can avoid any unnecessary BTree manipulation, range indexing becomes a possibility for Join Nodes.

We can analyse a rule and determine for each object change, at the point that it enters a rule which later nodes depend on this object. We can either avoid unnecessary checks and just propagate to the next node, or just avoid propagation all together. This can all help reduce the amount of work done during the matching phase.

I'm not sure of any literature or other engines that implement this Rete enhancement, so if you know of anything please point me in the right direction.

For a bit of historical information on Drools. In early 2.0 beta releases and in the Drools 3.0 final release there were attempts at "true modify". The approach in Drools 3.0 meant that each Tuple used Maps and Sets to keep references to matches and children. It worked, but performance was not scalable as memory use went through the roof. Which is why Drools 4.0 returned to a more traditional symmetrical Rete implementation. It's been a long sought for goal, that we haven't managed to get right in the past, but feel we are finally there. So I should add, other implementations or literature that worked in scalable way :)

Planning the traveling tournament problem

noreply@blogger.com (Geoffrey De Smet) — Mon, 28 Dec 2009 18:19:00 +0000

One of the older examples in Drools Planner is the Traveling Tournament Problem as defined by Trick et al. I haven't improved/optimized on it much in the last couple of years, but recently I made a diagram to explain the problem more clearly:

We need to schedule matches between N teams while respecting the following hard constraints:

Each team plays twice against every other team: once home and once away.

Each team has exactly 1 match on each playing day.

No team must have more than 3 consecutive home or 3 consecutive away matches.

No repeaters: no 2 consecutive matches of the same 2 opposing teams.

There's only one soft constraint:

Minimize the total distance traveled by all teams.

This might look like a really easy problem, but even for low N's (12 <= N <= 24) they haven't found (or at least proven) the optimal solution yet. Regularly better solutions are found for the larger N's.

Still, those N's are embarrassingly small compared to real-world planning problems such as examination timetabling (N >= 1000), shift rostering or bin packaging.

Screencasts on some FAQ

noreply@blogger.com (Kris Verlaenen) — Tue, 15 Dec 2009 23:52:00 +0000

We regularly see the same questions pop up on the mailing list or on our irc channel. While we try to write documentation on how to do all these things, some things might be easier to explain using a quick example. I have recently created screencast for two such issues.

Debugging your Drools application in Eclipse

The Drools Eclipse plugin contains various debug views that allow you to do advanced debugging of your Drools application, showing the object in your session, the agenda, etc. Check out section 7.10 of the Drools Expert documentation. This screencast shows you how to get these debug views working for a simple Hello World rule. It also shows how to use breakpoints inside a rule.

Domain-specific nodes in Drools Flow

Drools Flow allows you to create your own domain-specific nodes. Such nodes have their own icon, properties and possibly even a custom editor. This screencast shows how you can create your custom work item node, use it in your process, and then register a handler to execute it at runtime.

Enjoy!

Cisco ANA - "Drools Inside" :)

noreply@blogger.com (Mark Proctor) — Thu, 10 Dec 2009 01:45:00 +0000

The Cisco ANA PDF is online, showing their Drools integration for their Advanced Network Abstraction (ANA) product. You can download the PDF here. So maybe Cisco products should have a new badge "Drools Inside" :)

click to enlarge

If anyone from Cisco reads my blog and wants to chat about Drools, feel free to contact me mproctor at gmail d0t com.

Calendar support with Drools

noreply@blogger.com (Mark Proctor) — Wed, 09 Dec 2009 13:19:00 +0000

Last week I blogged about 'cron' and 'int' (interval) based timer support:
"Cron and Interval based timers for rule firing and re-firing"

This week I've added Calendaring support. Calendaring allows you to provide a Set of Calendar implementations that specify allowed and disallowed time segments. With this you could create a "week day" Calendar which would specify Monday to Friday as the included time segments, leaving Saturday and Sunday as not included. I can then specify that Calendar in a rule. Monday to Friday if the rule activates it will fire, over the weekend if the rule activates it will ignored.

The Calendar api is modelled on Quartz :

public interface Calendar {    
    boolean isTimeIncluded(long timestamp); 
}

Quartz provides several good Calendar implementations, so it makes sense to leverage those, for this we we provide an adapter helper method:

Calendar QuartzHelper.quartzCalendarAdapter(org.quartz.Calendar quartzCal)

Calendars are registered with the StatefulKnowledgeSession:

ksession.getCalendars().set( "week day", weekDayCal );

Which means they can now be used in rules. They can be used in conjunction with normal rules and rules including timers.

rule "weekdays are high priority"
   calendars "weekday"
when 
    Alarm()
then
    send( "priority high - we have an alarm );
end 

rule "weekend are low priority"
   calendars "weekend"
when 
    Alarm()
then
    send( "priority low - we have an alarm );
end

Now I can already imagine some of you are thinking, well that's kinda cool and it's nice the semantics of Calendars and a Calendaring api supported out of the box. But I could achieve much the same thing by asserting Calendars as facts, placing the Calendar constraint as the last pattern and it'll block activations that are not included in the required time. While this is true, it would not work with Timer based rules. As we can now do this:

rule "weekdays are high priority"
   calendars "weekday"
   timer (int:0 1h)
when 
    Alarm()
then
    send( "priority high - we have an alarm );
end 

rule "weekend are low priority"
   calendars "weekend"
   timer (int:0 4h)
when 
    Alarm()
then
    send( "priority low - we have an alarm );
end

The above rules use an interval based timer, a cron timer is also supported. On weekdays while there is an alarm it will trigger the rule initially straight away (delay of 0) and then every hour. At the weekends it will trigger the rule every four hours. If we had inserted the Calendar as a fact, we'd have to find some additional way to re-trigger the evaluation. Calendars themselves do not have mutable state, instead it's more like a function that tells you if the specified date is included or not. While this is not impossible to solve, it's getting messy very quickly. You'll need additional trigger facts, that will force Calendar evaluation at required points in time, that are managed by your own scheduler. This way it's efficient (no network propagation), clear syntax and intent and works out of the box. I should add that it'll work out of the box with our simulation api, thanks to our unified clock implementation.

So what we have now is conditional rule based timers and calendaring. The cool thing here is we can use this for Drools Flow, using it to start processes or trigger wait states. While process centric implementations do have timer and calendaring support, the conditional rule integration adds a whole new level of power to this.

Drools Planner (AKA Drools Solver) Devoxx presentation movie

noreply@blogger.com (Geoffrey De Smet) — Mon, 07 Dec 2009 18:50:00 +0000

Thanks to Parleys Beta, I am proud to present:
Examination timetabling with Drools Planner - the movie
Actually, it's not as much a movie as it is a Devoxx 2009 presentation.

Click here to watch it full screen at beta.parleys.com

I made a few updates since the live presentation at Devoxx, such as the rename from Drools Solver to Drools Planner.

Just before posting this blog, David alerted me of a small (but embarrassing) calculation mistake in one of the slides. Can you find it?

Some Tohu videos

noreply@blogger.com (Michael Neale) — Thu, 03 Dec 2009 00:47:00 +0000

Tohu is the project which ads Q&A and "smart form" intelligence on top of drools (and provides a very nice CSS stylable and embeddable jquery based ajax front end as well). (see project page here).

Some interesting demo videos made by solnet here explaining how it works:

Example 2 (spreadsheet to define Q&A)

Example 1

Yet more !

(In case you are wondering, the accent you can here is New Zealand - or Middle Earth as I prefer to refer to it - perhaps only NZ and Australian citizens can tell the difference between !).

Enjoy !