陈 伟（电子信息控制重点实验室）

本文分析了复杂环境下无人机航迹规划问题。首先，基于飞行环境建立了约束模型和优化模型；其次在算法的设计上，采用了引入局部搜索操作的粒子群算法，有效平衡了算法在整个搜索过程中的全局搜索能力和局部搜索能力，并通过仿真实验证明了模型和算法的有效性。

引言

无人机具有低成本、小体积、强隐蔽性和高生存力等特点，在多个领域取得了广泛应用。为保证无人机高效完成指定任务，需要为其规划特定的航迹，而随着任务复杂性和飞行环境复杂多变性逐渐增加，预规划航迹往往不能满足实际需求，需要对环境和任务进行实时评估，并进行在线航迹规划。

无人机航迹规划技术，是在综合考虑无人机任务、飞行环境以及自身性能约束下，设计合理的飞行路线，以最大限度地保障无人机成功完成任务并返航。其核心是在综合考虑无人机平台约束和环境约束前提下，如续航时间、油耗、机动性能、威胁等，设计最优或较优的航迹。由于约束因素较多，数学模型较为复杂，是典型的NP-Hard优化问题。在相关理论研究中，广泛采用的方法包括概略图法、单元分解法、人工势场法、数学规划法和进化算法。其中，进化算法基于其启发式的搜索能力，能够处理复杂且变化的问题，得到广泛的研究，主要包括遗传算法、蚁群算法和粒子群算法。

遗传算法是一种模拟生物进化过程的启发式搜索算法，在早期的路径规划问题中被广泛采用。但受限于编码方式，遗传算法在进行航迹规划时的编解码过程往往比较复杂，增加了计算复杂度。蚁群算法是模拟蚂蚁觅食行为的启发式算法，通过不断更新起点至食物源的路径信息素实现最优路径的获取。由于蚁群算法起源于路径选择，使其在航迹规划中设计思路清晰、编解码过程简单，应用非常广泛。然而，蚁群算法的运行机制使得求解过程易于陷入局部最优值，同时当解空间增大时，计算复杂度显著提升，限制了其在三维航迹规划上的应用。

粒子群算法是模拟鸟群觅食行为的启发式算法，形式简单，性能高效，广泛应用于神经网络、数据挖掘等领域。在航迹规划中，有多种三维航迹规划的粒子群算法，第一种是基于地形和威胁信息建立最小威胁曲面，并在该曲面上进行最优航迹搜索。同时，通过将三维航迹在水平面进行投影构建有限多项式，进而将航迹规划问题转化为解空间多项式组合问题，降低了计算复杂度；第二种是以平台机动性能限制、威胁程度和目标距离作为适应度函数，采用连续粒子群算法进行实时规划，求取航迹的中间节点；第三种粒子群算法，引入自适应变异算子，实现粒子速度和位置的自适应更新和变异，以处理三维航迹规划问题；第四种是结合粒子群优化算法和B样条插值方法，通过特定的编码方式和适应度评价函数，使得生成的航迹具有较好的平滑度；第五种以障碍物顶点为基础构造二维解空间，将航迹规划问题转化为非线性最小化问题，在静态和动态环境下实现了最优无碰撞航迹的设计；第六种是针对粒子群算法后期搜索能力不足等缺点，对惯性权重因子进行了改进，并在三维航迹规划中取得了良好的效果。

相关研究表明，标准的粒子群算法在前期具有良好的全局搜索能力，但后期局部搜索能力不足，因此引入的动态调整惯性权重因子方法被广泛采用，以提升算法在后期的局部搜索性能。然而，在相关的改进算法中，由于惯性权重因子的逐渐减小，算法的全局搜索能力显著下降，易于陷入局部最优解。为保证算法的全局搜索能力，同时加强算法的局部搜索能力，本文引入局部搜索算子，实现算法整体性能的提升。

问题分析

在航迹规划的相关设计中，主要对飞行环境模型、约束条件和性能指标函数进行分析。在飞行环境模型中，主要包括可通行威胁区和不可通行威胁区。其中，可通行威胁区是指无人机可以从该区域飞行通过，但该区域的某些因素会影响无人机的飞行安全和任务执行能力，包括强风区、侧风区或其他人为影响因素。不可通行威胁区是指无人机不能从该区域威胁通过，否则无人机会损毁，主要包括地形限制和障碍物等。其飞行环境模型如图1所示。

图1 飞行环境威胁图。

在约束条件分析上，主要考察平台机动性能的限制，包括转向角、最小航迹段和油耗。设无人机航迹表示如(1)所示。

其中（xS，yS）和（xT，yT）分别表示无人机任务的起点和终点，（xi，yi）表示航迹第i个中间节点。

根据平台的机动性能，航迹的转向角应不小于特定角度θmin，即有

其中(xi-1，yi-1)，(xi，yi)，和(xi+1，yi+1)为航迹的相邻节点，Angle{.，.}为两向量间的夹角，可由余弦定理进行计算。

在最小航迹段约束中，由于平台的惯性，无人机在相邻两次改变飞行姿态期间，必须保证最低的直线飞行距离，即有

在油耗约束中，忽略无人机在不同飞行速度下油耗的差异，将油耗与整体航程等同考虑，可得

在航迹规划中，性能指标作为衡量航迹的唯一标准，在很大程度上决定了算法的性能。结合相关文献研究，以航迹所经过区域的威胁度和航迹长度作为评价指标，可以建立如下的优化数学模型。其中，α为权重因子，表征航迹长度length(x，y)和航迹威胁threat(x，y)在总体性能指标中所占比重，可以根据不同需求进行具体设计。

算法设计

粒子群优化算法的每个粒子都有自己的位置和速度，粒子的位置代表解空间的点，通常以xi表示，粒子的速度代表粒子的搜索方向和前进距离，通常以vi表示。该算法在初始时候随机初始化，以f(xi)衡量该粒子的适应度，并以pBesti表示第i个粒子搜索过的最优位置，以gBest表示种群搜索过的最优位置。在进化过程中，粒子基于个体最优信息和全局最优信息进行更新，如(6)、（7）所示。

其中ωd为惯性权重因子，c1和c2分别为个体学习因子和全局学习因子。

研究表明，粒子群算法的搜索能力和更新方程中的参数有很大关系，包括惯性权重因子、个体/全局学习因子和种群规模。惯性权重因子能够平衡算法的全局和局部搜索能力，是重要的控制参数。研究指出，较大的惯性权重因子可以保证算法具有较好的全局搜索能力，而较小的惯性权重因子可以保证较好的局部搜索能力。学习因子决定着粒子向个体历史信息和全局历史信息学习的程度，相关文献对其进行了深入研究并给出了指导性设计意见。在种群规模上，大量的理论研究和仿真实例表明，针对解空间较小的情形，种群规模为20，一般能够满足性能需求，而对于复杂解空间，种群规模为50，一般能够满足性能需求。

从上述分析可知，通过动态调节惯性权重因子，能够有效平衡算法在前期的全局搜索能力和后期的局部搜索能力，一般采用线性或指数递减的形式。另一方面，由于算法在中后期的全局搜索能力下降，会增加陷入局部最优解的风险，尤其在处理具有较多局部最小值的问题时性能欠佳。针对此类情形，本文提出了局部搜索的优化策略，其中粒子群算法始终保持较大的惯性权重因子，以保证算法对全局的搜索能力。同时，在每一次迭代后引入局部搜索算子，对当前解的相邻空间进行局部随机搜索，如(8)所示。

可以看出，局部搜索的前进方向依然受个体最优和全局最优的影响，可以有效地增加算法对历史信息的利用效率。同时应满足v d＜vmax，其中vmax表征算法进行局部搜索领域的范围。根据随机搜索的步长，可以形成新的个体。进一步，将局部搜索的新个体与当前个体进行比较，保留性能较优个体。算法流程如图2所示。

图2 改进PSO算法流程图。

仿真实验

根据图1的环境威胁图，采用基于局部搜索的改进粒子群算法，设计种群数为50，迭代50代，惯性权重因子ω=0.9，学习因子分别为c1=c2=1.5，其稳定的航迹规划结果（最优解出现概率不低于80%）如图3所示。而对于标准粒子群算法（权重因子动态变化），在采用相同种群规模时达到相同的稳定结果需迭代100代左右，体现了局部搜索操作的有效性。

为了进一步比较标准粒子群算法与本文改进粒子群算法的效率，按相同的参数设置运行分别运行20和50次，并进行统计分析，结果如表1所示。可以看出，本文中的算法在有限的迭代步数内具有较强的稳定性。

图3 航迹规划效果图

表1 运行结果统计表

结论

本文针对典型的无人机任务场景，考察了二维情形下无人机航迹规划问题。基于对粒子群算法的深入研究和分析，提出了局部搜索的进化策略。相对于惯性权重动态变化的粒子群算法，本文改进的算法既保证了在整个进化过程中都具有良好的全局搜索能力，也保证了对局部区域的充分搜索。仿真实验表明，基于局部搜索的粒子群算法在航迹规划中有效。 ■