解决仓储物流中实时任务分配与长期路径规划的协同问题,提升效率并减少机器人数量。
The Combined Problem of Online Task Assignment and Lifelong Path Finding in Logistics Warehouses: Rule-Based Systems Matter
- 采用规则驱动的长期路径规划,适应严重局部拥堵环境。
- 实验显示执行时间仅为现系统83.77%,吞吐量相同下仅需60%机器人。
- 适合需要高并发、低资源消耗的智能仓储场景,如美团等大型平台。
我们研究了在线任务分配与长期路径规划的联合问题,这对物流行业至关重要。然而,现有研究或聚焦于长期路径规划(假设任务分配已知),或仅考虑离线版本(任务预先可知)。我们认为,为最大化系统吞吐量,应直接处理集成这两个组件的在线版本。为此,我们提出了该联合问题的形式化框架及其求解概念,并设计了一种基于规则的长期规划器,在实际机器人模型下表现良好,即使在严重局部拥堵环境下亦能稳定运行。在此基础上,我们自动化搜索与底层路径规划器匹配的任务分配策略。在美团(中国最大电商平台之一)仓库场景的仿真实验表明:(a) 时间效率方面,本系统所需执行时间仅为当前部署系统的83.77%,优于其他最先进算法8.09%;(b) 经济效率方面,可实现相同吞吐量仅需当前60%的机器人数量。代码与演示见 https://github.com/Fernadoo/Online-TAPF。
原文摘要 · Abstract (English)
We study the combined problem of online task assignment and lifelong path finding, which is crucial for the logistics industries. However, most literature either (1) focuses on lifelong path finding assuming a given task assigner, or (2) studies the offline version of this problem where tasks are known in advance. We argue that, to maximize the system throughput, the online version that integrates these two components should be tackled directly. To this end, we introduce a formal framework of the combined problem and its solution concept. Then, we design a rule-based lifelong planner under a practical robot model that works well even in environments with severe local congestion. Upon that, we automate the search for the task assigner with respect to the underlying path planner. Simulation experiments conducted in warehouse scenarios at Meituan, one of the largest shopping platforms in China, demonstrate that (a)in terms of time efficiency, our system requires only 83.77% of the execution time needed for the currently deployed system at Meituan, outperforming other SOTA algorithms by 8.09%; (b)in terms of economic efficiency, ours can achieve the same throughput with only 60% of the agents currently in use. The code and demos are available at https://github.com/Fernadoo/Online-TAPF.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。