基于动态权重的A星算法改进方法、系统、装置及介质

基于动态权重的a星算法改进方法、系统、装置及介质
技术领域
1.本发明涉及无人机避障及路径规划的技术领域，尤其涉及一种基于动态权重的a星算法改进方法、系统、装置及介质。


背景技术：

2.目前，无人机的研究方向主要是无人机的路径规划问题。路径规划是当前研究的重点，特别是当无人机执行一些紧急特殊的任务时，能够在避开障碍物的情况下，搜索到一条飞行时间最短并且路径距离最小的路线，就显得极其重要，由此可以被广泛应用于地质勘测、人员搜救以及救灾工作等。因此，无人机路径搜索技术的精确性和效率一直是我们研究的重点方向。目前存在多种无人机路径规划算法。dijkstra算法因为其遍历节点多，效率低，耗时长，无法自行扩展可行路径点等不足点，而不太适用对于时间敏感的场景。人工势场法存在局部最优的问题，可能导致最终目标不可达。粒子群算法易陷入局部极点值，可能出现早熟收敛等问题，对所设参数有一定依赖性。
3.a星算法(也称为a*算法)作为一种现代智能算法，是一种启发式寻优算法，因其运算量大且搜索效率低等缺点，故后来出现了实时性较强的d*算法，它对于动态复杂局部环境具有较好的适应度，但是它依然存在计算量较大的缺点。传统的a*算法由代价函数f(n)确定，它由两部分组成，f(n)＝g(n) h(n),g(n)表示从起始节点到达当前节点的已产生的路径代价，h(n)表示从当前节点到达目标点的启发式路径代价。实验发现，g(n)和h(n)的权重会影响整体的寻路效率。当g(n)占的比重较大时，相当于dijkstra算法，此时节点体现较强的扩展性，路径准确度更高，但是因为节点增加了，计算量增加，效率降低。当h(n)占的比重较大时，相当于贪婪bfs算法，此时节点体现较强的目标导向性，效率明显提高，但是可能得到的路径不准确。


技术实现要素：

4.为至少一定程度上解决现有技术中存在的技术问题之一，本发明的目的在于提供一种基于动态权重的a星算法改进方法、系统、装置及介质。
5.本发明所采用的技术方案是：
6.一种基于动态权重的a星算法改进方法，包括以下步骤：
7.获取无人机飞行的过程中采集的环境信息；
8.对a星算法的估价函数进行改进；
9.设计动态权值生成器，根据环境信息实时生成当前节点的启发式权值；
10.当无人机离起始点较近时，h(n)占的比重较大；当无人机不断接近目标时，g(n)的权值逐渐增加；
11.其中，h(n)为从指定位置运行到终点的估计代价，g(n)为从起点移动到指定方格的移动代价。
12.进一步地，所述对a星算法的估价函数进行改进，包括：
13.采用加权评估的方法对a星算法的估价函数进行改进，其中，改进的估价函数如下：
14.f(n)＝wgg(n) whh(n)
15.wg和wh的权值之和为1，采用wh作为启发函数的权重系数，wh的表达式为：
[0016][0017]
其中w
gm
in表示wg的初始值；w
gmax
表示wg的最大值；d表示无人机从初始位置到目标位置的直线距离；h(n)表示为无人机当前位置至目标位置之间的欧式距离，作为估计代价。
[0018]
进一步地，所述设计动态权值生成器，根据环境信息实时生成当前节点的启发式权值，包括：
[0019]
将当前节点距离目标点的欧几里得距离h(n)和起始点距离目标点的直线距离d，以及wg的初始值w
gmin
和最大值w
gmax
代入wh的表达式中，求得权值，将求得的权值添加到估价函数的启发式权值上。
[0020]
进一步地，所述环境信息包括搜索区域信息以及区域的栅格化，障碍物信息，无人机的位置信息和目标信息。
[0021]
本发明所采用的另一技术方案是：
[0022]
一种基于动态权重的a星算法改进系统，包括：
[0023]
数据采集模块，用于获取无人机飞行的过程中采集的环境信息；
[0024]
算法改进模块，用于对a星算法的估价函数进行改进；
[0025]
权重获取莫，用于设计动态权值生成器，根据环境信息实时生成当前节点的启发式权值；
[0026]
当无人机离起始点较近时，h(n)占的比重较大；当无人机不断接近目标时，g(n)的权值逐渐增加；
[0027]
其中，h(n)为从指定位置运行到终点的估计代价，g(n)为从起点移动到指定方格的移动代价。
[0028]
进一步地，所述对a星算法的估价函数进行改进，包括：
[0029]
采用加权评估的方法对a星算法的估价函数进行改进，其中，改进的估价函数如下：
[0030]
f(n)＝wgg(n) whh(n)
[0031]
wg和wh的权值之和为1，采用wh作为启发函数的权重系数，wh的表达式为：
[0032][0033]
其中w
gmin
表示wg的初始值；w
gmax
表示wg的最大值；d表示无人机从初始位置到目标位置的直线距离；h(n)表示为无人机当前位置至目标位置之间的欧式距离，作为估计代价。
[0034]
进一步地，所述设计动态权值生成器，根据环境信息实时生成当前节点的启发式权值，包括：
[0035]
将当前节点距离目标点的欧几里得距离h(n)和起始点距离目标点的直线距离d，以及wg的初始值w
gmin
和最大值w
gmax
代入wh的表达式中，求得权值，将求得的权值添加到估价函数的启发式权值上。
[0036]
进一步地，所述环境信息包括搜索区域信息以及区域的栅格化，障碍物信息，无人机的位置信息和目标信息。
[0037]
本发明所采用的另一技术方案是：
[0038]
一种基于动态权重的a星算法改进装置，包括：
[0039]
至少一个处理器；
[0040]
至少一个存储器，用于存储至少一个程序；
[0041]
当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现上所述方法。
[0042]
本发明所采用的另一技术方案是：
[0043]
一种计算机可读存储介质，其中存储有处理器可执行的程序，所述处理器可执行的程序在由处理器执行时用于执行如上所述方法。
[0044]
本发明的有益效果是：本发明在无人机对目标点进行寻路地过程中，通过对a星算法的路径评价函数加入实时调整的动态启发式权值，来实现寻路的精确度与效率的统一。
附图说明
[0045]
为了更清楚地说明本发明实施例或者现有技术中的技术方案，下面对本发明实施例或者现有技术中的相关技术方案附图作以下介绍，应当理解的是，下面介绍中的附图仅仅为了方便清晰表述本发明的技术方案中的部分实施例，对于本领域的技术人员而言，在无需付出创造性劳动的前提下，还可以根据这些附图获取到其他附图。
[0046]
图1是本发明实施例中一种基于动态权重的a星算法改进方法的逻辑流程示意图；
[0047]
图2是本发明实施例中一种基于动态权重的a星算法改进方法的matlab仿真结果示意图。
具体实施方式
[0048]
下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。对于以下实施例中的步骤编号，其仅为了便于阐述说明而设置，对步骤之间的顺序不做任何限定，实施例中的各步骤的执行顺序均可根据本领域技术人员的理解来进行适应性调整。
[0049]
在本发明的描述中，需要理解的是，涉及到方位描述，例如上、下、前、后、左、右等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。
[0050]
在本发明的描述中，若干的含义是一个或者多个，多个的含义是两个以上，大于、小于、超过等理解为不包括本数，以上、以下、以内等理解为包括本数。如果有描述到第一、第二只是用于区分技术特征为目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量或者隐含指明所指示的技术特征的先后关系。
[0051]
本发明的描述中，除非另有明确的限定，设置、安装、连接等词语应做广义理解，所属技术领域技术人员可以结合技术方案的具体内容合理确定上述词语在本发明中的具体
含义。
[0052]
本发明实施例基于传统的a*算法的启发式搜索的基础上，为解决其存在的搜索效率低下的问题，提出了一种基于启发式动态加权的改进a*算法。传统的a*算法由代价函数f(n)确定，它由两部分组成，f(n)＝g(n) h(n)，g(n)表示从起始节点到达当前节点的已产生的路径代价，h(n)表示从当前节点到达目标点的启发式路径代价。实验发现，g(n)和h(n)的权重会影响整体的寻路效率。当g(n)占的比重较大时，相当于dijkstra算法，此时节点体现较强的扩展性，路径准确度更高，但是因为节点增加了，计算量增加，效率降低。当h(n)占的比重较大时，相当于贪婪bfs算法，此时节点体现较强的目标导向性，效率明显提高，但是可能得到的路径不准确。基于此，本发明旨在对g(n)和h(n)的权重取一个动态的权衡，以满足在不同的飞行环境的搜索效果，即兼顾路径搜索时间和路径长度的合理化。通过动态加权的方式f(n)＝wgg(n) whh(n)，可以达到很好地权衡代价函数中启发式函数f(n)和已产生路径代价g(n)之间权重的效果，进而解决路径搜索效率低下的困境。
[0053]
综上，基于动态加权a*算法很好地应用于无人机航迹规划，降低了无人机航迹代价，缩短了算法完成时间，提高了不确定复杂环境下无人机航迹规划的搜索速度和精度。
[0054]
如图1所示，本实施例提供一种基于动态权重的a星算法改进方法，包括以下步骤：
[0055]
s1、在无人机飞行的过程中，利用无人机自身携带的传感器来探测前进方向上的环境，进行环境建模。所述建模信息主要包括搜索区域信息以及区域的栅格化，障碍物信息，无人机的位置信息和目标信息。
[0056]
在本发明的其中一个实施例中，利用无人机自身携带的传感器来进行探测获取环境信息中，其中，环境信息主要包括搜索区域信息以及区域的栅格化，障碍物信息，无人机的位置信息和目标信息；
[0057]
在本发明的其中一个实施例中，在无人机的基座上分别投放三个传感器，根据传感器收集的环境信息进行环境建模。建模信息是通过传感器进行探测，并利用获得环境信息参数运用于a*算法，主要是起始点和目标点的信息，障碍物信息以及无人机的实时飞行信息。
[0058]
s2、对传统的a*算法的估价函数f(n)＝g(n) h(n)进行改进。
[0059]
传统的a*算法主要是根据估价函数f(n)来进行启发式搜索，它由两部分组成,从起点移动到指定方格的移动代价g(n)，和从指定位置运行到终点的估计代价h(n)，计算方式都是曼哈顿距离，即f(n)＝g(n) h(n)。由于g(n)和h(n)在无人机航行路径规划的不同时期，两者对无人机航行路径价值评估的影响有一定的差异，所以调整wg和wh会使路径发生变化，不同的权重对寻路的性能产生的效果不一样。
[0060]
在本发明的其中一个实施例中，鉴于a*算法不仅可以用来寻找最短路径，还可以使用启发式来引导自己。移动代价g(n)和路径启发式代价h(n)在无人机航行路径规划的不同时期，两者对无人机航行路径价值评估的影响有一定的差异，所以调整wg和wh会使路径发生变化，不同的权重对寻路的性能产生的效果不一样。
[0061]
a*算法不仅可以用来寻找最短路径，还可以使用启发式来引导自己。故本发明为启发式函数添加动态权值改进a*算法对寻路过程进行优化，即采用如下估价函数：f(n)＝wgg(n) whh(n)，采用加权评估的方法进行优化，wg和wh的权值之和为1，即wg wh＝1。本发明
采用wh作为启发函数的权重系数，其计算方式为：其中w
gmin
表示wg的初始值；w
gmax
表示wg的最大值；d表示无人机从初始位置到目标位置的直线距离，h(n)也被称为启发函数，但与传统a*算法的h(n)一般用曼哈顿距离的计算方式不同，在这里其表示为无人机当前位置至目标位置之间的欧式距离，即根据无人机当前的飞行信息，即可容易求得上述参数。
[0062]
根据上述计算权值的方式，设计动态权值生成器，实时生成当前节点的启发式权值。
[0063]
运用该改进方法，当离起始点较近时，h(n)占的比重较大，表现出较强的目标导向性，寻路的效率更高；当无人机不断接近目标时，g(n)的权值逐渐增加，使搜索的路径更为合理。通过该种方式为a*算法估价函数的启发式函数动态分配权值，可以有效提高路径搜索的效率。
[0064]
s3、根据步骤s2中计算权值的方式，设计动态权值生成器，并且根据步骤s1中获取的相关环境信息，实时生成当前节点的启发式权值。
[0065]
在本发明的其中一个实施例中，将当前节点距离目标点的欧几里得距离h(n)和起始点距离目标点的直线距离d，以及wg的初始值w
gmin
和最大值w
gmax
代入表达式求得该权值，将求得的权值添加到估价函数的启发式权值上。
[0066]
当g(n)占的比重较大时，相当于是dijkstra算法，每次只考虑源节点最近的点。
[0067]
当h(n)占比较大的比重时，相当于是贪婪bfs算法，每次只考虑离目标节点最近的节点。
[0068]
h(n)是一种对当前节点到目的节点的启发式估计代价值，如果此估计值精确度等于实际值，那么a*算法可以非常高速地找到最优路径(搜索过程中几乎不会走弯路)，如果h(n)大多都是小或等于从n节点移动到目的节点的实际代价，那么a*算法保证能找到一条最短路径。如果h(n)有时比从n节点移动到目的节点的实际代价高，则a*不能保证找到一条最短路径，但它运行得更快。也就是说我们在利用a*算法求解时，应该把握搜索的准确性与效率的均衡。
[0069]
运用该改进方法，当离起始点较近时，h(n)占的比重较大，表现出较强的目标导向性，寻路的效率更高；当无人机不断接近目标时，g(n)的权值逐渐增加，使搜索的路径更为合理。通过该种方式为a*算法估价函数的启发式函数动态分配权值，可以有效提高路径搜索的效率。
[0070]
通过对a*算法的路径评价函数加入实时调整的动态启发式权值，即f(n)＝wgg(n) whh(n)，实现了无人机路径规划效率的提升和路径规划合理性的优化，一定程度上提高了路径的搜索效率。如图2所示，图2为基于动态权重的a星算法改进方法的matlab仿真结果示意图，图中黑色方块为障碍物和边界点，红色方块为close节点，绿色方块为open节点，连线
为路径path。
[0071]
本发明提出的一种基于启发式动态权值的改进a*算法，突破了传统a*算法估价函数所带来的性能约束，通过为a*算法的估价函数动态分配权值，有效提高了搜索路径地精度和效率。首先利用无人机自身携带的传感器进行环境探测以获取环境信息，主要包括搜索区域信息以及区域的栅格化，障碍物信息，无人机的位置信息和目标信息。在无人机对目标点进行寻路地过程中，通过对a*算法的路径评价函数加入实时调整的动态启发式权值，即f(n)＝wgg(n) whh(n)，来实现寻路的精确度与效率的统一。
[0072]
本实施例还提供一种基于动态权重的a星算法改进系统，包括：
[0073]
数据采集模块，用于获取无人机飞行的过程中采集的环境信息；
[0074]
算法改进模块，用于对a星算法的估价函数进行改进；
[0075]
权重获取莫，用于设计动态权值生成器，根据环境信息实时生成当前节点的启发式权值；
[0076]
当无人机离起始点较近时，h(n)占的比重较大；当无人机不断接近目标时，g(n)的权值逐渐增加；
[0077]
其中，h(n)为从指定位置运行到终点的估计代价，g(n)为从起点移动到指定方格的移动代价。
[0078]
进一步作为可选的实施方式，所述对a星算法的估价函数进行改进，包括：
[0079]
采用加权评估的方法对a星算法的估价函数进行改进，其中，改进的估价函数如下：
[0080]
f(n)＝wgg(n) whh(n)
[0081]
wg和wh的权值之和为1，采用wh作为启发函数的权重系数，wh的表达式为：
[0082][0083]
其中w
gmin
表示wg的初始值；w
gmax
表示wg的最大值；d表示无人机从初始位置到目标位置的直线距离；h(n)表示为无人机当前位置至目标位置之间的欧式距离。
[0084]
进一步作为可选的实施方式，所述设计动态权值生成器，根据环境信息实时生成当前节点的启发式权值，包括：
[0085]
将当前节点距离目标点的欧几里得距离h(n)和起始点距离目标点的直线距离d，以及wg的初始值w
gmin
和最大值w
gmax
代入wh的表达式中，求得权值，将求得的权值添加到估价函数的启发式权值上。
[0086]
进一步作为可选的实施方式，所述环境信息包括搜索区域信息以及区域的栅格化，障碍物信息，无人机的位置信息和目标信息。
[0087]
本实施例的一种基于动态权重的a星算法改进系统，可执行本发明方法实施例所提供的一种基于动态权重的a星算法改进方法，可执行方法实施例的任意组合实施步骤，具备该方法相应的功能和有益效果。
[0088]
本实施例还提供一种基于动态权重的a星算法改进装置，包括：
[0089]
至少一个处理器；
[0090]
至少一个存储器，用于存储至少一个程序；
[0091]
当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现
图1所示方法。
[0092]
本实施例的一种基于动态权重的a星算法改进装置，可执行本发明方法实施例所提供的一种基于动态权重的a星算法改进方法，可执行方法实施例的任意组合实施步骤，具备该方法相应的功能和有益效果。
[0093]
本技术实施例还公开了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存介质中。计算机设备的处理器可以从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备执行图1所示的方法。
[0094]
本实施例还提供了一种存储介质，存储有可执行本发明方法实施例所提供的一种基于动态权重的a星算法改进方法的指令或程序，当运行该指令或程序时，可执行方法实施例的任意组合实施步骤，具备该方法相应的功能和有益效果。
[0095]
在一些可选择的实施例中，在方框图中提到的功能/操作可以不按照操作示图提到的顺序发生。例如，取决于所涉及的功能/操作，连续示出的两个方框实际上可以被大体上同时地执行或所述方框有时能以相反顺序被执行。此外，在本发明的流程图中所呈现和描述的实施例以示例的方式被提供，目的在于提供对技术更全面的理解。所公开的方法不限于本文所呈现的操作和逻辑流程。可选择的实施例是可预期的，其中各种操作的顺序被改变以及其中被描述为较大操作的一部分的子操作被独立地执行。
[0096]
此外，虽然在功能性模块的背景下描述了本发明，但应当理解的是，除非另有相反说明，所述的功能和/或特征中的一个或多个可以被集成在单个物理装置和/或软件模块中，或者一个或多个功能和/或特征可以在单独的物理装置或软件模块中被实现。还可以理解的是，有关每个模块的实际实现的详细讨论对于理解本发明是不必要的。更确切地说，考虑到在本文中公开的装置中各种功能模块的属性、功能和内部关系的情况下，在工程师的常规技术内将会了解该模块的实际实现。因此，本领域技术人员运用普通技术就能够在无需过度试验的情况下实现在权利要求书中所阐明的本发明。还可以理解的是，所公开的特定概念仅仅是说明性的，并不意在限制本发明的范围，本发明的范围由所附权利要求书及其等同方案的全部范围来决定。
[0097]
所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
[0098]
在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装
置。
[0099]
计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(ram)，只读存储器(rom)，可擦除可编辑只读存储器(eprom或闪速存储器)，光纤装置，以及便携式光盘只读存储器(cdrom)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。
[0100]
应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(pga)，现场可编程门阵列(fpga)等。
[0101]
在本说明书的上述描述中，参考术语“一个实施方式/实施例”、“另一实施方式/实施例”或“某些实施方式/实施例”等的描述意指结合实施方式或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施方式或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施方式或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施方式或示例中以合适的方式结合。
[0102]
尽管已经示出和描述了本发明的实施方式，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施方式进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。
[0103]
以上是对本发明的较佳实施进行了具体说明，但本发明并不限于上述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做作出种种的等同变形或替换，这些等同的变形或替换均包含在本技术权利要求所限定的范围内。