1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Welcome to AI Stack Exchange. The question start looks fine. However, it falls over at the end. The site cannot answer "any help is welcome" or just post links. Ideally you should post a question which can be answered with an objectively correct answer ("any help" is too broad and too subjective). For instance, perhaps "What is this problem called in the AI literature, and are there known ways to solve it?" might be more on-topic - would that phrasing work for you? $\endgroup$ – Neil Slater Oct 19 '18 at 13:54
  • $\begingroup$ Yes, that phrasing is actually quite on point, thanks! Let me edit my question $\endgroup$ – Nawra C Oct 19 '18 at 14:14
  • $\begingroup$ Also I just noticed you are on Data Science here, and this is probably more suitable for another site (I thought it was on AI as you could tell from my comment!) . . . there are a couple of alternative sites that might be better for this. I'm not 100% certain if a better fit for AI or elsewhere - there are going to be people in Data Science who recognise this problem, so I'll leave that for now. It may get migrated but that will need a moderator. $\endgroup$ – Neil Slater Oct 19 '18 at 14:23
0
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ I guess if it's suitable for a Kaggle Competition kaggle.com/c/packing-santas-sleigh - then the topic should probably be OK on Data Science $\endgroup$ – Neil Slater Oct 19 '18 at 15:19
  • $\begingroup$ I understand why no "perfect" solution has been found, since if we take into account that the objects can be rotated in any 90 degrees, it means (if x != y != z of each objects) that there are 6 possible rotations, meaning that ONLY for rotations there are factorial(6*nbOfObjects)... if nbOfObjects = 20, then we already have 6.689503e+198 cases of rotations, and that's not even talking about position. $\endgroup$ – Nawra C Oct 19 '18 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.