AI that maximizes the storage of rectangular parallelepipeds in a bigger parallelepiped

Question

As you can see in the title, I'm trying to program an AI in Java that would help someone optimize his storage.

The user has to enter the size of his storage space (a box, a room, a warehouse etc...) and then enter the size of the items he has to store in this space. (note that everything must be a rectangular parallelepiped) And the AI should find the best position for each item such that the space is optimized.

Here is a list of what I started to do :

• I asked the user to enter the size of the storage space (units are trivial here except for the computing cost of the AI later on I'm guessing), telling him that the values will be rounded down to the unit
• I started by creating a 3-dimensional array of integers representing the storage space's volume, using the 3 values taken earlier. Filling it with 0s, where 0s would later represent free space and 1s occupied space.
• Then, store in another multidimensional array the sizes of the items he has to store And that's where the AI part should be starting. First thing the AI should do is check whether the addition of all the items' volumes doesn't surpass the storage space's volume. But then there are so many things to do and so many possibilities that I get lost in my thoughts and don't know where to start...

In conclusion, can anyone give me the proper terms of this problem in AI literature, as well as a link to an existing work of this kind ? Thanks

Answer 1

This looks very much like a variation of the bin packing problem. The bad news is that this is mathematically a hard problem, NP-hard in fact (which means that no polynomial-time solution is possible). The good news is that it is heavily studied, with multiple approaches to solving it, or at least optimising solutions to within reasonable bounds.

Which approach to optimisation will work best for you will depend on how physically accurate you want your model to be. Your voxel approach already makes some decisions in that regard, but you may also want to consider issues such as gravity, stability of any piles of structures you create, and access to items. These things add additional constraints that make modelling the problem and implementing an optimiser harder, so you might want to start with more unrealistic model initially.

One simple approach might be to use a simple heuristic e.g. pack largest objects first, fill close to edges first etc. Then attempt to swap or revise the order of packing of a few pieces and see if it makes an improvement. You can make those changes greedily, or look into making them more randomly but with a system that rewards better improvements. Approaches such as simulated annealing or genetic algorithms can be used as stochastic approaches, many others are possible. There are a very large number of global optimisers that might help with such a combinatorial problem.

Here is an example of solving a bin packing problem using Simulated Annealing.

Here is an example of solving a bin packing problem using a Genetic Algorithm