Thursday, April 24, 2008

Solving the Examination problem part 2: score function

This is the second part in a blog series about drools-solver and the Examination problem. If you haven't done so, read Solving the Examination problem: Domain diagram first.

Each possible solution has a score. Before we try to find the best solution, we need a way to calculate the score of a solution. And that's where the drools rule engine comes into play.

So the current working solution is asserted into the working memory (based on it's getFacts() method) and a number of score rules are fired upon it. Generally, each (hard or soft) constraint translates into a single score rule.

For example, this is the score rule to penalize all exams for which the period duration doesn't suffice.
// More time required during a period than available in that period.
rule "periodDurationTooShort"
when
// Any exam who's duration is longer that it's period duration ...
$exam : Exam(eval(topicDuration > periodDuration));
then
// ... is penalized hard.
insertLogical(new IntConstraintOccurrence("periodDurationTooShort", ConstraintType.NEGATIVE_HARD,
$exam.getTopicStudentSize(),
$exam));
end

Of course, some rules are more complicated, like the score rule to penalize all conflicting exams in a row:
// Two exams in a row which share students
rule "twoExamsInARow"
when
// When 2 in row exams are penalized, ...
$institutionalWeighting : InstitutionalWeighting(twoInARowPenality != 0);

// ..., any 2 exams that share students ...
$topicConflict : TopicConflict($leftTopic : leftTopic, $rightTopic : rightTopic);

// ... of which the periods ...
$leftExam : Exam(topic == $leftTopic, $leftPeriod : period);
$rightExam : Exam(topic == $rightTopic, $rightPeriod : period);

// ... occur on the same day ...
eval($leftPeriod.getDayIndex() == $rightPeriod.getDayIndex());

// ... and are successive, ...
eval(Math.abs($leftPeriod.getPeriodIndex() - $rightPeriod.getPeriodIndex()) == 1);
then
// ..., are penalized softly.
insertLogical(new IntConstraintOccurrence("twoExamsInARow", ConstraintType.NEGATIVE_SOFT,
$topicConflict.getStudentSize() * $institutionalWeighting.getTwoInARowPenality(),
$leftExam, $rightExam));
end

Using the drools rule engine to calculate the score has a bunch of advantages:
  • The constraint score rules are easier to implement, once you get the hang of the DRL pattern syntax.

  • The implementations of the constraints are isolated from each other.
    So adding extra constraints is easy and scalable.

  • If the working solution changes into an adjacent solution (for example due to a solver move), drools does forward-chaining. This means you get delta based score calculation without any effort. That's a huge performance boost without breaking a sweat.

Now that we know how to calculate the score of solution, we can recognize a good solution. In a next blog we 'll take a look at finding the best solution we can find out of 10^5761 possible solutions.

Tuesday, April 08, 2008

Dr. Forgy's 1979 PhD thesis in chapter by chapter PDF

James C. Owen of KSBC has kindly provided PDF'ized versions of Dr Charles Forgy's thesis, where he defines the RETE algorithm (Charles Forgy is the inventor of the RETE algorithm, which is kind of important to rule engines ;).

For those who are interest in this, you can find them here. They are broken down by chapter as they are pretty large. There is a whole lotta history here (which I thoroughly enjoy). The 70's and 80's were a golden age for software (and music !).

Monday, April 07, 2008

BRMS for Drools 5

Also: Introducing Guvnor.



Guvnor is the new name for the BRMS. The term BRMS kind of has an industry meaning that is slightly different from what we call the Drools BRMS (when we say it, we mean the repository and web tools mostly). Hence, the name Guvnor (kind of related to governance - but really, it just sounds cool). On top of that, we are extending guvnor to manage other asset types - which aren't directly related to rules (but that's another story, for another day).

Anyway, the new look guvnor:


Hopefully, we will have snapshots and milestones available for this very shortly.

Here is a quite tour of some of the more interesting features:

1. Web based decision tables:

This is obviously quite different from the spreadsheet based ones, and use a similar approach to the guided editor to help you set up the table to allow people to enter rule data.

The columns are configured just so:


You can also configure lists of values, or use data driven enumerations (just like before):


You can of course mix and match this with other rule types, as not everything is easy to represent in decision tables.

The most interesting feature (to me) is the integrated testing UI. I am a big fan of test driving anything. So, you can do that with rules. You can specify what you expect your results to be for a given scenario. You can narrow that scenario to an individual rule, if you want, or you can exclude rules (you would want to do this if a particular rule had a destructive side effect). You can also simulate dates for checking date effective rules etc.
This sort of scenario based expectation testing works well when your rules focus on the data and the logic on the data, and avoid programmatic logic and external side effects, of course.

What a scenario looks like:

You can see the expectations (which has one failure in this case) and the input data.

Also, you can treat a list of scenarios as a test suite:

And then run it to get unit test like green/red bars (well all love seeing green !):


From this we can also see what percentage of rules were exercised (and thus increase our confidence that we almost know what we are doing !).

I demonstrated this in Melbourne last week, and this really helped clarify to people what it was all about.

Sunday, April 06, 2008

Revisiting ANTLR

I believe most of you users that had a look at the Drools source code, in special at the parser, knows that we use ANTLR as our parser generator. We started using ANTLR v2, with our first grammar written by Bob, and then we moved to ANTLR v3 right after it was available, still in beta phase.

We always used a regular single step ANTLR generated parser, specially because of this heritage from ANTLR v2, but DRL is becoming a complex language to parse as we make it more user friendly and add features to it.

So, this weekend I decided to learn about the next step in flexibility provided by ANTLR, and that takes the form of multi-step AST/Tree grammars.

Have in mind that I'm a beginner in the parser/compiler black magic arts, but I must say I'm astonished by the simplicity with which ANTLR allows us to handle complex scenarios. AST and Tree grammars are an amazing tool! Add template processing to that and you get something really unique!

I will not repeat here what is in ANTLR docs and specially in Terence's book, but I can safely tell you: if you need to write a parser, ANTLR is the one stop for you and The Definitive ANTLR Reference book is your must read bible. Thank you twice Terence!

So, soon we shall move our main grammar to a multi-step AST/Tree parser, and hopefully get even better user feedback on DRL rules, ranging from better error reporting to more intelligent context assistance. Stay tuned.

My thanks also to Alexandre Porcelli, that provided real-time help with some questions I had during the weekend.

Cheers,
Edson

Wednesday, April 02, 2008

Michael talking in Melbourne on Thursday night

Anyone feel free to come along.

Hosted at:

Thursday April 3rd at 7pm
Red Hat - Level 5, 455 Bourke St Melbourne

I will be showing off a whole lot of stuff.

Feel free to come, ping MJBUG@googlegroups.com to RSVP if you can.

Tuesday, April 01, 2008

Google Summer of Code Deadlines extended

The GSoC application deadlines have been extended until 7th of April, as detailed here. I preveiously discussed the Drools GSoC projects here. For the lazy I'm listing those below again, so please hurry about get your applications in here:

  • Subversion/CVS and JCR synchronisation. This allows our web based BRMS, called Guvnor, to synchronise it's content with what's used in an IDE, such as Eclipse
  • Eclipse file upload tool with meta-data properties editing. You should be able to right click a file or a folder and upload to the web based Guvnor. Previously uploaded files(assets) should be recognised and uploaded as a modify.
  • SBVR, structured natural language, implementation for Drools. Can do either or both the frontend or the backend.
  • Eclipse tooling enhancements including any of the following: search, refactoring, reformatting.
  • Animate the Rete view to represent network propagation.
  • Improve the DSL capabilities of Drools, supporting more complex grammars.
  • Improve the Guvnor, web based BRMS, to handle the management of more asset types. Including images, video, sound etc. Guvnor involves JCR, Seam and GWT work.
  • Create a Web based process designer for Drools ruleflow using GWT Designer.
  • Web based, GWT, Audit viewer.