基于Voronoi图和蚁群优化算法的无人机航路规划方法

摘要

本发明提供了一种基于Voronoi图和蚁群优化算法相结合的无人机航路规划方法。首先根据地形、雷达、导弹和高炮威胁等各种威胁源的具体特征进行建模，而无人机的航路代价包含其所受的威胁代价和燃油代价；然后对Voronoi图各边给出初始信息素值，令蚂蚁从距离出发点最近的Voronoi节点开始搜索，根据状态转移规则选择行进的Voronoi边，以距离目标点最近的Voronoi节点为终点结束搜索；当所有蚂蚁完成各自候选航路选择后，按改进更新规则对Voronoi图中各边的信息素进行更新，其中没有蚂蚁经过的边进行信息素蒸发，重复这一过程直至搜索到无人机最优航路。该方法具有较好的实时性和快速性，所搜索到的航路更逼近实际的无人机最优航路。

主权项

1.一种基于Voronoi图和蚁群优化算法的无人机航路规划方法，其特征在于：该方法的具体步骤如下：第一步：根据威胁源分布构造Voronoi图，并计算Voronoi图中每条边的总代价；参数初始化，为Voronoi图每条边赋初始信息素值；第二步：将所有蚂蚁置于距离出发点最近的Voronoi图节点，并根据公式$P_{k(a,b)}\left(t\right)=\left\{\begin{array}{cc}\frac{{\tau }_{\mathrm{ab}}^{\alpha }\left(t\right){\eta }_{\mathrm{ab}}^{\beta }\left(t\right)}{\underset{b\in \mathrm{allowed}\left(a\right)}{\Sigma }{\tau }_{\mathrm{ab}}^{\alpha }\left(t\right){\eta }_{\mathrm{ab}}^{\beta }\left(t\right)}& \mathrm{if\; b}\in \mathrm{allowed}\left(a\right)\\ 0& \mathrm{otherwise}\end{array}\right.$选择下一节点，直至所有蚂蚁完成搜索过程；其中，τ_ab(t)表示Voronoi图中边ab上的信息素值；η_ab(t)表示节点a相对于节点b的可见性，η_ab(t)＝1/J_a，b，J_a，b是边ab的总代价；allowed(a)是第k只蚂蚁由节点a到达的所有可行节点集合；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度；第三步：根据公式$J_i={\mathrm{kJ}}_f^i+(1-k)J_t^i$计算出可行路径的代价，并更新所找到的最优路径；其中，k为安全性能与燃油性能的权系数，k∈[0，1]，其值根据无人机所执行的任务而定，如果任务重视飞行时的安全性，则k选择较小的值；如果任务需要飞机的快速性，则k选择较大的值；总之，加权的大小取决于权项的重要性和可行性的综合指标；第四步：参照当前循环中最优路径更新所有Voronoi边信息素值，规则如下列公式所示；τ(a，b)＝(1-ρ)τ(a，b)+ρΔτ(a，b)$\mathrm{\Delta \tau }(a,b)=\underset{k=1}{\overset{\mathrm{num}}{\Sigma }}\Delta {\tau }_k(a,b)$其中，num是蚂蚁的数量，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，ρ的取值范围为：Δτ_k(a，b)表示蚂蚁k经过边ab后信息素增量，其值由下式给出：$\Delta {\tau }_k(a,b)=\left\{\begin{array}{cc}Q/J_{k\min }& \mathrm{if}(a,b)\in \mathrm{path}\\ 0& \mathrm{otherwise}\end{array}\right.;$其中，Q表示信息素强度，Q值是一个常数；J_kmin表示蚂蚁k在本次循环中的最小代价；第五步：若满足循环结束条件，则循环结束并输出程序计算结果，否则跳转到第二步。