提出无需仿真、可快速优化自动化仓库布局的新方法。
Stress-Relief Annealing: Polynomial-Time Simulation-Free Layout Optimization for Automated Warehouses

- 将任务需求转化为应力场,预测交通热点
- 19分钟完成优化,吞吐量翻倍且支持更多机器人
- 适用于多种路径规划算法和不同规模仓库
我们研究自动化仓库中物理布局的优化问题,其中数百至数千台机器人协同运输包裹。以往研究表明,优化仓库布局(如货架位置)能显著提升吞吐量。然而,当前最先进的布局优化方法基于进化算法,将整个仓库视为黑箱,依赖随机突变搜索高质量布局,需大量仿真评估候选方案,样本效率极低。本文提出应力释放退火(Stress-Relief Annealing, SRA),一种多项式时间、无需仿真的布局优化算法。SRA将任务需求转换为每个顶点的应力场,可预测仓库内交通集中区域,其峰值与吞吐量上限严格相关。实验表明:(1) SRA在人类设计的仓库上提升吞吐量并增强可扩展性,使可维持的机器人数量约翻倍;(2) 在仅19分钟单核CPU时间内达到或超过进化基线性能,后者需25,000次仿真及64核机器上25小时;(3) 优化效果在不同多智能体路径规划算法、非均匀任务需求及尺寸翻倍的仓库中均具泛化能力。
原文摘要 · Abstract (English)
We study the problem of optimizing physical layouts for automated warehouses, where hundreds to thousands of robots are coordinated to transport packages. Previous works have shown that optimizing the warehouse layout (e.g., the physical location of the storage shelves) significantly improves throughput. However, state-of-the-art layout optimization approaches are based on evolutionary optimization methods, which treat the entire warehouse as a black box and rely on random mutation to search for high-quality layouts. While the optimization outcomes are promising, these methods require a massive number of simulations to evaluate candidate solutions, making them sample-inefficient. In this paper, we present Stress-Relief Annealing (SRA), a polynomial-time simulation-free layout optimization algorithm. SRA turns the task demand into a per-vertex \emph{stress field} that predicts where traffic will concentrate in the warehouse; the field's peak provably caps the throughput. Our experimental results show that (1) SRA improves both the throughput and the scalability of a human-designed warehouse, roughly doubling the number of robots it can sustain, (2) it matches or exceeds the throughput of the evolutionary baselines while taking only $19$ minutes on one CPU core, against their $25{,}000$ simulations and $25$ hours on a $64$-core machine, and (3) the gain generalizes across different Multi-Agent Path Finding algorithms, non-uniform task demands, and a warehouse with doubled dimensions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。