0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Have you looked at en.wikipedia.org/wiki/Knapsack_problem ? $\endgroup$
    – Oliver Mason
    Commented Sep 30, 2021 at 7:48
  • $\begingroup$ @OliverMason: I know the Knapsack problem, but I‘m not sure how I can solve my problem with this. For me it‘s necessary to know the distinct position of the shapes on the rectangular area. After a proper positioning I want to cut the shapes out. I edited also my question for hope of being more precise... $\endgroup$
    – tueftla
    Commented Sep 30, 2021 at 8:23

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hey Sanyou, thanks a lot for your response. I wanted to create my own environment with OpenAI Gym with the action space select one of the three shapes, rotate it when you want and place it in the area. Positiv rewards are given for placing a shape, considering the minimum distance of the shapes. When there is an overlap between shapes or the edge of the area then the reward is negativ. These rewards are given after every disposal of shapes. At the end (agent cannot place a further shape) I think I have to give also rewards concerning the quantity of shapes and the waste... $\endgroup$
    – tueftla
    Commented Sep 30, 2021 at 13:18
  • $\begingroup$ I think setting up the AI gym is straightforward as it is returning "raw" state and action choice(?) The challenge though is the reward function. The gym can be helpful, similiar to what you said, by giving penalty or do nothing when constraint is violated e.g.. shapes are intersected, or even terminate early. I said helpful because careful reward function design can help the model learn better. As for the final reward i.e., number of shapes and wasted area, you can aggregate them by linear/nonlinear combination, or you can treat them as separate reward and turn this into Multiple Objective RL $\endgroup$
    – Sanyou
    Commented Sep 30, 2021 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .