一种路径规划方法、装置和自动化巡检设备与流程

1.本公开涉及计算机技术领域，特别涉及一种路径规划方法、装置和自动化巡检设备。


背景技术：

2.自动化巡检是一项应用于企业智能化管理的技术，可以代替或辅助人工进行巡检。与人工巡检相比，在降低工人劳动强度、提升运营水平、提高企业现代化科学管理和数字化管理、危险环境作业等方面发挥着重要的作用。
3.在自动化巡检中，如何进行路径规划是一个关键问题。


技术实现要素：

4.本公开提供了一种路径规划方法、装置和自动化巡检设备。
5.根据本公开的第一方面，提出了一种路径规划方法，包括：根据第一仿生学算法，确定从起始点至目标点的第一规划路径；对蚁群算法中的参数进行初始化，所述参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量，在所述初始化时，所述信息素增量根据所述第一规划路径确定；根据所述信息素浓度确定多条候选路径，并根据所述多条候选路径确定当前适应度最大的路径；根据所述多条候选路径更新所述信息素增量，以得到更新后的信息素增量；根据所述更新后的信息素增量和信息素挥发因子，更新所述信息素浓度，以得到更新后的信息素浓度，所述信息素挥发因子与迭代次数或迭代时间相关；迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由所述起始点至所述目标点的第二规划路径。
6.在一些实施例中，所述信息素挥发因子满足：在所述迭代时间小于第一时间阈值的情况下，所述信息素挥发因子为第一常数值；在所述迭代时间大于第二时间阈值的情况下，所述信息素挥发因子为第二常数值，所述第二时间阈值大于所述第一时间阈值，所述第二常数值小于所述第一常数值；在所述迭代时间大于或等于第一时间阈值、且小于或等于第二时间阈值的情况下，所述信息素挥发因子介于所述第二常数值和所述第一常数值之间、且所述信息素挥发因子与所述迭代时间呈负相关。
7.在一些实施例中，所述信息素挥发因子满足：在所述迭代次数小于第一次数阈值的情况下，所述信息素挥发因子为第三常数值；在所述迭代次数大于第二次数阈值的情况下，所述信息素挥发因子为第四常数值，所述第二次数阈值大于所述第一次数阈值，所述第四常数值小于所述第三常数值；在所述迭代次数大于或等于第一次数阈值、且小于或等于第二次数阈值的情况下，所述信息素挥发因子介于所述第四常数值和所述第三常数值之间、且所述信息素挥发因子与所述迭代次数呈负相关。
8.在一些实施例中，所述第一时间阈值和所述第二时间阈值根据第一随机数确定，或者，所述第一次数阈值和所述第二次数阈值根据第二随机数确定。
9.在一些实施例中，所述信息素挥发因子与所述迭代时间或所述迭代次数呈负指数
关系。
10.在一些实施例中，所述第一仿生学算法包括蜂群算法。
11.在一些实施例中，所述根据第一仿生学算法，确定由起始点至目标点的第一规划路径包括：在蜂群算法的参数初始化阶段，根据高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成多个第一候选解；根据所述多个第一候选解，确定由起始点至目标点的第一规划路径。
12.在一些实施例中，根据所述多个第一候选解，确定由起始点至目标点的第一规划路径包括：在引领蜂和跟随蜂阶段，在所述多个第一候选解中的至少一部分第一候选解的邻域内生成第二候选解，并且，在所述第二候选解的适应度大于所述至少一部分第一候选解的情况下，根据所述第二候选解对所述至少一部分第一候选解进行更新；在存在至少一个第一候选解连续n次都没有被更新的情况下，根据所述高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成第三候选解，并基于所述第三候选解更新所述至少一个第一候选解，n为大于1的整数。
13.根据本公开的第二方面，提出了一种路径规划装置，包括：第一规划模块，被配置为根据第一仿生学算法，确定从起始点至目标点的第一规划路径；第二规划模块，包括：初始化单元，被配置为对蚁群算法中的参数进行初始化，所述参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量，在所述初始化时，所述信息素增量根据所述第一规划路径确定；第一确定单元，被配置为根据所述信息素浓度确定多条候选路径，并根据所述多条候选路径确定当前适应度最大的路径；第一更新单元，被配置为根据所述多条候选路径更新所述信息素增量，以得到更新后的信息素增量；第二更新单元，被配置为根据所述更新后的信息素增量和信息素挥发因子，更新所述信息素浓度，以得到更新后的信息素浓度，所述信息素挥发因子与迭代次数或迭代时间相关；第二确定单元，被配置为迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由所述起始点至所述目标点的第二规划路径。
14.根据本公开的第三方面，提出了一种自动化巡检设备，包括如前所述的路径规划装置。
15.根据本公开的第四方面，提出一种电子设备，包括：存储器；以及，耦接至所述存储器的处理器，所述处理器被配置为基于存储在所述存储器的指令执行如上述的路径规划方法。
16.根据本公开的第五方面，提出一种计算机可读存储介质，其上存储有计算机程序指令，该指令被处理器执行时实现路径规划方法。
17.通过以下参照附图对本公开的示例性实施例的详细描述，本公开的其它特征及其优点将会变得清楚。
附图说明
18.构成说明书的一部分的附图描述了本公开的实施例，并且连同说明书一起用于解释本公开的原理。
19.参照附图，根据下面的详细描述，可以更加清楚地理解本公开。
20.图1为根据本公开一些实施例的路径规划方法的流程示意图。
21.图2为根据本公开一些实施例的栅格化地图的示意图。
22.图3为根据本公开另一些实施例的路径规划方法的流程示意图。
23.图4为根据本公开一些实施例的路径规划装置的结构示意图。
24.图5为根据本公开一些实施例的第二规划模块的结构示意图。
25.图6为根据本公开一些实施例的自动化巡检设备的结构示意图。
26.图7为根据本公开一些实施例的电子设备的结构示意图。
27.图8为根据本公开一些实施例的计算机系统的结构示意图。
具体实施方式
28.现在将参照附图来详细描述本公开的各种示例性实施例。应注意到：除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对布置、数字表达式和数值不限制本公开的范围。
29.同时，应当明白，为了便于描述，附图中所示出的各个部分的尺寸并不是按照实际的比例关系绘制的。
30.以下对至少一个示例性实施例的描述实际上仅仅是说明性的，决不作为对本公开及其应用或使用的任何限制。
31.对于相关领域普通技术人员已知的技术、方法和设备可能不作详细讨论，但在适当情况下，所述技术、方法和设备应当被视为授权说明书的一部分。
32.在这里示出和讨论的所有示例中，任何具体值应被解释为仅仅是示例性的，而不是作为限制。因此，示例性实施例的其它示例可以具有不同的值。
33.应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步讨论。
34.为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本公开进一步详细说明。
35.相关技术中，可利用仿生学算法进行路径规划。但是，单一的仿生学算法有各自的局限性，优化空间有限，路径规划效果不理想。
36.鉴于此，本公开提供了一种路径规划方法和装置，通过将第一仿生学算法与蚁群算法相融合，利用第一仿生学算法确定的第一规划路径确定初始的信息素增量，避免了迭代初期对路径的盲目搜索，有助于更快地寻找到最优路径。与此同时，通过令信息素挥发因子与迭代时间或迭代次数相关，实现了信息素挥发因子随迭代时间或迭代次数的动态调整，有助于在迭代前期加快算法搜索速度，在迭代后期加快算法收敛速度，从而提高路径规划效果。
37.图1为根据本公开一些实施例的路径规划方法的流程示意图。如图1所示，路径规划方法包括步骤s110至步骤s160。
38.在步骤s110中，根据第一仿生学算法，确定从起始点至目标点的第一规划路径。
39.在一些实施例中，第一仿生学算法为蜂群算法。具体实施时，第一仿生学算法也可采用除蚁群算法之外的其他仿生学算法。
40.在一些实施例中，根据蜂群算法确定第一规划路径包括：在蜂群算法的参数初始化阶段，根据高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成多个第一候
选解；根据多个第一候选解，确定由起始点至目标点的第一规划路径。
41.在一些实施方式中，蜂群算法的参数初始化包括：对蜂群算法中的种群规模、第一候选解(或者称为初始解)的个数及维数、最大限制次数、最大迭代次数等参数进行初始化；根据高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成多个第一候选解；计算所述多个第一候选解中每一个的适应度。
42.例如，根据如下公式生成多个第一候选解：
[0043][0044]
其中，表示第i个第一候选解的第j个维度，表示候选解的第j个维度的下限值，表示候选解的第j个维度的上限值，n(μ,σ2)表示高斯概率密度函数。
[0045]
在一些实施例中，根据多个第一候选解确定第一规划路径包括：在多个第一候选解的基础上，通过引领蜂、跟随蜂、侦察蜂搜索新的候选解，并从候选解中选取适应度最大的候选解。在经过多次迭代后，将通过蜂群算法选取的适应度最大的候选解作为第一规划路径。
[0046]
在一些实施方式中，在多个第一候选解的基础上，通过引领蜂、跟随蜂、侦察蜂搜索新的候选解，并从候选解中选取适应度最大的候选解包括：在引领蜂和跟随蜂阶段，在多个第一候选解中的至少一部分第一候选解的邻域内生成第二候选解，并且，在第二候选解的适应度大于所述至少一部分第一候选解的情况下，根据第二候选解对所述至少一部分第一候选解进行更新；在存在至少一个第一候选解连续n(n为最大限制次数)次都没有被更新的情况下，表明进入侦察蜂阶段，在侦察蜂阶段，根据高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成第三候选解，并基于第三候选解更新所述至少一个第一候选解，n为大于1的整数；记录所有第一候选解中适应度最大的候选解。
[0047]
在本公开一些实施例中，通过根据高斯概率密度函数、候选解的上限值和下限值确定路径的初始解，弥补了以随机值方式生成初始解容易使算法陷入局部最优的缺点，提升了蜂群算法的全局搜索能力以及蜂群算法的搜索效率。进一步，通过在侦察蜂阶段，根据高斯概率密度函数、候选解的上限值和下限值生成新的候选解，弥补了以随机值方式生成新的候选解容易使蜂群算法陷入局部最优的缺点，进一步提升了蜂群算法的全局搜索能力以及蜂群算法的搜索效率。
[0048]
在一些实施例中，在对第一仿生学算法的参数进行初始化之前，还包括环境建模。例如，在自动化巡检场景中，对自动化巡检设备(例如执行自动化巡检任务的机器人)的巡检环境进行建模。通过环境建模，便于确定后续进行路径规划的搜索空间。
[0049]
在一些实施例中，采用栅格法、自由空间法、可视图法或拓扑法，进行环境建模。
[0050]
在步骤s120中，对蚁群算法中的参数进行初始化。
[0051]
其中，蚁群算法中的参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量。
[0052]
例如，蚁群算法中的参数初始化包括：设置蚁群算法中的蚂蚁数量m、节点i与节点j之间的距离d
ij
、信息素浓度、信息素增量、信息素启发因子、期望值启发因子等参数。其中，信息素启发因子表示之前遗留的信息素对下一位置的影响程度，期望值启发因子表示启发
信息对下一位置的影响程度。
[0053]
其中，在蚁群算法的参数初始化时，信息素增量根据第一规划路径确定。例如，根据如下方式初始化信息素增量：将搜索空间中出现在第一规划路径上的相邻两个节点之间的路段的信息素增量设为1，将搜索空间中其他相邻节点之间的路段的信息素增量设为0。其中，搜索空间可根据环境建模得到的地图确定。
[0054]
在本公开实施例中，通过根据第一规划路径确定信息素增量的初始值，弥补了蚁群算法迭代初期对路径的盲目搜索，有助于更快地寻找到最优路径。
[0055]
在步骤s130中，根据信息素浓度确定多条候选路径，并根据多条候选路径确定当前适应度最大的路径。
[0056]
在一些实施例中，对于设置的多只蚂蚁中的每一只来说，根据信息素浓度和节点间的距离计算节点间的转移概率；根据节点间的转移概率，以轮盘赌方式选择下一节点，直至到达终点。这样一来，得到了多条候选路径。计算多条候选路径中每一条的适应度，并从中选取当前适应度最大的路径。
[0057]
在步骤s140中，根据多条候选路径更新信息素增量，以得到更新后的信息素增量。
[0058]
在步骤s150中，根据更新后的信息素增量和信息素挥发因子，更新信息素浓度，以得到更新后的信息素浓度。
[0059]
其中，信息素挥发因子与迭代次数或迭代时间相关。
[0060]
在一些实施例中，信息素挥发因子与迭代次数或迭代时间呈负相关。例如，信息素挥发因子与迭代次数或迭代时间呈负指数关系。
[0061]
在另一些实施例中，信息素挥发因子满足：在迭代时间小于第一时间阈值的情况下，信息素挥发因子为第一常数值；在迭代时间大于第二时间阈值的情况下，信息素挥发因子为第二常数值，第二时间阈值大于第一时间阈值，第二常数值小于第一常数值；在迭代时间大于或等于第一时间阈值、且小于或等于第二时间阈值的情况下，信息素挥发因子介于第二常数值和第一常数值之间、且信息素挥发因子与迭代时间呈负相关。
[0062]
在一些实施方式中，第一时间阈值、第二时间阈值为预先设置的常数。
[0063]
在另一些实施方式中，第一时间阈值、第二时间阈值根据第一随机数确定。
[0064]
例如，根据如下公式计算第一时间阈值和第二时间阈值：
[0065][0066][0067]
其中，t1表示第一时间阈值，t2表示第二时间阈值，h1表示第一随机数，在该示例中，第一随机数为大于0.5的整数。
[0068]
在再一些实施例中，信息素挥发因子满足：在迭代次数小于第一次数阈值的情况下，信息素挥发因子为第三常数值；在迭代次数大于第二次数阈值的情况下，信息素挥发因子为第四常数值，第二次数阈值大于第一次数阈值，第四常数值小于第三常数值；在迭代次数大于或等于第一次数阈值、且小于或等于第二次数阈值的情况下，信息素挥发因子介于第四常数值和第三常数值之间、且信息素挥发因子与迭代次数呈负相关。例如，信息素挥发
因子与迭代次数呈负指数关系。
[0069]
在一些实施方式中，第一次数阈值、第二次数阈值为预先设置的常数。
[0070]
在另一些实施方式中，第一次数阈值、第二次数阈值根据第二随机数确定。
[0071]
在本公开实施例中，通过令信息素挥发因子与迭代时间或迭代次数相关，实现了信息素挥发因子随迭代时间或迭代次数的动态调整。进一步，通过在迭代前期设置较大的信息素挥发因子，能够加快算法的搜索速度，在迭代后期设置较小的信息素挥发因子，能够使算法加快收敛，从而更好地平衡全局搜索能力与局部搜索能力，改善路径规划效果。
[0072]
在一些实施例中，根据如下公式更新信息素浓度：
[0073]
τ
ij
(t+1)＝(1-f(p))τ
ij
(t)+δτ
ij
(t+1)
[0074][0075]
其中，τ
ij
(t+1)表示更新后的信息素浓度，τ
ij
(t)表示更新前的信息素浓度，f(p)表示信息素挥发因子，δτ
ij
(t+1)表示更新后的信息素增量，表示通过步骤s130确定的多条候选路径中的第k条候选路径对应的信息素增量。
[0076]
在本公开实施例中，通过令信息素挥发因子与迭代时间或迭代次数相关，并通过以上公式对每次迭代得到的优质路径上的信息素浓度进行增强，对每次迭代得到的劣质路径上的信息素浓度进行削弱，能够更加充分地发挥蚁群算法的正反馈效应，更好地平衡全局搜索能力与局部搜索能力，改善路径规划效果。
[0077]
在步骤s160中，迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由起始点至目标点的第二规划路径。
[0078]
在本公开实施例中，通过将第一仿生学算法与蚁群算法相融合，利用第一仿生学算法确定的第一规划路径确定初始的信息素增量，避免了迭代初期对路径的盲目搜索，有助于更快地寻找到最优路径。与此同时，通过令信息素挥发因子与迭代时间或迭代次数相关，实现了信息素挥发因子随迭代时间或迭代次数的动态调整，有助于在迭代前期加快算法搜索速度，在迭代后期加快算法收敛速度，从而提高路径规划效果。
[0079]
图2为根据本公开一些实施例的栅格化地图的示意图。在本公开一些实施例中，利用栅格法来为智能机器人的巡检环境建立模型，建模结果参见图2。
[0080]
如图2所示，黑色栅格表示巡检环境中的障碍点(或者称为不可访问点)，白色栅格表示巡检环境中的可访问点。在一些实施例中，利用栅格的序号i和栅格的坐标(x，y)来表示一个栅格。在一些实施例中，栅格的坐标具体为栅格的中心点的坐标。
[0081]
图3为根据本公开另一些实施例的路径规划方法的流程示意图。如图3所示，路径规划方法包括步骤s301至步骤s318。其中，步骤s301至步骤s310为基于蜂群算法规划路径的子流程，步骤s311至步骤s318为基于蚁群算法规划路径的子流程。
[0082]
在步骤s301中，创建二维栅格地图。
[0083]
在一些实施例中，采用栅格法对自动化巡检设备的工作环境空间进行建模，从而得到栅格地图。如图2所示，栅格地图包括多种栅格，例如可访问点、障碍点、起始点和目标
点(或称为“终止点”)。
[0084]
在步骤s302中，初始化种群。
[0085]
在一些实施例中，步骤s302包括：对蜂群算法中的参数进行初始化，其中，蜂群算法中需要初始化的参数包括但不限于起始点、终止点、初始解的个数及维数、最大限制次数、最大迭代次数；计算各个初始解的适应度。其中，一个初始解表示一条由起始点至目标点的初始路径，初始解的个数表示初始路径的条数，初始解的维数表示初始路径上经过的节点的个数。
[0086]
例如，根据如下公式产生初始解：
[0087][0088]
其中，表示第i个初始解的第j个维度，表示候选解的第j个维度的下限值，表示候选解的第j个维度的上限值，n(μ,σ2)表示高斯概率密度函数。
[0089]
在步骤s303中，引领蜂搜索邻域内的解，并计算适应度值，采用贪心算法选择较好解。
[0090]
在一些实施例中，设置多个引领蜂(或者称为雇佣蜂)，令引领蜂在初始解的邻域范围内进行搜索，以产生新的解(即新的路径)。
[0091]
例如，根据如下公式搜索邻域内的解：
[0092]vid
＝x
id
+φ*(x
id-x
jd
)
[0093]
其中，v
id
表示在初始解x
id
的邻域内搜索产生的新的解，x
id
表示第i个初始解，x
jd
表示第j个初始解，φ表示在[-1.1]内服从均匀分布的随机数，用于控制解的生成范围。
[0094]
解的适应度反映了解的优劣程度。通常来说，解的适应度越高，表明这个解越优，即这条路径越优。
[0095]
在一些实施例中，根据如下公式计算解的适应度：
[0096]
fit＝1/d
[0097][0098]
其中，fit表示解(路径)的适应度，d|x
！
+xj|表示路径上相邻两个节点之间的距离，t表示路径上的节点数量。
[0099]
在计算得到引领蜂新产生的解的适应度之后，将引领蜂新产生的解的适应度与初始解的适应度进行比较。如果引领蜂新产生的解的适应度大于初始解的适应度，令新产生的解取代初始解；如果引领蜂新产生的解的适应度小于或等于初始解的适应度，保持初始解不变。
[0100]
在步骤s304中，计算得到的解被选择的概率。
[0101]
在蜂群算法中，跟随蜂(或称为观察蜂)以一定的概率选择引领蜂(或称为雇佣蜂)。换言之，跟随蜂(或称为观察蜂)以一定的概率选择引领蜂对应的解。
[0102]
在一些实施例中，根据如下公式计算得到的解被选择的概率：
[0103][0104]
其中，pi表示选择第i个解的概率，fiti表示第i个解的适应度，n是解的个数。
[0105]
在步骤s305中，跟随蜂采用轮盘赌方式选择引领蜂，在选择解的邻域搜索，计算适应度值，采用贪心法选择较好解。
[0106]
在蜂群算法中，跟随蜂(或称为观察蜂)采用轮盘赌方式选择引领蜂。换言之，跟随蜂(或称为观察蜂)采用轮盘赌方式选择引领蜂对应的解。
[0107]
在一些实施例中，跟随蜂采用轮盘赌方式选择引领蜂对应的解包括：生成一个在[-1,1]之间服从均匀分布的随机数；并将选择第i个解的概率pi与该随机数进行比较；如果pi大于该随机数，选择第i个解。
[0108]
在选择引领蜂对应的解之后，在选择的解的邻域内再进行搜索，以产生新的解，并将新产生的解的适应度与选择的解的适应度进行比较。如果跟随蜂新产生的解的适应度大于其选择的解的适应度，令新产生的解取代其选择的解；如果跟随蜂新产生的解的适应度小于或等于其选择的解的适应度，保持其选择的解不变。
[0109]
在步骤s306中，判断是否有被废弃的解。
[0110]
在一些实施例中，若一个解连续n次(n为最大限制次数)都没有被更新，则将该解作为需要被废弃的解。在存在需要被废弃的解的情况下，执行步骤s307和步骤s308；否则，执行步骤s08。
[0111]
在步骤s307中，引领蜂转为侦察蜂，在解空间随机搜索新的解。
[0112]
在一些实施例中，考虑到根据随机值确定的随机搜索解的随机性太强，将导致在搜索过程中容易陷入局部最优，难以得到全局最优路径。鉴于此，在本公开一些实施例中，根据高斯概率密度函数、解的上限值、以及解的下限值，随机搜索新的解。例如，在步骤s307中，采用步骤s302中生成初始解所用的公式，产生新的解。
[0113]
在步骤s308中，记录迄今为止最好的解。
[0114]
在步骤s309中，判断是否达到终止条件。
[0115]
在一些实施例中，终止条件为当前迭代次数达到最大迭代次数。在这些实施例中，步骤s309包括：判断当前迭代次数是否达到最大迭代次数。
[0116]
在步骤s309的判断结果为是的情况下，执行步骤s310；否则，再次执行步骤s303。
[0117]
在步骤s310中，输出阶段最优解。
[0118]
在该步骤中，将蜂群算法得到的阶段最优解作为第一规划路径。其中，第一规划路径用于初始化时确定蚁群算法中信息素增量。例如，第一规划路径表示为x＝{x1，x2，
…
，xn}。其中，x1，x2，
…
，xn表示该路径上依次经过的节点。
[0119]
在步骤s311中，设置参数。
[0120]
在该步骤中，设置蚁群算法中的参数。其中，需要设置的参数包括但不限于：蚂蚁的数量为m、相邻节点之间的距离、相邻节点之间的路段的信息素浓度、相邻节点之间的路段的信息素增量、信息素启发因子α，期望值启发因子β、以及信息素挥发因子。以及，在该步骤中，将禁忌表设置为空。其中，禁忌表用于记录蚂蚁走过的节点。
[0121]
在一些实施例中，在初始化时，根据第一规划路径确定信息素增量包括：将搜索空
间中出现在第一规划路径上的相邻两个节点之间的路段的信息素增量设为1，将搜索空间中其他相邻节点之间的路段的信息素增量设为0。
[0122]
在步骤s312中，在起始点放置蚂蚁寻找路线。
[0123]
在步骤s313中，根据转移概率选择下一节点。
[0124]
在一些实施例中，根据如下公式计算蚂蚁从当前节点i转移到节点j的概率:
[0125][0126]
其中，表示蚂蚁从当前节点i转移到节点j的概率，表示节点i与节点j之间的路段的信息素浓度的α次幂，表示节点i与节点j之间的路段的期望值的β次幂，α表示信息素启发因子，β表示期望因子，ak表示蚂蚁k下一步可访问的节点的列表，ak可根据所有可访问点的节点列表与蚂蚁k的禁忌表确定。
[0127]
其中，节点i与节点j之间的路段的期望值可根据如下公式确定：
[0128][0129][0130]
其中，η
ij
(t)表示节点i与节点j之间的路段的期望值，d
ij
(t)表示节点i与节点j之间的路段长度，i
x
和iy表示节点i的坐标，j
x
和jy表示节点j的坐标。
[0131]
在一些实施例中，根据上述公式计算蚂蚁从当前节点转移到另一节点的概率后，基于轮盘赌方式选择下一节点。接下来，根据蚂蚁选择的节点，更新禁忌表、未访问节点列表和允许访问的节点列表。迭代执行节点选择步骤、节点列表更新步骤，直至蚂蚁到达目标点。
[0132]
在步骤s314中，判断所有蚂蚁是否都到达终点。
[0133]
在步骤s314的判断结果为是的情况下，执行步骤s315；否则，执行步骤s313。
[0134]
在步骤s315中，对信息素增量、信息素浓度进行更新。
[0135]
在一些实施例中，根据多个蚂蚁确定的多条候选路径确定更新后的信息素增量；根据更新后的信息素增量、以及信息素挥发因子，确定更新后的信息素浓度。
[0136]
在一些实施例中，根据如下公式确定信息素挥发因子：
[0137]
[0138][0139]
其中，t表示迭代时间，f(ρ)表示信息素挥发因子，q1和q2表示两个随机数，ρ和c表示两个系数，且ρ∈[0.2,0.5]，q1∈[0,1]，q2∈[1,2]。
[0140]
在一些实施例中，根据如下公式对信息素增量、信息素浓度进行更新：
[0141][0142]
τ
ij
(t+1)＝(1-f(p))τ
ij
(t)+δτ
ij
(t+1)
[0143]
其中，τ
ij
(t+1)表示更新后的信息素浓度，τ
ij
(t)表示更新前的信息素浓度，f(p)表示信息素挥发因子，δτ
ij
(t+1)表示更新后的信息素增量，表示确定的多条候选路径中的第k条候选路径对应的信息素增量。
[0144]
在步骤s316中，记录各蚂蚁路径长度并更新最优路径。
[0145]
在一些实施例中，在蚁群算法中，根据路径的长度确定路径的适应度。例如，将路径的长度的倒数作为路径的适应度。在该示例中，路径的长度越短，则路径的适应度越大。从多条候选路径中选取长度最短的候选路径，作为当前的最优路径。
[0146]
在步骤s317中，判断是否达到最大迭代次数。
[0147]
在该步骤中，判断蚁群算法的当前迭代次数是否达到最大迭代次数。在步骤s317的判断结果为是的情况下，执行步骤s318；否则，再次执行步骤s312。
[0148]
在步骤s318中，输出最优路径。
[0149]
在该步骤中，将最终得到的适应度最大的路径作为最优路径(即第二规划路径)，并将最优路径进行输出。
[0150]
在本公开实施例中，通过将蜂群算法与蚁群算法相融合，利用蜂群算法得到的规划路径确定初始的信息素增量，避免了蚁群算法迭代初期对路径的盲目搜索，有助于更快地寻找到最优路径。与此同时，通过对蜂群算法中的搜索公式进行调整，引入高斯概率密度函数产生新的搜索解，弥补了蜂群算法中以随机值方式进行搜索容易陷入局部最优解的缺点，提升了蜂群算法的全局搜索能力和搜索效率；通过令蚁群算法中的信息素挥发因子与迭代时间或迭代次数相关，实现了信息素挥发因子随迭代时间或迭代次数的动态调整，有助于在蚁群算法迭代前期加快算法搜索速度，在蚁群算法迭代后期加快算法收敛速度，从而提高路径规划效果。
[0151]
图4为根据本公开一些实施例的路径规划装置的结构示意图。如图4所示，路径规划装置400包括第一规划模块410和第二规划模块420。
[0152]
第一规划模块410，被配置为根据第一仿生学算法，确定从起始点至目标点的第一规划路径。其中，第一规划路径用于确定蚁群算法中的信息素增量的初始值。
[0153]
第二规划模块420，被配置为根据第一路径规划，利用蚁群算法，确定从起始点至目标点的第二规划路径。
[0154]
以下结合图5对根据本公开一些实施例的第二规划模块的结构进行详细说明。如图5所示，第二规划模块420包括初始化单元421、第一确定单元422、第一更新单元423、第二更新单元424、第二确定单元425。
[0155]
初始化单元421，被配置为对蚁群算法中的参数进行初始化。其中，所述参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量。在初始化时，信息素增量根据第一规划路径确定。
[0156]
第一确定单元422，被配置为根据信息素浓度确定多条候选路径，并根据多条候选路径确定当前适应度最大的路径。
[0157]
第一更新单元423，被配置为根据多条候选路径更新所述信息素增量，以得到更新后的信息素增量。
[0158]
第二更新单元424，被配置为根据更新后的信息素增量和信息素挥发因子，更新所述信息素浓度，以得到更新后的信息素浓度。其中，信息素挥发因子与迭代次数或迭代时间相关。
[0159]
第二确定单元425，被配置为迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由所述起始点至所述目标点的第二规划路径。
[0160]
在本公开实施例中，通过以上装置，能够将第一仿生学算法与蚁群算法相融合，利用第一仿生学算法确定的第一规划路径确定初始的信息素增量，避免了迭代初期对路径的盲目搜索，有助于更快地寻找到最优路径。与此同时，通过令信息素挥发因子与迭代时间或迭代次数相关，实现了信息素挥发因子随迭代时间或迭代次数的动态调整，有助于在迭代前期加快算法搜索速度，在迭代后期加快算法收敛速度，从而提高路径规划效果。
[0161]
图6为根据本公开一些实施例的自动化巡检设备的结构示意图。如图6所示，自动化巡检设备600包括路径规划装置610。
[0162]
路径规划装置610，被配置为：根据第一仿生学算法，确定从起始点至目标点的第一规划路径；对蚁群算法中的参数进行初始化，所述参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量，在初始化时，信息素增量根据所述第一规划路径确定；根据信息素浓度确定多条候选路径，并根据多条候选路径确定当前适应度最大的路径；根据多条候选路径更新信息素增量，以得到更新后的信息素增量；根据更新后的信息素增量和信息素挥发因子，更新信息素浓度，以得到更新后的信息素浓度，信息素挥发因子与迭代次数或迭代时间相关；迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由起始点至目标点的第二规划路径。
[0163]
在本公开实施例中，通过以上自动化巡检设备，能够更高效地确定更优的自动化巡检路径，从而改善自动化巡检设备的巡检效果。
[0164]
图7为根据本公开一些实施例的电子设备的结构示意图。
[0165]
如图7所示，电子设备700包括存储器710；以及耦接至该存储器710的处理器720。存储器710用于存储执行路径规划方法对应实施例的指令。处理器720被配置为基于存储在存储器710中的指令，执行本公开中任意一些实施例中的路径规划方法。
[0166]
图8为根据本公开一些实施例的计算机系统的结构示意图。
[0167]
如图8所示，计算机系统800可以通用计算设备的形式表现。计算机系统800包括存储器810、处理器820和连接不同系统组件的总线830。
[0168]
存储器810例如可以包括系统存储器、非易失性存储介质等。系统存储器例如存储有操作系统、应用程序、引导装载程序(boot loader)以及其他程序等。系统存储器可以包括易失性存储介质，例如随机存取存储器(ram)和/或高速缓存存储器。非易失性存储介质例如存储有执行中的至少一种路径规划方法的对应实施例的指令。非易失性存储介质包括但不限于磁盘存储器、光学存储器、闪存等。
[0169]
处理器820可以用通用处理器、数字信号处理器(dsp)、应用专用集成电路(asic)、现场可编程门阵列(fpga)或其它可编程逻辑设备、分立门或晶体管等分立硬件组件方式来实现。相应地，诸如第一规划模块、第二规划模块等的每个模块，可以通过中央处理器(cpu)运行存储器中执行相应步骤的指令来实现，也可以通过执行相应步骤的专用电路来实现。
[0170]
总线830可以使用多种总线结构中的任意总线结构。例如，总线结构包括但不限于工业标准体系结构(isa)总线、微通道体系结构(mca)总线、外围组件互连(pci)总线。
[0171]
计算机系统800这些接口840、850、860以及存储器810和处理器820之间可以通过总线830连接。输入输出接口840可以为显示器、鼠标、键盘等输入输出设备提供连接接口。网络接口850为各种联网设备提供连接接口。存储接口860为软盘、u盘、sd卡等外部存储设备提供连接接口。
[0172]
这里，参照根据本公开实施例的方法、装置和计算机程序产品的流程图和/或框图描述了本公开的各个方面。应当理解，流程图和/或框图的每个框以及各框的组合，都可以由计算机可读程序指令实现。
[0173]
这些计算机可读程序指令可提供到通用计算机、专用计算机或其他可编程装置的处理器，以产生一个机器，使得通过处理器执行指令产生实现在流程图和/或框图中一个或多个框中指定的功能的装置。
[0174]
这些计算机可读程序指令也可存储在计算机可读存储器中，这些指令使得计算机以特定方式工作，从而产生一个制造品，包括实现在流程图和/或框图中一个或多个框中指定的功能的指令。
[0175]
本公开可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。
[0176]
通过上述实施例中的路径规划方法、装置和自动化巡检设备，能够改善路径规划效果。
[0177]
至此，已经详细描述了根据本公开的路径规划方法、装置和自动化巡检设备。为了避免遮蔽本公开的构思，没有描述本领域所公知的一些细节。本领域技术人员根据上面的描述，完全可以明白如何实施这里公开的技术方案。

技术特征：
1.一种路径规划方法，包括：根据第一仿生学算法，确定从起始点至目标点的第一规划路径；对蚁群算法中的参数进行初始化，所述参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量，在所述初始化时，所述信息素增量根据所述第一规划路径确定；根据所述信息素浓度确定多条候选路径，并根据所述多条候选路径确定当前适应度最大的路径；根据所述多条候选路径更新所述信息素增量，以得到更新后的信息素增量；根据所述更新后的信息素增量和信息素挥发因子，更新所述信息素浓度，以得到更新后的信息素浓度，所述信息素挥发因子与迭代次数或迭代时间相关；迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由所述起始点至所述目标点的第二规划路径。2.根据权利要求1所述的路径规划方法，其中，所述信息素挥发因子满足：在所述迭代时间小于第一时间阈值的情况下，所述信息素挥发因子为第一常数值；在所述迭代时间大于第二时间阈值的情况下，所述信息素挥发因子为第二常数值，所述第二时间阈值大于所述第一时间阈值，所述第二常数值小于所述第一常数值；在所述迭代时间大于或等于第一时间阈值、且小于或等于第二时间阈值的情况下，所述信息素挥发因子介于所述第二常数值和所述第一常数值之间、且所述信息素挥发因子与所述迭代时间呈负相关。3.根据权利要求1所述的路径规划方法，其中，所述信息素挥发因子满足：在所述迭代次数小于第一次数阈值的情况下，所述信息素挥发因子为第三常数值；在所述迭代次数大于第二次数阈值的情况下，所述信息素挥发因子为第四常数值，所述第二次数阈值大于所述第一次数阈值，所述第四常数值小于所述第三常数值；在所述迭代次数大于或等于第一次数阈值、且小于或等于第二次数阈值的情况下，所述信息素挥发因子介于所述第四常数值和所述第三常数值之间、且所述信息素挥发因子与所述迭代次数呈负相关。4.根据权利要求2或3所述的路径规划方法，其中，所述第一时间阈值和所述第二时间阈值根据第一随机数确定，或者，所述第一次数阈值和所述第二次数阈值根据第二随机数确定。5.根据权利要求2或3所述的路径规划方法，其中，所述信息素挥发因子与所述迭代时间或所述迭代次数呈负指数关系。6.根据权利要求1至3任一所述的路径规划方法，其中，所述第一仿生学算法包括蜂群算法。7.根据权利要求6所述的路径规划方法，其中，所述根据第一仿生学算法，确定由起始点至目标点的第一规划路径包括：在蜂群算法的参数初始化阶段，根据高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成多个第一候选解；根据所述多个第一候选解，确定由起始点至目标点的第一规划路径。8.根据权利要求7所述的路径规划方法，其中，根据所述多个第一候选解，确定由起始点至目标点的第一规划路径包括：
在引领蜂和跟随蜂阶段，在所述多个第一候选解中的至少一部分第一候选解的邻域内生成第二候选解，并且，在所述第二候选解的适应度大于所述至少一部分第一候选解的情况下，根据所述第二候选解对所述至少一部分第一候选解进行更新；在存在至少一个第一候选解连续n次都没有被更新的情况下，根据所述高斯概率密度函数、候选解的上限值、以及候选解的下限值，生成第三候选解，并基于所述第三候选解更新所述至少一个第一候选解，n为大于1的整数。9.一种路径规划装置，包括：第一规划模块，被配置为根据第一仿生学算法，确定从起始点至目标点的第一规划路径；第二规划模块，包括：初始化单元，被配置为对蚁群算法中的参数进行初始化，所述参数包括搜索空间中相邻两节点间的路段的信息素浓度和信息素增量，在所述初始化时，所述信息素增量根据所述第一规划路径确定；第一确定单元，被配置为根据所述信息素浓度确定多条候选路径，并根据所述多条候选路径确定当前适应度最大的路径；第一更新单元，被配置为根据所述多条候选路径更新所述信息素增量，以得到更新后的信息素增量；第二更新单元，被配置为根据所述更新后的信息素增量和信息素挥发因子，更新所述信息素浓度，以得到更新后的信息素浓度，所述信息素挥发因子与迭代次数或迭代时间相关；第二确定单元，被配置为迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由所述起始点至所述目标点的第二规划路径。10.一种自动化巡检设备，包括：权利要求9所述的路径规划装置。11.一种电子设备，包括：存储器；以及耦接至所述存储器的处理器，所述处理器被配置为基于存储在所述存储器的指令，执行如权利要求1至8任一所述的路径规划方法。12.一种计算机可存储介质，其上存储有计算机程序指令，该指令被处理器执行时实现如权利要求1至8任一所述的路径规划方法。

技术总结
本公开提出了一种路径规划方法、装置和自动化巡检设备，涉及计算机技术领域。其中，路径规划方法包括：根据第一仿生学算法，确定从起始点至目标点的第一规划路径；对蚁群算法中的参数进行初始化；根据信息素浓度确定多条候选路径，并根据多条候选路径确定当前适应度最大的路径；根据多条候选路径更新所述信息素增量；根据更新后的信息素增量和信息素挥发因子更新信息素浓度，信息素挥发因子与迭代次数或迭代时间相关；迭代执行路径确定、信息素增量更新、以及信息素浓度更新步骤，直至达到最大迭代次数，并将最终得到的适应度最大的路径作为由起始点至目标点的第二规划路径。通过以上方法，能够改善路径规划效果。能够改善路径规划效果。能够改善路径规划效果。


技术研发人员：邢东旭 刘倩 赵艺涵 聂潼羽
受保护的技术使用者：中国电信股份有限公司
技术研发日：2023.07.06
技术公布日：2023/10/11