AC-HAPE3D:基于强化学习的异形填充算法

AC-HAPE3D: an algorithm for irregular packing based on reinforcement learning

在3D打印、快递物流等领域,需要将形状各异的零件或货物在限定的空间中摆放,称为异形填充。给出一种摆放方案,以便将尽可能多的多面体放入给定容器;或者一批物体紧密地摆放,使得占用体积最小,则称为异形填充问题。这是个NP问题,很难高效求解。基于此,研究在一个可变维度的三维容器内摆放给定的一组多面体,使得打包后容器的可变维度最小。并提出一个基于强化学习的算法AC-HAPE3D,利用启发式算法HAPE3D将问题建模为马尔可夫过程,再利用基于策略的强化学习方法 Actor-Critic进行学习。同时用体素来表示容器和多面体,从而简化状态信息的表达,并用神经网络表示价值函数和策略函;为了解决状态信息长度以及动作空间可变的问题,采取遮罩的方法来屏蔽部分输入和输出,并且引入LSTM来处理变长的状态信息。在5个不同的数据集进行的实验表明算法能够取得较好的结果。

In areas such as 3D printing and express logistics, irregular packing results from the need to place parts or goods of different shapes in a defined space. A placement solution could be put forward, allowing as many polyhedra as possible to fit into a given container, or a batch of objects could be placed so closely together that they occupy the smallest volume, which is known as the irregular packing problem. This is an NP problem but is difficult to solve efficiently. This paper undertook the following investigation: placing a given set of polyhedra inside a 3D container with a variable dimension, so that the variable dimension of the packed container could be minimized. We proposed a reinforcement learning based algorithm, AC-HAPE3D. This algorithm could model the problem into a Markov process using the heuristic algorithm HAPE3D, and then utilize the policy-based reinforcement learning method Actor-Critic. We simplified the representation of state information by using voxels to represent containers and polyhedra, and employed neural networks to represent value and policy functions;to address the problem of variable length of state information as well as action space, we adopted a masking approach to masking some of the inputs and outputs, and introduced LSTM to handle variable length of state information. Experiments conducted on five different datasets show that the algorithm can yield good results.