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.