1.一种多无人机覆盖路径规划方法,其特征在于,包括以下步骤:
S1导入需实施覆盖路径规划区域的信息,确定需要覆盖的区域和禁止飞越的区域,并确定所述需要覆盖的区域中的需访问点的集合AS;
S2配置参数信息,包括:簇数目K、迭代次数常数MI、策略选择常数SC,所述簇数目K对应参与覆盖搜索无人机的数目,策略选择常数SC用于调整不同的簇中心点产生策略的使用比例,其为小于1的数;
S3设置迭代计算变量的初值,包括:邻域搜索策略的步长step、循环变量counter从MI开始逐步减小,减小到0时调整step大小,并重新从MI值开始递减;
S4判断循环变量counter是否大于迭代次数常数MI,如果大于MI,则转到步骤S5,否则转到步骤S6;
S5在需访问点的集合AS中,随机选择K个点作为簇的初始中心点,然后转到步骤S9;
S6判断counter是否大于 ,如果大于,则转到步骤S7,否则转到步骤S8;
S7采用随机搜索策略产生K个簇的新中心点,然后转到步骤S9;
S8采用邻域搜索策略产生K个簇的新中心点;
S9分配AS集合中所有点到距离最近的簇中;
S10对每个簇采用牛耕法进行路径规划,得到新路径newPaths;
S11计算新路径newPaths的评估值newF;
S12判断评估值newF是否小于目前最优方案bestPaths的评估值minF;若newPaths优于bestPaths,则将bestPaths更新为newPaths,minF更新为newF,且计数器counters设置为MI,否则,计数器counter减小1;
S13判断counter是否减小到了0;如果counter小于或等于0,则调整搜索步长step为,其中,C2为小于1的步长调整系数;
S14判断step是否小于MinStep,如果step不小于MinStep,则转到步骤S4进行迭代计算,否则,迭代计算结束,输出最优路径规划方案bestPaths,其中,MinStep为邻域搜索策略的最小步长。
2.根据权利要求1所述的多无人机覆盖路径规划方法,其特征在于,所述步骤S1具体包括:采用基于栅格的技术,将需实施覆盖路径规划区域离散为栅格,并把栅格分为A、N、B三类,A类栅格对应需要覆盖的区域,记录栅格中心点为:As(x,y),其中,A为点的类别,s为点的序号,(x,y)为点的坐标;N类栅格对应禁飞区,将相邻的禁飞区栅格合并为尽可能大的矩形,记录禁飞区矩形为:NRt(N0,N1),其中,t为矩形的序号,N0为矩形的左上角点,N1为矩形的右下角点;B类栅格为其它栅格,这些栅格不需要覆盖搜索,也不禁止UAV飞越,因此,整个区域信息可以表示为G=G(AS,NRS),其中,AS为A类栅格中心点的集合,NRS为禁飞区对应矩形的集合。
3.根据权利要求2所述的多无人机覆盖路径规划方法,其特征在于,所述步骤S3中,设置迭代计算变量的初值,具体包括:;
其中,step为邻域搜索策略的步长,step值越大,邻域搜索的范围越大;DN是属性值域划分数,C1是一个小于1的常数,用于设置初始步长大小;bestPaths为列表,记录当前最优的路径规划方案;minF记录bestPaths对应的价值函数的评估值。
4.根据权利要求2所述的多无人机覆盖路径规划方法,其特征在于,步骤S7中,采用随机搜索策略产生K个簇的新中心点,具体包括:在当前每个簇所有点的值域范围里,随机选择一个值作为簇新的中心点,如下式:;
其中,newCPi,j是第i个簇新中心点的第j个属性的值;minPi,j是第i个簇中所有点第j个属性的极小值;maxPi,j是第i个簇中所有点第j个属性的极大值;rand是一个0到DN之间的随机整数,DN是属性值域划分数; 是序号为k的A类栅格中心点的第j个属性值;CSi为分配到第i个簇中的所有点。
5.根据权利要求4所述的多无人机覆盖路径规划方法,其特征在于,所述步骤S8具体包括:在当前每个簇中心点的邻域范围里,搜索并产生簇的新中心点,步长step对应邻域搜索范围的大小,簇新中心点计算公式如下:;
其中,newCPi,j是第i个簇新中心点的第j个属性的值;oldCPi,j是第i个簇当前中心点的第j个属性的值;stepPj是newCPi,j在第j个属性上的增量;rand是区间[‑C3,C3]范围内的随机整数,C3是常量;minPj是AS集合中所有点第j个属性的极小值;maxPj是AS集合中所有点第j个属性的极大值。
6.根据权利要求5所述的多无人机覆盖路径规划方法,其特征在于,所述步骤S10包括以下步骤:S10‑1按顺序从{CS1,CS2,…,CSk}取出CSi为当前簇;
S10‑2对当前簇CSi中所有点,采用深度优先搜索方向和起始点不同的牛耕法规划出多条路径;深度优先搜索方向分为:Horizontal,即水平、Vertical,即垂直、Diagonal,即对角线,起始点分为:XminYmin,即左上角点,XminYmax,即左下角点,XmaxYmin,即右上角点,XmaxYmax,即右下角点,不同的深度优先搜索方向和起始点组合成不同的牛耕法对簇CSi实施路径规划;
S10‑3计算当前簇CSi不同路径价值函数的评估值,选择评估值最小的路径为当前簇的规划路径,记作pathi,并将pathi添加到newPaths列表中;
路径评估综合考虑路径的长度和转角,采用的价值函数有飞行时间和能量消耗;
S10‑4是否已完成所有簇CSi的路径规划任务,如未完成,转到步骤S10‑1。
7.根据权利要求6所述的多无人机覆盖路径规划方法,其特征在于,所述步骤S11中,评估值newF根据制定的评价函数得到,所述评价函数F表示为:;
其中,F为路径规划方案newPaths的价值函数,值越小,对应的方案越优;F0为newPaths中各路径耗时CTi的均值;F1为newPaths中各路径耗时偏离均值F0的程度;C4为常量,调整F中F0和F1的占比,C4越大,F1占比越重,所得的规划方案中各无人机耗时更均衡。
8.一种电子设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述处理器执行所述程序时实现上述权利要求1‑7任一项所述的方法。
9.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该计算机程序被处理器执行时实现上述权利要求1‑7任一项所述的方法。