基于改进灰狼优化算法的区域监测机器人路径规划

李 靖, 杨 帆,2*

(1.河北工业大学电子信息工程学院，天津 300401；2.河北工业大学天津市电子材料与器件重点实室，天津 300401)

路径规划是机器人控制领域研究的重点和热点问题，也是机器人顺利完成各项作业任务的前提条件。按照算法的基本原理，可以将路径规划算法分为传统算法、图形学算法、群智能算法以及深度学习算法。传统算法主要有人工势场法[1]、模糊逻辑算法[2]、禁忌搜索算法[3]等，其缺点在于建模困难，具有一定的局限性。图形学算法主要有C空间法[4]、自由空间法[5]、栅格法[6]、voronoi图法[7]等，其优点在于建模简单，但其搜索能力不足，对于大规模任务量的路径搜索具有局限性。群智能算法主要有粒子群算法(particle swarm optimization,PSO)[8]、蚁群算法(ant colony optimization,ACO)[9]、遗传算法(genetic algorithm,GA)[10]、鲸鱼算法(whale optimization algorithm,WOA)[11]、灰狼优化算法(grey wolf optimizer,GWO)[12]等，运用自然启发的智能仿生学算法，往往可以解决环境相对复杂的场景，但是其计算量相对前两种会更高些。此外，还有深度学习路径规划算法[13]，其鲁棒性最高，但需要大数据集的支撑，训练、验证、测试迭代导致时间复杂度大，且需要高要求的硬件支撑，对小样本数据集无法进行无偏差的估计。

针对大任务量区域监测场景，综合考虑四类路径规划算法的优缺点，群智能算法更加符合精度与速度的要求。杨桂华等[14]融合了确定性选择与随机性选择策略，将改进蚁群算法用于室内移动机器人路径规划算法。黄长强等[15]改进蚁狮算法进行航迹规划，将混沌调节因子引入蚂蚁群体，将反调节因子引入蚁狮行为中，提高了探索能力和开发能力。余胜东等[16]提出了应用混沌萤火虫算法的无人机航迹规划，引入立方映射混沌算子来提高了局部搜索能力和鲁棒性。

GWO算法自提出以来，就因其在寻优的良好性能，结构简单，易实现等优点被广泛关注。GWO算法在收敛速度和求解精度上优于PSO算法已经被验证[12]，但其仍具有提升空间。如王秋萍等[17]采用余弦规律的搜索因子，引入了动态权重策略，平衡全局搜索和局部开发能力，提高了GWO算法的求解精度。郭振洲等[18]运用指数函数衰减搜索因子α，使收敛因子随着迭代次数的增加非线性动态变化，在搜索与开发阶段寻求平衡，以确保逼近最优解。徐松金等[19]引入了随机收敛因子以平衡搜索能力，引入了差分变异进行个体更新，以提高算法收敛与精确度。

基于上述分析，提出了一种基于改进灰狼优化算法的区域监测机器人路径规划方法。首先引入Logistic混沌映射、自适应调整策略、静态加权平均权重策略改进灰狼优化算法，随后将机器人载电量、路径长度短作为约束，引入K-means算法进行任务聚类，通过改进的灰狼优化算法(improved grey wolf optimizer,IGWO)算法对模型进行离线求解，规划出路线，将大任务量监测作业自动转换成分时分步作业，为机器人自动自主区域监测任务奠定了基础。

1 问题建模

假设区域工作环境地图已知，T={T1,T2,…,Tn}为任务点集合，O为机器人投放点(起点)位置，要求Robot遍历n个任务点，且需回到起点，遍历路径为R={O,T1,T2,…,Tn，O}，则路径长度L为

(1)

以机器人电量消耗进行约束，机器人作业需要消耗电量，机器人全程作业任务消耗到电量为

q=ruL

(2)

式(2)中：ru为机器人单位距离消耗的电量。

为了机器人能够顺利完成任务并能返回出发地聚集，要求机器人作业任务的电量消耗q，要小于机器人带电量Q，可以表示为

q

(3)

以大任务量巡查监测作业为背景，通过机器人定点巡视，当发现异常点，便调度临近的机器人群到达指定异常点进行检查，排除故障，实现自动监测，自主完成作业的目的。首先改进传统灰狼优化算法，加强求解能力；随后通过改进的灰狼优化算法求解在电量约束下的问题建模模型，遍历任务点进行监测，发现异常点派遣临近机器人群避障到达异常点，以便排除故障。

2 改进的灰狼优化算法(IGWO)

2.1 传统灰狼优化算法(GWO)

2.1.1 GWO算法的等级结构

灰狼优化算法[12]是模拟食物链顶端的捕食者狼群的捕食行为产生的算法。灰狼大都喜欢群居，且具有非常严格的社会等级制度，如图1金字塔结构的等级制度所示。

图1 灰狼的社会等级结构Fig.1 Hierarchy of gray wolf

2.1.2 GWO算法的数学模型

在GWO算法数学建模中，每只灰狼代表种群中 1 个候选解，将最优解视为α，第二、第三个最佳候选解视分别为β和δ，其余的候选解视为ω。在GWO算法中，搜索(优化)由α、β和δ引导，ω狼跟随这三只狼。

D=|CXp(t)-X(t)|

(4)

X(t+1)=Xp(t)-AD

(5)

式(5)中：t表示当前迭代次数;A和C为系数向量;Xp为猎物的位置向量;D为灰狼个体与猎物之间的位置关系向量；X为灰狼的位置向量。A、C计算公式为

A=2ar1-a

(6)

C=2r2

(7)

式中:r1和r2的模是[0,1]的随机数;a为收敛因子，其数值随着迭代次数的增加从2线性减小到0，计算公式为

(8)

式(8)中:t为当前迭代次数;tmax为最大迭代次数。

灰狼追踪猎物位置的数学模型描述如式(9)～式(11)所示：

{Dα=|C1Xa-X|

Dβ=|C2Xβ-X|

Dδ=|C3Xδ-X|

(9)

{X1=Xα-A1Da

X2=Xβ-A2Dβ

X3=Xδ-A3Dδ

(10)

(11)

式中：C1、C2、C3为随机向量；Dα、Dβ和Dδ分别为α狼、β狼和δ狼与狼群其他成员之间的距离；Xα、Xβ、Xδ分别为α狼、β狼和δ狼的位置；X为当前狼的位置。狼群中ω狼的位置由α狼、β狼和δ狼共同决定。

2.2 改进的灰狼优化算法(IGWO)

2.2.1 基于Logistic映射的种群初始化

混沌具有随机性、遍历性和规律性的特点。引入混沌序列，可以使初始种群个体尽可能地利用解空间的信息，改善全局搜索能力，由于Logistic映射[20]简单混沌且遍历均匀性较好，因此在种群初始化时，使用Logistic映射产生混沌序列，对狼群进行种群位置初始化。Logistic映射的表达式如式(12)所示：

xn+1=axn(1-xn)

(12)

式(12)中：xn∈[0,1]为混沌变量；a=4。设x0=0.428 8。图2为30个种群Logistic映射种群初始化后的气泡图。

图2 基于Logistic映射的种群初始化气泡图Fig.2 Population initialization bubble diagram based on Logistic Mapping

2.2.2 控制参数自适应调整策略

a对GWO算法全局搜索及局部开发能力具有平衡作用，它随着迭代次数的增加不断地从2线性衰减到0，而迭代收敛的过程并不是线性的，因此，提出了一种非线性控制参数自适应调整策略，如式(13)所示。通过调整a的自适应值来平衡GWO算法的搜索能力和开发能力，在迭代初期全局搜索时，a较大，非线性变化速率快，全局搜索能力强，避免局部最优，在迭代后期a较小，非线性变化速率慢，则在某个区域内寻求最优解，开发能力强，收敛速度加快。

(13)

式(13)中：t为当前迭代次数；Tmax为最大迭代次数；n∈[1,2]为非线性调制指数；ainitial为控制参数a的初始值，ainitial=2。a的非线性衰减对比如图3所示。

图3 控制参数a对比Fig.3 Contrast chart of control parameter a

2.2.3 静态加权平均策略

加权平均策略的主要思想是为三个头狼分配配重，以显示金字塔的层次结构，这里引入文献[17]的静态加权平均策略，分配给α狼的权重为0.5，β狼的权重为0.3，则δ狼的权重为0.2，如式(14)所示：

(14)

3 问题建模求解

3.1 K-means算法

K-means算法[21]是无监督聚类算法，不需要有任何的先验知识，其原理思想是基于一种划分的思想，以距离作为数据间相似性度量的标准，数据间的距离越小，则表明相似性越高，则可以归为一个类簇。

根据问题建模可知任务点样本集T={T1,T2,…,Tn}，假设聚类集合为μ={μ1,μ2,…，μk}

距离函数为

(15)

式(15)中：Tm为第m个任务；μi表示第i类到聚类中心。

聚类中心更新公式为

(16)

准则函数为

(17)

式中：xj表示第j类样本中的数据。

3.2 约束条件下IGWO算法模型求解

考虑机器人电量约束，通过检查行驶路径机器人所消耗的电量q是否大于机器人的载电量，如果qQ，需要对任务点进行聚类，将任务划分成k个子任务，分别在子任务内进行IGWO算法求解规划路径，即转换成类旅行商问题(traveling salesman problem，TSP)，并分别判断子任务内电量约束是否满足qQ的情况，便重新对任务进行k+1类聚类，在子任务类内进行路径规划及电量判断，直到子任务(k+2，k+3,…,k+m)内路径规划对应的行驶电量满足q

图4 问题建模求解流程图Fig.4 Flow chart of problem model solving

4 实验仿真及结果分析

实验仿真环境为处理器Intel Corei7 CPU @1.8 GHz 2.0 GHz，内存16 G，操作系统WIN10，64位，仿真软件为MATLAB 2019a进行仿真。

4.1 IGWO算法测试仿真

为了验证改进灰狼优化算法的性能，选取了国际上6个经典基准测试函数进行测试，其中Sphere函数、Rosenbrock 函数、Schwefel’s 2.22函数为单峰测试函数、Rastrigin函数、Griewank函数和Ackley函数为多峰测试函数，测试函数的维数、定义域如表1所示。分别对PSO算法，GWO算法及IGWO算法进行了仿真测试，其测试结果对比如图5所示，对比平均值及标准差如表2所示。其中，种群规模设置为30，最大迭代次数设置为500次。

Sphere 函数：

(18)

Schwefel’s 2.22函数：

(19)

Rosenbrock函数：

(20)

Rastrigin函数：

(21)

Ackley函数：

(22)

Griewank函数：

(23)

表1 测试函数Table 1 Test function

图5 基准测试函数测试结果Fig.5 Benchmark function test results

表2 基准测试函数优化结果对比Table 2 Optimization comparison of test functions

实验结果表明，对于单峰测试函数，IGWO算法的收敛速度及精度略高于GWO算法。而对于多峰测试函数，IGWO算法的收敛速度远远高于PSO算法及GWO算法，效果更佳明显。

4.2 基于IGWO算法的区域搜索机器人路径规划仿真

假设环境地图为1 000×1 000的区域内，模拟随机生成50个任务点与100个任务点两种情况进行算法仿真(图6～图8)。起点坐标设置为(0,0)，一个机器人从起点坐标逐一巡视任务点，且能在任务完成后，回到起点坐标处。

图6 50个任务点路径规划效果Fig.6 Results of path planning for 50 task points

图7 适应度对比Fig.7 Comparison of fitness values

图8 100个任务点路径规划效果Fig.8 Results of path planning for 100 task points

图6为50个任务点仿真效果，通过GWO算法和IGWO算法对多任务点一次性遍历的路径长度分别为7 782.746 3、8 709.361 4 m，IGWO算法比GWO算法规划路径长度缩短了926.615 1 m，效率提升了10.64%。图7为50个任务点GWO 算法与IGWO 算法的最优适应度值曲线对比，可以清晰地看出IGWO算法比GWO算法收敛更快，对模型的求解能力更强。在机器人最大载电量的限制下，规划长度远远大于已有机器人最大行走长度 3 500 m，因此需要将任务点进行聚类，将任务分时分步处理，任务点聚类成2类时，满足已有机器人最大路径长度(电量)约束，将搜索任务分成2次处理，第一次遍历27个任务点进行搜索，路径为0—32— 41— 40—11— 43—35—36—29—24— 45— 8—3—39— 6—1— 44—7—20— 42—28—13—10—30—31— 49— 47—50—0，路径长度为3 485.164 2 m，第二次遍历23个任务点进行搜索，路径为：0—34—21—26—2— 46—22—19—25— 4—27—18— 48—38—15—5—16—17—33—37—23—14—12—9—0，路径长度为3 489.207 6 m，两次路径长度合计为6 974.371 8 m，比传统GWO算法一次性直接遍历路径规划长度缩短了19.92%，比IGWO算法未任务点聚类一次性规划长度缩短了10.39%，且满足了机器人电量约束。

图8为100个任务点测试结果，此时2聚类不能满足电量约束条件，继续进行3聚类，才能满足约束，从而得到图8(d)路径规划结果。如表3所示，100任务点路径规划总长度由传统GWO算法的20 342.147 2 m 缩短到IGWO算法的19 378.594 8 m，再在机器人电量约束的条件下，进行任务点3聚类，其路径长度缩短为10 965.772 8 m，缩短比例为53.91%。由此可见，在大任务量作业的场景中，本文算法路径规划优势更佳明显。

表3 路径规划测试结果Table 3 Test results of path planning

5 结论

针对大任务量监测作业，提出基于改进灰狼优化算法区域监测机器人路径规划算法。该算法选取寻优性能良好且稳定的灰狼优化算法，并对其进一步改进，以Logistic混沌映射加强种群多样性，以控制参数自适应调整策略平衡灰狼优化算法的搜索和开发能力，以静态加权平均权重策略，更新种群位置，加快收了敛速度，从而增强了算法的模型求解能力。根据任务量规模及机器人载电量约束，引入K-means算法任务聚类，并通过IGWO算法进行路径求解，将大规模任务量自动自主的转化成分时分步任务。实验结果表明，IGWO算法无论是在单峰函数还是多峰函数的测试上收敛效果均有提高，特别在多峰函数更佳明显。基于改进灰狼优化算法的区域监测机器人路径规划在大规模任务量的场景更能体现出优越性，任务规模越大，路径缩短比例更高。