ASAP: Learning Generalizable Online Bin Packing via Adaptive Selection After Proposal

📄 arXiv: 2501.17377v2 📥 PDF

作者: Han Fang, Paul Weng, Yutong Ban

分类: cs.LG, cs.AI

发布日期: 2025-01-29 (更新: 2025-06-16)

💡 一句话要点

提出ASAP框架，通过自适应选择提升在线装箱问题的泛化性和适应性。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 在线装箱问题 深度强化学习 泛化性 适应性 元学习

📋 核心要点

  1. 现有基于深度强化学习的在线装箱方法泛化性不足，难以适应新的数据分布。
  2. ASAP框架将决策分解为提议和选择两个策略，分别负责生成候选动作和选择最优动作。
  3. 结合预训练、后训练和元学习，ASAP在泛化性和适应性方面均表现出色。

📝 摘要（中文）

本文提出了一种名为ASAP的框架，用于解决在线3D装箱问题（3D-BPP）中基于深度强化学习（DRL）策略的泛化性和适应性问题。现有基于DRL的方法由于分布偏移，在新实例上的表现可能不佳，并且忽略了适应性，即快速微调策略以适应新的测试分布。ASAP将决策过程分解为提议和选择两个策略，提议策略负责提出有希望的动作，选择策略从中选择。为了有效学习这些策略，引入了一个结合预训练和后训练的训练框架，并采用元学习进行增强。在线适应过程中，仅微调选择策略以快速适应测试分布。实验表明，ASAP在离散和连续设置下的同分布和异分布实例上都表现出优异的泛化和适应能力。

🔬 方法详解

问题定义：论文旨在解决在线3D装箱问题（3D-BPP），现有基于深度强化学习（DRL）的策略在新实例上表现不佳，原因是训练数据和测试数据之间存在分布偏移。此外，现有方法忽略了适应性，即快速调整策略以适应新的测试分布的能力。

核心思路：论文的核心思路是将决策过程分解为两个策略：提议策略和选择策略。提议策略负责生成一组有希望的候选动作，而选择策略则负责从这些候选动作中选择最佳动作。这种分解降低了选择策略的搜索空间，使其更容易学习和适应新的分布。

技术框架：ASAP框架包含以下几个主要组成部分：1) 提议策略：负责生成一组有希望的候选动作。2) 选择策略：负责从提议策略生成的候选动作中选择最佳动作。3) 训练框架：结合预训练、后训练和元学习，用于训练提议策略和选择策略。在在线适应阶段，只对选择策略进行微调，以快速适应新的测试分布。

关键创新：ASAP的关键创新在于将决策过程分解为提议和选择两个策略，并采用元学习来增强泛化性和适应性。与现有方法相比，ASAP能够更好地处理分布偏移，并能够快速适应新的测试分布。

关键设计：ASAP的训练框架包括预训练和后训练两个阶段。在预训练阶段，使用大量数据训练提议策略和选择策略。在后训练阶段，使用元学习技术对选择策略进行微调，以提高其适应性。损失函数的设计旨在鼓励提议策略生成高质量的候选动作，并鼓励选择策略选择最佳动作。具体的网络结构和参数设置未知。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，ASAP在同分布和异分布实例上都表现出优异的泛化和适应能力。具体性能数据和对比基线未知，但论文强调ASAP在离散和连续设置下均有效。

🎯 应用场景

ASAP框架可应用于物流、仓储、制造业等领域，用于优化装箱方案，提高空间利用率，降低运输成本。该研究对于提升智能决策系统的泛化性和适应性具有重要意义，未来可扩展到其他在线优化问题。

📄 摘要（原文）

Recently, deep reinforcement learning (DRL) has achieved promising results in solving online 3D Bin Packing Problems (3D-BPP). However, these DRL-based policies may perform poorly on new instances due to distribution shift. Besides generalization, we also consider adaptation, completely overlooked by previous work, which aims at rapidly fine-tuning these policies to a new test distribution. To tackle both generalization and adaptation issues, we propose ASAP, which decomposes a solver's decision-making into two policies, one for proposal and one for selection. The role of the proposal policy is to suggest promising actions, which allows the selection policy to choose among them. To effectively learn these policies, we introduce a training framework that combines pre-training and post-training, enhanced by meta-learning. During online adaptation, we only fine-tune the selection policy to rapidly adapt to a test distribution. Our experiments demonstrate that ASAP exhibits excellent generalization and adaptation capabilities on in-distribution and out-of-distribution instances for both discrete and continuous setups.