多功能室外智能移动机器人避障轨迹自动规划方法

刘学文，任兴贵，许 诺，徐定杰

(1.哈尔滨工业大学，哈尔滨 150000；2.广州华夏职业学院，广州 510935)

1 引言

多功能室外移动机器人是一种高智能机器人系统，其可以满足多种要求，如进行自主驾驶、辅助驾驶、车道分界线的快速视觉检测等功能，在智能传输导航系统、巡检清洁、智能农业以及工业自动化等领域都有着重要应用。路径规划是机器人技术的核心问题，它要求机器人能够在室外不间断实时感知周围环境，迅速进行判断，自动规划出平滑、不碰撞的可靠路径。其中，不断提高移动机器人智能导航性能的关键技术是视觉技术和智能控制技术，许多学者对此展开了大量的研究，但是效果还不是十分理想，如文献[3]提出的Bezier曲线算法，该算法规划的运行轨迹存在超调，不连续等问题，文献[4]提出的灰狼优化算法不能实时地感知周围环境到时轨迹自动规划效果较差。

为此本文研究一种多功能室外智能移动机器人避障轨迹自动规划方法，该方法在复杂的室外环境下，可快速实时地规划出最优路径，即用最短的时间和最小的耗能到达目标点位置。本文利用改进遗传算法对多个空间搜索而不会限于局部最优，简化二维路径编码，用一维路径编码融合调整的适应度函数，选择最优的适应度函数，对自适应参数进行改进，得到改进的遗传算法，提高了遗传算法运算效率，从而获取稳定性高的最短路径，提高移动机器人动态避障能力。仿真实验结果证明所提方法可以很好地解决因局部极小值而不能到达目标的问题。在室外移动机器人的避障轨迹规划过程中，发挥出快速、准确的优势。

2 避障轨迹自动规划方法设计

多功能室外智能移动机器人的传感参量-控制-避障动作物理模型架构主要由多功能室外智能移动机器人、机器人运动机构、机器人运动控制单元、机器人避障装置、避障处理单元和3个红外传感器组构成，如图1所示。

根据图1可知，利用3种红外传感器组，检测多功能室外智能移动机器人避障轨迹，按照获取的避障通知信号发送端位置，对多功能室外智能移动机器人和障碍物的相对位置进行估计，并依据其相对位置进行避障处理，以提高避障判断的准确性。

采用改进遗传算法实现多功能室外智能移动机器人避障轨迹自动规划。遗传算法可在进化过程中通过搜索由多个可行解构成的群体空间的不同区域，获取近似全局最优解。通过在遗传算法中加入自适应调整方法改进遗传算法的自适应参数，使路径规划效果更好。

图1 多功能室外智能移动机器人的传感 参量-控制-避障动作物理模型架构框图Fig.1 Physical model architecture of sensing parameter control obstacle avoidance action of multifunctional outdoor intelligent mobile robot

2.1 遗传操作算子

1) 复制算子。以随机的初始种群为起点，为群体规模，随机产生路径(=1，2，…，)，将与适配值成比例的概率作为标准进行个体挑选，方法如下：

算出个体适配值：(=1，2，…，)

算出选择复制的概率：∑

算出期望的复制数：

实际算出的复制数：期望复制数遵循四舍五入取整数。

2) 杂交算子。按照杂交概率(07左右)，进行交叉繁殖，繁殖的个体是任意复制产生的配对，经过交叉后，产生一对新个体。

3) 变异算子。变异是随意打乱群体中的基因，为避免过度成熟而丢失重要遗传信息，每个基因的变异概率在0000 9～009。变异要和杂交混合使用。但为保证下一代结构不会被破坏，变异要低概率进行。

4) 优化结果。最终的优化标准就是在坐标得到的最优路径，是通过算法不断循环最后收敛得出的最优结果。而一个循环的结束的标志是新一代群体出现。

2.2 路径编码方式

采用遗传算法进行路径规划过程中，在线计算的时间跟编码的长度与搜索空间有关。所以本文的规划方法是选择了一种将路径的二维码变成一维码的简化编码长度的方式，如图2所示。多功能室外智能移动机器人当前的位置为起点，预测的局部路径为目标点，起点和目标点之间的距离是规划路径。最优路径点序列坐标可通过路边限制区域得到，调整二维路径点序列坐标需在原地面坐标系内完成，最终得到新坐标，该过程能够使得编码长度减少。起点与目标点间连线是轴，将其划分成个相同段，一维坐标编码改进过程可以看成是简化的改进的路径的过程。

图2 简化路径编码方式示意图Fig.2 Schematic diagram of path coding mode

2.3 选择适应度函数

遗传算法的优劣主要取决于适应度调整方法，为了使多功能室外智能移动机器人可以自动规划一条最优避障路线，适应度函数的选择显得十分重要。

本文中选择的适应度函数需要既能把路径规划的必要条件用于遗传优化中又使用了最少的适应度函数项数。其中路边约束、动态避障、路径最短适应度函数，是路径规划的必要条件，3个条件的实现过程如下：

1) 路边约束适应度函数。图2所示的路径编码方式中折线方式描述的机器视觉获取的信息，可求出路边各折线方程。由于解空间范围被路边约束限定，所以要在路边约束区域中选取不同值，选取过程为：确定路两边折线与轴所有垂直直线的2个交点的轴坐标值和所有位置;基于机器人中心与大于移动机器人最高半径的路边安全距离，则可得到路中心收缩量。选定的范围(1,2)。用式(1)描述路边约束适应度函数1：

(1)

其中，路径上所有点是。当适应度为1时，则说明各路径点在路边安全距离内，否则为0。

2) 动态避障适应度函数。有个重要的约束条件就是动态避障。如果机器的视觉与激光雷达可确定障碍物个数、位置、速度等信息，则规划局部动态路径规划时，忽略机器人与障碍物运行速度的改变原因是：控制周期小于400 ms，且障碍物和机器人都可以假设均保持匀速直线运动，机器人运行速度被路径跟踪控制算法控制。机器人与障碍物的半径和要小于各点与障碍物间最小距离，这是动态规避的基本保障。

设是机器人从点到(，)所需时间，-1是从-1(-1，-1)到(，)所需时间，则存在：

=-1+-1

(2)

(3)

其中，当前机器人运行速度为，设在时刻，第个障碍物位置是(()，())，则有：

()=()+

()=()+

(4)

其中，第个障碍物的起始坐标是(()，())，第个障碍物当前运行速度在坐标系分量是、。

设在时刻，是第个障碍物与路径点(,)的距离，用式(5)表示：

(5)

则在任意路径上障碍物与点的最短距离是：

=min()

(6)

其中，=1，2，…，；=1，2，…，。组成路径点的个数为，障碍物的个数是。因此,动态避障的适度函数2是：

(7)

式中:表示起始坐标与障碍物之间的半径；表示安全半径。综合上述分析能够得出：遇到障碍物时，要想使得机器人可以成功实现避障，应该确保其同障碍物间的安全半径和低于路径各点同不同障碍物的最低距离，且该种情况下适应度是1，否则是0。

3) 路径最短适应度函数。选择路径最短的适应度函数如式(8)：

(8)

最终得到遗传算法的综合适应度函数是：

[1]Laufer,B.&P.,Nation.(1999).A Vocabulary Size Test of Controlled Productive Ability,Language Testing,16(1).33-51.

=1×2×3

(9)

式(9)的综合适应度函数，不仅能够规避三项加权求和的不稳定问题，还可以整合三项约束条件。

2.4 改进自适应参数

为了进一步优化遗传算法，本文中将自适应参数进行改进，这样就可以使用最少的运算，实现最多的路线规划，提高了路径规划效率，减少红外传感器检测机器人避障轨迹速度，进而得到最优避障轨迹。

种群最优个体适应值用表示，同一种群平均适应值用表示，从关系式=-中可得出，当局部最优和过早收敛的可能性大时，种群个体间适应值差别小，的值也小；反之则值大。种群收敛程度用平均适应值和最优适应值之间的差距描述。-也可以决定交叉概率和变异概率的参数。实际上，式(10)、式(11)的描述反映出、值是和-成反比关系的。

=(-)

(10)

=(-)

(11)

其中，、为比例系数。通常同一代的不同个体、值也不同，是为了保证优良个体得以繁殖。、值越小越能为适应值优良个体提供保障，、值大表示个体的适应值差。所以、也与变异个体适应值、交叉个体适应值′有关系。具体表达式为式(11)、式(12)：

(11)

(12)

其中，0≤,,,≤10，且为常数。基于改进遗传算法的多功能室外智能移动机器人避障轨迹自动规划流程如图3所示。

图3 基于改进遗传算法的多功能室外智能 移动机器人避障轨迹自动规划流程框图Fig.3 Flow chart of obstacle avoidance trajectory automatic planning of multifunctional outdoor intelligent mobile robot based on improved genetic algorithm

根据图3可知，基于改进遗传算法的多功能室外智能移动机器人避障轨迹自动规划流程主要通过随机初始化种群，产生第一对新个体，转化路径编码方式，选择路边约束适应度函数、动态避障适应度函数和路径最短适应度函数，改进自适应参数，通过交叉和变异操作，产生下一代种群，输出最优路径，实现多功能室外智能移动机器人避障轨迹自动规划。

3 实验结果

本文实验选择的智能移动机器人是深圳史河机器人科技有限公司生产的MR700轻型四驱移动机器人，该机器人四驱驱动搭载单悬架系统和预装Ubuntu 64位系统。选取Gazebo作为移动机器人避障轨迹仿真实验平台，具有很多传感器模型库，可实现低中速全自主行驶，实现快速视觉检测，通过传感器得到传感参量，包括温度23 ℃、外界重力9.78 m/s等参数，MR700轻型四驱移动机器人的技术参数如表1所示。

表1 移动机器人的技术参数

采用本文中方法规划机器人路径，设遗传算法和改进遗传算法的种群大小为40，初始交叉率0.6，初始交叉变异率0.4，平滑概率0.35，偏转角度期望值45°。安全裕度1.0。求得的最小值，也是安全范围和平滑条件的最短路径。具体仿真实验结果如下：

随着进化代数的增加，实验分析遗传算法以及本文中方法采用的改进遗传算法的种群平均适应值及最优个体之间的变化关系，结果用图4表示。

图4 不同算法进化代数与适应值关系曲线Fig.4 Relationship between evolutionary algebra and fitness of different algorithms

由图4可得，改进遗传算法随着进化代数的增加，平均值与最优值都在不断地变化，到进化代数达到45代以后，平均值和最优值都得到有效收敛，趋于稳定和统一，最终得到最优值。该图直观呈现了适应度值与进化代数间关系。遗传算法随着进化代数的增加，平均值与最优值在进化代数达到60代后，才得到收敛，数据才相对稳定，得到最优值。

通过对比可得出，本文方法采用的改进遗传算法，种群平均适应值及最优个体进化次数更少，更快速地得到最佳值，从而在规划路径时，更具有优势。

本文方法应用的改进遗传算法通过不断迭代优化，寻找安全平滑的最短路径结果如图5所示。

图5 优化算法与最优路径关系图Fig.5 Relationship between optimization algorithm and optimal path

从图5数据可得出，本文方法应用的改进遗传算法在迭代优化过程中，路径发生显著改变。从路径变化可得出，随着不断优化，适应值不断收敛，机器人避障轨迹逐渐清晰，到第56代时，可以非常快速且清晰地找到最优路径，完成避障，仿真实验结果表明本文中方法的避障轨迹规划效果较好。

为进一步验证本文方法的避障规划效果，与文献[3]的Bezier曲线轨迹规划方法与文献[4]的改进灰狼轨迹规划方法进行比较，设置3种情景描述移动机器人的避障所耗时间。3种方法的路径规划仿真对象为MR700轻型四驱移动机器人，均无负载，每种情景的起点与终点位置一致，温度、重力、障碍物摆放位置也相同，仿真障碍物相对位置关系如图6所示。

图6 障碍物相对位置关系示意图Fig.6 Relative position relationship of obstacles

仿真实验具体情景如下。

情景A：障碍物数量为8个，起点与目标点都在安全半径之内，障碍物与轮式机器人距离5 m。

情景B：障碍物数量为8个，起点在安全半径内，目标位置在安全半径之外，障碍物与轮式机器人距离10 m。

情景C：障碍物数量为12个，起点与目标位置均在安全半径之外，障碍物与轮式机器人距离15 m。

仿真实验结果如表2所示。

表2 移动机器人运动耗时Table 2 Comparison of time-consuming movement of mobile robots s

由表2可得，3种情境下，本文方法避障轨迹规划时间均少于其他2种方法。可以有效地提高移动机器人的作业效率。本文将路径的二维码变成一维码的简化编码长度，并通过选择适应度函数，缩短了移动机器人运动耗时，提高了多功能室外智能移动机器人避障轨迹自动规划的运算效率。

4 结论

本文研究的规划方法主要是利用改进遗传算法寻优的过程，实现多功能室外智能移动机器人避障轨迹的高质量自动规划。通过仿真实验结果得出如下结论：

1) 在设置的参数一致的情况下，本文提出的避障轨迹自动规划方法，种群平均适应值及最优个体进化次数更少，得到最优路径更快。

2) 随着本文方法应用改进遗传算法不断优化，适应值收敛，机器人在第56代时，可以快速且清晰地找到最优路径，完成避障。

3) 对比传统规划方法，本文方法所耗时间更少，更能有效地提高移动机器人的作业效率。

4) 本文提出的多功能室外智能移动机器人避障轨迹自动规划方法更具有实时性、稳定性。最优路径规划更具有避障功能，在实际的应用过程中，节省时间，提高工作效率。