动态仓储环境下的多机器人路径规划方法

2022-03-18杨世团于宝成吴云韬

计算机应用与软件 2022年3期

杨世团于宝成，2* 吴云韬,2

1(智能机器人湖北省重点实验室湖北武汉 430205)1(武汉工程大学计算机科学与工程学院湖北武汉 430205)

0 引言

目前世界各工业国普遍把改造物流结构、降低物流成本作为企业在竞争中的重要措施[1]。为适应现代生产需要，物流正向着现代化的方向发展，智能仓储应运而生。而路径规划是现代智能仓储的关键技术。在机器人路径规划问题上，王秀红等[2]使用复杂对角线距离来作为A*算法当前点到目标点的估计距离，显著减少了A*算法搜索节点的数目。陈敏等[3]针对快速扩展随机树(RRT)算法的最近邻函数添加了角度约束，解决了差动机器人运动学约束问题。卢月品等[4]针对狭窄环境下遗传算法初代种群难以有效初始化的问题，提出了以Dijkstra算法为基准路径的种群初始化方法，并引入全局通行度和路径安全度概念，降低了算法时间复杂度，提高了获得路径的安全度。但上述方法都是针对单机器人静态地图环境的方法，而在仓储环境下由于机器人运动环境比较狭窄，随着环境中工作机器人数目的增多，各机器人对于其他工作中的机器人就是移动的障碍物，路网极易发生拥塞死锁问题。针对这一问题，Liu等[5]提出了一种基于遗传算法的离线、在线两阶段调度策略，当机器人间发生路线冲突时调用在线路径规划重新为小车规划路径，但存在反应滞后问题。刘敬一等[6]提出了基于边的时间窗模型，依据各机器人进出各边时间窗，保证不同任务间的时间窗发生重叠，但对各边的时间窗约束降低了系统的鲁棒性。程传奇等[7]提出了一种融合改进A*算法和动态窗口法的全局动态路径规划方法，可实时避障，但A*算法的计算复杂度随空间维数增加呈指数增加。王雷等[8]将全局路径规划与局部路径规划相结合，并且根据机器人与动态障碍物碰撞类型的不同，提出了相应的避碰策略，利用自适应遗传算法求解机器人动态路径规划问题。刘二辉等[9]基于相连的路径片段组成的三角形建立使路径缩短的启发式变异规则，对遗传操作的每一代最优解进行模拟退火操作，显著提升了算法动态环境下的路径寻优能力，但方法计算复杂，实时性较差。

基于以上文献，遗传算法在求解动态路径规划问题时具有较强的鲁棒性。本文着眼于仓储环境下多机器人运动的拥塞死锁以及路径规划算法的收敛速度问题，在文献[4]、文献[8]、文献[9]对遗传算法静态路径规划研究的基础上，提出了以路网实时状态表建立的小车单任务耗时模型为遗传操作评价指标，利用改进的遗传算法来搜索当前路网最优路径的方法。首先使用循环加障碍点的Dijkstra方法创建初始种群；然后在每一代种群中使用以单任务耗时模型为基础的路径评价函数进行选择、交叉等遗传操作，利用拥塞惩罚函数在迭代过程中不断剔除拥塞路径；同时增加路径合法性检查(路径是否连续)使搜索都在可行解空间内。经MATLAB仿真实验验证，本文所用方法能有效找到当前时间最优路径的同时避免了路网拥塞死锁问题，并提高了算法的收敛速度，具有较强的系统鲁棒性。

1 环境建模与问题描述

根据仓储环境的实际应用场景构建仓储机器人运动的空间模型如图1所示。主要分为三个功能区域：小车停靠区、货架区、分拣区[10]。货架和空间中的一些设备作为小车路径规划的障碍点，货架间的空白环境为小车的运动环境。我们将仓储环境离散为栅格地图，每个栅格代表空间的不同位置，使用数字标识如图2所示，相邻栅格的连线构成了小车运动的路径。同时为方便计算栅格间的距离，根据标记点的数字建立平面直角坐标系，若有地图中每行有mx个栅格，则栅格标记数字Ni与坐标点(xi,yi)的映射关系为:

图1 仓储环境模型图

图2 仓储环境栅格图

(1)

1.1 拥塞死锁问题分析

在多机器人任务执行运动过程中，由于每个栅格点同一时间之内只能有一个机器人通过，那么相对狭窄的运动环境可能会产生多种路径冲突情况如图3，这些路径冲突情况会严重影响机器人的搬运效率，针对这些路径冲突情况需要我们为搬运小车制定交通规则去处理，与现实交通规则类似，具体避让规则为：(1) 准备进入路口的小车让已在路口之中的小车先行；(2) 转弯车辆让直行车辆先行；(3) 右转车辆让左转车辆先行；(4) 同向行驶的小车后方车辆减速排队。而机器人依据上述交通规则通过上述路径冲突区域时，在此期间可能会集聚更多的机器人在此区域中，这样机器人避让过程中又产生新的冲突情况，从而导致路网中该区域长时间的阻塞甚至死锁情况的发生。

图3 几种常见的路径冲突

1.2 单任务耗时模型

结合上述的运动环境和对拥塞死锁问题的分析，我们以点到点的小车行驶时间最短为目标，结合实际小车的运动参数(行进速度、转动速度等)建立了小车点到点的任务耗时模型。首先路径的长度和转弯时间是任务耗时的重要指标，另外考虑前文对拥塞死锁问题的分析，为避免新规划小车进入拥塞区域，我们使用如图4所示的路网状态表实时记录小车占用的栅格情况，即依据小车实时返回的位置信息，当前小车所在的栅格即是被占用状态，无小车占用的栅格为空闲状态。在为小车规划路径时，若有正在执行任务的小车出现在新规划的路径栅格里，则为此新路径增加额外的阻塞惩罚值。据此单任务耗时模型的数学描述为:

图4 某时刻路网状态表及阻塞惩罚路径示例

O=Tz+Tt+WTG

(2)

式中：Tz是在路网中正常行驶需要的时间，我们以小车通过一个栅格的时间为单位，正常运行的时间即为路径长度；Tt表示小车耗费的转弯时间；WTG表示迭代过程中的第G代个体在当前路网状态下的阻塞惩罚函数值。各参数计算公式如下:

(3)

(4)

WTG=S×ΦG

(5)

式中：n为路径中的栅格点数量；(xi,yi)为路径中的第i个点的坐标；w表示小车转动的角度，小车每次转动的角度不会超过180°；S表示迭代过程中当前路网状态表下路径中包含的小车个数；Φ取常数1.001;G表示迭代过程中的当前代数。WTG随迭代次数的增加而呈指数级增加，这样无论是新规划小车的路径还是系统检测到死锁情况发生之后重新为小车规划的路径，都以避开正在执行任务的小车为目的，从而避免拥塞死锁情况的发生。

模型约束条件如下：

(1) 路网顶点数远大于小车数量；

(2) 每个栅格点只能容纳一辆小车；

(3) 每个任务只能由一辆小车完成。

2 基于单任务耗时模型的改进遗传算法

遗传算法是依据遗传学生物进化机理的计算模型，具有内在的隐并行性和更好的全局寻优能力，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工智能等领域。它是现代有关智能计算中的关键技术[11]。本文提出改进的遗传算法(improved genetic algorithm,IGA)来解决仓储调度中的拥塞问题。使用Dijkstra算法生成遗传操作对象，将搜索空间约束在可行的解空间之中；使用考虑拥塞控制的单任务耗时模型为基础的适应度函数，从而得到全局最优解。算法流程如图5所示。

图5 遗传算法流程

2.1 路径个体描述

路径个体由从起始点到目的点相连的无障碍栅格点组成，为避免出现环路，路径中每个栅格点只能出现一次，如在12×12栅格环境中栅格1到栅格29的路径个体[1,2,3,4,5,6,18,29]。而且由于起始点与终点的不同，路径个体的长度也会不同，因此在路径个体的编码上采用变长度的字符串编码。如对于12×12的栅格地图，栅格点数字最大为244，因此次使用8位定长的二进制码来表示栅格点数字,那么上例栅格1到栅格29个体的基因型为[00000001 00000010 00000011 00000100 00000101 00000110 00010010 00011101]。根据地图环境大小变化可以方便地选择不同长度的二进制字符串对路径中的栅格标记数字进行编码。

2.2 种群初始化

2.2.1生成加权地图

使用Dijkstra算法生成到目标点的路径，需要建立栅格各个顶点之间的加权地图：

步骤1设总栅格数为n,初始化n×n的矩阵，根据个顶点数字转换成的坐标填入各顶点之间的欧氏距离。

步骤3将为障碍点的顶点到其他任何顶点、其他顶点到为障碍顶点的值设为N无穷大，表示障碍点不可达。

步骤4输出当前矩阵即为路网各顶点间的加权图。

2.2.2生成初始化种群

与文献[12]完全随机的创建初始化种群不同，本文采用循环使用Dijkstra算法的方法去创建初始化种群，根据起始点纵坐标与目标点纵坐标的差值创建大小不同的种群，保证了每个个体及其后代都是潜在的最优解。而完全随机顶点构成的路径个体大部分是不合法/连续的，需要我们在算法中加入约束去选出合法/连续的路径个体，这不仅增加了算法的计算复杂度，也会对算法的收敛速度产生很大影响。为保证每条个体的差异性，每生成一条路径后将此路径的中点放入路网障碍点集合中，完成种群初始化之后再还原初始地图。具体流程如图6所示。

图6 初始化种群

2.3 适应度函数

适应度函数被用来描述种群个体的优劣，是遗传算法选择算子的操作依据，决定了个体的生存能力。本文中的最优解即完成任务耗时最短的路径。因此以前文所提的单任务耗时模型为基础的路径个体适应度函数如下：

Fi(P)=Omax-Oi

(6)

式中:Fi(P)为种群P中第i个路径个体的适应度；Omax为种群P的最大耗时；Oi为种群P第i个路径个体耗时。

2.4 选择算子

选择过程体现遗传算法适者生存的基本准则，通过遗传选择接近于最优的个体最终使算法收敛于最优解。本文采用轮盘赌法与优替劣组合选择策略，具体为：首先计算种群中各个个体适应度占整个种群适应度的比例Vi，如式(7)所示，每次叠加一个个体的比例并记录当前数值即为轮盘标记值，从小到大排列种群大小个随机数，逐个取出随机数与以第一个加入的个体的轮盘标记值对比，若小于该标记值则将该个体取出放入下一代，接下来对比下一个标记值；若大于则取第二个随机数，与该标记值对比，直到随机数小于轮盘标记值，取出轮盘标记值对应的个体。

(7)

2.5 交叉及变异

选择算子一定程度上推动种群趋于高适应度，但也会损失种群的多样性，可能导致算法最终收敛于局部最优解，发生早熟现象。因此需要进行交叉、变异操作来抑制早熟现象。交叉是父代个体之间以交叉概率Pc两两交换部分基因生成新的个体来增加种群多样性。本文使用重复点交叉方法如图7所示，具体为：从当前种群中依次取出两个个体，判断两者之间重复点的个数为m；如果随机数rand小于交叉概率Pc且重复点个数m大于0，则随机选择m个交叉点中的一个，交换父本、母本从交叉点之后的后半段。

图7 个体交叉示意图

变异操作是在选择、交叉操作的后面进行的。对于种群中的每一个个体，每次生成一个随机数rand，判断与变异概率Px的大小；如果小于Px，则随机选择该路径一点改变为该点相邻的八个点中的一个，并使用Dijkdstra算法连接变异点与原来路径，避免因变异产生中断路径。

2.6 终止条件

终止条件决定程序是否继续执行。终止条件判定种群是否已经进化成熟/或得了全局最优解且不再有进化趋势。具体为：达到最大终止代数100代；算法运行时间超过20 s；连续50代最优适应度值没有变化。满足上述条件之一即终止程序。

3 实验分析

为了验证算法的有效性，使用MATLAB做了实验仿真，构建了四个障碍点占比分别为20%、30%、40%、50%的20×20栅格地图作为实验环境，将小车理想化为一个质点，每次选取10个通路上的随机位置作为当前工作中小车所在位置，记录到路网状态表中，对地图指定目标点做路径规划实验。其中实验平台参数为：Intel core i7 8700处理器，8 GB运行内存。

3.1 实验参数

在遗传算法的基本运行参数选取上，种群规模是根据起始点和终点动态选取的，交叉概率一般取0.4～1.00，本文取0.8；变异概率一般取0.001～0.1，由于初始种群已经趋于高适应度，所以相对提高变异概率，本文取0.1。

3.2 实验思路

本文的实现目标为：(1) 得到无碰撞的小车路径；(2) 避免发生路网拥塞；(3) 加快算法收敛速度。本文的实验思路为：(1) 准备了多个路网复杂程度不同的地图来检验算法不同环境下的搜索能力；(2) 模拟常见的路径冲突情况，检验算法避免路网阻塞的能力；(3) 最后与文献[2]启发式动态搜索算法A*、文献[3]中改进的快速扩展随机(IRRT)在运算时间、最优路径长度、转弯个数等指标上做了对比实验来检验算法的性能。

3.2 实验结果分析

实验具体结果如下：由图8和表1可知分别为两种遗传算法在30%、40%、50%、60%障碍点下的路径规划结果,可以看出不同复杂程度的路网环境下都实现了预期目标，表明了本文算法在不同复杂程度路网环境下的搜索能力，具有较强的系统鲁棒性。且由于RRT算法所搜方向的随机性，本文方法相较于文献[3]中改进的RRT算法在转弯个数有明显减少。

(a) 环境1

表1 本文方法在四种环境下的具体实验结果

图9则展示了四个环境下50次实验的适应度值随迭代次数变化的情况，可以看出在障碍点较为稀疏的环境1、环境2下，算法基本在15～20代之间收敛于最优解，在障碍点较为密集的环境3、环境4下基本能在35～40代左右收敛于最优解，而且最终种群的平均适应度与最优适应度保持一致。

(a) 环境1

图10为仓储环境中两种常见路径冲突情况下的路线规划效果。黑色点模拟正在工作中的AGV小车，灰色点为新规划小车的起始点。可见不考虑路网拥塞的文献[2]中改进A*算法、文献[3]中改进RRT算法仍会将小车引向拥塞区域，而本文算法则会尽量绕过拥塞区域，避免使拥塞区域情况恶化，但在此情况下增加了路径长度。

(a) 相向冲突下的阻塞避免

最后与文献[2]启发式动态搜索算法A*、文献[3]中改进的快速扩展随机(IRRT)在各个环境下就路径长度、转弯个数、运算时间等指标进行了对比实验。表2-表5分别为四种环境下最远距离的两点进行50次重复路径规划实验的详细数据。由数据可知本文所提算法由于躲避任务中工作的小车，在最终长度上相较于改进A*算法有所损失，而且损失程度随着环境复杂程度增加而更加明显，但由于在遗传操作过程中增加了路径合法性检查和转弯控制，算法在运算速度和路径转弯控制上优势明显。