一种基于改进a*算法的无人机航线规划算法
【专利摘要】本发明涉及一种无人机在大范围复杂三维空间的航线规划算法，包括以下步骤，首先基于2.5维网格(每个网格点包含经度、纬度、高程信息)划分三维空间；然后在雷达、灾害天气、禁飞区等约束条件下，综合考虑航线高度、被探测概率、航线长度等影响因子改进A*代价函数，基于算法搜索流程，确定初始航线；最后为了满足无人机性能约束(包括最小步长、转弯半径、爬升率、安全高度等)，进行一系列处理得到最终的可飞行航线。本发明涉及算法稳定、收敛性好、效率高、可满足大范围低空航线规划要求，可运用于军事国防、应急救灾等相关领域之中。
【专利说明】—种基于改进A*算法的无人机航线规划算法

【技术领域】
[0001]本发明具体涉及一种算法，特别是一种用于无人机在大范围复杂三维空间的航线规划算法。

【背景技术】
[0002]现代军事低空突防主要由无人机完成，为了提高无人机低空突防生存概率和作战效能，需要利用地形的遮蔽作用，在敌防御系统盲区内低空或超低空飞行。其中，关键问题是无人机的航线规划。对于该问题的研究已有多年的历史，有很多研究成果。一些学者试图在人工智能等相关领域寻找智能优化算法，但它们解决大范围无人机路径搜索问题都有一些常见的弊病。A*算法在二维图形搜索领域的成熟运用使得它解决该问题具有先天的优势，但目前成果存在以下问题:(I)目标空间为小范围人造简单地形图，障碍物少且规则，未考虑雷达、恶劣天气等复杂威胁体。无法体现算法在复杂环境中的适应性、收敛性及效率问题。(2) —些学者使用平面区域划分(Voronoi图等)的方法，这类空间划分是基于一定高度的，因此本质上依然是在二维空间中进行路径规划。但山区地形实时截面运算的计算量太大，而且无人机基于一定高度上飞行的理论前提不成立。(3)不考虑无人机的机动性能约束，不是可飞航线。


【发明内容】

[0003]本发明目的在于提供一种表用于无人机在大范围复杂三维空间的航线规划算法，所涉及算法可满足大范围低空航线规划要求。
[0004]本发明采用的技术方案如下:
[0005]首先将三维连续空间使用离散二维空间表示，即规划空间表示为一定经差和纬差离散网格的网络图，并且为每个节点赋予当地地形的高程信息；然后在雷达、灾害天气、禁飞区等约束条件下，改进A*代价函数使航线高度、被探测概率、航线长度三项指标同方向作用关系，并进行归一化处理，在此基础上使用算法搜索流程，确定初始航线；在无人机最小步长、转弯半径、爬升率、安全高度约束下，建立航线保护区模型，进行一系列处理得到最终的可飞行航线，最后检验算法的稳定性和收敛性以及效率。
[0006]本发明与现有技术相比具有以下优点:
[0007]基于2.5维网格模型，每个节点的邻域仅仅存在8个可扩展方向，算法计算效率要远大于3维网格划分方式；在雷达、灾害天气、禁飞区等约束条件下，将航线高度、被探测概率、航线长度进行归一化处理，改进了 A*算法；在无人机最小步长、转弯半径、爬升率、安全高度约束下，优化了航线。本发明涉及算法稳定、收敛性好、效率高、可满足大范围低空航线规划要求。

【具体实施方式】
[0008]以下以航线规划算法流程对本发明作进一步的详细说明，但本发明的保护范围并不局限于此。
[0009]I目标空间划分
[0010]A*算法是一种启发式搜索算法，需要一个由点和边组成的网络空间，在此目标空间中引入启发信息，由定义好的代价函数确定节点拓展的规则，最终得到两点之间的最优路径。但基于DEM和DOM的三维环境本质上是一个连续状态的栅格空间，并不存在传统二维路径搜索中的路由网，从而无法利用路径搜索算法寻找最短路径中的节点和边，必须对其进行空间划分。
[0011]一些研究尝试使用规则三维网格的空间划分方法。该方法的最大问题在于每个节点的可扩展方向在仅仅考虑邻域的情况下也有26个，要收敛到最优解会耗费大量的时间和内存资源，且随规划空间增大呈指数级增长。因此本发明提出如图1所示的2.5维网格模型，每个网格点包含经度、纬度、高程信息。此时每个节点的邻域仅仅存在8个可扩展方向，算法计算效率要远大于3维网格划分方式。
[0012]2基于A*算法的初始航线确定
[0013]2.1代价函数改进
[0014]对于以上划分的目标网络空间，需要定义A*算法的代价函数对可拓展节点进行评估，从而挑选出最优路径中的节点-边列表。A*代价函数一般公式如下:
[0015]f (n) = g (n) +h (η)(I)
[0016]其中η是待扩展节点，g(n)是状态空间中从初始节点到节点η的实际代价，h(n)是从节点η到目标节点的估计代价。A*算法本身的性质决定了代价函数的表达式是影响搜索性能的主要因素。对于无人机低空航线规划问题，Asseo S.J给出了对代价函数的参考公式，如下所示:

【权利要求】
1.一种无人机航线规划算法，其特征在于:包括以下步骤:首先基于2.5维网格划分三维空间；然后在雷达、灾害天气、禁飞区等约束条件下，综合考虑航线高度、被探测概率、航线长度等影响因子改进A*代价函数，基于算法搜索流程，确定初始航线；最后在最小步长、转弯半径、爬升率、安全高度约束下，进行一系列处理得到最终的可飞行航线；该算法稳定、收敛性好、效率高。
2.根据权利要求1所述一种无人机航线规划算法，其特征在于:所述2.5维网格为2.5维网格模型，每个网格点包含经度、纬度、高程信息，其每个网格点的邻域存在8个可扩展方向。
3.根据权利要求1所述一种无人机航线规划算法，其特征在于:基于2.5维网格划分三维空间，其每个网格点的邻域存在8个可扩展方向远小于规则三维网格的空间划分中每个网格点的邻域存在26个可扩展方向。
4.根据权利要求1所述一种无人机航线规划算法，其特征在于:A*代价函数中g(H)首先改进为
，使代价函数的航线高度、被探测概率、航线长度三项指标是同方向的作用关系。
5.根据权利要求1所述一种无人机航线规划算法，其特征在于:A*代价函数中(进行归一化处理，进一步改进为
6.根据权利要求 1 所述一种无人机航线规划算法，其特征在于:A*代价函数中
7.根据权利要求1所述一种无人机航线规划算法，其特征在于:算法搜索基于2.5维空间划分和改进Α*代价函数。
8.根据权利要求1所述一种无人机航线规划算法，其特征在于:在最小步长、转弯半径约束下采用FFP算法对航线数据进行数据压缩，使无人机能够找出尽可能最长的直线趋势，从而避免频繁的转弯。
9.根据权利要求1所述一种无人机航线规划算法，其特征在于:在爬升率、安全高度约束下，建立航线保护区模型，计算得到优化后的转折点，构成航线。
10.根据权利要求1所述一种无人机航线规划算法，其特征在于:该算法稳定、收敛性好为算法在不同距离、不同网格大小的情况下均可以并且快速的计算出一条最优航线。
【文档编号】G01C21/20GK104075717SQ201410025640
【公开日】2014年10月1日 申请日期:2014年1月21日 优先权日:2014年1月21日
【发明者】王伟, 江华, 王鹏, 占伟伟 申请人:武汉吉嘉伟业科技发展有限公司