基于对向节点查询改进双向A*算法的路径规划方法

基于对向节点查询改进双向a*算法的路径规划方法
技术领域
1.本发明属于路径规划算法技术领域，具体涉及一种基于对向节点查询改进双向a*算法的路径规划方法。


背景技术：

2.随着社会发展进入智能化时代，移动机器人被广泛应用于交通运输，工业生产和社会服务等领域，引导移动机器人进行路径规划与目标导航也成为了研究的热点，其中a*算法可进行静态环境中的全域地图的路径规划，能够较为方便地得到有效的最优路径。但由于其单向的搜索机制会存在不断叠加冗余节点，降低搜索效率的问题。为此，国内外众多研究者从多个方向对a*算法进行了改进。
3.针对传统a*算法存在的搜索效率低等问题，有研究者提出以双向搜索机制代替传统单向搜索机制的方式来改进a*算法。专利cn110220528a《一种基于a星算法的自动驾驶无人车双向动态路径规划方法》通过初始化栅格地图，设置好起点和目标点位置及无人车的移动步长；创建两个open列表和两个close列表的方式，分别用于从起点向目标点方向使用a*算法搜索和从目标点向起点方向使用a*算法搜索，提高了搜索效率。
4.但在双向搜索过程中，常规的双向a*算法往往以对向节点直接作为目标点来进行搜索，会出现搜索节点错位，没有在中间交汇的问题，需要保证搜索路径在中间交汇。
5.此外，现有技术中通过通过对a*算法的路径评价函数加入实时调整的动态启发式权值，来实现寻路的精确度与效率的统一。具体可参见专利cn114527788a《基于动态权重的a星算法改进方法、系统、装置及介质》等。


技术实现要素：

6.针对传统a*算法存在搜索过程中节点冗余量大，搜索效率低等缺陷，本发明提出了一种基于对向节点查询改进双向a*算法的路径规划方法,以双向搜索的方式来改进a*算法，减少其搜索节点数量，提高搜索效率。在双向搜索过程中，为避免出现搜索节点错位，没有在中间交汇的问题，常规的双向a*算法往往以对向节点直接作为目标点来进行搜索，但这样往往会增加遍历节点，降低搜索效率。通过分析发现，为保证路径交汇，需要当评估函数相同时，进一步计算当前节点与对向节点的代价函数，以代价函数作为查询信息，选择较小值作为搜索节点。使用对向节点作为查询信息，不仅保留了双向a*算法两端同时进行搜索的优点，也避免了中间路径不交汇或者为了保证路径交汇带来的节点冗余问题。
7.也就是说，本发明通过双向搜索和对向节点查询的方式改进传统a*算法，在全局地图中，以起始点和终点为算法原点，同时进行双向路径搜索，计算全局评估函数来确定最佳路径。
8.考虑通过双向搜索的方式虽然提高了搜索效率，但在搜索过程中，会出现两条路径错位，没有在中间交汇的情况。针对这种情况，当全局评估函数相同时，以对向节点为查询信息进一步确定搜索节点，通过构建当前节点与对向搜索的最新节点的代价函数来保证
路径在中间点交汇。并在优选的实施例方案中从起点和终点分别建立open表和close表，子节点放入open表，父节点放入close表。根据全局评估函数和构建的代价函数确定新的搜索节点，直至找出最优路径。
9.本发明提出的方法相比于传统a*算法减少了搜索节点数，提高了搜索效率。
10.本发明解决其技术问题具体采用的技术方案是：
11.一种基于对向节点查询改进双向a*算法的路径规划方法，其特征在于，包括以下步骤：
12.步骤s1：初始化地图，确定全局地图中的起点与终点；
13.步骤s2：以起点和终点分别作为父节点，计算所述父节点周围8个子节点的全局评估函数；
14.步骤s3：比较所述父节点周围8个子节点的全局评估函数，选取值最小的子节点作为新的父节点；当全局评估函数相同时，计算子节点与另一端最新的父节点的代价函数，选择代价函数值较小的子节点作为新的父节点；
15.步骤s4：循环执行步骤s3，当搜索节点在路径中相遇时，结束搜索，确定最优路径。
16.进一步地，在步骤s3中，所述评估函数为：
17.f(n)＝g(n)+h(n)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
18.f(n)为当前节点到目标点的全局评估函数，g(n)是从起点到当前节点的实际代价，以欧几里得距离表示，h(n)代表设想中的当前节点到目标点的代价，采用曼哈顿距离表示，即两个坐标点之间的绝对值之和，设起点为a(x1,y1)，当前节点为b(x2,y2)，终点为c(x3,y3)，节点全局评估函数具体计算方式如下：
[0019][0020]
h(n)＝|x
3-x2|+|y
3-y2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)
[0021][0022]
进一步地，所述代价函数为：
[0023][0024]f′
(n)＝h(n)+g(n)+k
×
g'(n)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0025]
另一端最新的父节点为d(x4,y4)，先计算该节点代价函数f(n)，如公式(4)所示，当其与其他子节点计算得到的f(n)相同时，再计算两者f’(n)值，选择代价函数值较小的子节点作为新的父节点，其中k为对向搜索影响系数，取值在[0,1]。
[0026]
进一步地，在步骤s3的循环过程中，先计算子节点的全局评估函数，选择值较小的子节点作为下一步的父节点，若全局评估函数值相同，则进一步计算代价函数，选择值较小的子节点作为下一步的父节点，以保证搜索路径在中间交汇。
[0027]
进一步地，从起点和终点分别建立open表和close表，子节点放入open表，父节点放入close表。根据全局评估函数和构建的代价函数确定新的搜索节点，直至找出最优路径。
[0028]
相比于现有技术，本发明及其优选方案提供的方案具有如下优点：
[0029]
1、以起点与终点进行双向搜索方式来寻找最优路径，相比于传统a*算法减少了搜
索节点数量，提高搜索效率，节省了搜索时间。
[0030]
2、在进行路径搜索时，当全局搜索评估函数相同时，加入子节点与另一端最新的父节点的代价函数计算，不仅保留了双向a*算法两端同时进行搜索的优点，也避免了中间路径不交汇或者为了保证路径交汇带来的节点冗余问题。
附图说明
[0031]
下面结合附图和具体实施方式对本发明进一步详细的说明：
[0032]
图1为本发明实施例整体工作流程示意图；
[0033]
图2为本发明优选的具体实施流程图；
[0034]
图3为本发明实施例仿真路径图。
具体实施方式
[0035]
为让本专利的特征和优点能更明显易懂，下文特举实施例，作详细说明如下：
[0036]
应该指出，以下详细说明都是例示性的，旨在对本技术提供进一步的说明。除非另有指明，本说明书使用的所有技术和科学术语具有与本技术所属技术领域的普通技术人员通常理解的相同含义。
[0037]
需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本技术的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
[0038]
如图1所示，本发明提供的基于对向节点查询改进双向a*算法的路径规划方法具体包括如下步骤：
[0039]
初始化地图，所使用地图为栅格地图，确定全局地图中的起点与终点；
[0040]
从起点与终点进行双向搜索来寻找最优路径。以起点和终点作为父节点，计算其周围8个子节点的全局评估函数，评估函数为：
[0041]
f(n)＝g(n)+h(n)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
[0042]
f(n)为当前节点到目标点的全局评估函数，g(n)是从起点到当前节点的实际代价，我们以欧几里得距离表示，h(n)代表设想中的当前节点到目标点的代价，一般用曼哈顿距离表示，即两个坐标点之间的绝对值之和，我们设起点为a(x1,y1)，当前节点为b(x2,y2)，终点为c(x3,y3)，则该节点全局评估函数具体计算方式如下：
[0043][0044]
h(n)＝|x
3-x2|+|y
3-y2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)
[0045][0046]
比较周围8个子节点的全局评估函数，选取值最小的子节点作为新的父节点，当全局评估函数相同时，计算子节点与另一端最新的父节点的代价函数，代价函数如下：
[0047][0048]f′
(n)＝h(n)+g(n)+k
×
g'(n)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0049]
另一端最新的父节点为d(x4,y4)，先计算该节点代价函数f(n)，如公式(4)所示，当其与其他子节点计算得到的f(n)相同时，再计算两者f’(n)值，选择代价函数值较小的子节点作为新的父节点，其中k为对向搜索影响系数，取值在[0,1]。选择代价函数值较小的子节点作为新的父节点。
[0050]
循环上一步过程，当搜索节点在路径中间相遇时，结束搜索，确定最优路径。循环过程先计算子节点的全局评估函数，选择值较小的子节点作为下一步的父节点，若全局评估函数值相同，则进一步计算代价函数，选择值较小的子节点作为下一步的父节点，保证了搜索路径在中间交汇。
[0051]
在具体的实施过程中，一般可以从起点和终点分别建立open表和close表，子节点放入open表，父节点放入close表。根据全局评估函数和构建的代价函数确定新的搜索节点，直至找出最优路径。
[0052]
因此，可以在实际工作过程中采用如图2所示的具体方案实现手段：
[0053]
基于对向节点查询改进双向a*算法的路径规划方法具体流程如下：
[0054]
(1)初始化地图，设定起始点与终点，以起点建立open表1和close表1并初始化，以终点建立open表2和close表2并初始化。
[0055]
(2)将起点设为父节点1并添加进入close表1，列出父节点1周围八个点并根据条件添加进入open表1，这里的条件包括是否超出地图范围，是否是障碍物，是否已加入close表1。
[0056]
(3)将终点设为父节点2并添加进入close表2，列出父节点2周围八个点并根据条件添加进入open表2，这里的条件包括是否超出地图范围，是否是障碍物，是否已加入close表2。
[0057]
(4)通过条件的父节点1周围的点我们将其定为子节点1，计算子节点1的f(n)值，判断子节点1是否已经在open表1中，如果是则需要考虑更新，若新的路径的代价函数更低，则更新为新路径，不在open表1中则直接加入open表1。
[0058]
(5)通过条件的父节点2周围的点我们将其定为子节点2，计算子节点2的f(n)值，判断子节点2是否已经在open表2中，如果是则需要考虑更新，若新的路径的代价函数更低，则更新为新路径，不在open表2中则直接加入open表2。
[0059]
(6)判断open表1中是否出现close表2中的点或者open表2中是否出现close表1中的点，若出现则代表搜索完成找到目标点。
[0060]
(7)判断open表1和open表2是否为空，若为空则代表没找到路径，原因是地图中不存在起点到终点的路径。
[0061]
(8)比较各个子节点1的f(n)值，选出值最小的子节点1，若出现值相同的情况，计算子节点1以close表2中最新放入的值作为目标点的f(n)值，取值较小的子节点1，将该子节点1加入close表1并从open表1中删除。将该子节点1设为父节点1，然后再循环第(2)步中的父节点1操作,直至找到路径或者确定不存在路径。
[0062]
(9)比较各个子节点2的f(n)值，选出值最小的子节点2，若出现值相同的情况，计算子节点2以close表1中最新放入的值作为目标点的f’(n)值，以此作为查询信息，取值较小的子节点2，将该子节点2加入close表2并从open表2中删除。将该子节点2设为父节点2，然后再循环第(2)步中的父节点2操作,直至找到路径或者确定不存在路径。
[0063]
图3是依据本实施例方案进行的一次仿真模拟实验的路径图，证明了算法的可行性和效率。
[0064]
本领域内的技术人员应明白，本技术的实施例可提供为方法、系统、或计算机程序产品。因此，本技术可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本技术可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
[0065]
本技术是参照根据本技术实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0066]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0067]
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0068]
以上所述，仅是本发明的较佳实施例而已，并非是对本发明作其它形式的限制，任何熟悉本专业的技术人员可能利用上述揭示的技术内容加以变更或改型为等同变化的等效实施例。但是凡是未脱离本发明技术方案内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与改型，仍属于本发明技术方案的保护范围。
[0069]
本专利不局限于上述最佳实施方式，任何人在本专利的启示下都可以得出其它各种形式的基于对向节点查询改进双向a*算法的路径规划方法，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本专利的涵盖范围。

技术特征：
1.一种基于对向节点查询改进双向a*算法的路径规划方法，其特征在于，包括以下步骤：步骤s1：初始化地图，确定全局地图中的起点与终点；步骤s2：以起点和终点分别作为父节点，计算所述父节点周围8个子节点的全局评估函数；步骤s3：比较所述父节点周围8个子节点的全局评估函数，选取值最小的子节点作为新的父节点；当全局评估函数相同时，计算子节点与另一端最新的父节点的代价函数，选择代价函数值较小的子节点作为新的父节点；步骤s4：循环执行步骤s3，当搜索节点在路径中相遇时，结束搜索，确定最优路径。2.根据权利要求1所述的基于对向节点查询改进双向a*算法的路径规划方法，其特征在于，在步骤s3中，所述评估函数为：f(n)＝g(n)+h(n)
ꢀꢀꢀꢀꢀ
(1)f(n)为当前节点到目标点的全局评估函数，g(n)是从起点到当前节点的实际代价，以欧几里得距离表示，h(n)代表设想中的当前节点到目标点的代价，采用曼哈顿距离表示，即两个坐标点之间的绝对值之和，设起点为a(x1,y1)，当前节点为b(x2,y2)，终点为c(x3,y3)，节点全局评估函数具体计算方式如下：h(n)＝|x
3-x2|+|y
3-y2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)3.根据权利要求2所述的基于对向节点查询改进双向a*算法的路径规划方法，其特征在于，所述代价函数为：f
′
(n)＝h(n)+g(n)+k＝g'(n)
ꢀꢀꢀꢀꢀꢀꢀ
(6)另一端最新的父节点为d(x4,y4)，先计算该节点代价函数f(n)，如公式(4)所示，当其与其他子节点计算得到的f(n)相同时，再计算两者f’(n)值，选择代价函数值较小的子节点作为新的父节点，其中k为对向搜索影响系数，取值在[0,1]。4.根据权利要求1所述的基于对向节点查询改进双向a*算法的路径规划方法，其特征在于，在步骤s3的循环过程中，先计算子节点的全局评估函数，选择值较小的子节点作为下一步的父节点，若全局评估函数值相同，则进一步计算代价函数，选择值较小的子节点作为下一步的父节点，以保证搜索路径在中间交汇。5.根据权利要求1所述的基于对向节点查询改进双向a*算法的路径规划方法，其特征在于，从起点和终点分别建立open表和close表，子节点放入open表，父节点放入close表。根据全局评估函数和构建的代价函数确定新的搜索节点，直至找出最优路径。

技术总结
本发明涉及一种基于对向节点查询改进双向A*算法的路径规划方法，通过双向搜索和对向节点查询的方式改进传统A*算法，在全局地图中，以起始点和终点为算法原点，同时进行双向路径搜索，计算全局评估函数来确定最佳路径。考虑通过双向搜索的方式虽然提高了搜索效率，但在搜索过程中，会出现两条路径错位，没有在中间交汇的情况。针对这种情况，当全局评估函数相同时，以对向节点为查询信息进一步确定搜索节点，通过构建当前节点与对向搜索的最新节点的代价函数来保证路径在中间点交汇。本发明提出的方法相比于传统A*算法减少了搜索节点数，提高了搜索效率。提高了搜索效率。提高了搜索效率。


技术研发人员：任志英 马帅峰 郑明魁 黄凯迪 林晗
受保护的技术使用者：福州大学
技术研发日：2023.02.27
技术公布日：2023/9/20