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.
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.
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 article, I 'll prove that brute force takes billions of years even for small planning problems.
Geoffrey De Smet is a Java developer from Gent, Belgium. In his spare time, he specializes in solving automated planning problems and develops the Drools Planner project.