基于多任务强化学习的堆垛机调度与库位推荐

doi:10.19678/j.issn.1000-3428.0063943

摘要/Abstract

摘要： 堆垛机调度是物流仓储自动化中的重要任务，任务中的出入库效率、货物存放等情况影响仓储系统的整体效益。传统调度方法在面对较大规模调度问题时，因处理大状态空间从而导致性能受限和收益降低。与此同时，库位优化与调度运行联系密切，但现有多数工作在处理调度问题时未能考虑到库位优化问题。为解决仓储中堆垛机调度问题，提出一种基于深度强化学习算法的近端策略优化调度方法。将调度问题视为序列决策问题，通过智能体与环境的持续交互进行自我学习，以在不断变化的环境中优化调度。针对调度中伴生的库位优化问题，提出一种基于多任务学习的调度、库位推荐联合算法，并基于调度网络构建适用于库位推荐的Actor网络，通过与Critic网络进行交互反馈，促进整体的联动和训练，从而提升整体效益。实验结果表明，与原算法模型相比，该调度方法的累计回报值指标平均提升了33.6%，所提的多任务学习的联合算法能有效地应对堆垛机调度和库位优化的应用场景，可为该类多任务问题提供可行的解决方案。

关键词: 堆垛机调度, 库位优化, 多任务学习, 深度强化学习, 近端策略优化

Abstract: Stacker scheduling is an essential task in warehousing automation.Inbound-outbound efficiency and storage situations affect overall efficiency.When handling large-scale problems, traditional scheduling methods cannot achieve performance because processing large state spaces is challenging.Meanwhile, optimization of repository location is closely related to scheduling operation, but most existing works ignore it when addressing scheduling problems.To solve the scheduling problem, this study proposes a method based on the deep reinforcement learning algorithm Proximal Policy Optimization(PPO).The method considers the warehousing scheduling a sequence decision-making problem.It conducts self-learning through continuous interaction between agent and environment, thereby optimizing the scheduling in a changing environment.A novel algorithm based on multitask learning network is proposed to address the optimization problem of repository location with scheduling tasks.Based on the scheduling network, the algorithm constructs an actor network of repository recommendations.The actor network participates in training through interactive feedback with the critic network, thereby promoting the overall benefit.The experimental results affirm the efficacy of the proposed scheduling method, as evidenced by its average increase of 33.6% in the index of cumulative reward in comparison to the original algorithm model.The proposed multitask learning network can effectively handle the scenarios of stacker scheduling and repository location optimization, thus providing a feasible solution for this type of multitask problem.

Key words: stacker scheduling, location optimization, multi-task learning, deep reinforcement learning, Proximal Policy Optimization(PPO)

中图分类号:

TP399

饶东宁, 罗南岳. 基于多任务强化学习的堆垛机调度与库位推荐[J]. 计算机工程, 2023, 49(2): 279-287,295.

RAO Dongning, LUO Nanyue. Stacker Scheduling and Repository Location Recommendation Based on Multi-Task Reinforcement Learning[J]. Computer Engineering, 2023, 49(2): 279-287,295.

http://www.ecice06.com/CN/Y2023/V49/I2/279

图/表 13

20230216182746

20230216182749

20230216182753

20230216182757

20230216182801

20230216182804

20230216182808

20230216182811

20230216182814

20230216182817

20230216182820

20230216182823

20230216182826

参考文献

[1] D'ANDREA R.Guest editorial:a revolution in the warehouse:a retrospective on kiva systems and the grand challenges ahead[J].IEEE Transactions on Automation Science and Engineering, 2012, 9(4):638-639.
[2] YUAN Z, GONG Y M.Improving the speed delivery for robotic warehouses[J].IFAC-PapersOnLine, 2016, 49(12):1164-1168.
[3] BALLESTÍN F, PÉREZ Á, QUINTANILLA S.A multistage heuristic for storage and retrieval problems in a warehouse with random storage[J].International Transactions in Operational Research, 2020, 27(3):1699-1728.
[4] 于赫年, 白桦, 李超.仓储式多AGV系统的路径规划研究及仿真[J].计算机工程与应用, 2020, 56(2):233-241. YU H N, BAI H, LI C.Research and simulation on path planning of warehouse multi-AGV system[J].Computer Engineering and Applications, 2020, 56(2):233-241.(in Chinese)
[5] 鲁建厦, 陈寿伍, 易文超, 等.跨层穿梭车仓储系统复合作业路径规划[J].计算机集成制造系统, 2021, 27(6):1799-1808. LU J S, CHEN S W, YI W C, et al.Path planning of compound operations in tier-to-tier multi-shuttle warehouse system[J].Computer Integrated Manufacturing Systems, 2021, 27(6):1799-1808.(in Chinese)
[6] SCHULMAN J, WOLSKI F, DHARIWAL P, et al.Proximal policy optimization algorithms[EB/OL].[2022-01-10].https://arxiv.org/abs/1707.06347.
[7] KONDA V R, TSITSIKLIS J N.Actor-Critic algorithms[C]//Proceedings of Advances in Neural Information Processing Systems.Cambridge, USA:MIT Press, 2000:1008-1014.
[8] KUSHMERICK N, HANKS S, WELD D S.An algorithm for probabilistic planning[J].Artificial Intelligence, 1995, 76(1/2):239-286.
[9] 饶东宁, 郭海峰, 蒋志华.基于并行概率规划的股票指数模拟[J].计算机学报, 2019, 42(6):1334-1350. RAO D N, GUO H F, JIANG Z H.Stock index simulation based on parallel probabilistic planning[J].Chinese Journal of Computers, 2019, 42(6):1334-1350.(in Chinese)
[10] CUI H, KELLER T, KHARDON R.Stochastic planning with lifted symbolic trajectory optimization[C]//Proceedings of International Conference on Automated Planning and Scheduling.Washington D.C., USA:IEEE Press, 2021:119-127.
[11] MNIH V, KAVUKCUOGLU K, SILVER D, et al.Human-level control through deep reinforcement learning[J].Nature, 2015, 518(7540):529-533.
[12] SCHULMAN J, LEVINE S, ABBEEL P, et al.Trust region policy optimization[C]//Proceedings of International Conference on Machine Learning.Washington D.C., USA:IEEE Press, 2015:1889-1897.
[13] KAHN G, VILLAFLOR A, DING B S, et al.Self-supervised deep reinforcement learning with generalized computation graphs for robot navigation[C]//Proceedings of 2018 IEEE International Conference on Robotics and Automation.Washington D.C., USA:IEEE Press, 2018:5129-5136.
[14] KIM B, PINEAU J.Socially adaptive path planning in human environments using inverse reinforcement learning[J].International Journal of Social Robotics, 2016, 8(1):51-66.
[15] WU Y X, SONG W, CAO Z G, et al.Learning improvement heuristics for solving routing problems[J].IEEE Transactions on Neural Networks and Learning Systems, 2022, 33(9):5057-5069.
[16] ZHANG C, SONG W, CAO Z G, et al.Learning to dispatch for job shop scheduling via deep reinforcement learning[C]//Proceedings of Advances in Neural Information Processing Systems.Cambridge, USA:MIT Press, 2020:1621-1632.
[17] 杨思明, 单征, 丁煜, 等.深度强化学习研究综述[J].计算机工程, 2021, 47(12):19-29. YANG S M, SHAN Z, DING Y, et al.Survey of research on deep reinforcement learning[J].Computer Engineering, 2021, 47(12):19-29.(in Chinese)
[18] DUAN Y, CHEN X, HOUTHOOFT R, et al.Benchmarking deep reinforcement learning for continuous control[C]//Proceedings of International Conference on Machine Learning.Washington D.C., USA:IEEE Press, 2016:1329-1338.
[19] MNIH V, BADIA A P, MIRZA M, et al.Asynchronous methods for deep reinforcement learning[C]//Proceedings of International conference on machine learning.Washington D.C., USA:IEEE Press, 2016:1928-1937.
[20] SCHULMAN J, MORITZ P, LEVINE S, et al.High-dimensional continuous control using generalized advantage estimation[EB/OL].[2022-01-10].https://arxiv.org/abs/1506.02438.
[21] RUDER S.An overview of multi-task learning in deep neural networks[EB/OL].[2022-01-10].https://arxiv.org/abs/1706.05098.
[22] 周伟枭, 蓝雯飞.融合文本分类的多任务学习摘要模型[J].计算机工程, 2021, 47(4):48-55. ZHOU W X, LAN W F.Summarization model using multi-task learning fused with text classification[J].Computer Engineering, 2021, 47(4):48-55.(in Chinese)
[23] KIM S, HORI T, WATANABE S.Joint CTC-attention based end-to-end speech recognition using multi-task learning[C]//Proceedings of 2017 IEEE International Conference on Acoustics, Speech and Signal Processing.Washington D.C., USA:IEEE Press, 2017:4835-4839.
[24] YU F, CHEN H F, WANG X, et al.BDD100K:a diverse driving dataset for heterogeneous multitask learning[C]//Proceedings of 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition.Washington D.C., USA:IEEE Press, 2020:2633-2642.
[25] JIANG Y, CAO Z G, ZHANG J.Learning to solve 3-D Bin packing problem via deep reinforcement learning and constraint programming[J].IEEE Transactions on Cybernetics, 2021, 22(9):1-12.
[26] IOFFE S, SZEGEDY C.Batch normalization:accelerating deep network training by reducing internal covariate shift[C]//Proceedings of the 32nd International Conference on Machine Learning.Washington D.C., USA:IEEE Press, 2015:448-456.
[27] 汤洪涛, 闫伟杰, 陈青丰, 等.自动化立体仓库货位分配与作业调度集成优化[J].计算机科学, 2020, 47(5):204-211. TANG H T, YAN W J, CHEN Q F, et al.Integrated optimization of location assignment and job scheduling in automated storage and retrieval system[J].Computer Science, 2020, 47(5):204-211.(in Chinese)

选择文件类型/文献管理软件名称

选择包含的内容