[收稿日期]2020-09-27
[基金项目]2019年国家级大学创新创业训练项目“基于强化学习的AGV 路网规划研究”（201910240005）[作者简介]杜卓颖，女，满族，河北秦皇岛人，研究方向：物联网工程。 车辆调度系统流程
doi:10.3969/j.issn.1005-152X.2020.12.018
杜卓颖，李金禧，张祥来，朱
琳
（哈尔滨商业大学
网络视频编码器
管理学院，黑龙江哈尔滨
150000）
[摘
要]“货到人”拣选系统背景下，对AGV 的路径进行优化是提高拣选效率、降低运行成本的关键。首先，
针对仓储环境引入路径表概念，存储相似路径，减少重复搜索同一路径的工作；其次，针对传统Q 学习收敛速度慢及容易陷入局部最优解问题，借助模拟退火算法中的动态探索因子思想以一定概率跳出局部最优解。最后，采用栅格法建立仿真环境，将改进Q 学习算法与A*算法、传统Q 学习算法对比进行仿真实验，实验结果验证了本方法的有效性。 [关键词]仓储物流；Q 学习；“货到人”拣选系统；AGV；路径规划
[中图分类号]TP242[文献标识码]A [文章编号]1005-152X(2020)12-0088-05
AGV Path Planning of "Cargo-to-man"Picking System Based on Improved Q Learning
Du Zhuoying,Li Jinxi,Zhang Xianglai,Zhu Lin
(School of Management,Harbin University of Commerce,Harbin 150000,China)
Abstract:AVG path optimization is the key to improving efficiency and reducing operating cost of a cargo-to-man picking system.In this paper,we introduced the concept of path table into the storage environment to store similar paths,so as to eliminate repeated searches for the same paths.Next,targ
et at the slow convergence and propensity toward local optimization of the traditional Q learning process,we leveraged the dynamic exploration factor in the simulated annealing algorithm to break out of local optimization at certain probability.At the end,we used the grid method to establish the simulation environment,and compared the improved Q learning algorithm with the traditional Q learning algorithm by way of a simulation experiment,the result of which verified the effectiveness of the improved learning algorithm.
Keywords:warehousing logistics;Q learning;"cargo-to-man"picking system;AGV;path planning
1引言
目前仓储内的货物流通开始更多的使用AGV 智
能小车作为载体，随着自动化水平的提高和成本的降低，现在多数使用的是“货到人”拣选模式。在拣选过程中，系统内的拣选人有固定站位，货物通过AGV 小车等载体自动输送到拣选人面前。这种模式不仅可以提高拣选和存储的效率，还可以有效减低人工成本和劳动强度[1]。因此，本文将在以“货到人”
拣选系统为背景的仓储中进行仿真实验。
目前对单智能体的路径规划方法有很多：一是使用搜索算法，如姜涛，等[3]提出利用Dijkstra 算法提高路径规划中的定位精度问题，使机器人与障碍物之间距离最大化，使移动机器人的运动轨迹具有较高的可执行性，减少碰撞几率，实现了小型移动机器人在信号丢失情况下的自主返航；陈靖辉，等[4]基于A*算法，通过消除对称路径，减少扩展节点的方法，提高搜索效率和算法性能；二是使用启发式算法，如
-
-88
梁凯，等[5]基于蚁算法进行动态路径规划时的缺陷，提出了结合狼分配原则、局部搜索策略和两步可行域搜索策略的改进蚁算法；周驰，等[6]在标准粒子算法的基础上，结合遗传算法的交叉变异思想、变邻域搜索、动态惯性权重的寻优策略，对仓储环境叉车运动进行寻路。
随着对强化学习研究的深入，部分学者也将强化学习方法应用于路径规划中。由于Q学习的探索方式，导致Q学习算法的收敛速度并不高，算法性能较差。因此很多人对传统Q学习算法进行改进，如王健，等[7]改进传统Q学习算法探索收敛速度过低的问题，通过动态调整探索因子的探索方法，提高机器人对环境的熟知程度，提高算法收敛速度；张峰，等[8]提出基于树的经验存储结构来存储探索过程中的状态转移概率，并据此提出了基于期望经验回放的Q学习算法。该方法降低算法复杂度，实现
对环境状态转移的无偏估计，减少Q学习算法的过估计问题；赵辰豪，等[9]使用Boltzmann选择策略，通过动态调整算法对动作的选择概率，使回报值与动作被选概率呈正相关，提高学习的合理性与有效性，从而提高算法收敛速度。除此之外，遗传算法、模拟退火算法等对于解决单智能体的路径规划问题也有很好的效果。
传统Q学习存在收敛速度慢、寻路时容易陷入局部最优解的问题。对此，本文提出一种改进Q学习的强化学习算法。受文献[2]的启发，提出将类似模拟退火算法的动态调整选择策略因子的特性与Q 学习算法相结合，动态选择下一步动作，进一步提高Q学习算法的收敛速度，提高算法性能，改善传统Q 学习容易陷入局部最优的问题。仿真方面，结合“货到人”拣选系统这一实际物流场景，模拟出仓储AGV 拣货送到拣选台的流程，到了一种能够在充满货架和障碍的静态环境中使AGV路线最优的解决方法。
2“货到人”拣选系统
“货到人”拣选采用物流机器人（AGV）驼载货物到拣选人面前的方式，供人拣选。相对于传统的“人到货”拣选方式，“货到人”拣选在作业效率、成本控制、拣选正确率等方面，都具有显著的优势[10]。目前有几种主流的“货到人”拣选方案，包括多层穿梭车方案、Autostore方案、Miniload方案、旋转货架方案和类Kiva方案。从市场热度来看，随着亚马逊Kiva机器人的大规模应用，类Kiva机器人（也称为
智能仓储机器人）得到越来越多的关注和追捧[11]。该系统相较于其他的方案更加灵活，易扩展性强，高度自动化，可以极大程度地代替人工。同时项目建立交付快，非常适用于一些库存保有量大、商品订单多品种的场景。本文采用的便是类Kiva机器人方案。
3基于Q学习的AGV路径规划
强化学习是做出最佳决策的科学，Q学习算法是其中的一个分支。Q学习算法是马尔科夫决策过程的递增式动态规划算法，由状态、动作和奖励组成的三元组来对Q值进行选择更新，最终得到AGV最大限度的回报值，是通过值函数进行估计后验概率来得到预测的算法。在进行路径规划时，Q学习算法对AGV进行初始化操作，设AGV的初始状态为s，并建立矩阵R和矩阵Q分别存储AGV每步探索的即时奖励和Q值函数值。通过AGV随机选择下一步路径动作a并计算相应的Q值函数值，来进行Q值表的更新操作。在该算法下，每个Q(s,a)都有对应的一个Q值，即为得到的累计回报。最终根据得到的最大累计回报，选择相对应的AGV行走动作。
传统Q学习的主要流程如图1所示。
对于Q学习来说，最重要的一步是根据Q值函数对Q值表进行更新。Q值函数一般表示为：
Q'(s,a)=Q(s,a)+α(R(s,a)+γ*max Q'(s',a')-Q(s,a))（1）根据Q值函数计算AGV路径下一步动作所带来的可能影响，并根据选择策略选择带来最好影响的路径动作。其选择策略为：
π=arg max Q(s,a)（2）距离计算采用曼哈顿距离测算法，AGV小车只
-
-89
能上下左右运动，排除对角线行走：
c =||x 1-x 2+|
|y 1-y 2（3）
其中，
Q'为更新的Q 值函数值，s'为s 的下一时刻路径状态，α'为α的下一时刻路径动作。α为学习率，定义了Q 值更新占原Q 值的比例，
γ为折扣因子，定义未来奖励的重要程度。α和γ是Q 值函数的两个可操作数，通常认为取值0时为程度最不重要，取值1时为程度最重要。
但传统Q 学习算法具有自身的局限性，在寻路时较容易陷入局部最优解，并且当仓储内的AGV 数量增
多或者单一AGV 可选择的行走动作集合过大时，易导致整体的状态空间过大，出现Q 学习算法效率降低，学习效果不明显等问题，产生“维数灾难”。
4
基于改进Q 学习的AGV 路径规划
4.1
模拟退火算法
模拟退火算法从某一较高初始温度出发，通过
温度参数的不断降温，使算法中的解逐步趋于稳定。并在解集中以一定的概率跳出局部最优解，来寻目标函数的全局最优解。在模拟退火算法执行过程中，主要存在三个参数设定问题：温度T 、退火速度（迭代次数L ）和温度管理（降温方式）。
每求出一个新的最短路径解x'，都要计算优化目标函数f (x )的增量，
Δf =f (x')-f (x )。在寻最短路径时，若Δf <0则接受x'作为最优路径保留下来，否则以概率p 的可能来接受x 作为最优路径。其中p 为：
p =exp(-Δf/(kT ))
（4）
文献[2]提出，降火过程中降火函数的选取在一定程度上也会对算法收敛速度有很大的影响。经过大量文献分析，笔者发现在寻最短路径过程中对于同一温度下的可选路径进行“充分”搜索是相当必要的，而因此也消耗了大量的时间成本。循环次数增
加必定带来计算开销的增大。针对此问题并且结合本算例的特殊性，笔者提出使用路径表来缓解时间成本的压力。
4.2改进Q 学习算法
在模拟退火算法中，通过以一定的概率跳出当
前局部最优解的思想对于AGV 寻路优化有一定的借鉴意义。结合上述模拟退火算法的思想，对传统Q 学习的每个状态和动作的选择执行模拟退火降温过程，并将其中动作选择策略添加一个概率，使得算法能够以一定的概率跳出局部最优解。根据“货到人”拣选系统的特殊性，在动态调节因子的基础上增加一个路径表PTable ，用于存放已得到的最优路径，包括路径起点、路径终点、路径经过节点、该段路起点和终点四周的四个点的坐标信息，以及所存储节点之间的父子节点关系。该改进Q 学习算法核
人体穴位模型心算法的伪代码如下，其流程图如图2所示。
（0）扫描路径表PTable ，若起点终点存在，则直接使用；若不存在，则从（1）执行。
（1）初始化初始温度T 、终止温度T min 、退火速度q 、初始化Q (s,a )。
（2）初始化动作a ，状态s 。（3）退火T =q*T 。
（4）AGV 在状态s 时刻，选择随机动作a ，计算回报值a max 。
（5）随机产生一个（0,1）之间的随机数β。（6）判断β与概率p 进行比较，根据上述选择策略采取相应的最好动作a max 或者随机动作a 。
（7）若冷却完成，T =T min ，执行下一步；否则返回
-
-90
（2）。
（8）依据Q学习算法Q值函数（式（1））和选择策略（式（2））更新Q值表。
（9）更新路径表PTable。
图2改进Q学习算法基本流程
5仿真实验
5.1实验描述
精油与肌肤百度影音设计一个简单的方格“货到人”拣选系统环境（如图3所示），拣选环境模拟为26*26的栅格（单位：1），图中“START”和“GOAL”所在的区域分别为车辆的停车点和拣选台区域。中间部分8个2*9长方形黑区域代表货架，其余17个突起的灰填充块状区域模拟静态仓储环境多AGV相遇情况。其中货架区域底部可走车。
1020
图3仿真仓储环境图
给出5组任务，每组任务10个货物坐标点，随机给出每组任务的货架坐标和拣选台坐标点，任务逻辑为AGV从停车点出发，首先到达第一个任务货架，将货架运到拣选台，拣选完毕后将货架送回原位置，再走到下一任务货架，直至10个任务点全部走完，从拣选台返回停车点。
基于上述规则，比较在相同情况下分别采用改进Q学习和传统A*算法、传统Q学习算法时AGV 的行驶
距离长短，并且比较两种算法的寻路时间，来判断改进Q学习算法的有效性和优越性。其中，本次实验不考虑订单的任务分配问题，因此订单编号和位置均为随机，并未做归并处理。
5.2实验结果与分析
模拟退火算法中规定初始温度T=1000，终止温度T min=0.001，降温系数q=0.90。规定最大迭代次数为100000次。当迭代超过最大迭代次数时或寻到路径，本次寻路结束。在Q学习算法中，规定学习率α=0.7，折扣因子γ=0.95，奖励矩阵R如下：
R=
ì
í
î
ï
ï
100，达到目标点
-100，遇到障碍物
0，其他
给定5组路径信息（见表1），其中前三组为随机坐标点，第四组为第二组的对照组，拣选台同第二组重合，停车点为第二组停车点的相邻点，任务点坐标为部分重复点；第五组为第一组对照组，拣选台坐标为第一组相邻点，停车点坐标不同，任务点坐标与第
-
-91
一组部分相同或为相邻点。第四组、第五组用于测试路径表与改进Q 学习的配合情况。
表1
任务点坐标
组别1234
51
(6,21)(9,6)(16,6)(9,6)(11,20)2
(11,20)(10,16)(10,10)(9,21)(19,5)3
(16,5)(6,20)(10,20)(15,21)(14,11)4
(20,10)(9,21)(14,21)(19,5)(19,6)5
(19,6)(15,21)(18,21)(9,16)(20,6)6四球机
(11,16)(19,6)(21,16)(10,16)(16,5)7
(16,20)(18,5)(19,11)(8,5)(14,11)8
(20,21)(8,5)(17,5)(15,6)(20,10)9
(21,15)(8,11)(18,6)(8,16)(16,5)10
(5,11)(10,16)(20,10)(11,5)(21,20)拣选台(26,8)(25,16)(25,14)(25,16)(26,9)停车点
(5,26)(12,25)(9,25)(12,26)(19,25)
通过对比图4、图5可知，仓储环境中三种算法均能到最短路径，寻路长度误差5%以内。寻路能力基本相同。但较于A*算法和传统Q 学习算法，改进Q 学习算法收敛到最优值的速度普遍快于其他两种
算法的均值，效率最高可提高20%。由于改进Q 学习算法引进了路径表，使第四组和第五组任务点寻路的效率大大提高，且具有一定的稳定性。
图4
三种算法寻路长度对比
图5
三种算法收敛对比
6结语
本文针对“货到人”拣选系统，提出一种结合动
态探索因子和路径表的改进Q 学习算法，来改善传统Q 学习算法效率低下、容易陷入局部最优解的问
题。首先引入动态探索因子，将传统Q 学习的最优选择策略以一定的概率实现，并提出路径表的概念，一定程度上节省了探路成本。然后建立栅格环境模拟仓储，通过仿真实验，将改进Q 学习算法和传统Q 学习、A*两种算法对比，得出在“货到人”拣选背景下仓储物流机器人AGV 的拣货路径最短。通过实验，改进Q 学习算法能够到最优解，并且收敛速度优于传统A *算法和传统Q 学习算法，在一定程度上体现了该算法的高效和可用性。
[参考文献]
[1]尹军琪.“货到人”拣选技术及其应用[J].物流技术与应用,2015,20(10):137-140.
[2]季野彪，牛龙辉.基于模拟退火策略的强化学习路径规划算法[J].现代计算机,2019,(32):12-16.
[3]姜涛，王建中，施家栋.小型移动机器人自主返航路径规划方法[J].计算机工程,2015,41(1):164-168.
[4]陈靖辉，崔岩，刘兴林，等.基于改进A~*算法的移动机器人路径规划方法[J].计算机应用研究,2020,37(S1):118-119.[5]梁凯，毛剑琳.基于改进蚁算法的移动机器人动态路径规
划[J].电子测量技术,2020,43(7):56-60.
[6]周驰，董宝力.基于改进混合粒子算法的窄巷道仓储三维拣选路径规划[J].浙江理工大学学报(自然
科学版),2020,(6).[7]王健，赵亚川，赵忠英，等.基于Q(λ)-learning 的移动机器人路径规划改进探索方法[J].自动化与仪表,2019,34(11):39-41,67.
[8]张峰，钱辉，董春茹，等.随机状态下基于期望经验回放的Q 学习算法[J].深圳大学学报(理工版),2020,37(2):202-207.[9]赵辰豪，吴德伟，何晶，等.基于改进Q 学习算法的导航认知图构建[J].空军工程大学学报(自然科学版),2020,21(2):53-60.
[10]霍达，饶金海，卢宗慧，等.“货到人”拣选系统在某食品企业浮雕玻璃
自动化车间的应用[J].制造业自动化,2019,41(11):66-69.[11]任芳.“货到人”拣选方案及其创新发展[J].物流技术与应
用,2017,22(10):80-84.
寻
路长度（单位：）
寻
路时间（单位：）
三种算法寻路长度对比
三种算法寻路时间对比
A*算法
传统Q 学习算法改进Q 学习算法
A*算法
传统Q 学习算法改进Q 学习算法
前两种算法收敛均值
460440
420
400380360340320300
150140
130
120110100908070601
2
34
5
组别
1
2
34
5
组别
1s -
-92
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议