0

I have a rectangular area, where I need to place some 2 dimensional geometrical shapes - like a square or circle or a little more complicated shapes. And after the arrangement these shapes should be cut out.

Requirements to the disposal of shapes:

  • These shapes are not allowed to intersect
  • And also they must disposed on the recatangular area
  • They must have at least a minimum distance
  • The waste should be minimized
  • When more than one shape is arranged on this area it is desirably that the shapes have a certain quantity (e.g. shape A: 50 %, shape B: 30 %, shape C: 20 %)

After the arrangement I get the coordinates of the single shapes so that I can cut out my shapes...

To solve this I thought of (deep) reinforcement learning but because I'm new to ML I'm not sure if there is a more appropriate method to solve this problem.

I hope that you can give me some hints or simply confirm my assumption that (deep) reinforcement learning is appropriate. And perhaps you can also offer me some useful links...

Many thanks in advance for your help!

And lastly a little picture which is showing a possible bad result because shape A and shape E intersect. And probably there is to much waste.

enter image description here

tueftla
  • 103
  • 3

1 Answers1

1

You might want to start on googling the "Irregular Cutting Stock Problem". I think your problem formulation is similar to Irregular Cutting Stock Problem. Some cool papers are up in the results such as this heuristic method which is tested on real-world based problem instances.

By browsing the existing heuristic/metaheuristic methods, you may get inspiration on how to represent the solution, how to evaluate immediate shapes placement, and the existing local search operators. By then, you can try ML-based adaptive operator selection (AOS) method so that given the current state of the sheet and the existing shapes, you can choose the "best" local search operator to improve the placement. On the other hand, if you can embed the current state of the sheet as well as the current considered shape, you can predict the action of placing that shape (x,y,rotation degree) and train your model with RL methods assuming you have defined the appropriate reward function for the action you've taken.

Sanyou
  • 175
  • 2
  • 10