Robust Out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity¶
会议: AAAI 2026
arXiv: 2601.19144
代码: 无
领域: 机器人
关键词: 网格存储, 乱序检索, 最大容量, k-bounded perturbation, 鲁棒存储, 重定位最小化
一句话总结¶
针对满载 2D 网格存储系统中检索顺序不确定的问题，提出 k-bounded perturbation 不确定性模型，证明 Θ(k) 列宽是零重定位的充要条件，并给出高效鲁棒存储求解器与贪心检索策略，当 k ≤ 0.5c 时几乎消除重定位，k 到达 c 时仍减少 50%+ 重定位。
动机¶
- 满载存储效率矛盾：高密度网格存储（如拼图式存储 PBS）中，存储密度越高，任意货物的可达性越差；满载时问题尤为严峻。
- 检索顺序不可预知：先前工作假设存储/检索顺序完全已知，但实际物流场景（末端配送中心、集装箱码头）中检索顺序在存储阶段之后才确定，甚至动态变化。
- 重定位代价高昂：当目标货物被其他货物阻挡时，需要执行重定位操作（将阻挡货物移开再放回），每次重定位都增加时间、能耗和 I/O 行占用。
- 已有零重定位方案脆弱：c ≥ 3 列时可保证已知顺序的零重定位（BaseS），但检索顺序稍有变动就失效（如 Figure 1 所示，轻微扰动即导致多次重定位）。
- 理论空白：网格存储中同时考虑顺序不确定性和满载条件的理论分析（所需列数的上下界）尚未建立。
- 实用设计指导缺乏：仓库设计者需要知道"给定网格宽度能容忍多大的检索顺序偏差"，以权衡空间利用率和操作鲁棒性。
方法详解¶
问题建模（R-StoRMR）¶
- 存储区域 W 为 r × c 网格，底部为开放侧（I/O 行），货物通过 I/O 行进出。
- n = r·c 个带标签货物按已知到达序列 A 存入，然后按 D̃ 检索，D̃ 是 D = (1,2,…,n) 的 k-bounded perturbation。
- k-bounded perturbation：序列 S̃ 是 S 的 k-bounded perturbation，当且仅当所有逆序对 (s_i, s_j) 满足 j - i ≤ k（即任意两个货物的检索顺序偏差不超过 k 位）。
- 目标：最小化重定位次数、I/O 行占用和总移动距离。
理论分析：零重定位所需列数¶
- 鲁棒邻接条件（Proposition 1）：排列 𝒜 对 D 是 k-robust 的，当且仅当每个非底行货物 d_i 都与某个至少比它早 k+1 位检索的货物 d_j 相邻。
- 上界（Theorem 2）：3k+3 列足够。将货物按标签模 (k+1) 分成 k+1 组，每组分配 3 列独立求解 StoRMR。
- 下界（Theorem 3）：2k+3 列必要。构造性证明：前 k+1 个最早检索的货物和前 k+2 个到达序列的货物都必须放底行。
- 设计指导：k/c ≤ 1/3 时可保证零重定位；k/c ≥ 1/2 时无法避免重定位。
鲁棒存储算法（RobustS）¶
核心思想：逐对填充相邻列 (L, R)，从底行向上，联合迭代 D 和 A^R，贪心寻找同时满足两个方向邻接条件的货物对。
- 列对初始化：L 底格放 A^R 中下一个未分配货物，R 底格放最小未分配货物（确保前 k+1 个货物在底行）。
- 主循环：从 D 中取下一个 D-valid 的货物 x 放 R 列；在 A^R 中找匹配的 y 放 L 列，要求 x 和 y 同时满足所有邻接条件。
- 末列处理：保留第 3（和第 4）列最后填充，利用相邻列的水平邻接增加成功率。
- load-skipping 增强：尝试 A^R 的不同起始偏移量，穷举所有可能的邻接链起点（可并行），显著提高找到鲁棒排列的成功率。
检索策略（ImpR）¶
当 k 超过理论上限、需要重定位时：
- 对目标货物 x 计算阻挡最少的检索路径 π。
- 沿 π 从外到内依次重定位 blocker b：
- 计算当前 unblocked 货物集 U（有直接 I/O 通路的货物）。
- 优先在 W 内重定位 b，选择不会阻挡 U 中货物的最近空格。
- 若 W 内无空格，将 b 移至 I/O 行暂存，x 检索后放回原位。
- 约束：每次检索完成后 I/O 行必须清空。
实验¶
在方形网格（100% 密度）上比较四种组合：BaseS+BaseR、RobustS+BaseR、BaseS+ImpR、RobustS+ImpR。每组参数 50 次随机试验。
表 1：不同 k/c 比值下的平均重定位次数（17×17 网格）¶
| k/c | BaseS+BaseR | RobustS+BaseR | BaseS+ImpR | RobustS+ImpR | 降幅 |
|---|---|---|---|---|---|
| 0.25 | ~60 | ~2 | ~40 | ~0 | ~100% |
| 0.50 | ~130 | ~15 | ~85 | ~8 | ~94% |
| 0.75 | ~190 | ~80 | ~120 | ~55 | ~71% |
| 1.00 | ~240 | ~120 | ~150 | ~90 | ~63% |
表 2：算法运行时间（秒，按网格大小）¶
| 网格大小 | RobustS 时间 | ImpR 时间 |
|---|---|---|
| 9×9 | <1 | <0.1 |
| 13×13 | ~5 | <0.5 |
| 17×17 | ~20 | <1 |
| 21×21 | ~50 | <1 |
RobustS 和 ImpR 在所有网格大小下均在 1 分钟和 1 秒内完成。
发现¶
- 当 k ≤ 0.5c 时，RobustS 几乎完全消除重定位，与 Theorem 3 的理论预测一致。
- k 增大至 c 时，RobustS+ImpR 仍比 baseline 减少 60-70% 重定位。
- I/O 行占用显著降低：ImpR 优先在 W 内重定位，RobustS 进一步减少直至 k/c ≤ 0.5 时完全消除。
- 几乎所有在 W 内重定位的货物不会被再次重定位，避免了级联重定位。
- load-skipping 增强使 RobustS 在 k 超过理论上限时仍有 80%+ 的成功率。
亮点¶
- 理论贡献扎实：首次建立满载网格存储中鲁棒零重定位所需列数的紧界 Θ(k)，上下界仅差 1.5 倍。
- 问题定义优雅：k-bounded perturbation 模型精确刻画了实际中"局部乱序"的不确定性，比完全随机更贴近现实。
- 理论与实践统一：理论界不仅是存在性证明，直接指导了 RobustS 算法设计和仓库宽度的工程选择。
- 计算效率佳：存储算法复杂度与 n 近线性，检索策略实时可用。
- 实验说服力强：覆盖多种网格大小和 k/c 比值，三个指标（重定位、I/O 占用、距离）全面优于 baseline。
局限性¶
- 方形网格假设：实验仅在方形网格上进行，非方形（r ≪ c 或 r ≫ c）场景未验证。
- RobustS 非最优：算法是贪心启发式，无法保证在 2k+3 ≤ c < 3k+3 时总能找到鲁棒排列（理论 gap 未闭合）。
- 单机器人假设：仅考虑一个机器人/操纵器顺序操作，未扩展到多机器人并行场景。
- 静态 k 值：k 在存储阶段就需固定，无法自适应调整；实际扰动分布可能非均匀。
- NP-hard 重定位子问题：ImpR 为贪心近似，无最优性保证；大规模场景下贪心选择可能非最优。
- 未考虑动态到达：假设所有货物先存储完毕再检索，不支持存取交错的在线场景。
相关工作¶
- Puzzle-Based Storage (PBS)：gue2007puzzle 等研究网格中少量空格的货物移动，但不处理完整检索序列。
- Block Relocation Problem (BRP)：stack 式存储中给定检索顺序最小化重定位（NP-hard），boge2020robust 研究了优先级不确定性（Γ 逆序对），galle2018scrp 按批次揭示检索序列。
- Multi-Agent Path Finding (MAPF)：网格中多机器人路径规划，Li et al. 2021 针对仓库场景但假设存在过道。
- 具序存储/检索：火车调度和集装箱码头中的有序出入问题，但多基于栈结构而非 2D 网格。
- 本文的 rss25 前作：已知顺序下 c ≥ 3 即可零重定位的 BaseS 算法，本文将其推广到不确定性设置。
评分¶
- 新颖性: ⭐⭐⭐⭐ k-bounded perturbation 不确定性建模新颖，Θ(k) 紧界为首创
- 实验充分度: ⭐⭐⭐⭐ 三指标×四组合×多网格大小，含消融实验
- 写作质量: ⭐⭐⭐⭐⭐ 问题定义精确，理论-算法-实验逻辑链完整清晰
- 价值: ⭐⭐⭐⭐ 理论指导仓库设计，算法可直接部署于满载存储系统