优化机器人分拣系统的任务分配，提升分拣效率。
Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems
- 结合进化算法与整数规划优化任务映射。
- 相比贪心策略，吞吐量提升最高达27%。
- 适合研究多机器人协同与物流系统优化者。
我们研究如何优化机器人分拣系统（RSS）中目的地到分拣口的任务映射以提升吞吐量。在实际系统中，机器人需将包裹从入料工位运送到对应目的地的分拣口（如洛杉矶或匹兹堡）。任务映射决定了机器人可投放包裹的分拣口。优化任务映射面临三大挑战：其一，任务映射与机器人目标分配、路径规划相互依赖；其二，当分拣口接收足够包裹后会关闭，以便下游处理；其三，同一目的地分布于多个分拣口会增加处理时间。本文首次形式化定义任务映射及任务映射优化（TMO）问题，并构建了RSS仿真器用于评估不同映射方案。提出基于进化算法与混合整数线性规划的简化TMO方法，在不同地图尺寸、分拣口数量和目的地数的设置下，验证了优化映射优于贪心生成映射的效果。最后，利用质量多样性算法分析多样化任务映射的吞吐表现。代码已开源：https://github.com/lunjohnzhang/tmo_public。
原文摘要 · Abstract (English)
We study optimizing a destination-to-chutes task mapping to improve throughput in Robotic Sorting Systems (RSS), where a team of robots sort packages on a sortation floor by transporting them from induct workstations to eject chutes based on their shipping destinations (e.g. Los Angeles or Pittsburgh). The destination-to-chutes task mapping is used to determine which chutes a robot can drop its package. Finding a high-quality task mapping is challenging because of the complexity of a real-world RSS. First, optimizing task mapping is interdependent with robot target assignment and path planning. Second, chutes will be CLOSED for a period of time once they receive sufficient packages to allow for downstream processing. Third, task mapping quality directly impacts the downstream processing, as scattered chutes for the same destination increase package handling time. In this paper, we first formally define task mappings and the problem of Task Mapping Optimization (TMO). We then present a simulator of RSS to evaluate task mappings. We then present a simple TMO method based on the Evolutionary Algorithm and Mixed Integer Linear Programming, demonstrating the advantage of our optimized task mappings over the greedily generated ones in various RSS setups with different map sizes, numbers of chutes, and destinations. Finally, we use Quality Diversity algorithms to analyze the throughput of a diverse set of task mappings. Our code is available online at https://github.com/lunjohnzhang/tmo_public.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。