结合强化学习与启发式搜索，实现2D箱子装载的高效动态规划。
A Hierarchical Bin Packing Framework with Dual Manipulators via Heuristic Search and Deep Reinforcement Learning
- 分层架构：启发式搜索选物品与顺序，强化学习定具体位置。
- 支持重装、信息不全等场景，实测利用率接近最优。
- 适用于双机械臂协同，仿真中执行效率高，适合工业部署。
我们研究了二维箱体装载问题（2D BPP），目标是在已知所有物品尺寸的情况下最大化箱子利用率。离线问题已被证明是NP难问题，而半在线与在线版本更难，因无法提前获知全部物品信息。尽管已有方法解决2D与3D BPP，但2D BPP在完全优化利用率方面仍研究不足。本文提出一种分层框架，结合深度强化学习（RL）与启发式搜索，用于求解2D半在线与在线BPP。启发式搜索负责选择待装物品、确定装载顺序及物品朝向，而强化学习代理则决定物品在箱内的精确位置。该方法可处理多种实际场景，包括重装、不同信息完备度、不同数量可访问物品，以及双机械臂协调。实验表明，该方法在各类实际场景中均实现近似最优的装载利用率，主要得益于其重装能力。此外，算法在基于物理的仿真环境中进行了评估，通过测量执行时间来衡量其实用性能。
原文摘要 · Abstract (English)
We address the bin packing problem (BPP), which aims to maximize bin utilization when packing a variety of items. The offline problem, where the complete information about the item set and their sizes is known in advance, is proven to be NP-hard. The semi-online and online variants are even more challenging, as full information about incoming items is unavailable. While existing methods have tackled both 2D and 3D BPPs, the 2D BPP remains underexplored in terms of fully maximizing utilization. We propose a hierarchical approach for solving the 2D online and semi-online BPP by combining deep reinforcement learning (RL) with heuristic search. The heuristic search selects which item to pack or unpack, determines the packing order, and chooses the orientation of each item, while the RL agent decides the precise position within the bin. Our method is capable of handling diverse scenarios, including repacking, varying levels of item information, differing numbers of accessible items, and coordination of dual manipulators. Experimental results demonstrate that our approach achieves near-optimal utilization across various practical scenarios, largely due to its repacking capability. In addition, the algorithm is evaluated in a physics-based simulation environment, where execution time is measured to assess its real-world performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。