基于稀疏A*算法和遗传算法的航迹规划方法

摘要

本发明涉及一种基于稀疏A*算法和遗传算法的航迹规划方法，属于无人机航迹规划技术领域。本方法针对航迹规划的特点，首先利用SAS算法规划出初始参考航迹，它把约束条件结合到算法搜索中去，可以有效的删除搜索空间中的无用节点，缩短了搜索时间；当无人机实时飞行出现突发威胁时，利用遗传算法进行实时的航迹规划，生成局部最优或者近似最优的航迹，直到威胁消除，UAV返回到原全局最优参考航迹继续飞行。该发明提出的方法具有较好的实时性和快速性，搜索到的航迹更逼近实际的无人机最优航迹；可应用于复杂环境下的机器人路径规划、城市车辆路径规划等技术领域。

主权项

1.基于稀疏A*算法和遗传算法的航迹规划方法，其特征在于：包括如下步骤：步骤1：飞行环境建模；UAV飞行环境规划的三维规划空间表示为几何空间区域{(x，y，z)|0≤x≤Xmax，0≤y≤Ymax，0≤z≤Zmax}；采用数字化栅格的方法将规划空间离散为若干个单元栅格；步骤2：设置无人机航迹规划的初始条件，包含规划的起始点、目标点、威胁分布及地形信息，具体实现方法如下：首先，给定经步骤1栅格化后的飞行环境规划空间中每个单元的高程信息；然后，将飞行任务中的威胁模型化：将威胁的地理位置、高度和影响范围等威胁指数转化为离散化规划空间中的单元信息；最后，在飞行环境模型和威胁模型建立后，根据任务要求，在离散化规划空间中找到起始点S和目标点G(x_g,y_g,z_g)；所述起始点S位于栅格顶点；步骤3：根据任务要求，利用SAS算法生成全局最优的参考航迹；具体实现方法为：步骤3.1，在与当前航迹点相邻的栅格顶点中，排除不满足约束条件的点，将其余的相邻栅格顶点作为下一步可能的航迹点；在初步判断出无人机下一步的可能航迹点后，从当前航迹点开始，计算下一步可能航迹点的代价值g_i：$g_i=w_i{l}_i^2+w_2{h}_i^2+w_3{f}_{\mathrm{TAi}}---\left(3\right)$式中l_i表示第i段航迹的长度，h_i为第i个飞行节点的飞行高度，f_TAi表示第i段航迹的威胁指数；w₁为l_i的系数、w₂为h_i的系数、w₃为f_TAi的系数；步骤3.2，计算步骤3.1得到的可能的航迹点到目标位置的代价估值u_i，(x_i，y_i，z_i)为第i点的坐标值，(x_g，y_g，z_g)为目标点的坐标；u_i＝(x_i-x_g)²+(y_i-y_g)²+(z_i-z_g)²                         (4)步骤3.3，计算步骤3.1得到的各个可能的航迹点总的航迹代价f_i：f_i＝g_i+u_i                                              (5)将f_i按大小顺序排列，放入OPEN表中，从建立的OPEN表中选择f_i最小的点作为下一个航迹点放入CLOSED表中；在初始化时，将起始点S放入OPEN表，CLOSED表置空；步骤3.4，将步骤3.3得到的下一个航迹点作为下一步循环的当前航迹点，继续按照步骤3.1至步骤3.3所述方法寻找下一航迹点，直到某一点与目标点G的距离小于L为止，航迹搜索过程结束；步骤3.5，从得到的CLOSED表中的最后航迹点开始向上回溯，直到起始点，再加入目标点，最终得到从起始到目标的全局最优飞行参考航迹；步骤4：UAV沿步骤3确定的最优参考航迹飞行，当出现突发威胁时，启动基于遗传算法的UAV三维航迹规划算法进行在线局部航迹规划，生成局部最优或者近似最优的航迹；具体实现过程如下：步骤4.1，根据突发威胁的情况，确定局部航迹规划的起始点、终止点和威胁指数；步骤4.2，根据步骤4.1确定的起始点、终止点，随机生成m条染色体，每条染色体表示一条飞行航迹；所有航迹的第一个和最后一个节点的坐标相同；所述m条染色体包含了可行航迹和不可行航迹；步骤4.3，计算步骤4.2得到的每一条航迹J的适应值F(J)其中，C(J)为航迹代价，n为航迹的节点个数；$C\left(J\right)=\underset{i=1}{\overset{n}{\Sigma }}(w_1{l}_i^2+w_2{h}_i^2+w_3{f}_{\mathrm{TAi}})---\left(7\right)$C_max为m条染色体中所有可行航迹中的最大代价；对于可行航迹，只需要根据m条染色体计算它的航迹代价；对于不可行航迹的适应值，与它本身的约束违背量以及m条染色体有关，如果m条染色体没有可行航迹，C_max为0；本发明采用的航迹评价方法，不但包含航迹的代价，还要考虑航迹的各种约束条件；约束违背量为根据航迹约束条件进行正规化处理后得到；步骤4.4，选取局部最优航迹；具体方法为：按照比例适应度分配的选取方法，从m条染色体中选取S个染色体组成繁殖池；对于某个染色体i，其适应度为F_i，则其被选择的概率P_i为$P_i=\frac{F_i}{{\Sigma }_{i=1}^m{F}_i}---\left(8\right)$步骤4.5，根据预先设计的概率机制，选择相应的进化算子作用于被选出的S个染色体；由于每次进化都要利用平滑算子和定向扰动算子，所以，平滑算子和定向扰动算子被选择的概率为1；步骤4.6，通过进化算子的作用生成新个体，将新生成的个体加入到染色体中，按照步骤4.3的方法计算新个体的适应值；步骤4.7，将扩展后的染色体中适应值较小的S个染色体删除，使其恢复到原来的染色体大小；步骤4.8，重复步骤4.4至步骤4.7，判断是否满足终止条件：迭代过程进行到预先给定的最大次数，或者最优个体在若干次迭代中其适应值保持不变；当满足了终止条件，则从m条染色体中选出适应值最小的染色体作为所求航迹；步骤5：UAV沿步骤4得到的局部最优航迹飞行，直到威胁消除，UAV返回到步骤3得到的全局最优参考航迹继续飞行；至此，就实现了基于SAS和遗传算法的航迹规划过程。