路径规划方法、装置和非易失性计算机可读存储介质与流程

1.本公开涉及路径规划技术领域，特别涉及一种路径规划方法、路径规划装置和非易失性计算机可读存储介质。


背景技术：

2.在众多行业中，自动化巡检已经成为提高巡检效率和安全性的通用解决方案，如通信基站、光伏电站、交通巡检、海事巡检、城市管道等。采用自动化巡检技术可以大幅提升巡检精细化程度提升巡检效率。与人工巡检相比，自动化巡检技术在作业环境、解放人力、灵活作业、提高效率、提升质量等方面有着显著的优势。
3.在相关技术中，基于三维空间中的多个节点信息路径规划。


技术实现要素：

4.本公开的发明人发现上述相关技术中存在如下问题：三维空间搜索节点多，空间复杂度较高，导致路径规划的效果差。
5.鉴于此，本公开提出了一种路径规划技术方案，能够提高路径规划的效果。
6.根据本公开的一些实施例，提供了一种路径规划方法，包括：根据狼群算法的不同路径搜索阶段，配置距离判定因子，距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，第二路径搜索阶段位于第一路径搜索阶段和第三路径搜索阶段之间；根据距离判定因子，利用狼群算法规划第一路径。
7.在一些实施例中，配置距离判定因子包括：根据人工狼的当前位置、固定距离判定因子，确定动态距离判定因子作为距离判定因子。
8.在一些实施例中，确定动态距离判定因子包括：根据位置参数和尺度参数确定动态距离判定因子，动态距离判定因子与当前位置与位置参数的差值的绝对值负相关，与尺度参数负相关。
9.在一些实施例中，路径规划方法还包括：根据第一路径中各节点之间是否具有连接关系，配置第一路径中各节点之间的信息素浓度；根据信息素浓度和第一路径，利用蚁群算法规划第二路径。
10.在一些实施例中，利用蚁群算法规划第二路径包括：根据各蚂蚁在当前次迭代过程中寻找到的路径的质量，确定信息素挥发因子，信息素挥发因子用于增强寻找到当前次迭代过程中的最优路径的蚂蚁对下一次迭代过程的影响，减弱寻找到当前次迭代过程中的最差路径的蚂蚁对下一次迭代过程的影响。
11.在一些实施例中，在当前次迭代过程中寻找到的路径的质量越高的蚂蚁的信息素挥发因子越大。
12.在一些实施例中，确定信息素挥发因子包括：配置第一随机数和第二随机数，第一随机数小于第二随机数；根据第二随机数，确定优劣程度等于第一质量参数的蚂蚁的信息素挥发因子，第一质量参数对应于寻找到当前次迭代过程中的最优路径的蚂蚁的质量；根
据第一随机数，确定优劣程度等于第二质量参数的蚂蚁的信息素挥发因子，第二质量参数对应于寻找到当前次迭代过程中的最差路径的蚂蚁的质量，第一质量参数大于第二质量参数；根据第一随机数和第二随机数的均值，确定其他蚂蚁的信息素挥发因子。
13.在一些实施例中，利用狼群算法规划第一路径包括：根据狼群算法中当前所有可以连通的两个节点之间的距离之和，确定狼群算法的游走行为的适应度；根据适应度，规划第一路径。
14.在一些实施例中，路径规划方法还包括：利用栅格法对待规划路径的空间进行建模；根据建模结果，规划第一路径。
15.根据本公开的另一些实施例，提供一种路径规划装置，包括：配置单元，用于根据狼群算法的不同路径搜索阶段，配置距离判定因子，距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，第二路径搜索阶段位于第一路径搜索阶段和第三路径搜索阶段之间；规划单元，用于根据距离判定因子，利用狼群算法规划第一路径。
16.在一些实施例中，配置单元根据人工狼的当前位置、固定距离判定因子，确定动态距离判定因子作为距离判定因子。
17.在一些实施例中，配置单元根据位置参数和尺度参数确定动态距离判定因子，动态距离判定因子与当前位置与位置参数的差值的绝对值负相关，与尺度参数负相关。
18.在一些实施例中，配置单元根据第一路径中各节点之间是否具有连接关系，配置第一路径中各节点之间的信息素浓度；规划单元根据信息素浓度和第一路径，利用蚁群算法规划第二路径。
19.在一些实施例中，配置单元根据各蚂蚁在当前次迭代过程中寻找到的路径的质量，确定信息素挥发因子，信息素挥发因子用于增强寻找到当前次迭代过程中的最优路径的蚂蚁对下一次迭代过程的影响，减弱寻找到当前次迭代过程中的最差路径的蚂蚁对下一次迭代过程的影响。
20.在一些实施例中，在当前次迭代过程中寻找到的路径的质量越高的蚂蚁的信息素挥发因子越大。
21.在一些实施例中，配置单元配置第一随机数和第二随机数，第一随机数小于第二随机数；根据第二随机数，确定优劣程度等于第一质量参数的蚂蚁的信息素挥发因子，第一质量参数对应于寻找到当前次迭代过程中的最优路径的蚂蚁的质量；根据第一随机数，确定优劣程度等于第二质量参数的蚂蚁的信息素挥发因子，第二质量参数对应于寻找到当前次迭代过程中的最差路径的蚂蚁的质量，第一质量参数大于第二质量参数；根据第一随机数和第二随机数的均值，确定其他蚂蚁的信息素挥发因子。
22.在一些实施例中，规划单元根据狼群算法中当前所有可以连通的两个节点之间的距离之和，确定狼群算法的游走行为的适应度；根据适应度，规划第一路径。
23.在一些实施例中，规划单元利用栅格法对待规划路径的空间进行建模，根据建模结果，规划第一路径。
24.根据本公开的又一些实施例，提供一种路径规划装置，包括：存储器；和耦接至存储器的处理器，处理器被配置为基于存储在存储器装置中的指令，执行上述任一个实施例中的路径规划方法。
25.根据本公开的再一些实施例，提供一种非易失性计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述任一个实施例中的路径规划方法。
26.在上述实施例中，通过设置动态变化的距离判定因子，使得路径搜索的前、后期的搜索速度较小，中期的搜索速度较大。这样，能够使得狼群算法的后期更容易进入围攻行为，以提高路径规划的效果。
附图说明
27.构成说明书的一部分的附图描述了本公开的实施例，并且连同说明书一起用于解释本公开的原理。
28.参照附图，根据下面的详细描述，可以更加清楚地理解本公开：
29.图1示出本公开的路径规划方法的一些实施例的流程图；
30.图2示出本公开的路径规划场景建模的一些实施例的示意图；
31.图3示出本公开的路径规划方法的另一些实施例的流程图；
32.图4示出本公开的路径规划装置的一些实施例的框图；
33.图5示出本公开的路径规划装置的另一些实施例的框图；
34.图6示出本公开的路径规划装置的又一些实施例的框图。
具体实施方式
35.现在将参照附图来详细描述本公开的各种示例性实施例。应注意到：除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、数字表达式和数值不限制本公开的范围。
36.同时，应当明白，为了便于描述，附图中所示出的各个部分的尺寸并不是按照实际的比例关系绘制的。
37.以下对至少一个示例性实施例的描述实际上仅仅是说明性的，决不作为对本公开及其应用或使用的任何限制。
38.对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，技术、方法和设备应当被视为说明书的一部分。
39.在这里示出和讨论的所有示例中，任何具体值应被解释为仅仅是示例性的，而不是作为限制。因此，示例性实施例的其它示例可以具有不同的值。
40.应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步讨论。
41.如前所述，三维空间搜索节点多，空间复杂度较高，在解决此类问题时，很多仿生学算法有较好的效果。但是，单一算法存在较大的局限性，缺点明显，优化空间有限。
42.针对上述技术问题，本公开对三维空间自动化巡检的路径规划进行了研究。本公开的技术方案在通过狼群-蚁群算法融合；完成信息素积累后，利用蚁群算法所有节点进行快速搜索，动态的调整信息素的更新规则；并选择同长度路径拐点较少原则，加快后期收敛速度，获得更好的求解目标。
43.在一些实施例中，基于三维仿真环境，建立三维栅格地图；使用狼群算法与蚁群算法相结合的方式来缩减搜索时间、寻找最短搜索路径。
44.例如，确定巡检节点的起止位置，通过初始化狼群、竞争头狼、头狼召唤、围攻猎物以及狼群更新5个步骤来实现求解最短路径问题；并根据狼群算法特点，动态调整距离判定因子ω，提升中期算法搜索速度，后期收敛速度，更容易进行围攻行为。从而，提高融合算法的前期信息素积累。
45.本公开的实施例采用狼群算法与蚁群算法结合的方式，充分发挥狼群算法的并行性、搜索快的特点，具有较高的向最优解收敛的速度。对距离判定因子进行动态计算，生成初始信息素分布；蚁群算法通过信息素的累积和更新，调整挥发因子，并改变信息素挥发因子的更新规则，收敛于最优路径。
46.本公开在应用于三维空间的自动化巡检的路径规划时，不仅提升了寻找最优解的能力，而且提高了其收敛速度。
47.例如，可以通过下面的实施例实现本公开的技术方案。
48.图1示出本公开的路径规划方法的一些实施例的流程图。
49.如图1所示，在步骤110中，根据狼群算法的不同路径搜索阶段，配置距离判定因子。距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，第二路径搜索阶段位于第一路径搜索阶段和第三路径搜索阶段之间。
50.在一些实施例中，利用栅格法对待规划路径的空间进行建模；根据建模结果，规划第一路径。环境建模是路径规划的基础，仿真无人机飞行应先对其飞行环境进行建模。例如，可以通过栅格法、自由空间法、可视图法等进行建模。
51.例如，可以通过图2中的实施例，利用栅格法来为无人机的飞行环境等路径规划场景建立模型。
52.图2示出本公开的路径规划场景建模的一些实施例的示意图。
53.如图2所示，首先以o为顶点构造abco-a1b1c1o1三维空间，其中x轴为无人机横向移动的方向，y轴为无人机纵向移动的方向，z轴为垂直于水平面的方向。
54.例如，在建立好三维空间后，沿着z轴方向对oo1边进行s等分，每过一个等分点做一个平行于aoa1o1的平面，可以得到s+1个平面；利用栅格法对每一个平面进行划分，沿着x轴方向对oa边行进行m等分；沿着y轴对of边进行n等分，最后每一个平面可以划分为m
×
n个栅格。
55.这样，就可以得到每一个离散点的坐标值，将这些节点集合设为p。空间中每一个节点都有相对应的两个坐标值：等分点序号坐标和空间内具体位置坐标。通过这两个坐标，空间中的任意一个节点都可以用数学方法表示出来，用于后续的路径规划。
56.例如，可以通过表1中的栅格化三维地图数据结构进行建模。
57.表1
58.成员含义point:int[][][]三维栅格地图上的坐标点，用三维数组表示start:int[][][]地图上巡检的起始点end:int[][][]地图上巡检的目标点allow:int[][][]地图上可以经过的点bar:int[][][]地图上的障碍点，不可经过
[0059]
建模后，可以通过图1中的其余步骤进行路径规划。
[0060]
例如，可以先对狼群算法中的参数等进行初始化。初始化参数，人工狼位置xi及人工狼的数量n；初始化迭代次数为k，探狼比例因子α，最大游走次数tmax，更新比例因子β。
[0061]
例如，在游走行为中，计算每个种群中个体(即人工狼)的适应度的大小，最优个体为头狼(适应度为y
lead
)，次优的s
num
个为探狼(适应度为yi)；探狼进行游走行为，若yi《y
lead
，则探狼进行自主决策；探狼向h个方向分别前进一步，并记录前进一步后的猎物气味浓度(即适应度)，选择气味最大(即适应度最高)且大于当前气味浓度的方向前进一步；重复以上游走行为，直到yi》y
lead
。
[0062]
在一些实施例中，根据狼群算法中当前所有可以连通的两个节点之间的距离之和，确定狼群算法的游走行为的适应度；根据适应度，规划第一路径。
[0063]
例如，可以采用如下方式，构建气味浓度即适应度的函数。构建的目标适应度函数是用来评估每个人工狼的适应度。适应度的大小会决定人工狼生存的概率，会影响找到最终目标的概率。适应度高则更容易找到目标，生存概率大。
[0064]
例如，对于任一条连通的路径，包括开始点s，途径点cm(m＝1,2,...n)，终点f。用g表示从开始点s到指定栅格的移动成本，h表示从指定栅格到终点d的预估成本，f＝g+h表示该点的总成本。成本越低，适应度越高。
[0065]
例如，在上下左右移动的过程中，单位移动成本为c1(例如为1)，对角线移动成本为c2(例如为1.7)，c1小于c2。
[0066]
例如，综合移动成本f越小，则速度越快，生存概率越大。所以，可以引入a*算法，将路径中任意可连通两点间的移动成本预估出来，一开展选择。
[0067]
例如，构建的适应度函数可以为；
[0068]
fit＝1/l，
[0069]
l(xi+xj)表示相邻两个端点xi(i
x
,iy,iz)和xj(j
x
,jy,jz)的距离，t为节总数。在探狼i的yi》y
lead
的情况下，替换头狼发起召唤行为。
[0070]
例如，在召唤行为中，人工猛狼向猎物奔袭，在yi》y
lead
的情况下，替换头狼发起召唤行为；否则，持续奔袭，直到探狼与头狼件的距离d
is
《d
near
。
[0071]
在一些实施例中，根据人工狼的当前位置、固定距离判定因子，确定动态距离判定因子作为距离判定因子。例如，根据位置参数和尺度参数确定动态距离判定因子，动态距离判定因子与当前位置与位置参数的差值的绝对值负相关，与尺度参数负相关。
[0072]
例如，判定距离d
near
可以表示为：
[0073][0074]
f(xi,ω)为对固定距离判定因子ω进行动态调整后，确定的动态距离判定因子。
[0075]
这是因为，以固定值确定距离判定因子ω的方式比较单一，取值大小影响wpa的收敛速度。ω值增加会加速收敛，但值过大将导致猛狼难以进入围攻行为。所以，动态调整ω能更快搜索得到最优路径。
[0076]
例如，f(xi,ω)可以符合拉普拉斯概率密度函数，如下：
[0077][0078]
λ表示尺度参数，μ表示位置参数，b为可调整参数。
[0079]
在步骤120中，根据距离判定因子，利用狼群算法规划第一路径。
[0080]
例如，在围攻行为中，在d
is
＜d
near
的情况下，对参与围攻行为的人工狼位置进行更新，执行围攻行为。
[0081]
例如，在更新过程中，按胜者为王的原则，更新头狼的位置；按强者生存的原则，对整个群体进行更新。
[0082]
例如，在终止过程中，判断是否达到优化精度要求或者最大迭代次数；若达到，则输出头狼的位置即最优解，否则，再次从游走行为开始执行。
[0083]
例如，上述实施例中的初始化、游走行为、召唤行为、围攻行为、更新过程、终止过程构成了通过狼群算法进行路径规划的迭代过程。
[0084]
在一些实施例中，表2示出了狼群算法的参数。
[0085]
表2
[0086]
成员含义start：int[][][]巡检的起始位置点坐标end：int[][][]巡检的终止位置点α：int探狼比例因子β：int群体更新比例因子ω：int距离判定因子s：int步长因子tmax：int最大游走次数
[0087]
在一些实施例中，根据第一路径中各节点之间是否具有连接关系，配置第一路径中各节点之间的信息素浓度；根据信息素浓度和第一路径，利用蚁群算法规划第二路径。
[0088]
例如，通过狼群算法得到的阶段最优解，即第一路径s＝{x1，x2，...，xn}。对此路径上任意相邻2个途径点xi、xj的连接赋予信息素值增量δτ
ij
(0)，例如可以取值为1；对于没有连接的两个节点，可以赋予的增量值δτ
ij
(0)为0。
[0089]
例如，在初始化流程中，初始化蚂蚁种群数量m，信息素挥发因子ρ。对于狼群算法的搜索路径，s＝{x1，x2，...，xn}相邻两个节点xi与节点xj之间存在连接关系，结合狼群算法的搜索结果，定义δτ
ij
(0)＝1，为额外的信息素增量，否则δτ
ij
(0)＝0。
[0090]
例如，可以通过表3设置蚁群算法的参数。
[0091]
表3
[0092]
成员含义start：int[][]巡检的起始位置点坐标end：int[][]巡检的终止位置点sizepop：int种群数量itermax：int迭代次数probability：double转移概率
p信息素挥发因子pheromone信息素
[0093]
在一些实施例中，计算转移概率。例如，可以计算从节点xi到节点xj的转移概率。xi到xj的距离为：
[0094][0095]
进而，确定启发函数η
ij
：
[0096][0097]
启发函数也就是任意两个点之间的期望度。
[0098]
例如，从xi转移到xj的选择概率是由两节点之间的信息素强度和选择代价决定的。
[0099]
例如，蚂蚁k从当前节点xi转移到可行节点xj的概率为：
[0100][0101]
其中，ak＝c-tabuk为可访问节点
[0102]ak
＝{0，1，...，n-1}表示蚂蚁k下一步允许选择的节点。t(i，j)表示存储在路径段l(i，j)上的信息素浓度。α、β为可调参数，并且随时间变化而调整，主要作用是确定信息素浓度和可见度的相对重要性。
[0103]
在一些实施例中，根据各蚂蚁在当前次迭代过程中寻找到的路径的质量，确定信息素挥发因子，信息素挥发因子用于增强寻找到当前次迭代过程中的最优路径的蚂蚁对下一次迭代过程的影响，减弱寻找到当前次迭代过程中的最差路径的蚂蚁对下一次迭代过程的影响。
[0104]
例如，在当前次迭代过程中寻找到的路径的质量越高的蚂蚁的信息素挥发因子越大。
[0105]
例如，配置第一随机数和第二随机数，第一随机数小于第二随机数；根据第二随机数，确定优劣程度等于第一质量参数的蚂蚁的信息素挥发因子，第一质量参数对应于寻找到当前次迭代过程中的最优路径的蚂蚁的质量；根据第一随机数，确定优劣程度等于第二质量参数的蚂蚁的信息素挥发因子，第二质量参数对应于寻找到当前次迭代过程中的最差路径的蚂蚁的质量，第一质量参数大于第二质量参数；根据第一随机数和第二随机数的均值，确定其他蚂蚁的信息素挥发因子。
[0106]
例如，可以改变信息素挥发因子的值。在已有一定信息素基础上，可以加快前期搜索速度，但为了避免算法过早的陷入局部最优，并平衡全局搜索能力与局部搜索能力，设置第一质量参数(如0.5)和第二质量参数(如0.2)构成的区间，如各蚂蚁的重量参数ρ∈[0.2,0.5]。
[0107]
例如，可以配置2个随机数，第一随机数q1∈[0,1]和第二随机数q2∈[1,2]。信息
素挥发因子可以为：
[0108][0109]
例如，找出每次迭代后的优质蚂蚁与最差蚂蚁，分别进行加强与削弱。对寻找到最优路径的蚂蚁信息素增强，以增强最优蚂蚁对下一次迭代的引导能力；对寻找到最差路径的蚂蚁信息素进行减弱，以减弱最差蚂蚁对下一次迭代的影响，从而有助于找到全局最优解。
[0110]
在一些实施例中，判断蚂蚁是否到达了目标节点。如果尚未到达则继续搜索，在到达目标节点后，记录各个路径长度、拐点数，并进行各路径长度对比。优先选择路径长度最短的；在同等长度的路径中，再选择拐点数少的，得到阶段最优解。
[0111]
在一些实施例中，判断是否达到最大迭代次数。若未达到，则返回至流程二进行重复执行，进行新一轮的迭代；达到最大迭代次数后输出最优解，得到全局最优路径。
[0112]
例如，上述实施例中的初始化、计算转移概率、改变信息素挥发因子、判断蚂蚁是否到达了目标节点、判断是否达到最大迭代次数构成了通过蚁群算法进行路径规划的迭代过程。
[0113]
在上述实施例中，对狼群算法的距离判定因子ω进行动态调整，使其符合拉普拉斯概率密度函数变化的方式。弥补了以固定值方式设置的ω太小导致的算法收敛慢，过大导致人工狼难以进入围攻行为，缺少精细化搜索的不足。从而，使得算法的中期搜索速度加快，后期收敛速度加快，达到了更好的进行全局搜索的目标。
[0114]
在上述实施例中，对蚁群算法的信息素更新方法做了改进，提出一种动态改变信息素挥发因子方法。对每次迭代后的优质蚂蚁与最差蚂蚁分别进行加强与削弱，更加充分地发挥蚁群算法的正反馈效应；并根据同长度路径拐点较少原则进行优质路径筛选，改进后可以更好地平衡全局搜索能力与局部搜索能力，提升算法后期的收敛速度。
[0115]
图3示出本公开的路径规划方法的另一些实施例的流程图。
[0116]
如图3所示，在步骤a1中，用栅格法对无人机的工作环境空间进行建模，用栅格地图表示。
[0117]
例如，首先，以o为顶点构造abco-a1b1c1o1三维空间，其中x轴为无人机横向移动的方向，y轴为无人机纵向移动的方向，z轴为垂直于水平面的方向；建立好三维空间后，沿着z轴方向对oo1边进行s等分，过一个等分点做一个平行于aoa1o1的平面，最后可以得到s+1个平面。
[0118]
例如，利用栅格法对每一个平面进行划分，沿着x轴方向对oa边行进行m等分，沿着y轴of边进行n等分，最后每一个平面可以划分为m
×
n个栅格。这样，就可以得到每一个离散点的坐标值，将这些点集合设为p。空间中每一个点都有相对应的两个坐标值：等分点序号坐标和空间内具体位置坐标。通过这两个坐标，空间中的任意一个节点都可以用数学方法表示出来。
[0119]
在步骤a2中，对狼群算法参数信息进行初始化。起点ps，终点pf，定义n条从起点到终点的路径，探狼的比例因子α，步长因子c，最大游走限制次数tmax，距离判定因子ω，群体
更新比例因子β。
[0120]
在步骤a3中，计算狼群中每个人工狼的适应度f(xi)，并对适应度进行排序。选择具有最优适应度值的狼为头狼，s
num
个探狼，并进行游走。
[0121]
例如，游走的位置判定为：
[0122][0123]
p(p＝1,2,...,h)为方向。
[0124]
在步骤a3.1中，此时探狼所感知的气味浓度即适应度为yi；自主决策后沿着气味浓度最大且大于当前位置yi的方向向前移动一步；重复执行此步骤，不断向前进行更新，直到某一探狼的适应度大于头狼或者达到最大的游走次数限制。
[0125]
在步骤a4中，狼群进行奔袭行为和召唤行为。在奔袭过程中，以固定值确定距离判定因子ω的方式比较单一，取值大小影响wpa的收敛速度，值增加会加速收敛，但值过大的话将导致猛狼难以进入围攻行为。
[0126]
针对这种情况，可以对距离判定因子ω进行改进，确保f(xi,ω)符合拉普拉斯概率密度函数变化。
[0127]
在步骤a5中，选取头狼的位置为猎物的位置，对猎物进行围攻；更新参与围攻行为的人工狼的位置。若idx超出了变化范围，则设置其为边界值。
[0128]
例如，位置更新公式可以为：
[0129][0130]
为人工狼i(包括猛狼和探狼)在第d维空间中采取围攻行为时的攻击步长。
[0131]
在步骤a6中，按照头狼产生规则更新头狼的位置，再按照狼群更新机制对整个群体进行更新，去除狼群中最差的r匹人工狼，同时随机产生r匹人工狼。
[0132]
例如，r的取值为之间的随机整数。
[0133]
在步骤a7中，判断x
id
的位置是否满足不在障碍内，且它与相邻两点的连线不经过障碍的条件。若满足，则取x
id
为第i匹人工狼的位置；否则随机选取一个满足条件的点为第i匹人工狼的位置。
[0134]
在步骤a8中，判断是否符合终止条件，若不符合，则转到步骤2；若符合跳出循环，记录头狼的位置，即最优的轨迹。
[0135]
当狼群算法符合终止条件后，跳出，得到一个阶段最优解s＝{x1，x2，...，xn}，s表示一条路径，路径上相邻的两个点xi，xj为连接关系，接下来转入蚁群算法。
[0136]
在步骤b1中，设置蚁群算法参数。
[0137]
例如，蚂蚁的数量为m，节点i与节点j之间的距离为dij(ij＝12..n)。t时刻i与j连接路径上的信息素浓度为τ
ij
(t)，表示在时刻t时的信息素数量。
[0138]
例如，信息素初始值增量δτ
ij
(0)为狼群算法搜索积累。δτ
ij
(0)的计算方式如下：通过狼群算法得到的阶段最优解s，对此路径上任意相邻2个途径点xi、xj的连接赋予信息素值增量，取值为1；对于没有连接的，增量值为0。
[0139]
例如，信息素启发因子α表示之前遗留的信息素对下一位置的影响程度。期望值启发因子β表示启发信息对下一位置的影响程度。信息素挥发因子f(p)，并将禁忌表设置为空。
[0140]
在步骤b2中，在巡检的初始点蚂蚁开始进行巡检，并通过转移概率判断下一访问点，更新禁忌表、未访问节点列表和允许访问的节点列表。计算转移概率
[0141]
在步骤b3中，根据动态信息素更新规则，对蚁群算法迭代过程中的信息素挥发因子进行动态变化。
[0142]
例如，找出每次迭代后的优质蚂蚁与最差蚂蚁对其进行加强与削弱；对寻找到最优路径的蚂蚁信息素增强，增强最优蚂蚁对下一次迭代的引导能力；对寻找到最差路径的蚂蚁信息素进行减弱，减弱最差蚂蚁对下一次迭代的影响，从而有助于找到全局最优解。
[0143]
例如，信息素更新方式以及动态信息素挥发因子计算方式如下：
[0144]
τ
ij
(t+1)＝(1-f(p))τ
ij
(t)+δτ
ij
(t+1)
[0145][0146]
在步骤b4中，对所有蚂蚁位置进行判断；如果已达到终点，则进行记录，包括每只蚂蚁的路径长度，以及对应的拐点数，并找出当前迭代的最优路径，以长度最短优先，拐点数最少为次优先的评价标准；若未达到，则根据转移概率判断下一访问点；
[0147]
在步骤b5中，判断是否达到最大迭代次数，若已达到，则输出最优解，算法结束；否则重复进行步骤b2，重新寻找新的路线。
[0148]
上述实施例中，对狼群算法的距离判定因子ω进行动态调整。根据狼群算法特点，使ω在搜索前、后期较小，中期较大的动态变化方式，加速中期的搜索速度，使后期更容易进入围攻行为，加快了算法后期的收敛速度，弥补了以固定值方式设置的ω太小导致的算法收敛慢，过大导致人工狼难以进入围攻行为，缺少精细化搜索的不足。
[0149]
上述实施例中，对蚁群算法的信息素挥发因子做了改进，对优质蚂蚁与最差蚂蚁分别对其进行加强与削弱，充分发挥蚁群算法的正反馈效应，使其寻找的最优解更加准确，同时变信息素挥发因子可以平衡全局搜索能力与局部搜索能力，使得算法更快向最优解收敛。
[0150]
图4示出本公开的路径规划装置的一些实施例的框图。
[0151]
如图4所示，路径规划装置4包括：配置单元41，用于根据狼群算法的不同路径搜索阶段，配置距离判定因子，距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，第二路径搜索阶段位于第一路径搜索阶段和第三路径搜索阶段之间；规划单元42，用于根据距离判定因子，利用狼群算法规划第一路径。
[0152]
在一些实施例中，配置单元41根据人工狼的当前位置、固定距离判定因子，确定动态距离判定因子作为距离判定因子。
[0153]
在一些实施例中，配置单元41根据位置参数和尺度参数确定动态距离判定因子，动态距离判定因子与当前位置与位置参数的差值的绝对值负相关，与尺度参数负相关。
[0154]
在一些实施例中，配置单元41根据第一路径中各节点之间是否具有连接关系，配
置第一路径中各节点之间的信息素浓度；规划单元根据信息素浓度和第一路径，利用蚁群算法规划第二路径。
[0155]
在一些实施例中，配置单元41根据各蚂蚁在当前次迭代过程中寻找到的路径的质量，确定信息素挥发因子，信息素挥发因子用于增强寻找到当前次迭代过程中的最优路径的蚂蚁对下一次迭代过程的影响，减弱寻找到当前次迭代过程中的最差路径的蚂蚁对下一次迭代过程的影响。
[0156]
在一些实施例中，在当前次迭代过程中寻找到的路径的质量越高的蚂蚁的信息素挥发因子越大。
[0157]
在一些实施例中，配置单元41配置第一随机数和第二随机数，第一随机数小于第二随机数；根据第二随机数，确定优劣程度等于第一质量参数的蚂蚁的信息素挥发因子，第一质量参数对应于寻找到当前次迭代过程中的最优路径的蚂蚁的质量；根据第一随机数，确定优劣程度等于第二质量参数的蚂蚁的信息素挥发因子，第二质量参数对应于寻找到当前次迭代过程中的最差路径的蚂蚁的质量，第一质量参数大于第二质量参数；根据第一随机数和第二随机数的均值，确定其他蚂蚁的信息素挥发因子。
[0158]
在一些实施例中，规划单元42根据狼群算法中当前所有可以连通的两个节点之间的距离之和，确定狼群算法的游走行为的适应度；根据适应度，规划第一路径。
[0159]
在一些实施例中，规划单元42利用栅格法对待规划路径的空间进行建模，根据建模结果，规划第一路径。
[0160]
图5示出本公开的路径规划装置的另一些实施例的框图。
[0161]
如图5所示，该实施例的路径规划装置5包括：存储器51以及耦接至该存储器51的处理器52，处理器52被配置为基于存储在存储器51中的指令，执行本公开中任意一个实施例中的路径规划方法。
[0162]
其中，存储器51例如可以包括系统存储器、固定非易失性存储介质等。系统存储器例如存储有操作系统、应用程序、引导装载程序boot loader、数据库以及其他程序等。
[0163]
图6示出本公开的路径规划装置的又一些实施例的框图。
[0164]
如图6所示，该实施例的路径规划装置6包括：存储器610以及耦接至该存储器610的处理器620，处理器620被配置为基于存储在存储器610中的指令，执行前述任意一个实施例中的路径规划方法。
[0165]
存储器610例如可以包括系统存储器、固定非易失性存储介质等。系统存储器例如存储有操作系统、应用程序、引导装载程序boot loader以及其他程序等。
[0166]
路径规划装置6还可以包括输入输出接口630、网络接口640、存储接口650等。这些接口630、640、650以及存储器610和处理器620之间例如可以通过总线660连接。其中，输入输出接口630为显示器、鼠标、键盘、触摸屏、麦克、音箱等输入输出设备提供连接接口。网络接口640为各种联网设备提供连接接口。存储接口650为sd卡、u盘等外置存储设备提供连接接口。
[0167]
本领域内的技术人员应当明白，本公开的实施例可提供为方法、系统、或计算机程序产品。因此，本公开可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本公开可采用在一个或多个其中包含有计算机可用程序代码的计算机可用非瞬时性存储介质包括但不限于磁盘存储器、cd-rom、光学存储器等上实施的计算
机程序产品的形式。
[0168]
至此，已经详细描述了根据本公开的路径规划方法、路径规划装置和非易失性计算机可读存储介质。为了避免遮蔽本公开的构思，没有描述本领域所公知的一些细节。本领域技术人员根据上面的描述，完全可以明白如何实施这里公开的技术方案。
[0169]
可能以许多方式来实现本公开的方法和系统。例如，可通过软件、硬件、固件或者软件、硬件、固件的任何组合来实现本公开的方法和系统。用于方法的步骤的上述顺序仅是为了进行说明，本公开的方法的步骤不限于以上具体描述的顺序，除非以其它方式特别说明。此外，在一些实施例中，还可将本公开实施为记录在记录介质中的程序，这些程序包括用于实现根据本公开的方法的机器可读指令。因而，本公开还覆盖存储用于执行根据本公开的方法的程序的记录介质。
[0170]
虽然已经通过示例对本公开的一些特定实施例进行了详细说明，但是本领域的技术人员应该理解，以上示例仅是为了进行说明，而不是为了限制本公开的范围。本领域的技术人员应该理解，可在不脱离本公开的范围和精神的情况下，对以上实施例进行修改。本公开的范围由所附权利要求来限定。

技术特征：
1.一种路径规划方法，包括：根据狼群算法的不同路径搜索阶段，配置距离判定因子，所述距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，所述第二路径搜索阶段位于所述第一路径搜索阶段和所述第三路径搜索阶段之间；根据所述距离判定因子，利用所述狼群算法规划第一路径。2.根据权利要求1所述的路径规划方法，其中，所述配置距离判定因子包括：根据人工狼的当前位置、固定距离判定因子，确定动态距离判定因子作为所述距离判定因子。3.根据权利要求2所述的路径规划方法，其中，所述确定动态距离判定因子包括：根据位置参数和尺度参数确定所述动态距离判定因子，所述动态距离判定因子与所述当前位置与所述位置参数的差值的绝对值负相关，与所述尺度参数负相关。4.根据权利要求1-3任一项所述的路径规划方法，还包括：根据所述第一路径中各节点之间是否具有连接关系，配置所述第一路径中各节点之间的信息素浓度；根据所述信息素浓度和所述第一路径，利用蚁群算法规划第二路径。5.根据权利要求4所述的路径规划方法，其中，所述利用蚁群算法规划第二路径包括：根据各蚂蚁在当前次迭代过程中寻找到的路径的质量，确定信息素挥发因子，所述信息素挥发因子用于增强寻找到所述当前次迭代过程中的最优路径的蚂蚁对下一次迭代过程的影响，减弱寻找到所述当前次迭代过程中的最差路径的蚂蚁对下一次迭代过程的影响。6.根据权利要求5所述的路径规划方法，其中，在所述当前次迭代过程中寻找到的路径的质量越高的蚂蚁的信息素挥发因子越大。7.根据权利要求5所述的路径规划方法，其中，所述确定信息素挥发因子包括：配置第一随机数和第二随机数，所述第一随机数小于所述第二随机数；根据所述第二随机数，确定优劣程度等于第一质量参数的蚂蚁的信息素挥发因子，所述第一质量参数对应于寻找到所述当前次迭代过程中的最优路径的蚂蚁的质量；根据所述第一随机数，确定优劣程度等于第二质量参数的蚂蚁的信息素挥发因子，所述第二质量参数对应于寻找到所述当前次迭代过程中的最差路径的蚂蚁的质量，所述第一质量参数大于所述第二质量参数；根据所述第一随机数和所述第二随机数的均值，确定其他蚂蚁的信息素挥发因子。8.根据权利要求1-3任一项所述的路径规划方法，其中，所述利用所述狼群算法规划第一路径包括：根据所述狼群算法中当前所有可以连通的两个节点之间的距离之和，确定所述狼群算法的游走行为的适应度；根据所述适应度，规划所述第一路径。9.根据权利要求1-3任一项所述的路径规划方法，还包括：利用栅格法对待规划路径的空间进行建模；根据建模结果，规划所述第一路径。10.一种路径规划装置，包括：
配置单元，用于根据狼群算法的不同路径搜索阶段，配置距离判定因子，所述距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，所述第二路径搜索阶段位于所述第一路径搜索阶段和所述第三路径搜索阶段之间；规划单元，用于根据所述距离判定因子，利用所述狼群算法规划第一路径。11.根据权利要求10所述的路径规划装置，其中，所述配置单元根据所述第一路径中各节点之间是否具有连接关系，配置所述第一路径中各节点之间的信息素浓度；所述规划单元根据所述信息素浓度和所述第一路径，利用蚁群算法规划第二路径。12.根据权利要求10或11所述的路径规划装置，其中，所述规划单元利用栅格法对待规划路径的空间进行建模，根据建模结果，规划所述第一路径。13.一种路径规划装置，包括：存储器；和耦接至所述存储器的处理器，所述处理器被配置为基于存储在所述存储器中的指令，执行权利要求1-9任一项所述的路径规划方法。14.一种非易失性计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现权利要求1-9任一项所述的路径规划方法。

技术总结
本公开涉及一种路径规划方法、装置和非易失性计算机可读存储介质，涉及路径规划技术领域。该路径规划方法，包括：根据狼群算法的不同路径搜索阶段，配置距离判定因子，距离判定因子使得第一路径搜索阶段和第三路径搜索阶段的搜索速度小于第二路径搜索阶段的搜索速度，第二路径搜索阶段位于第一路径搜索阶段和第三路径搜索阶段之间；根据距离判定因子，利用狼群算法规划第一路径。本公开的技术方案能够提高路径规划的效果。提高路径规划的效果。提高路径规划的效果。


技术研发人员：邢东旭 刘倩 程秀菊 刘姗姗 许晓莹
受保护的技术使用者：中国电信股份有限公司
技术研发日：2023.08.23
技术公布日：2023/10/15