Saturday, July 02, 2011

Real-time planning with Drools Planner: demo video

Real-time planning problems, such as airport runway scheduling, have a paradox:
  • Optimizing such a planning problem into a usable, good solution takes minutes or even hours (because they are NP-complete).
  • The planning facts can change up to a few (milli)seconds before the planning is used.
So by the time the solver finds a good solution to the problem, the problem might have already changed.

Yet, JBoss Drools Planner can handle this. For Drools Planner 5.3, I 've created out-of-the-box support for real-time planning (sources of the prototype are here). Take a look at a demo video:


Real-time planning with Drools Planner: demo video from Geoffrey De Smet on Vimeo.

Log

Here the log of a different run which shows what's going on:

08:44:44,055 [pool-1-thread-1] INFO  Solving with random seed (0).
...
// The solution is feasible after 2450 ms
08:44:46,505 [pool-1-thread-1] INFO  Greedy phase ended at step index (199) for best score (0hard/-80090soft).
08:44:46,639 [pool-1-thread-1] INFO  Step index (0), ..., new best score (0hard/-79840soft), ...
...
08:44:52,194 [pool-1-thread-1] INFO  Step index (84), ..., new best score (0hard/-73820soft), ...
// Another thread schedules the computer deleting event, while the Planner thread is solving
08:44:52,246 [AWT-EventQueue-0] INFO  Scheduling deleting of computer (Computer 3).
08:44:52,254 [pool-1-thread-1] INFO  Step index (85), ...,     best score (0hard/-73820soft), ...
08:44:52,257 [pool-1-thread-1] INFO  Done 1 PlanningFactChange(s), new score (0hard/-71520soft), possibly uninitialized. Restarting solver.
...
// The solution is feasible again after 71 ms
08:44:52,317 [pool-1-thread-1] INFO  Greedy phase ended at step index (9) for best score (0hard/-75250soft).
08:44:52,374 [pool-1-thread-1] INFO  Step index (0), ..., new best score (0hard/-74850soft), ...
...
08:44:55,666 [pool-1-thread-1] INFO  Step index (57), ..., new best score (0hard/-70660soft), ...
...

Use cases

In the demo I am scheduling computer processes on a grid of computers, but there are plenty of other real-time planning problems, such as:
  • Train station track/platform scheduling
  • Airplane gate scheduling at the airport
  • Hospital emergency room/doktor/patient scheduling
  • ...
And all of these need to be able to scale in data and constraints, which is no problem for Drools Planner.

No comments:

Post a Comment