基于改进正余弦算法的机器人路径规划

马莹莹，杜暖男

(1. 天津市机电工艺技师学院 信息传媒系，天津 300350； 2. 天津海运职业学院 信息工程系，天津 300350)

0 引 言

机器人路径规划，简称RPP，旨在决策给定起终点间的最优路径，从而使得线路长度、机器人能耗等指标达到最优[1]。近年来，智能移动机器人获得了广泛应用，业务场景包含智慧生产、货物搬运、异常环境探测等[2]。因此，开发RPP问题的决策算法意义重大。

传统RPP决策方法有视图法、自由空间法以及人工势场法等[3]。在各类实际工程场景中，以上算法逐步暴露出亟待改善的问题点。视图法所求路径棱角明显，因而所得线路难以构成全局最优；自由空间法的计算复杂度很大，难以应对复杂障碍空间的情况。近年来进化算法的发展为解决RPP问题提供了新思路，诸如遗传、蚁群等算法均在此问题上获得了成功应用，但也存在些许不足。比如：遗传算法生成线路容易包含障碍物在内，使得结果容易违反约束；基本蚁群算法的搜索时间相对过长、容易停滞。显而易见，上述缺陷使得进化算法求解RPP的效率较为低下。因此，有必要针对上述缺陷开发基于进化算法的高效RPP决策方法。

正余弦算法(sine cosine algorithm，SCA)是2016年由学者S. MIRJALILI[4]提出的一种新型进化算法。SCA算法具有架构简单、计算效率高等特点，且研究表明，SCA算法的整体搜索性能较萤火虫算法、花朵授粉算法、粒子群算法等更具优势[5]。SCA算法在众多经典优化问题上效果显著，例如图像分割、目标跟踪、电力系统调度等[6-8]。为此，笔者将该算法运用到RPP这一重要工程问题的求解。

SCA算法模拟了正余弦函数的震荡特征，据此进行迭代搜索，同时其初始化过程采用随机方法，这一定程度上限制了算法的表现性能，同时SCA的种群更新过程过度依赖于当前已知最优解，且不同解个体间缺乏强有力的信息交流，这弱化了算法后期的求解能力。为解决以上问题，笔者构建的HSCA算法采用反学习初始化方法，用于产生优质初始解；在迭代环节中，该算法以优化目标为依据进行模因分组进而构建多种群，并通过融合TLBO进化机制强化个体交流，力求增强算法的局部挖掘能力。另外，笔者将HSCA算法与Spline插值法相结合，力求在确保RPP问题路径规划精度的同时降低优化难度，从而获得高质量的平滑路径曲线。

1 机器人路径规划建模

1.1 环境模型

图1给出了RPP的示意，起终点分别以正方形和三角形表示，障碍物用圆表示。

图1 RPP示意Fig. 1 Schematic diagram of RPP

基于二维平面坐标系，每个圆可表示为：

(x-a)2+(y-b)2=r2

(1)

式中：参数(a,b)为圆中心；r为半径。

RPP要求确定一条由连接起点(x0,y0)和终点(xn+1,yn+1)的路径H={(x0,y0),(x1,y1),…,(xn,yn),(xn+1,yn+1)}，从而使得决策目标最优。其中，(x1,y1),(x2,y2),…,(xn,yn)为待优化的导航点坐标。基于以上描述可知，导航点的数目n决定了当前待优化问题的维度。同时，直接将路径点相连绘制的线路图形棱角较为明显。为此，笔者引入Spline方法构造线路[9-10]。如图2，算法所需优化的坐标点为采样导航点，而插值导航点表示通过Spline方法得到的坐标。

图2 Spline插值示意Fig. 2 Schematic diagram of spline interpolation method

1.2 路径评价函数

笔者在RPP模型以线路长度作为目标函数，在线路评价函数构建中引入惩罚函数法以解决线路避开障碍物这一约束：

(2)

(3)

式中：ω为惩罚系数，取值为正；K为障碍物总数；(ak,bk)为障碍物k的坐标中心；rk为半径；Vi,k∈[0,1]为当前线路中第i个导航点(xi,yi)与第k个障碍物间避障约束值；Vi,k=0为满足避障约束。基于此，评价函数L取值越小，线路长度越短且违反避障约束程度越小，该线路的质量越优。

2 SCA与TLBO算法

2.1 SCA算法

(4)

式中：d=1,…,D;i=1,…,N。

在表达式中，xi=(xi1,xi2,…,xiD)为第i个解的表达式，xid为xi第d维的取值，rand(0,1)为[0,1]上的随机数。

在迭代过程中，针对解xi，迭代更新公式为：

(5)

式中：g为当前迭代次数；x*为已知最好解；参数r2、r3和r4为随机量，取值范围设置为r2∈[0,2π]、r3∈[0,2]、r4∈[0,1]。控制参数r1定义为：

(6)

式中：a为常数；G为算法的最大迭代次数。

SCA算法流程为：

Step 1初始化：借助随机方法生成初始种群。

Step 2目标函数计算：计算每个解的目标函数值。

Step 3确定最优个体：将算法迭代至当前阶段所搜得的目标函数值最小个体标记为已知最优解。

Step 4更新算法参数：更新系数r1、r2、r3和r4。

Step 5更新个体位置：依据式(5)生成子代种群。

Step 5终止判断：若满足终止条件，停止迭代并输出最好解；否则转Step 2。

2.2 TLBO算法

在TLBO算法中，个体更新包括 “教学阶段”和“学习阶段”两部分[11]。

(7)

在学习阶段，TLBO通过将候选解与其他解进行位置差分，并据此进行位位置更新，表达式为：

(8)

TLBO算法流程为：

Step 1初始化：采用随机方法生成初始解。

Step 3学习阶段：对于当前种群中的每个解，借助该个体与其他解向量之间的差分量生成新个体，并借助贪婪保留策略生成子代解。

Step 4终止判断：若达到终止条件，停止搜索并给出最优解；否则转Step 2。

3 HSCA算法

SCA的随机初始化方法一定程度上制约了其搜索效率，同时其迭代过程仅借助已知最优解和候选解之间的差分量更新个体位置，忽略了其他个体间的信息交流。鉴于此，HSCA以反向学习方法构建质量较高的初始种群，同时凭借模因分组和TLBO进化机制强化不同个体信息交流，旨在增强基本SCA算法的搜索性能。

3.1 反向学习初始化方法

HSCA采用反学习方法构建种群：首先，利用随机方法生成N个解，并为每个解生成对应的反向解，最后选取最好的N个解作为初始种群[12]。

图3为对比了两种初始化方法在二维解空间的随机分布情况。显然，反向学习初始化方法在均匀、全面地探索解空间方面更具优势。

图3 初始化方法对比Fig. 3 Comparison of initialization methods

算法的初始解构造过程为：

Step 1定义参数i←1和参数d←1。

Step 2若表示式i≤S成立，转Step 3，否则转Step 7。

Step 3若表达式d≤D成立，转Step 4，否则转Step 5。

Step 5定义参数d←d+1，若d>D成立，转Step 6；否则转Step 3。

Step 6定义参数i←i+1，随后转Step 2。

3.2 模因分组与种群进化

HSCA算法保留了基本SCA算法的进化机制，利用式(5)更新个体位置，即借助已知最优解和候选解之间的差分量更新种群。基于此，按照目标值排序，并以q个解为一组划分为p个模因组[13]。分组过程归纳如下：①将最优解放在第一组，第二优解放在第二组，依次类推；②将排位第p+1位的个体将被置入第一组，排位第p+2位的个体将被置入第二组；③重复以上分配过程，直至将最后一个解置入第p组。

随后，HSCA算法采用TLBO的“教学阶段”更新组内的非局部最优解，并以TLBO的“学习阶段”更新组内的所有解。给定一个解x，式(9)、式(10)分别为HSCA算法中“教学阶段”和“学习阶段”涉及的更新公式：

(9)

(10)

3.3 HSCA算法流程

HSCA算法的实现流程梳理如下：

Step 1初始化：利用反向学习法创建初始解。

Step 2SCA更新：确定当前种群中的最优解，利用SCA算法更新式(2)生成新个体的位置。

Step 3模因分组：依据个体的路径评价函数值将种群划分为p个子种群。

Step 4组内教学：对于各个子种群，采用TLBO的“教学阶段”更新组内的非局部最优解。

Step 5组内学习：对于各个子种群，借助TLBO的“学习阶段”更新组内的各个解。

Step 6终止判断：若满足HSCA决策算法所设置的终止条件，停止迭代并输出最好解；否则转到Step 2。

4 实验结果与分析

为分析HSCA的性能，开展基准函数和RPP问题测试，并进行多种同类算法的对比。利用MATLAB2016b编程，平台参数为内存8 GB、CPU为Intel Core i5-2430M 2.4 Hz。

4.1 基准函数测试

选取文献[14]中的函数进行测试(表1)，参数n为函数维度。首先，对比HSCA与SCA算法，目的在于分析验证改进措施的有效性。考虑n分为20和40的情形，对于每组算例，两种决策方法分别跑20次。HSCA与SCA的种群置为60，迭代终止次数置为2 000，同时HSCA的q值设为10。表2给出了测试结果的均值和标准差数值比较。

表1 函数定义Table 1 Function definition

由表2可知，HSCA相比于SCA所取得的均值更小。换而言之，HSCA算法的整体寻优效果更优。同时，HSCA算法20次独立运行所得结果的标准差较SCA更小，说明HSCA算法鲁棒性更佳。

表2 SCA与HSCA算法目标函数值对比Table 2 Objective function value comparison of SCA andHSCA algorithm

进一步地，将HSCA与其他几种改进SCA算法对比，包括MSCA[8]、OBSCA[15]和SCA-DE[7]。维度n=40，对于各测试算例，所有方法分别跑20次，种群规模取60，迭代终止次数置为2 000，HSCA算法的子种群规模设置为10，其他参数设置同文献[7,8,15]。表3对4种算法的仿真结果进行了分析，图4为4种算法求解基准测试函数的平均进化曲线。

由表3可知，HSCA算法所得结果的均值优于MSCA、OBSCA和SCA-DE算法，表明反向学习初始化方法以及基于TLBO的多种群进化策略的嵌入使得SCA的搜索性能更强。同时，HSCA算法的标准差更小则验证了其运行状态更稳定。另外，由图4可知， HSCA算法初始阶段的种群质量更优，且最终所寻得的解更具竞争性。

表3 4种改进SAC算法目标函数值对比Table 3 Objective function value comparison of four kinds ofimproved SCA algorithms

图4 平均进化曲线对比Fig. 4 Comparison of mean evolution curves

4.2 路径规划仿真

分别将HSCA、MSCA、OBSCA和SCA-DE算法运用于简单(以Case 1表示)和复杂环境(以Case 2表示)的路径规划实验。问题参数设置如下：Case 1障碍数和导航点数为6和10，Case 2中相应参数为12和100。算法设置如下：决策方法运行次数置为20，种群规模和迭代次数为30和300， HSCA子种群规模为6，对比算法的其他参数同各文献[7,8,15]。实验结果归纳如图5、图6和表4。

图5 最优路径Fig. 5 Optimal paths

图6 最优进化曲线Fig. 6 Optimal evolution curves

表4 两种环境下4种测试算法线路长度对比Table 4 Comparison of the path length with four kinds oftest algorithms in two environment m

图5对比了4种SCA算法在Case 1和Case 2中所得的最佳路径，HSCA算法所规划出的路径最优。特别是在Case 2对应的复杂障碍环境中，笔者所提出的HSCA算法优势明显。进一步的，图6对比了4种SCA算法在Case 1和Case 2下的最优进化曲线。据此可知，反向学习方法使得HSCA算法在迭代初期解的质量更佳；同时，模因分组以及基于TLBO的多种群进化方法有效提升了算法的搜索性能。表4为4种改进SCA算法的优化结果，显然笔者提出的HSCA在优化目标优越性和稳定性两方面很具有竞争性。

5 结 论

提出了一种混合正余弦算法来求解机器人路径规划问题。算法采用反向学习初始化方法，用于构建高质量的初始种群；同时在迭代搜索过程中，以优化目标为依据进行模因分组进而构建多种群；并通过融合TLBO算法强化各子种群内的信息交流，达到了增强算法局部挖掘能力的目的。在仿真实验部分，结合基准函数开展了HSCA算法的横向和纵向的对比实验，同时将HSCA算法应用于简单和复杂障碍环境的机器人路径规划问题。测试结果表明，HSCA算法的收敛效果显著，具有良好的寻优精度和稳健的鲁棒性。