一种基于深度强化学习的三维装箱智能决策系统与方法

摘要: 本发明涉及三维装箱技术问题领域,具体是一种基于深度强化学习的三维装箱智能决策系统与方法。背景技术:1、三维装箱问题(three-dimensionalbinpa...
一种基于深度强化学习的三维装箱智能决策系统与方法

本发明涉及三维装箱技术问题领域,具体是一种基于深度强化学习的三维装箱智能决策系统与方法。

背景技术:

1、三维装箱问题(three-dimensional bin packing problem, 3d-bpp)是组合优化领域的经典np-hard问题,其核心目标是在有限空间的容器中装载尽可能多的货物,以最大化空间利用率并降低运输成本。该问题不仅具有重要的理论研究价值,更在物流运输、仓储管理、集装箱装载、电商包裹分拣等实际场景中具有广泛的应用需求。随着全球电子商务和智能物流的快速发展,如何高效地将不同尺寸的货物装入有限空间的容器中,已成为现代物流系统面临的核心挑战。

2、尽管一维装箱问题(1d-bpp)已可在中等规模实例(约1000件货物)上实现精确求解,但三维装箱问题由于空间维度的扩展,其计算复杂度呈指数级增长,至今仍难以获得全局最优解。

3、三维装箱问题的研究现状:

4、目前,求解三维装箱问题的常用方法主要包括数学规划法(如分支定界法、整数线性规划)、启发式算法(如极值点法、层构造法)以及深度强化学习(drl);

5、数学规划法将货物装箱问题视为一种带约束的优化问题,其核心在于构建装载问题的数学模型和设计优化算法。数学规划法常用的模型包括0-1整数规划模型、混合整数模型和线性规划模型等,常用的算法则分为分支定界法、单纯形法、深度优先搜索算法、动态规划算法、回溯法和贪婪算法等。具体而言,bhattacharya等人在发表的文章中,采用深度优先搜索算法能够有效解决小规模的单品种货物二维配装优化问题,但由于该算法的计算复杂度随装入货物规格数目的增加呈指数增长,因此不适合求解大规模的配装问题。martello、pisinger和vigo等人提出了一种分支定界法用于求解单一背包问题,但在假设货物摆放姿态固定的情况下,该方法在多项式时间内只能对20件货物进行优化计算。hifi提出了一种结合深度优先搜索算法和动态规划算法的方法,用于求解三维货物装箱问题,该方法在考虑货物摆放姿态约束和摆放复杂度约束的情况下,能够在多项式时间内对50件货物进行优化计算。此外,hifi、kacem、nègre等人探讨了线性规划方法在三维装箱问题中的应用。delorme、iori和martello等人系统综述了一维与三维装箱及下料问题的数学模型与精确算法。国内,李鹏和汤勇等人在《三维货物装箱问题的研究进展》(铁道科学与工程学报)中对三维装箱问题的研究进展进行了综述。

6、在启发式算法研究方面,mahvash、awasthi和chauhan等人利用极点定价和列生成提供可旋转装箱的优质上下界。harrath借助分层构造与milp联立,兼顾荷载平衡与层数优化。tresca、cavone、carli等人同样基于层构造方法设计了求解器。chen、huo和duan等人以及yang、wu、hao等人把箱体尺寸设计纳入求解闭环。近年来,研究者还通过参数重构、gan生成、双层遗传与自适应小生境等策略提升搜索效率。研究者把改进极值点与模拟退火串联以兼顾实时性与全局性,或引入转弯重心约束并以改进乌鸦搜索实现多概率随机游走。

7、上述启发式算法展示了传统智能方法在工程可解释性方面的优势,但在数据质量与策略泛化能力方面仍存在局限。

8、在基于人工智能的解决方案研究方面,现有方法多以强化学习和深度强化学习为算法主体。。zhao、she、zhu等人在会议论文中以受限马尔可夫决策过程刻画在线装箱并提出预测-投影掩码,使策略直接过滤不可行动作。同一团队通过堆叠树稳定性分析与配置树层级表示,实现高分辨率放置和大规模问题的分解求解。fukuda、yamakita和oyama在会议论文中进一步引入外部缓冲与树形动作规划,在复杂约束下提升填充率。tsang、mo、chung等人以及张长勇、姚凯超和张宇浩等人针对多箱并行与多类实际约束,采用ddqn与候选缓存相结合以保持在线可行性。xiong、ding、ding等人以及xiong、guo、peng等人分别通过候选位置图与transformer融合,实现从仿真到真实环境的稳健迁移。mu、kan、jiang等人把3d视觉定位、掩码注意力和边界点启发式整合进混合码垛平台,验证在rs/cut1/cut2数据集上的通用性。wong、tsai和ou等人和yang、song、chu等人系统分析物理规则、装卸启发式与ppo/drl的融合方式,说明规则知识可在奖励、动作和候选层面协助策略学习。刘胜、沈大勇、商秀芹等人表明多层树表示与对决网络评估能够缓解大动作空间带来的探索瓶颈。zhao、li和lin等人以及yin、chen和he等人从多模态编码、pointer network排序到双阶段双向放置策略,展示了在稀疏奖励与大动作空间下保持训练稳定性的多种神经体系。jiang、cao和zhang等人通过序列-姿态-位置分解与约束规划迭代优化,可将同一策略扩展到百件级规模。

9、面向复杂约束与场景扩展,erbayrak、özkır和yıldırım等人首次把familyunity、重心偏差与箱数并列为多目标。liu、zhou、yang等人处理不规则物体与多约束在线码垛,说明点云粒化、候选缓存等设计可提升实际部署的健壮性。相较传统启发式,wong等与yang等的混合drl方法将物理规则嵌入奖励与动作。

10、典型基线方法简介:

11、为便于理解本发明相对于现有技术的改进之处,下面对几种典型的方法进行介绍:

12、boundary rule(边界规则在线方法),该方法由 ceschia 等人提出,是一种基于人类装箱行为设计的启发式在线基线方法。其核心思想是模仿操作人员在装载过程中的实际动作——将新到达的物品尝试与已装载物品沿边界并排放置,同时尽量保持已装载区域的规则性,避免产生碎片化空隙。算法不依赖未来物品信息,仅根据当前已装载状态和物品列表进行贪婪决策,因此可作为典型的在线启发式基线。

13、bph(优先前瞻在线启发式方法)针对在线三维集装箱装载问题,允许智能体在装箱过程中前瞻若干件物品,并从中选择下一个最优物品进行装载,具有重新排序能力。该方法适用于物品非预先已知、需实时到达实时装箱的场景,如自动化仓库货物装载。实验表明该算法在运行时间、空间利用率和箱子使用数量方面均具有竞争力,是在线三维装箱方法中的代表性基线。

14、lbp(离线三维装箱问题方法)针对给定物品集,寻求使用最少数量的三维箱子完成装载。该类方法给出了连续下界的渐近最坏性能比,并设计了在单箱填充情况下的精确算法,进一步结合近似算法构建了精确分支定界框架。计算实验表明,该方法可有效求解一定数量物品的实例,并在合理时间内求得大量实例的最优解,是离线三维装箱方法中最具代表性的经典基线。

15、cmdrl(约束掩码调制深度强化学习方法)将放置动作的可行性预测作为辅助任务,让智能体在策略学习的同时预测每个货物-空间-旋转组合的可行性掩码;随后利用该掩码在训练期间调制actor网络输出的动作概率分布,使得采样过程直接过滤几何不可行的动作,从而高效学习可行的装箱策略。该方法是在线三维装箱领域中融合约束信息与深度强化学习的代表性方法。

16、上述方法在各自的研究场景中虽取得了较为显著成效,但仍存在以下不足:

17、第一,高质量训练数据的稀缺制约了策略学习的效率与效果。难以获得大量高质量标注数据,而随机生成的数据往往缺乏几何合理性,无法为策略学习提供有效的专家演示。现有方法多依赖真实数据或简单的随机生成数据,缺乏系统性的数据生成策略,导致训练效率与质量较低。

18、第二,容器空间的动态管理质量与效率尚需提升。装箱过程中,空闲空间的精确表达直接影响动作候选集合的质量和策略决策的有效性。现有方法难以准确刻画容器内的复杂空间结构,缺乏系统的几何分割策略,导致更新效率低下,限制了策略对最优放置位置的探索能力。

19、第三,动作状态空间复杂度、训练策略稳定性与网络架构动态适应问题。装箱问题的动作空间涉及货物选择、空间选择和姿态选择,这三种选择的组合规模呈指数级增长;同时,动作空间中待选货物数量与候选空间数量随装箱进程动态变化,导致动作空间规模不确定。状态空间中待放置货物数量与空闲空间数量同样呈动态变化特征,导致网络输入规模不确定。纯强化学习方法存在探索效率低、收敛速度慢的问题,而纯监督学习方法则难以超越专家演示,缺乏泛化能力。如何设计能够自适应状态空间和动作空间大小变化的网络架构,并采用有效的混合训练策略,在保证训练稳定性的同时提升策略性能与泛化能力,是现有方法面临的重要挑战。

技术实现思路

1、本发明所要解决的技术问题是针对上述现有技术的不足,提供一种基于深度强化学习的三维装箱智能决策系统与方法,本基于深度强化学习的三维装箱智能决策系统与方法针对训练数据稀缺问题,生成空间利用率100%的理想数据集,为策略学习提供高质量的训练样本;针对动作状态空间复杂问题,通过多头联合架构降低联合决策空间复杂度,在保证训练稳定性的同时提升策略性能与泛化能力,兼顾训练效率与求解质量。

2、为实现上述技术目的,本发明采取的技术方案为:

3、一种基于深度强化学习的三维装箱智能决策方法,包括以下步骤:

4、步骤1、获取容器尺寸信息和待装载的货物集合,初始化装箱环境;

5、步骤2、基于三向分割算法生成空间利用率为100%的理想数据集,所述理想数据集包含专家轨迹;所述专家轨迹中每一决策步记录有当前步放置的货物对象、货物状态序列及空闲空间集合;

6、步骤3、构建多头联合actor-critic策略网络,所述策略网络包括双嵌入层、双路transformer编码器、统计聚合模块、特征融合模块以及多路输出层;用于对归一化后的待放置货物特征向量和空闲空间特征向量进行编码与融合,并输出货物选择概率分布、空间选择概率分布、旋转选择概率分布、几何兼容性得分以及状态价值估计;

7、步骤4、在所述理想数据集上对所述策略网络进行监督学习预训练,以专家轨迹中记录的每步专家选择为训练目标初始化策略网络参数;

8、步骤5、切换至强化学习阶段,采用actor-critic架构通过与装载环境交互持续优化策略性能,以强化学习总损失更新网络参数;

9、步骤6、利用训练后的策略网络,对待装载货物进行序列化决策,输出每一决策步的货物选择、放置空间选择与旋转姿态选择,执行货物放置操作并更新容器占用状态,直至满足终止条件。

10、作为本发明进一步改进的技术方案,所述的步骤2具体包括:

11、设置参数初值,包括概率阈值及其调整间隔和调整步长;

12、对每个样本执行以下操作:

13、(1)初始化:将空闲空间集合初始化为容器整体空间,将占用状态张量初始化为全零张量,将物体列表初始化为空列表;

14、(2)循环放置:若空闲空间集合非空,从中随机选取一个空闲空间;生成随机数;对长度、宽度、高度三个维度分别计算物体生成尺寸,将三个维度的尺寸组合为当前货物;若当前货物可放置于当前空闲空间,则在占用状态张量中更新相应体素的占用标记,将当前货物加入物体列表,将当前空闲空间从空闲空间集合中移除,并将三向分割后经最大可用区域扩展得到的新子空间加入空闲空间集合;

15、(3)体积校验:循环放置结束后,若物体列表中所有物体的体积之和等于容器体积,则将该样本对应的物体序列与空闲空间集合加入数据集;否则丢弃该样本;

16、所述三向分割为:当货物被放置于当前空闲空间后,若当前空闲空间在长度方向上的剩余尺寸大于货物的长度,则沿长度方向正向在货物右侧生成一个新子空间;若当前空闲空间在宽度方向上的剩余尺寸大于货物的宽度,则沿宽度方向正向在货物前方生成一个新子空间;若当前空闲空间在高度方向上的剩余尺寸大于货物的高度,则沿高度方向正向在货物上方生成一个新子空间。

17、作为本发明进一步改进的技术方案,所述对长度、宽度、高度三个维度分别计算物体生成尺寸,具体为:

18、对于每个维度,若空闲空间在该维度的尺寸不小于两倍的预设最小尺寸,且均匀随机变量大于概率阈值,则在预设最小尺寸与第一数值之间均匀随机取值作为该维度生成尺寸;否则取第二数值作为该维度生成尺寸;

19、所述第一数值为空闲空间在该维度的尺寸减去该维度的预设最小尺寸后的值与预设最大尺寸之间的较小值,所述第二数值为空闲空间在该维度的尺寸与该维度的预设最大尺寸之间的较小值。

20、作为本发明进一步改进的技术方案,所述步骤3中:

21、所述双嵌入层包括物体嵌入层和空间嵌入层,所述物体嵌入层输入为待放置物体的归一化特征向量,所述空间嵌入层输入为归一化的空闲空间特征向量;

22、所述双路transformer编码器分别对双嵌入层输出的货物序列和空间序列进一步提取序列内依赖关系;

23、所述统计聚合模块对双路transformer编码器输出的变长序列计算各有效位置的均值、最大值与标准差并拼接压缩,分别得到货物聚合特征和空间聚合特征,并将货物聚合特征和空间聚合特征沿通道维度拼接为上下文向量;

24、所述特征融合模块输入为货物聚合特征与空间聚合特征拼接后的上下文向量,经一层全连接网络进行非线性变换,输出融合特征,用于捕获物体与空间之间的全局交互关系;

25、所述多路输出层包括物体选择头、空间选择头、旋转选择头、兼容性判断mlp及critic头;

26、所述物体选择头输入为物体编码向量与上下文向量的拼接,经线性变换输出物体选择logits,经softmax归一化得到物体选择概率;

27、所述空间选择头输入为空间编码向量与上下文向量的拼接,输出空间选择logits与空间选择概率;

28、所述旋转选择头输入为融合特征,经线性变换输出旋转选择logits与旋转选择概率;

29、所述兼容性判断mlp输入为所有物体编码向量、所有空间编码向量与上下文向量的拼接,经线性变换和tanh激活输出兼容性得分;

30、所述critic头输入为上下文向量,输出状态价值估计。

31、作为本发明进一步改进的技术方案,所述步骤4中监督学习预训练的损失函数为奖励正则化权重超参数乘以奖励正则化项得到的结果与交叉熵损失之和;

32、交叉熵损失为:

33、

34、奖励正则化项为:

35、

36、其中,为单回合最大决策步数,t表示决策步序号;为物体选择头输出的第步货物选择概率分布向量,为空间选择头输出的步空间选择概率分布向量,为旋转选择头输出的步的旋转选择概率分布向量;为第步的专家选择的货物选择索引,为第步的专家选择的空间选择索引,为第步的专家选择的旋转姿态索引;,为第步的即时奖励,为当前批次奖励的均值,为当前批次奖励的标准差。

37、作为本发明进一步改进的技术方案,所述步骤5中:

38、所述的actor-critic架构中:

39、记折扣因子为,折扣累积回报为,由critic头输出的状态价值函数为;

40、则优势函数定义为;

41、actor损失采用策略梯度形式:

42、

43、critic损失采用均方误差:

44、,

45、强化学习总损失为:

46、;

47、其中,t表示决策步序号,t为单回合最大决策步数,为第t+k步获得的即时奖励,为第t步的状态, 为第t步的联合采样归一化修正项。

48、作为本发明进一步改进的技术方案,所述方法还包括基于角点的最大空间延伸管理方法对装载过程中的可用空间进行动态维护:

49、每个空闲空间通过其左下后角点坐标唯一标识;

50、当货物占用空闲空间后,分别沿高度方向、长度方向和宽度方向三个方向生成新的角点位置并计算对应的最大可用空间尺寸;

51、允许新生成的空间在体积上存在部分重叠,仅在空闲空间集合中存在严格子集关系时执行去重,即:

52、;

53、其中,与分别两个空闲空间区域;分别为的角点在 轴上的坐标,分别为的长度、宽度、高度;分别为的角点在轴上的坐标,分别为的长度、宽度、高度; 表示左闭右开的空间区间;为逻辑与运算符;且仅当在长度、宽度、高度三个方向上的区间均被对应区间包含时,是的严格子集,此时应将从空闲空间集合中剔除以完成去重。

54、作为本发明进一步改进的技术方案,所述步骤6中的序列化决策采用分布式联合采样机制输出货物选择、放置空间选择和旋转姿态选择:

55、在每个决策步,遍历所有货物、空间、旋转的组合并通过几何可行性判断函数逐一检验每种组合是否满足几何约束,将可行组合纳入候选集合;

56、对每个可行组合计算联合得分,将候选集合中所有可行组合的联合得分归一化为概率分布,随后从概率分布中抽取一个组合作为本步动作;

57、所述几何可行性判断的检验结果被缓存,当后续决策步遇到相同货物、空间、旋转的组合时复用缓存的检验结果;

58、若当前状态下所有组合均不可行,则退化为三个独立的分类分布采样。

59、作为本发明进一步改进的技术方案,所述步骤5中即时奖励函数为体积比例奖励、局部利用率奖励、底部优先奖励和货物选择奖励之和,所述货物选择奖励在窗口选择模式下生效。

60、为实现上述技术目的,本发明采取的另一个技术方案为:

61、一种基于深度强化学习的三维装箱智能决策系统,包括:

62、输入与初始化模块,用于获取容器尺寸信息和待装载货物集合,并初始化装箱环境;

63、数据生成模块,用于基于三向分割算法生成空间利用率为100%的理想数据集;

64、策略网络模块,采用多头联合actor-critic策略网络;

65、训练模块,用于先在所述理想数据集上对策略网络进行监督学习预训练,再切换至强化学习阶段对策略网络进行进一步训练优化;

66、决策执行模块,用于利用训练后的策略网络对待装载货物进行序列化决策并执行货物放置操作。

67、本发明的有益效果为:

68、第一,本发明设计了基于三向分割的高质量理想数据集生成方法。该方法通过精确的几何分割和体积守恒约束,生成空间利用率为100%的专家演示数据,为监督学习阶段提供精确的专家标签和清晰的几何轨迹,为策略学习提供高质量的训练样本,有效解决了高质量训练数据稀缺的问题。与现有随机生成方法不同,该方法能够精确控制数据复杂度,通过概率参数调节货物尺寸分布,既保证了训练样本的质量,又为监督学习阶段提供了可靠的专家标签,有效解决了高质量训练数据稀缺的问题。

69、第二,本发明提出了基于角点的最大空间延伸管理方法。该方法通过角点坐标唯一标识空闲区域,并利用占用矩阵自底向上扩展三维空间,显著提升了空间表示的质量和动作候选集合的有效性。与传统"无重叠空间"策略不同,该方法允许新空间在体积上部分重叠,仅在集合中存在严格子集时执行去重,这一设计显著放宽了空间拓扑约束,使策略在同一位置拥有更多候选放置方案,有效解决了容器空间的动态管理质量与效率问题。

70、第三,本发明构建了多头联合策略网络架构与混合训练机制。该网络通过货物编码器、空间编码器、统计聚合模块和融合网络,实现对变长货物集合和容器空间集合的有效编码,并通过分布式联合采样机制降低状态-动作联合空间复杂度。在训练策略方面,采用监督学习与强化学习相结合的混合训练流程,通过专家演示快速初始化策略,再通过强化学习持续优化性能。在奖励函数设计方面,构建了多维度协同的奖励体系,包括体积比例奖励、局部利用率奖励、底部优先奖励和货物选择奖励,通过分段非线性函数和权重调节,有效引导策略学习高质量的装箱决策模式。这一综合设计有效解决了状态空间动态适配与有效特征提取问题、动作空间组合爆炸问题,同时兼顾了训练稳定性、训练效率和策略泛化能力。

71、综上所述,本发明在确保决策实时响应的前提下,实现了装载密度与空间利用率的协同提升,验证了框架的有效性与优越性。