智能搬运机器人重叠路径删除算法设计

孙建召，赵进超

（1.河南经贸职业学院计算机工程学院，河南 郑州 450000；2.郑州轻工业大学计算机与通信工程学院，河南 郑州 450000）

1 引言

智能型搬运机器人属于无人驾驶的自动车辆，它具有轨道或光学导向装置。依据计算机控制技术，按照给定的路线或计划的路线到达需要的地点，实现某种任务［1］。智能搬运机器人不仅要对被搬运对象进行精准识别，而且还应精确规划搬运最短路径。目前伴随着订单量的增加和配送需求的提高，已经逐渐趋向于自动化和智能化方向发展。电子商务物流是需要智能搬运机器人来执行某些配送工作的，目前较为成熟的智能机器人搬运过程都是以终点为目标的，并不能覆盖全部区域［2］。重叠路径删除是智能搬运机器人研究领域中的核心问题，它的任务就是在含有障碍物的区域内，避免智能型搬运机器人重复行走，并对全部障碍进行规避。目前相关领域大量学者对搬运机器人路径进行了研究，并取得了一定的研究成果。文献［3］提出在考虑时间窗的前提下，基于强化学习遗传蚁群算法，研究车间搬运机器人路径优化方法。采用扫描法，对初始搬运机器人数量进行求解，设置子路径节点的几何中心为虚拟节点，运用嵌入遗传算子的蚁群算法，对连接虚拟节点的最优路径进行求解，结合强化学习算法，求解子路径最优结果，通过设置目标解为基本、运输和时间惩罚成本的加权和，求出满足约束条件的最优解。该方法具有较高的优越性，但该方法的误判率较高。文献［4］提出快递机器人目标路径避障规划方法，通过建立三维运行空间模型，栅格化处理机器人运行空间，采用基本粒子群算法，结合邻近粒子信息，嵌入变异算子，使粒子全局搜索能力提高，实现快递机器人搜索最优路线。该方法能够有效避开障碍物，优化机器人目标路径，但该方法涉及较多的相似性计算，导致避障路径执行时间较长。

针对上述问题，提出了智能搬运机器人重叠路径删除算法设计。人工势场法是智能搬运机器人重叠路径删除领域中一种十分有效的算法［5］。采用人工势场法来对智能搬运机器人路径进行规划，可以将仓库周边环境信息转化成引力场和斥力场模型，找到一条从起点到终点的可行路径。并在此基础上，利用蝙蝠算法，将目标函数设置为最短路径，以此求得极限学习分类器参数最优值，通过最优分类器将智能搬运机器人错误路径排除。

2 智能搬运机器人重叠路径删除

2.1 获取智能搬运机器人最短路径

采用人工势场法，将仓库周边环境中存在的障碍物，按照智能搬运机器人的大小尺寸进行铺展。智能搬运机器人是在二维欧式空间中进行工作的［6］，假设智能搬运机器人在空间中的位置用X=[x y]T来表示，而且X方位中的引力场函数Uatt(X)在一般情况下都与智能搬运机器人的目标位置之间存在一定的关联，即：

式中：kp—增益系数，是一个正数；以式（1）为基础，利用下式给出Uatt(X)所对应的引力Fatt(X)的负梯度为：

式中：aRG—智能搬运机器人运行方向的单位向量智能搬运机器人当前到达目的地之间的路程，智能搬运机器人在这个引力的作用下，即可线性收敛到目的地［7］。利用式（3）推导出，斥力场函数表达式：

式中：ρ—智能搬运机器人与障碍物边缘之间的最小距离；η—正增益，式（3）主要是表示在距离障碍物边缘ρ0范围内，智能搬运机器人所受到来自障碍物的斥力，如果想在这个范围内使智能搬运机器人不能受到斥力的影响，η必须是大于0的任意数，(X-Xg)n= |(x-xg)n|+ |(y-yg)n|—智能搬运机器人距离目的地的具体数值，则斥力场函数的负梯度可表示为：

智能搬运机器人所受到的合力可以将其分解成两个分力之和，则：

式中：Frep1和Frep2—Frep的两个分力，它们的方向分别用aOR和aRG来表示；aOR—从物流布局中障碍物距智能搬运机器人最近点的单位向量；aRG—从智能搬运机器人到目的地的单位向量。

总势场Usum(X)表示引力场和斥力场两者之和：

通过对势场函数参数kp，η的分析来避免目标不能达到的问题。通过上述可知，只有当引力和斥力出现在相同的直线上，且朝向不同时，才能出现局部极小点［8］。智能搬运机器人、目的地和物流布局中障碍物距智能搬运机器人最近点在相同直线上，并且智能搬运机器人和障碍物分布在目标点两边。这时，智能搬运机器人所受的引力和斥力总和为：

为了避免局部极小点，通过人工势场函数参数，消除局部极小点，必须使总势场力Ftotal(X)指向目标点，即：

将式（2）和式（5）代入到式（8）中，可得：

因为kp，η>0，则有：

当ksup代表式（11）最右边的上确界，则：

通过上述分析可知，假设智能搬运机器人起点为（0，0）时，终点为（20，18），当kp=1，η=20时，智能搬运机器人在目的地附近移动，不能到达目的地；当kp=1，η=2时，则能够到达目的地。

由于智能搬运机器人在障碍物附近所受到合力方向的变化，其移动方向发生变化，导致在障碍物附近，智能型搬运机器人存在徘徊抖动的情况［9］。为此，结合两点之间直线距离最短原理，引入橡皮筋拉紧算法，获取智能搬运机器人最短路径。

2.2 搬运机器人重叠路径删除方法

针对智能搬运机器人搬运路径中存在重复路径的缺点，应用极限学习机算法来构建分类器，确定分类器参数ai、bi，为了获取更加理想的结果，需要对极限学习机算法参数进行选择，以智能搬运机器人最短路径选取准确率作为目标函数，构建数学模型：

蝙蝠算法［10］指的是在D维空间中，映射蝙蝠群体m，实现优化搜索的过程，进而获取最优解。

假设搜索空间为d维空间，第i个蝙蝠在t时刻的位置用来表示，搜索速度用来表示，利用式（14）和式（15）得到在t+1时刻智能搬运机器人的位置和速度更新公式为：

蝙蝠在整个搜索过程中，脉冲的响度和速率表达式：

式中：α和γ—常数。

采用二进制方式对极限学习机参数进行编码。由于极限学习机进行建模时，参数是十进制的，为此必须要计算出蝙蝠个体的适应度函数值，利用式（18）进行解码：

式中：minp和maxp—最小和最大的适应度函数值；l—重叠路径长度；p—十进制的任意码值；d—二进制代码值。

对极限学习分类器参数的最优选择，提高对智能搬运机器人重复路径的有效删除，利用下式给出表达式：

3 实验结果与分析

为了验证所提基于蝙蝠算法的智能搬运机器人重叠路径删除方法的综合有效性。将处理器为CPU G3200@3.00GH、内存为8GB的Windows系统作为实验环境。智能搬运机器人，如图1所示。

图1 智能搬运机器人Fig.1 Intelligent Handling Robot

选取m=50的种群数量，T=500的迭代次数，确保在整个搜索过程中，蝙蝠算法的声波响度和脉冲速率始终一致，即At+1(i)=0.25，Rt+1(i)=0.5。分别采用所提方法、文献［3］方法和文献［4］方法进行对比实验，利用3种方法进行重复路径删除操作，得到不同方法的重删率对比结果，如图2所示。

图2 不同方法的重删率对比结果Fig.2 Comparison of Deletion Rate of Different Methods

根据图2中的数据可以发现，当最大迭代次数达到500次，文献［3］方法的平均重删率为63%，文献［4］方法的平均重删率为78%，而所提方法的平均重删率为90%。由此可知，所提方法的重删率较高。因为所提方法引入橡皮筋拉紧算法，避免智能搬运机器人在障碍物附近发生徘徊抖动现象，获取智能搬运机器人最短路径，利用极限学习机算法构建分类器，通过设定目标函数为最短路径选择的正确率，利用蝙蝠算法建立数学模型并对其求解，得到分类器极限学习参数最优值，能够有效实现智能搬运机器人重叠路径删除，从而提高了所提方法的重删率。而由于文献［3］方法具有较高的误判率，文献［4］方法的路径选择数量影响相似精度，因此，两种方法都导致重删率受到不同程度的影响。综合上述分析可知，所提方法重删率最高，且优于文献［3］和文献［4］方法，具有一定的应用前景。

在此基础上，为了进一步验证所提方法的智能搬运机器人重叠路径删除执行时间，将所提方法与文献［3］方法和文献［4］方法的重叠路径删除执行时间进行对比，得到不同方法的重叠路径删除执行时间，如图3所示。

图3 不同方法的重叠路径删除执行时间对比结果Fig.3 Comparison Results of Overlapping Path Deletion Execution Time of Different Methods

根据图3中的数据可知，随着最大迭代次数的增加，不同方法的执行时间也逐渐增长。当迭代次数最大为500次时，文献［3］方法的重叠路径删除执行时间为7.3s，文献［4］方法的重叠路径删除执行时间为10.1s，而所提方法的重叠路径删除执行时间仅为4.4s。由此可知，所提方法的重叠路径删除执行时间较短。因为所提方法采用人工势场法，构造斥力场与引力场，通过人工势场函数参数，消除局部极小点，能够使智能搬运机器人快速到达目标地点，从而缩短了重叠路径删除执行时间。而文献［4］方法涉及较多的相似性计算，耗费的执行时间最高，文献［3］方法耗费的执行时间次之。

4 结束语

这里提出的智能搬运机器人重叠路径删除方法，通过对智能搬运机器人运动路径进行分析，引入人工势场函数中的参数，消除路径中的局部极小点，依据橡皮条拉紧原理，获取最短路径，将其准确度作为目标函数，并根据蝙蝠算法对其进行求解，以获取最优解分类器参数，通过分类器将智能搬运机器人重复路径进行删除。实验结果表明，所提方法能够有效降低执行时间，具有较高的重删率。