Saturday, February 27, 2010

Best score over time graphs

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.

Monday, February 22, 2010

Collection-oriented Match for massively parallel Drools 6

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.

Sunday, February 21, 2010

Versatile Benchmarking for Concurrent Production System Architectures

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."

Friday, February 19, 2010

Automated planning problems are cursed with NP completeness

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.

Tuesday, February 16, 2010

Enterprise Space Invaders !

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

Tuesday, February 09, 2010

CHEF: A Model of Case-based Planning

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."

Thursday, February 04, 2010

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

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

Monday, February 01, 2010

Open Source Healthcare Event (last week of March)

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

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.