0 引言

仓储系统在电子商务高速发展的今天面临着巨大挑战，引入机器人集群代替传统人工的智能化仓储系统成为现代物流发展的必然趋势。亚马逊[1]、海康威视[2]等企业的相关研究更是带动了智能仓储的快速兴起。

智能仓储系统中的安全隐患和运行障碍，主要来自于仓储物流机器人集群之间的碰撞和死锁问题，优秀的避障方法可以极大地提升系统的可靠性和运行效率。本文利用改进Q-Learning算法进行路径规划，将交通规则和路径预约表相结合保证机器人之间无碰撞运行，在路径规划中加入协同机制，强化各机器人之间的联系，从而在保证安全运行的基础上构建一个更加灵活、高效的智能仓储系统。

1 问题分析

智能仓储系统由货架、机器人和工作台三部分组成，本文利用文献[3]的仓库模型并加以改善，该模型具有灵活、高效等特点。将结构化的仓库环境用栅格地图表示，形成22×48的二维栅格，如图1所示。将栅格地图按列，由上到下依次对栅格进行编号，以方便后续研究。

图1 智能仓储系统栅格模型 

Fig.1 Grid model of intelligent warehousing system

在智能仓储系统这样快速变换的动态环境中，由于有多个机器人和货架的存在，机器人ri在进行物流任务时所规划的路径Pi，会产生两类碰撞，一类是与货架等静态障碍物的碰撞，另一类是与系统中运行的其他机器人的碰撞。文中，直接将货架所处的栅格位子在机器人路径规划时设为不可达，以此消除机器人与货架的碰撞。机器人之间的碰撞则复杂得多，会发生两机碰撞、三机碰撞、四机碰撞等多种情况，对系统的安全造成严重的威胁。为避免机器人之间的碰撞甚至死锁的问题，本文在智能仓储系统中加入交通规则，规定每条道路都是单行道，并且道路的方向规定为围绕货架的逆时针方向，如图2所示，箭头所指方向即机器人在该道路时运行的方向。机器人根据交通规则，每一步选择上、下、左、右或者原地等待这五个动作中的一个，直至到达任务目标点。

图2 智能仓储系统交通规则设定 

Fig.2 Setting of traffic regulation forintelligent storage system

交通规则的设定，有效地限制了机器人之间碰撞甚至死锁的发生，将碰撞类型限定在十字路口碰撞和追尾碰撞之中，如图3所示。本文采用预约表的办法来解决这两种碰撞，预约表的设计将在下文提出。

图3 交通规则下的两种碰撞类型 

Fig.3 Two types of collisions under traffic regulations

根据本文需求，希望m个机器人在无碰撞完成所有任务的情况下所走的总路程最短以及系统运行的总时间（系统中最后一个完成任务的机器人运行的步数）最短。因此，可将仓储物流机器人集群协同路径规划表示为一个典型约束条件下的优化问题，其数学模型如下：

式中：表示机器人ri规划的路径长度，由机器人完成所有分配任务的步数决定；C1(Pi)与C2(Pi,Pj)分别代表机器人是否与障碍物或其他机器人碰撞，用式（4）和式（5）表示如下：

C1(Pi)={01,,otherμri(x,ywis)e=μlj(x,y)(4)

式中μri(x,y)和μlj(x,y)分别为机器人和货架所在栅格的坐标（以栅格右下角的坐标为当前栅格坐标）。

式中，Pi⋂Pj≠∅表示机器人ri和rj规划的路径在时间和空间上有交集。

2 算法思路

仓储物流机器人集群在智能仓储系统中的物流任务分析如下：在智能仓储系统中有n个未完成的订单任务T={t1,t2,…,tn}，每一个任务对应货架L={l1,l2,…,le}（e为货架个数）中的一个，将这些订单任务分为m组K=(K1,K2,…,Km)。文献[4,5,6,7,8]详细介绍了多种任务分配方法，由于本文主要研究机器人集群的路径规划问题，因此在任务分配上直接采用文献[8]的基于遗传算法的多机器人任务分配方法。m个机器人R={r1,r2,…,rm}，根据任务分配方法得到对应的一组任务，每个机器人根据自己得到订单任务的不同位置依次进行路径规划，通过上、下、左、右或者原地等待这5个动作，从当前位置一步步移动到任务对应货架，取得货物后移送到指定工作台S={s1,s2,…,sv}（v为工作台的数量）进行相应处理，依次循环直至完成所有被分到的任务。

2.1 预约表设计

针对图3所示的两类碰撞问题，系统通过查阅预约表的相关信息，对将会发生碰撞的机器人当前状态进行判定，再根据避让规则安排相关机器人进行避让。十字路口型碰撞，采用分权重的方式进行避让，权重由路径规划算法形成的机器人完成所有任务的路径长度（即机器人运行总步数）决定，路径长度越长则权重越大，在十字路口处就享有优先通过权，如果权重相同则随机选择通过。追尾型碰撞则采取先来后到的原则进行避让，后占用栅格的机器人必须等先占用该栅格的机器人离开后才能占用该栅格。预约表通过路径规划算法形成，记录机器人集群中每个机器人单独运行时的完整路径以及每一步占用栅格的情况，包含了所有机器人完成所有任务的位置、时间信息。机器人可以通过查询预约表来获取当前栅格的占用情况以及机器人权重的大小，从而决定机器人下一步动作的选择。预约表是一个以机器人数量为行数，以系统中所有机器人中运行路径最长的机器人运行的总步数为列数的矩阵，针对预约表中每个机器人规划的路径长度不同的情况，则统一采用“0”补齐，如图4所示。

图4 预约表设计  

Fig.4 Design of reservation table

2.2 改进Q-Learning算法协同路径规划

目前流行的机器人路径规划算法主要有A*算法[9]、D*算法[10]以及强化学习Q-Learning算法[11]等。A*仅适用于可控的已知环境，并且在高度动态的环境容易形成死锁；D*算法寻找全局最优的能力较差；Q-Learning算法原理简单，在线适应性强以及未知环境下拥有强大的自主学习能力，在智能控制、机器人等领域受到广泛的运用。本文采用改进的Q-Learning算法结合设计的协同机制来进行机器人集群的协同路径规划，算法结构如图5所示。

图5 算法结构  

Fig.5 Algorithm structure

在Q-Learning中，奖惩函数是判断智能机器人运行好坏的重要指标，一般的奖励函数只是在机器人到达目标时给予相应瞬时奖励R1，本文在此基础上增设向目标点靠近动作的奖励R2，其计算公式为：

式中，Δd为机器人当前状态栅格S1（坐标为(xs1,ys1)）和前一状态栅格S0（坐标为(xs0,ys0)）与终点栅格S（坐标为(xs,ys)）的直线距离的差，其公式为：

为了让机器人尽快走向终点，机器人每走一步都将得到-1的奖励值。综上，本文的奖惩函数计算公式如下：

为了防止算法陷入局部最优，增加全局寻优的能力，本文在动作选择策略上增设贪婪度参数ε，比如ε=0.9时，就说明有90%的情况智能机器人会按照表的最大值选择行为，10%的情况使用随机选行为，该策略在实际仿真中有效提高了算法寻优的最优性。

本文协同机制设定为，根据当前预约表的情况，将当前预约表中规划路径最长和最短的机器人ri,rj进行配对，根据查询预约表信息获取rj完成所有物流任务时ri正在执行的物流任务，将ri的后一个物流任务交给rj去执行，根据路径规划算法规划任务重新分配后的两个机器人的新的路径，并更新预约表。以此方法进行循环，让当前预约表中路径最短的机器人去代替路径最长的机器人完成它的下一个任务，从而弥补了任务分配的不完善，减少机器人无任务待机状态，提升协同度，最终达到缩短系统运行总时间的目的。

3 模型仿真

为验证算法有效性，将本文设计的协同路径规划算法（简称算法1）和普通的基于交通规则和预约表的Q-Learning算法（简称算法2）在图1提出的智能仓储系统中进行比较。通过硬件配置为InterⓇCoreTMi7-2600电脑上的Matlab 2017a对其进行仿真实验。仿真实验分为两部分：

1）对比相同数量机器人执行不同任务数量的情况，机器人数量为12，任务数量依次为50,100,150,200,250;

2）比较相同任务数量由不同数量机器人执行情况，任务数量设定为250，机器人数量分别设定为6,12,24。

图6为不同路劲规划算法对12个机器人完成不同数量任务所花费的系统总时间。由图6可知，在机器人数量一定时，随着任务数量的不断提高，系统运行的总时间也不断提高。相较于算法2，算法1能有效减少系统运行的总时间，这是因为算法1的协同机制弥补了原先任务分配时的不足，减少了机器人完成任务后的空闲状态，避免资源的浪费，让各机器人之间的工作量更加平衡，随着任务数量的增加，协同机制的效果也就越明显。

图6 机器人执行不同任务数量的系统时间   

Fig.6 System time of different tasks performed by robot

图7为不同路径规划算法对不同机器人完成250个任务所花费的系统总时间。由图可知，在任务数量一定的情况下，机器人的数量越多，系统运行的总时间越少。相较于算法2，算法1仍然有效地减少了系统总的运行时间。随着机器人的数量增多，系统运行时间下降的趋势逐渐变缓，这是由于机器人越多，每个机器人分到的任务就越少。从宏观上看，各机器人之间完成所分配任务的总工作量差别就逐渐缩小，即机器人之间的工作量越平衡，协同机制产生的效果也就逐渐变小。

图7 不同数量机器人执行任务的系统时间   

Fig.7 System time for exceuting tasks of different number of robots

从图6、图7中可以看出，算法1所花费的系统运行时间都呈线性，显示了算法良好的性能。

4 结语

本文创新地提出一种仓储物流机器人集群避障及协同路径规划方法，完成了如下工作：在智能仓储系统中指定交通规则并设计相应路径预约表，防止机器人之间的碰撞及系统死锁；改进Q-Learning算法的奖惩函数，增设趋近目标点的奖励，加速算法的收敛；在路径规划中设计了相应的协同机制，增加各机器人之间的联系，减少机器人无任务可做的空闲状态，从而有效降低了系统运行的总时间。