基于自适应a星算法的飞行器最优路径确定方法
【专利摘要】本发明公开一种基于自适应A星算法的飞行器最优路径确定方法，主要解决现有技术划分路径长度过长、障碍物对飞行器的威胁值过大以及航路点数过多的问题。其实现步骤为：（1）在地图中设置飞行器的起始点SP和终止点EP；（2）生成障碍物区域；（3）将障碍物区域进行网格划分，得到网格地图；（4）在网格地图中，设飞行器的起始点SP所在的网格为SG、终止点EP所在的网格为EG；（5）根据飞行器的起始点所在网格SG和终止点所在网格EG，进行路径规划。本发明具有路径长度短、威胁值低、航路点数少的优点，可用于飞行器最优路径的确定。
【专利说明】基于自适应A星算法的飞行器最优路径确定方法
【技术领域】
[0001]本发明属于空间数据处理【技术领域】，特别涉及飞行器的路径规划，该方法可用于开展智能导航、无人驾驶等领域的路径规划。
【背景技术】
[0002]飞行器是依靠地形信息和敌情信息来进行路径规划，即在一定约束条件下，飞行器从起始点到终止点，搜寻能优先满足特定目的最优的飞行路径，其中飞行路径用一系列航路点表示。
[0003]随着军事技术、实际战争需求的不断发展，飞行器的路径规划建模从单一的系统发展到复杂多变的系统。飞行器的路径规划问题呈现出实时性、多维性、不确定性和非线性等复杂特征。建立在传统系统下的模型，仍习惯于从障碍物地形信息已知且不会改变的角度出发，以静态、理想化为主的方式来研究飞行器路径规划的建模问题，忽视了从实际的角度来看待整个飞行过程。目前大多数路径规划方法对于复杂的贴近真实环境的障碍物地形场景效果较差。这是因为传统算法采用的是简单的静态的规划方法，即在实际飞行器在飞行之前根据障碍物地形场景来进行路径规划，在飞行过程中路径不可改变以及障碍物符合特定规律，这与真实场景的差距较大。显然这种规划方法将障碍物地形场景进行了理想化的处理，而实际上飞行场景的地形信息是无规律无规则的。
[0004]目前主要有三类技术解决路径规划问题:1.传统算法，如栅格法，Voronoi图法；
2.智能优化算法，如遗传算法；3.其他算法，如动态规划算法。
[0005]传统算法是根据经典的数学方程式进行计算，较一般地理想的障碍物地图用此类算法计算出的路径在全局上较优，但对障碍物的要求较为理想化，针对实际地形地图的规划效果很大程度受到算法本身和障碍物理想化程度的影响。智能优化算法，如遗传算法是在1975年由John Holland提出，是一类借鉴生物界的进化规律，即利用适者生存、优胜劣汰遗传机制演化而来的随机化搜索方法，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。在鲁棒性上较传统算法有了明显的提高，对障碍物理想化的依赖程度减低，但智能优化算法的计算时间普遍过长，无法适应动态的，可变的更接近真实情景的地图进行路径规划。对于其他算法，如动态规划算法，由于算法自身限制，在局部路径上可以达到最优以及适应动态地图，但在全局规划上无法保证，可能会出现路径结果不稳定和计算不出总体路径的情况。

【发明内容】

[0006]本发明的目的在于针对已有技术的不足，提出一种基于自适应A星算法的飞行器最优路径确定方法，以提高对多种不同地图规划出的路径的正确度，同时提高对同一幅地图进行多次路径规划的路线的稳定性，增强对不同地图路径规划的鲁棒性。[0007]本发明的技术思路是:将所需的各类数据进行预处理，获得起止点和障碍物区域坐标，由起止点坐标差值比例，计算纵坐标方向网格尺寸大小，通过传统A星算法得出其路径规划的路径，并把搜索方向发生改变时的第一个航路点作为新的起始点，重新定义网格尺寸大小，用A星算法进行搜索，当满足终止点条件时，路径规划结束，输出所有的有效航路点。其具体步骤包括如下:
[0008](1)在地图中设置飞行器的起始点SP和终止点EP ；
[0009](2)生成障碍物区域:
[0010]2a)根据飞行器的起始点SP和终止点EP的位置，建立直角坐标系；
[0011]2b)设Pi，qi*别为飞行器需绕过的每一个障碍物的起点和终点的坐标，对Pi点分别做垂直于直角坐标系X轴和Y轴的直线，对Qi点分别做垂直于直角坐标系X轴和Y轴的直线，用这四条直线围成的一个矩形，表示障碍物区域Ti，其中i为障碍物的个数；
[0012](3)将障碍物区域进行网格划分，得到网格地图；
[0013](4)在网格地图中，设飞行器的起始点SP所在的网格为SG、终止点EP所在的网格为EG ；
[0014](5)根据飞行器的起始点所在网格SG和终止点所在网格EG，进行路径规划:
[0015]5a)令飞行器的起始点SP所在的网格SG为父节点Dj;设总计划移动距离为:Ej+1=Lb+Ep其中Lb为父节点&到与其相邻的每个网格b所需要走的路径长度，即父节点Dj到与其相邻的每个网格b中心连线的长度，b为相邻网格的标号，1 < b ( 8,Ej为从起始点所在网格SG到达父节点h所移动的距离，j为父节点h的标号；设定父节点h在起始点所在网格SG时初值为:j = 0, L = 0, Ej = 0 ；
[0016]5b)分别计算第一个相邻网格通过水平一垂直平移和垂直一水平平移这两条路径到达终止点所在网格EG的预估算耗费:Hn = R(k)*m，并将这两个预估算耗费的最小值记为HM，其中R(k)为平移过程中所经过的网格数，k为平移过程中所经过的网格标号，η为路径标号，η为整数，1≤η≤2，m为地图放大系数，1≤m≤20 ;
[0017]5c)对与父节点相邻的每一个网格重复步骤(5b)，得到各自的预估算耗费的最小值HMb ;
[0018]5d)计算与父节点0」相邻的每个网格b到终止点所在的网格EG的总估计值F(b):
[0019]F (b) = G (b) +HMb ；
[0020]其中G(b)为总移动耗费，其值与总计划移动距离相等，即总移动耗费:G(b)=
Ej+i ;
[0021]5e)将总估计值F(b)中的最小值所对应的网格x作为新的父节点Dj+1，总计划移动距离为:Ej+1 = LX+Ej，其中Lx为父节点0」到与其相邻的网格X中心连线的长度，则当前的计划移动路径为父节点&与新的父节点1+1所在的网格中心的连线；
[0022]5f)判断新的父节点^与父节点&的搜索方向是否相同，如果搜索方向相同，则返回步骤(5b)继续进行搜索；否则，执行步骤(5g)；
[0023]5g)将步骤(5f )中的新的父节点^作为新的起始点SP，并判断该点与终止点EP的距离是否小于2，若距离小于2，则停止路径规划，此时，网格地图中飞行器的起始点SP所在的网格SG到达终止点EP所在的网格EG的路径，即为网格地图中所有父节点Dt与Dt+1所在的网格中心连线组成的线段，其中0 < t < j，否则，返回步骤(3)。[0024]本发明与现有的技术相比具有以下优点:
[0025]第一，本发明所采用自适应A星算法，相比传统的A星算法，对飞行器进行路径规划所得出的路径在长度上有所缩短，航路点数减少，提高了规划出的路径的正确度。
[0026]第二，本发明与传统算法相比，飞行器在飞行过程中能够根据周围环境的变化，对当前地图进行实时更新，缩短了路径长度，并在此过程中降低了障碍物对飞行器的威胁值；
[0027]第三，本发明相比其他算法，由于不对障碍物地形地图进行任何理想化处理，克服了对于不同障碍物地形地图所规划出的路径的鲁棒性不足的缺点。
【专利附图】

【附图说明】
[0028]图1为本发明的实现流程图；
[0029]图2为本发明利用自适应A星算法进行路径规划的子流程图；
[0030]图3为本发明实验的障碍物地形地图；
[0031 ] 图4为本发明方法规划出的路径结果图；
[0032]图5为传统A星算法规划出的路径结果图。
【具体实施方式】
[0033]下面结合附图对本发明的步骤作进一步的详细描述。
[0034]参照图1，本发明的实现步骤如下:
[0035]步骤1.设置飞行器的起始点和终止点位置，即在地图中对飞行器的起始点SP和终止点EP进行标记。
[0036]步骤2.生成障碍物区域。
[0037]2a)根据飞行器的起始点SP和终止点EP的位置，建立直角坐标系；
[0038]2b)设Pi，qi*别为飞行器需绕过的每一个障碍物的起点和终点的坐标，对Pi点分别做垂直于直角坐标系X轴和Y轴的直线，对Qi点分别做垂直于直角坐标系X轴和Y轴的直线，用这四条直线围成的一个矩形，表示障碍物区域Ti，其中i为障碍物的个数；
[0039]步骤3.将障碍物区域进行网格划分，得到网格地图。
[0040]3a)设定每个网格X方向边长为2，依据起始点SP和终止点EP的坐标差值比例，计算网格Y方向的边长I:
[0041]Yi=2*yep~ysp ;
Xep -ΧΨ
[0042]其中(xsp, ysp)为起始点SP的坐标，(xep, yep)为终止点EP的坐标；
[0043]3b)依据每个网格的大小，将障碍物区域划分成含有100X 100个网格；
[0044]3c)在障碍物区域的所有网格中，将障碍物所覆盖到的网格值均设为1，其他网格值设为0，得到网格地图。
[0045]步骤4.在网格地图中，设飞行器的起始点SP所在的网格为SG、终止点EP所在的网格为EG。
[0046]步骤5.根据飞行器的起始点所在网格SG和终止点所在网格EG，进行路径规划。[0047]参照图2，本步骤的具体步骤是:
[0048]5a)令飞行器的起始点SP所在的网格SG为父节点Dj;设总计划移动距离为:Ej+1=Lb+Ep其中Lb为父节点&到与其相邻的每个网格b所需要走的路径长度，即父节点Dj到与其相邻的每个网格b中心连线的长度，b为相邻网格的标号，1 < b ( 8,Ej为从起始点所在网格SG到达父节点h所移动的距离，j为父节点h的标号；设定父节点h在起始点所在网格SG时初值为:j = 0, L = 0, Ej = 0 ；
[0049]5b)分别计算第一个相邻网格通过水平一垂直平移和垂直一水平平移这两条路径到达终止点所在网格EG的预估算耗费:Hn = R(k)*m，并将这两个预估算耗费的最小值记为HM，其中R(k)为平移过程中所经过的网格数，k为平移过程中所经过的网格标号，η为路径标号，η为整数，1≤η≤2，m为地图放大系数，1≤m≤20 ;
[0050]5c)对与父节点h相邻的每一个网格重复步骤(5b)，得到各自的预估算耗费的最小值HMb ;
[0051]5d)计算与父节点0」相邻的每个网格b到终止点所在的网格EG的总估计值F(b):
[0052]F (b) = G (b) +HMb ；
[0053]其中G(b)为总移动耗费，其值与总计划移动距离相等，即总移动耗费:G(b)=
Ej+i ;
[0054]5e)将总估计值F(b)中的最小值所对应的网格x作为新的父节点Dj+1，总计划移动距离为:Ej+1 = LX+Ej，其中Lx为父节点0」到与其相邻的网格X中心连线的长度，则当前的计划移动路径为父节点&与新的父节点1+1所在的网格中心的连线；
[0055]5f)判断新的父节点^与父节点&的搜索方向是否相同，如果搜索方向相同，则返回步骤(5b)继续进行搜索；否则，执行步骤(5g)；
[0056]5g)将步骤(5f )中的新的父节点^作为新的起始点SP，并判断该点与终止点EP的距离是否小于2，若距离小于2，则停止路径规划，此时，网格地图中飞行器的起始点SP所在的网格SG到达终止点EP所在的网格EG的路径，即为网格地图中所有父节点Dt与Dt+1所在的网格中心连线组成的线段，其中0 < t < j，否则，返回步骤(3)。
[0057]本发明的效果通过以下仿真进一步说明。
[0058]一、仿真条件
[0059]硬件平台为:IntelCore2Duo CPU E6550i2.33GHZ.2GB RAM
[0060]软件平台为:VC++6.0
[0061]实验所使用的障碍物地形图如图3所示，其中图3 (a)中的方形区域为障碍物区域，左上角的圆环为飞行器的起始点SP，右下角的圆环为飞行器的终止点EP，其他区域为无障碍物区域。图3 (b)中的两个方形区域均为障碍物区域，左上角的圆环为飞行器的起始点SP，右下角的圆环为飞行器的终止点EP，其他区域为无障碍物区域。图3 (c)中的两个圆形区域均为障碍物区域，左上角的圆环为飞行器的起始点SP，右下角的圆环为飞行器的终止点EP，其他区域为无障碍物区域。图3 (d)中的圆形和方形区域均为障碍物区域，左上角的圆环为飞行器的起始点SP，右下角的圆环为飞行器的终止点EP，其他区域为无障碍物区域。
[0062]二、仿真内容
[0063]仿真一，用本发明方法分别对图3 (a)~3 (d)进行路径规划，得到路径规划结果如图4，其中图4 (a)中从起始点SP至终止点EP的实线是对图3 (a)进行规划得到的路径，图4 (b)中从起始点SP至终止点EP的实线是对图3 (b)进行规划得到的路径，图4(c)中从起始点SP至终止点EP的实线是对图3 (c)进行规划得到的路径，图4 (d)中从起始点SP至终止点EP的实线是对图3 (d)进行规划得到的路径。
[0064]仿真二，用传统A星算法分别对图3 (a)~3 (d)进行路径规划，得到的路径规划结果如图5，其中图5 (a)中从起始点SP至终止点EP的实线是对图3 (a)进行规划得到的路径，图5 (b)中从起始点SP至终止点EP的实线是对图3 (b)进行规划得到的路径，图5(c)中从起始点SP至终止点EP的实线是对图3 (c)进行规划得到的路径，图5 (d)中从起始点SP至终止点EP的实线是对图3 (d)进行规划得到的路径。
[0065]三、结果分析
[0066]分别将图4和图5中规划出的路径长度、障碍物对飞行器的威胁值以及航路点数进行整理，得到的结果如表1，其中威胁值是障碍物区域对飞行器的威胁程度，根据雷达方程D = Ι/d4计算得出，其中d为飞行器距离障碍物的最短直线距离。
[0067]表1
【权利要求】
1.一种基于自适应A星算法的飞行器最优路径确定方法，包括如下步骤:(1)在地图中设置飞行器的起始点SP和终止点EP；(2)生成障碍物区域:2a)根据飞行器的起始点SP和终止点EP的位置，建立直角坐标系；2b)设Pi，％分别为飞行器需绕过的每一个障碍物的起点和终点的坐标，对Pi点分别做垂直于直角坐标系X轴和Y轴的直线，对Qi点分别做垂直于直角坐标系X轴和Y轴的直线，用这四条直线围成的一个矩形，表示障碍物区域Ti，其中i为障碍物的个数；(3)将障碍物区域进行网格划分，得到网格地图；(4)在网格地图中，设飞行器的起始点SP所在的网格为SG、终止点EP所在的网格为EG ；(5)根据飞行器的起始点所在网格SG和终止点所在网格EG，进行路径规划:5a)令飞行器的起始点SP所在的网格SG为父节点Dj;设总计划移动距离为:Ej+1 =Lb+Ep其中Lb为父节点&到与其相邻的每个网格b所需要走的路径长度，即父节点&到与其相邻的每个网格b中心连线的长度，b为相邻网格的标号，1 ≤ b≤ 8,Ej为从起始点所在网格SG到达父节点h所移动的距离，j为父节点h的标号；设定父节点h在起始点所在网格SG时初值为:j = 0，L = 0，E」=0 ;5b)分别计算第一个相邻网格通过水平一垂直平移和垂直一水平平移这两条路径到达终止点所在网格EG的预估算耗费:Hn = R(k)*m，并将这两个预估算耗费的最小值记为HM，其中R(k)为平移过程中所经过的网格数，k为平移过程中所经过的网格标号，η为路径标号，n为整数，1≤n≤2，m为地图放大系数，1≤m≤20 ;5c)对与父节点相邻的每一个网格重复步骤(5b)，得到各自的预估算耗费的最小值HMb ;5d)计算与父节点Dj相邻的每个网格b到终止点所在的网格EG的总估计值F(b):F(b) = G (b) +HMb ；其中G(b)为总移动耗费，其值与总计划移动距离相等，即总移动耗费:G(b) = EJ+1 ；5e)将总估计值F(b)中的最小值所对应的网格X作为新的父节点1+1，总计划移动距离为:Ej+1 = Lx+Ej，其中。为父节点Dj到与其相邻的网格X中心连线的长度，则当前的计划移动路径为父节点&与新的父节点1+1所在的网格中心的连线；5f)判断新的父节点^与父节点&的搜索方向是否相同，如果搜索方向相同，则返回步骤(5b)继续进行搜索；否则，执行步骤(5g)；5g)将步骤(5f)中的新的父节点h+1作为新的起始点SP，并判断该点与终止点EP的距离是否小于2，若距离小于2，则停止路径规划，此时，网格地图中飞行器的起始点SP所在的网格SG到达终止点EP所在的网格EG的路径，即为网格地图中所有父节点Dt与Dt+1所在的网格中心连线组成的线段，其中0 ≤t ≤j，否则，返回步骤(3)。
2.根据权利要求1所述的基于自适应A星算法的飞行器最优路径确定方法，其中步骤(3)所述的将障碍物区域进行网格划分，得到网格地图，按如下步骤进行:3a)设定网格X方向边长为2，依据起始点SP和终止点EP的坐标差值比例，计算网格Y方向的边长Y::
【文档编号】G01C21/20GK103697895SQ201410010003
【公开日】2014年4月2日 申请日期:2014年1月9日 优先权日:2014年1月9日
【发明者】于昕, 焦李成, 朱振强, 马晶晶, 马文萍, 刘军强, 李阳阳 申请人:西安电子科技大学