博文

【论文推荐】一类三维装箱问题的多智能体分层强化学习求解算法研究

已有 283 次阅读 2026-2-3 15:55 |个人分类:论文推荐|系统分类:博客资讯

编辑荐语

本期将给大家分享"一类三维装箱问题的多智能体分层强化学习求解算法研究(Research on multi-agent hierarchical reinforcement learning algorithm for solving one type of 3D bin packing problem)". 如您对本期相关内容有好的理解与建议, 欢迎评论区留言.

本文针对半在线场景下多箱体三维装箱(3D-BPP)这一复杂优化难题, 创新性地提出了多智能体分层强化学习求解框架. 研究将装箱过程中的货物选择、箱子选择与摆放位置规划三大关键决策, 建模为多智能体马尔可夫决策过程, 通过三个完全合作的智能体进行协同与分层决策, 实现了端到端的优化. 为提升算法稳定性, 文中引入值分布学习方法, 有效增强了训练过程的收敛性. 实验表明, 该算法在多种环境配置下均能显著提升空间利用率与货物装入量, 并在面对未知尺寸分布的货物时展现出优越的鲁棒性与泛化能力. 本工作不仅首次将多智能体分层强化学习系统应用于三维装箱问题, 为复杂动态场景提供了不依赖人工规则的智能求解新范式, 也对强化学习在组合优化与工业调度中的落地应用具有重要推动意义.

本文研究问题具有鲜明的工程背景与理论挑战, 所提出的多智能体分层框架设计巧妙, 在决策效率、空间利用率与算法适应性方面均取得显著突破. 推荐给从事强化学习、智能优化、物流调度、工业人工智能等相关领域的研究人员与工程师阅读参考.

论文介绍

一类三维装箱问题的多智能体分层强化学习求解算法研究

Research on multi-agent hierarchical reinforcement learning algorithm for solving one type of 3D bin packing problem

初阳1,2, 燕雪峰1,3, 张玄烨4, 徐云雯4, 李德伟4†

机构: 1. 南京航空航天大学计算机科学与技术学院; 2. 江苏自动化研究所; 3. 中国南京软件新技术与产业化协同创新中心; 4. 上海交通大学自动化系.

引用: 初阳, 燕雪峰, 张玄烨, 等. 一类三维装箱问题的多智能体分层强化学习求解算法研究. 控制理论与应用, 2025, 42(12): 2569 – 2576

DOI: 10.7641/CTA.2025.50058

全文链接:

http://jcta.alljournals.ac.cn/cta_cn/ch/reader/view_abstract.aspx?file_no=CCTA250058&flag=1

摘要

针对半在线场景下的多箱体三维装箱问题(3D-BPP), 为了提高装箱决策效率和装箱空间利用率, 本文提出一种多智能体分层强化学习算法. 该算法采用多智能体马尔可夫决策过程(MAMDP)对问题进行建模, 通过3个完全合作的智能体分别负责货物选择、箱子选择和摆放位置规划, 并引入值分布学习方法以增强算法的稳定性和收敛性. 实验结果表明, 该算法在不同环境配置下均表现出良好的性能, 空间利用率和装入货物数量显著提升, 且在多箱体和多货物选择场景下展现出较强的泛化能力. 与传统的启发式算法相比, 该算法在动态决策和适应性方面具有明显优势, 尤其在处理未知分布的货物尺寸时表现出较强的鲁棒性. 该算法首次将多智能体分层强化学习框架应用于3D-BPP, 实现装箱决策的端到端优化, 为复杂装箱场景提供了一种新颖的解决方案.

引言

随着电商与制造业的快速发展, 如何高效地利用有限的资源成为了现代化工业和商业领域中的关键问题. 三维装箱问题(3D bin packing problem, 3D-BPP)作为一种典型的组合优化问题, 其研究成果直接影响到自动化仓储系统, 智能物流配送和运输优化等核心技术环节. 在一般化的装箱场景下, 货物按照某个预设顺序依次到达, 装箱系统可以预览序列中接下来的若干货物, 从中选择货物并与多个箱子进行匹配, 执行器(通常是机械臂或吊具等)将选中货物放入箱子中的合适位置. 这种场景也被称为多箱体的半在线装箱问题, 其中涉及货物装载顺序规划、箱子选择、位置规划多个决策环节. 装箱任务的目标是在最大化空间利用率的同时, 尽量减少所需箱子的数. 由于3D-BPP属于NP难问题, 寻找全局最优解通常需要付出极高的计算代价, 因此如何高效解决3D-BPP是一个既具有理论价值又具有实践意义的问题.

对于三维装箱问题中的不同决策环节, 传统的解决方案是启发式算法, 研究者们主要关注的是位置规划阶段. 针对这一问题, Tresca等人[1]用物体依次形成平面或块来模仿人工装箱, Liu等人[2]和Tseremoglou等人[3]分别使用了角点与极点的候选摆放位置, 结合剪枝搜索策略降低解空间的复杂度. 文献[4]采用根据实际业务场景设计的多指标加权和作为指标, 针对货物装载顺序规划需要在装箱前或装箱时对货物进行排序解决装载顺序的问题. 此外, 研究者也设计了基于适应值的箱子选择方法, 根据各箱子当前空间占有情况以及物体体积计算出物体相对于箱子的适应值从而排序选取[5]. 对于与业务相关的相关约束, 沈倪等人[6]针对考虑温层和冷媒装载约束的冷链商品多箱型装箱问题提出了一种融合启发式算法, 李潇[7]在其提出的3D-BPP算法中重点关注了与机器人实现相关的装箱约束. 而在包含人类参与的装箱任务中, 徐翔斌等人[8]将最大空间法与有偏随机密钥遗传算法结合, 在不增加装箱成本的前提下提高了装卸工的作业姿势舒适度. 启发式算法的实现难度不高, 在预设规则引导下的装箱决策行为也具有一定的可解释性, 但随着问题规模的扩大, 在给定求解时间的限制下算法性能退化严重. 同时, 启发式算法的设计也高度依赖人类专家的领域知识, 因此, 针对特定场景设计新的启发式装箱求解算法是一项困难的任务.

随着深度学习技术的快速发展, 研究者们将装箱问题的求解建模为一个马尔可夫决策过程, 利用深度强化学习解决了单箱子的在线装箱中的位置规划问题. 例如, 采用鸟瞰图的方式表示箱子内部的状态, 利用卷积神经网络提取特征[9]; 赵航等人[10]提出一种树状结构的状态表示方法, 利用强化学习引导启发式算法的搜索过程, 极大缩小了决策空间, 并取得了较好的性能. 利用深度强化学习求解装箱问题时, 研究者们重点关注如何学习到更好的物品摆放策略, 然而在多箱体选择和预览货物选择等决策环节仍以预设规则为主, 这导致了算法对专家经验仍有一定程度的依赖, 且算法性能指标仍具有提升空间. 因此, 针对三维装箱问题中的箱体选择和预览货物选择等其他决策环节, 设计统一的数据驱动学习算法具有重要的理论与实践意义.

针对一种多箱体的半在线装箱问题, 为了摆脱其问题求解对人类经验的依赖, 提高装箱算法的性能, 本文提出一种多智能体分层决策的深度强化学习算法. 该方法利用问题的多阶段特点, 将原问题建模成一个多智能体马尔可夫决策过程, 进而利用多个完全合作的智能体以分层决策方式完成一次装箱操作中的箱子选择、货物选择及摆放位置规划等任务. 在多智能体的训练阶段引入了值分布的学习方法, 增强了深度强化学习算法的稳定性和收敛性能. 论文在多种环境配置下进行实验验证, 同多种启发式算法相比, 论文所提出算法都取得了更优秀的装箱性能指标, 并且学习到的分层决策装箱策略也具备一定的泛化能力.

结论

针对涉及箱子选择和货物预览选择的多箱体半在线装箱问题, 本文提出了一种创新的多智能体分层深度强化学习框架, 合作地完成箱子选择, 货物选择及摆放位置规划等环节的决策任务. 在不同设置下的实验结果表明: 1) 装箱问题的复杂度随箱子数量和可选择货物数量的增加而提升, 多智能体的分层决策框架在多个测试场景中展现出了良好的三维装箱问题求解性能, 不仅提高了装箱空间利用率和装入货物数量, 还减少了空间利用率的方差, 显示出了一定的泛化能力和适应性; 2) 多智能体强化学习装箱算法既能端到端地进行装箱决策, 也能让神经网络与启发式规则进行协同, 以适应特定场景. 与启发式方法相比, 多智能体合作强化学习方法在动态决策和适应性优化方面都具有一定优势; 3) 多智能体强化学习的装箱算法在面对未知分布的货物尺寸时, 仍能保持较好的装箱性能, 在应对货物尺寸的多样性与货物尺寸观测噪声时具有一定的鲁棒性.

作者简介

初阳副研究员, 目前研究方向为智能系统算法;

燕雪峰教授, 目前研究方向为人工智能相关算法;

张玄烨硕士研究生, 目前研究方向为智能强化学习方法;

徐云雯副研究员, 目前研究方向为智能系统决策与优化;

李德伟教授, 目前研究方向为复杂系统建模与优化控制.

期刊介绍

《控制理论与应用》(Control Theory & Applications)是经国家科学技术部批准, 教育部主管, 由华南理工大学和中国科学院数学与系统科学研究院联合主办的全国性一级学术刊物, 1984年创刊, 月刊, 国内外公开发行. 《控制理论与应用》是中国科学引文数据库首批统计源期刊之一，中文核心期刊，入选中国精品科技期刊顶尖学术论文F5000项目，中国科协自动化学科领域高质量科技期刊目录以及中国科协百篇优秀科技论文遴选计划，2021年入选广东省高质量科技期刊建设项目，2022-2024年连续获得基金委资助（科技活动专项）。

期刊封面2.jpg 目录2.jpg