基于Voronoi图和遗传算法的航迹规划

　　0　引言

　　航迹规划是指在综合考虑环境、任务和飞机性能等一系列约束条件的前提下,为飞机规划出一条从起点到终点的可飞路径。在防空技术日益完善的现代战争中,航迹规划是实现无人作战飞机突防攻击的关键技术,是提高飞机的作战性能,实施远程精确打击的有效手段,对于提高作战飞机的生存率和任务成功率至关重要[1]。

　　通常情况下,无人机航迹规划约束条件复杂[2]、规划空间广、任务多样、不确定因素多,因此很难一次性地规划出无人机的航迹。本文提出了一种无人机分层航迹规划的思想,整个航迹规划分成初始航迹生成和最优航迹搜索两步,即首先针对规划环境生成初始参考航迹,并对初始参考航迹施加约束条件和任务指标,然后从综合考虑了约束条件的参考航迹中运用一定的搜索技术搜索出满意的航迹。

　　根据分层规划的思想,首先根据任务飞行环境由Voronoi图生成初始航迹。由于无人机作战区域广阔,威胁错综复杂,从而Voronoi图生成一个巨大的初始航迹空间,通常的搜索算法要获得一条最优航迹需要很长的收敛时间和极大的内存空间,很难投入实际应用。遗传算法作为一种概率搜索算法,采用简单的编码技术,通过模拟生物“优胜劣汰”的世代进化机制,求得复杂问题的理想解。由于其不受问题求解空间限制假设的约束,不必要求待求解问题具有连续性、导数存在和单峰等特性,以及算法本身固有的并行性,使得遗传算法在航迹规划方面具有其他算法无可比拟的优越性[3]。因此,本文在Voronoi图生成航迹搜索空间的基础上,采用遗传算法进行航迹搜索,从而得到满意的航迹。

　　1　航迹空间生成

　　Voronoi图[4-7]是计算几何学中一种重要的几何结构,对于二维平面中的一个点集{pi},pi是其中任意点,则平面上包围所有到pi的距离都小于到{pi}中其他点距离的点的边组成的多边形称为pi的Voronoi多边形, {pi}的所有Voronoi多边形组成的图就称为Voronoi图,可以简述为任意相邻两点连线段的垂直平分线组成Voronoi图。

　　基于Voronoi图进行航迹生成的基本思想是:先将已知的敌方雷达威胁中心位置作为Voronoi图的点,以威胁大小作为Voronoi图邻近区域的“距离”量度,构建出Voronoi图,“距离”越大则所受威胁越小,Voronoi图的各条边在相应点的领域内距威胁“距离”最大,因而所受威胁相应最小,所以Voronoi图中的弧即构成飞行器安全性最高的可飞航线,线段与线段的交点即构成可飞的航迹节点,从而可以根据威胁源的强度大小和弧的长短给出各条弧的相应权值,最后利用遗传算法,从Voronoi图中搜索出最优飞行航迹。威胁模型采用基于人工势场[8]的方法建立,以威胁源为圆心,随着距离的增大,威胁强度以指数递减。具体公式为