云平台环境下基于深度强化学习的物流配送路径规划研究.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.32M 资料格式：pdf 举报版权申诉

weixin_38518376-12057866-4744300845143909702.pdf-第1页.png

第1页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第2页.png

第2页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第3页.png

第3页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第4页.png

第4页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第5页.png

第5页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第6页.png

第6页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第7页.png

第7页 / 共10页

weixin_38518376-12057866-4744300845143909702.pdf-第8页.png

第8页 / 共10页

文本预览

中国科技论文在线 http://www.paper.edu.cn 云平台环境下基于深度强化学习的物流配送路径规划研究葛茂根，李岩，韩保更，张楠* （合肥工业大学机械工程学院，合肥 230009）摘要：随着现代化工业生产的发展，智能配送系统的重要性与日剧增，配送任务规模的扩大，配送单元的路径规划任务会变得非常困难，传统的基于确定性规划类算法、启发式智能搜索算法的计算复杂度会极具增加。本文摒弃此类传统算法方案，而是基于云平台的强大计算能力，结合深度学习和强化学习各自优势，引入深度强化算法对智能配送路径规划任务进行建模。在云环境系统原型下进行仿真实验，验证了本文设计实现的基于云平台和深度强化学习的智能配送系统在大规模配送场景下的工程可行性和算法有效性。关键词：智能配送系统；云平台；深度强化学习；路径规划中图分类号：TP24 Research on Logistics Distribution Path-Planning Based on DRL under the Backgroud of Cloud Computing Platform GE Maogen, LI Yan, HAN Baogeng, ZHANG Nan (School of Mechanical Engineering，Hefei University of Technology，Hefei 230009) Abstract: With the development of modern industrial production, the scale of intelligent storage is more and more large. With the development of the scale of distribution system, the path planning task of the delivery vehicle becomes very difficult. The computational complexity which is based on the deterministic programming algorithm and the heuristic intelligent search algorithm is greater. We abandon such traditional algorithm programs and model intelligent delivery tasks on the basis of the powerful computing power of cloud platform, the respective advantages of deep learning and enhanced learning, and the depth-intensive algorithms. The final simulation experiment shows that our algorithm model does very well on large-scale intelligent distribution system tasks. Key words: Intelligent distribution system; Cloud platform; Deep reinforcement learning; Path-platform 0 引言智能物流是连接供应、制造及客户的桥梁，也是搭建智能工厂的重要基石，更是工业 4.0 的核心组成部分。随着全球科技的日益进步，基于云平台的智能物料配送系统结合最新的云计算和物联网技术，国内在工业 4.0、“一带一路”等重大发展契机的推动下，发展智能物流已成为行业共识，越来越多的企业也已经或者即将投入巨资建立智能物流体系。由于物料运输工业的大规模发展，智能配送单元的大规模的广泛使用，企业业务规模增长，针对大规模智能配送单元路径规划全局动态分布的问题[1]，是无法靠单个配送单元解决，需要大规模的智能配送单元网络系统来模拟抽象和建模分析。而传统的局域网内的物料配送系统，越来越无法满足承载大规模运算的负荷，效率低，资源成本高，负载能力低。引用云作者简介：葛茂根(1979-),男,教授、硕导,主要研究方向:制造系统运行优化. E-mail: gmg302@hfut.163.com - 1 - 5 10 15 20 25 30 35

中国科技论文在线 http://www.paper.edu.cn 平台，云计算技术[2]，完美的解决了由大规模智能配送单元配送网络系统的全局动态分布问题。通过提供云端的计算和存储等基础设施服务，降低企业在物流网络信息构建、传递、存储乃至计算上的门槛；同时，根据不同行业、不同业务以及企业自身状况，定制相应的解决方案。云平台的优势资源池化，可集群控制多个智能配送系统，可承载大规模运算的负荷，效率高，成本低，负载能力高[3]。基于云平台的智能物流配送系统还处于刚起步的阶段，在云平台上的智能调度路径规划大规模的分布动态建模分析，还有很多需要改进的解决的问题。而强化学习是机器学习的一种方法，具有很好的自适应性，适应解决大规模复杂问题，本课题提出强化学习算法在基于云平台的智能配送单元网络系统具有广阔的研究意义和应用前景。 1 智能配送系统路径规划研究现状传统非云架构下，对于路径规划算法的研究已有诸多成熟的方案[4]，比如：刘国栋[5]提出一种两个阶段的动态路径规划策略，对大规模 AGV 实时规划路径，动态的生成路径，基于启发式算法完成路径优化，能够增强对实际染污的故障的鲁棒性并适应不同地图，提高 AGV 调度柔性。凌忠奇[6]对多 AGV 复杂路径长流条件下的路径规划算法，采用全局已知固定线路的集中式控制的路径规划，研究了 AGV 之间的避碰问题，提出了一种基于预判的算法，解决了系统避碰问题；研究了路径规划的核心，建立基于拓扑图的地图的数据结构。系统有效的提高了智能配送单元的运行效率。目前随着云计算技术的发展，基于云平台构建应用方案的研究成为很多应用领域热点[7]。在工业智能配送系统领域，关于云平台结合多 AGV 的智能配送系统的研究相对较少，虽然对传统非云平台环境下的多 AGV 智能配送路径规划的研究有很多，但对于如何面向大规模配送任务，基于云平台环境构建高效的智能配送路径规划算法的研究则是一个较为新颖的研究方向。随着人工智能[8]、机器学习[9]的发展，研究人员提出一种面向不确定环境的自适应学习范式，即强化学习。强化学习技术在很多系统控制和游戏决策领域的应用有了不少初步尝试，尤其是在 Deep Mind 把深度学习和强化学习相互结合，设计的深度强化学习算法，已被共认为是现代最有前景的智能系统核心技术之一[10]。本质上，路径规划可以被定义为在配送环 40 45 50 55 60 境中通过不断决策，实现从初始点到目标点的可行路径，故这些成功应用探索证明强化学习算法对于解决大规模智能配送单元路径规划问题具有很大的潜力[11]。 65 强化学习中的原始 Q-learning 算法[12]维护一个 Q-table，即 Q 值表，描述了各个状态下对应不同动作的价值。通过动作完成后的奖励不断迭代更新这张表，来完成学习过程。然而当状态过多时，这种方法会造成维度灾难。为了解决此问题，借鉴深度学习的研究成果，利用一个深度神经网络，替代这张 Q 值表，就得到了 DQN 算法（Deep Q-Network）。DQN 算法是 DRL 中最为经典的算法，本文基于 DQN 算法，分别从地图建模，回报函数，以及算法架构角度综合考虑，设计了一种面向配送路径规划任务的有效算法。 70 - 2 -

中国科技论文在线 http://www.paper.edu.cn 2 基于 DRL 的配送路径规划算法设计深度强化学习的应用关键之一是如何对问题的决策环境进行建模，本小结就配送单元所在环境进行地图建模。 2.1 配送空间地图建模 75 80 85 理想状态下，配送环境空间是一个封闭有限空间，所有的配送单元都在这个空间中进行作业。为了能够使用 DL 算法，需要首先基于这个空间抽象定义出 DL 算法中的环境，其作用是维护一份全局状态，在所有配送单元的每一步动作决策时，提供状态信息用于决策。在配送路径规划问题上，把空间人为的降维并离散化成一个二维网格，其中每一个网格单元都是一个运动的单元空间，即：配送单元的一次运动只能从网格单元移动到另一个（包括自己）网格单元，而不可以横跨网格单元。此法一般称为栅格法[13]，构建的地图称为栅格地图。栅格地图一般为二值图，1 表示空间无障碍，可以通行；0 表示空间有障碍，无法通行。和第一种方式相比，其缺点是较为简陋，现实世界的仓储空间是连续的，离散空间无法完全对应现实空间。但同时，在路径规划的研究中，该方式人为去除了整个空间中和决策关联性较低的特征，而只保留了最为核心的环境特征，用于配送单元行动决策，可以很好地在本文算法仿真实验中实现，并能够为算法在现实世界应用起到示范作用。图 1 栅格地图示意图 Fig. 1 The grid map 2.2 回报函数（Reward）设计 90 考虑配送单元在路径巡游行进的过程中，每一步行动决策的各种可能情况，统筹设计每一个情况的回报函数。下面是本文设计的回报函数，包括了靠近目标、远离目标、发生碰撞等。表 1 回报函数 Tab. 1 Table report function State 靠近目标远离目标发生碰撞到达目标 Reward 1 -1 -100 100 95 2.3 算法策略本节的多配送单元路径规划的深度强化学习算法策略可以描述如下： - 3 -

中国科技论文在线 http://www.paper.edu.cn 初始化环境等各项数据；各个配送单元各自从不同起始点出发，感知周边环境；根据学习策略，选择动作。如果是 exploration，则随机生成下一步的动作；否则是 100 exploitation，则需要配送单元根据当前状态和积累的学习经验，选择下一步动作；根据选择的动作，环境状态转移到新状态，通过回报函数的返回值得到强化信号，并更新 DQN 网络；判断配送单元是否到达目标点，若达到目标点，完成一次学习过程；若没有，更新时间步 t = t + 1，并循环(2) ~ (4)； 105 达到设定的训练迭代数，结束整个学习过程。算法流程图如下。图 2 云 DQN 实时算法流程图 Fig. 2 Cloud DQN real-time algorithm flow chart 3 仿真实验 110 本文设计了一种基于云平台的智能配送系统架构，并基于深度强化学习算法构建的配送路径规划方案。本文的实验内容和目标分为三部分：（1）在云平台环境下，实现一个云端远程通信和配送单元的云控制系统原型框架，仿真测试 DQN 路径规划算法，验证本文提出的基于云平台的智能配送系统的可行性； 115 （2）在云平台环境下，对比多种路径规划算法，并做性能做分析，验证了基于云环境下 DQN 路径规划算法的有效性。（3）在云系统原型中进行性能压力测试实验，即通过不断增加配送单元数量，提高系统负载压力，以测试系统负载能力和验证云平台的弹性计算能力。 3.1 实验环境和条件 120 地图环境 - 4 -

中国科技论文在线 http://www.paper.edu.cn 本文实验中，采用栅格法构建配送单元所在的地图环境模型，即 N * N 矩阵方阵。每一个方块单元都是环境矩阵 WS 的一个元素，环境中的障碍物用黑色方格表示，可以通过黑块的累计形成不同的复杂障碍物。存在障碍物的方块单元对应标记=1 ，反之，=0 表示自由单元，即没有障碍物。机器人模型及运动空间表征 125 本文实验中，将配送单元简化成一个和方块单元大小一致、没有任何诸如质量等物理量的对象，故无需在路径规划算法中考虑配送单元的半径，在仿真实验中，其他配送单元和环境自有的障碍物一样，都会导致所在方块单元标记状态为 1。配送单元从动作向量 a = [1, 2, 3, 4, 5]定义的动作编码进行行动，其中的数值分别表示配 130 送单元向上走、向左走、向下走、向右走和原地静止这五类动作。参数设置对于文中深度强化学习算法的一些超参数设定：折扣因子 = 0.95，学习率 = 0.3，训练次数 M = 1000。 135 云计算资源条件和配置从实验需求和成本角度综合考虑，云平台系统采用第三方云平台 CVM(Cloud Virtual Machine) 云虚拟机（4 核 CPU，4 核 GPU，8GB 内存，10M 带宽）。 3.2 仿真实验一仿真实验一的内容是在云平台环境下，仿真实现和测试 DQN 路径规划算法，具体分为两步：训练阶段和测试阶段。 140 训练阶段：训练阶段的实验环境在云平台中的训练中心，选择在一台拥有 GPU 的 CVM 上，利用 tensorflow 框架编程实现 DQN。训练开始时，配送单元从起始点尝试往目标点行 145 进，训练中心的学习算法在每一步更新整个环境的状态。算法根据策略决定是否随机选择“探索”（exploration）还是“利用学习经验”（exploitation）。如果将地图环境数据传递给深度神经网络提取环境特征，然后，根据环境特征信息得到回报值 R，并反馈到传递 Q 值更新公式用于迭代计算。每当完成一次后，将 Q 学习次数 episode 加一。根据 episode 是否达到 1000 来决定是否完成学习。测试阶段：测试开始时，配送单元从起始点尝试往目标点行进，每一步更新环境状态。算法模型根据环境状态信息直接决策下一步行动。在数次迭代后，配送单元选择出驶向目标的最优路径。 150 训练实验结果：仿真实验一的训练阶段调整配送单元数量和配送环境规模，来测试 DQN 训练收敛过程，其收敛时间数据结果见下表。 155 - 5 -

中国科技论文在线 http://www.paper.edu.cn 表 2 训练实验结果 Tab. 2 training experimental results 实验编号配送单元数量配送环境大小（N*N）收敛迭代数 1 10 100 1 2 3 4 5 6 7 8 9 10*10 20*20 30*30 10*10 20*20 30*30 10*10 20*20 30*30 402 805 1502 203 501 1008 101 303 710 160 以实验 1、4、7 为例，画出实验过程中，训练收敛曲线图。下图展示了不同规模配送单元构成的系统模型，在训练收敛过程中代价函数收敛趋势。图 3 训练收敛趋势图 Fig. 3 Figure training convergence trend 165 在上图训练收敛趋势图中，实验 1 对应曲线 1，其配送呢单元数最少，但收敛速度最慢，而随着实验 4 和实验 7 中的配送单元逐渐增多，整个系统的收敛速度也在增加。原因在于 DQN 算法是通过不断探索新情况而逐渐学习的过程，在环境规模相同时，配送单元数越少，随机探索发现新情况的概率就越低，使得智能体难以学习到环境中更多的状态知识；而随着配送单元数越多，配送单元更大概率相互相遇，可以更快地学习到更多环境状态，使得收敛速度大大提高。 170 测试结果：最终学习得到的模型保存为一个参数文件，在部署测试时被恢复到模型中。测试的一个实例如下图，展示其最优路径、各个路径节点动作表。 - 6 -

中国科技论文在线 http://www.paper.edu.cn 图 4 测试实例的路径图示 Fig. 4 Test instance path icon 上图中，在地图可视化部分，黑色方块单元代表障碍物，蓝色 S 方块单元代表配送单元起始位置，红色 E 方块代表配送单元目标位置，而连接蓝色 S 和红色 E 的灰色方块链则代表规划得到的完整行动路径。上图中的路径展示了学习算法在路径规划中的决策过程，其中每一步规划决策的行动和状态转移如下表。表 3 测试实例的路径决策过程 Tab. 3 Test instance of the path decision-making process Agent 在环境中的前驱状态（x, 行动行动编码 ID Agent 在环境中的后继状态（x, y）（4, 2）（5, 2）（6, 2）（6, 3）（6, 4）（6, 5）（6, 6）（7, 6）（8, 6）（8, 7）（8, 8）（8, 9）（8, 10） 4 4 1 1 1 1 4 4 1 1 1 1 2 y）（5, 2）（6, 2）（6, 3）（6, 4）（6, 5）（6, 6）（7, 6）（8, 6）（8, 7）（8, 8）（8, 9）（8, 10）（7, 10） 3.3 仿真实验二仿真实验二是在云平台环境下，对比多种路径规划算法，并对其性能做分析。本实验在基于栅格法构建地图上，基于相同的任务分配等上下文，同时不考虑任何其他开销。对比实验基于同一台 CVM，分别部署三种路径规划算法模型：遗传算法、蚁群算法、 DQN 算法，在系统配置相同的条件下，通过调节配送单元数量，从单位时间配送任务完成量 S 指标，对算法性能进行观测和对比。规划完成次数，可以对比反应不同的路径规划算法的效率。其计算方式如下：单位时间配送任务完成量 S 反应了整个系统效率，在相同任务分配上下文下，统计路径假设系统以 t 为周期，对每一个配送单元，统计其在周期内完成的配送任务趟次， - 7 - 175 180 185 190

中国科技论文在线那么 t 时间内所有配送单元共完成∑ 次任务，则有=∑ /。 http://www.paper.edu.cn 图 5 云路径规划算法效率对比 Fig. 5 Efficiency Comparison of Graph Cloud Path Planning Algorithm 195 上图是基于云平台环境下相同配送任务分配策略和相同环境规模（30 * 30）下，三种不同路径规划算法的效率测试结果，通过实验对比，验证了 DQN 算法在云平台环境下，面向承载大规模配送任务的多配送单元路径规划的高效能力。特别地，随着配送单元数量的增加，对比传统的规划类算法，DQN 算法的性能效果更加明显。 3.4 仿真实验三 200 仿真实验三是在云平台环境下，基于 DQN 配送路径规划，对系统进行性能压测。对于实验测试的系统资源，考虑 CPU 和网络连接数，设置性能阈值指标，通过动态加压到阈值 205 后，触发弹性资源扩充，验证了配送系统基于云平台的弹性计算能力和优势。本实验使用了三台 CVM，实验先从 1 台 CVM 开始，逐渐增加配送单元量，在维护各个配送单元连接和计算的时候，系统负载逐渐增大，CVM 资源剩余量逐渐降低，在达到阈值时，触发弹性伸缩。实验中的弹性伸缩策略被设置为“变 1”，即扩充 CVM 时，每次只扩充 1 台；回收 CVM 时，每次只回收 1 台。在一般的系统中，CPU 作为核心计算资源、网络 IO 作为网络资源，任何一个都会成为系统瓶颈。为了简化性能指标，同时考虑两者对性能的影响，通过加权得到目标资源：（1） =0.5∗+0.5∗ =/ 进一步地，定义单位资源剩余率作为性能度量指标 Performance：（2） - 8 -

分享到：

赞收藏

资料库

云平台环境下基于深度强化学习的物流配送路径规划研究.pdf

相关推荐

开发技术

热门标签

最新资料