Event-triggered gray wolf optimization for quadrotor unmanned aerial vehicle three-dimensional trajectory planning
-
摘要: 针对复杂环境下四旋翼无人机三维航迹规划问题，提出了一种改进的事件触发灰狼优化算法(event triggered grey wolf optimization，ETGWO)。引入球面矢量刻画飞行路径的生成，通过减少搜索空间提升搜索能力；设计自适应权重动态调整飞行航迹成本适应度函数，以提高航迹规划效率和准确性；在灰狼优化算法(grey wolf optimization，GWO)基础上，选择使用改进的非线性收敛因子，提升算法的鲁棒性；为了更好地平衡算法的全局搜索和局部搜索能力，通过引入基于事件触发机制的灰狼个体位置更新速度来改进GWO算法的位置更新策略。仿真对比实验表明，所提出ETGWO算法在四旋翼无人机(quadrotor unmanned aerial vehicles, QUAV)飞行航迹规划方面具有更优越的性能。Abstract: An improved event-triggered gray wolf optimization algorithm (ETGWO) is proposed for the 3D path planning of quadrotor unmanned aerial vehicles in complex environments. First, the search space and search capabilities are reduced and improved, respectively, by introducing spherical vectors to characterize flight path generation. Second, the adaptive weights are designed to dynamically adjust the fitness function of the flight trajectory cost, thereby improving the efficiency and accuracy of path planning. Based on the gray wolf optimization (GWO) algorithm, a nonlinear convergence factor is selected to enhance the robustness of the algorithm. Additionally, to better balance the global and local search capabilities, the position update strategy of the gray wolf individuals is developed based on the update velocity, which is integrated with the event-triggered mechanism. Finally, simulation and comparative experiments are performed to confirm the superior planning performance of ETGWO compared with those of other algorithms.
-
四旋翼无人机(quadrotor unmanned aerial vehicle, QUAV) 因其工作效率高、成本低、适应多样化任务需求等特点，广泛应用于军事侦察、物流配送、农业监测、环境保护等领域[1-5]。路径规划是确保无人机安全高效完成指定任务的关键一环，需要在一系列约束条件下提前规划出一条从出发点到达任务点、能耗最小且无碰撞的飞行路径[6]。
目前，传统的无人机路径规划算法包括随机路图法[7]、人工势场法[8]、RRT*（repaidly-exploring random trees）算法[9]等。文献[10]应用模糊控制算法融合预测机制开发了一种局部路径规划策略，但在三维路径规划方面的研究较少。为了克服计算成本高的缺点，研究者们相继提出了启发式路径规划算法，如模拟退火算法[11]、Dijkstra算法[12]等。文献[13]利用改进模拟退火算法与共轭方向法对移动机器人全局路径规划进行求解；文献[14]在Dijkstra算法的基础上，从节约存储空间和提高运算效率方面进行改进，更好地解决了最短路径问题。虽然以上算法具有较好的路径规划能力，但是它们在复杂环境中难以得到高质量的路径。
在无人机路径规划问题中，对复杂的三维飞行环境进行建模是至关重要的，且被证实为一个NP-hard（non-deterministic poly nominal hard）问题。无人机需要考虑基本约束条件（如长度、转向角、时间、高度、俯仰角等），在保证安全的前提下使飞行航线避开障碍物和危险区域[15]。受自然界现象的启发，一系列的群体智能算法被开发出来[16-17]，如蚁群算法[18]、粒子群算法[19]、人工鱼群算法[20]、细菌觅食优化算法[21]、灰狼算法[22]等。文献[23-24]提出了一种双群学习粒子群算法，并设计了一种维数学习策略，使两个群体分别负责开发和探索，并应用于无人机路径规划问题。文献[25]提出了一种新的元启发式算法，模仿自然界中灰狼的领导等级制度和狩猎机制。文献[26-27]针对传统灰狼算法优化精度低等缺点，构建混合灰狼算法，将其应用机器人路径规划（robot path planning, RPP）问题。这些智能算法能根据不同的搜索策略迅速找到有效途径，并不断迭代获得最优路径。
为了获得QUAV飞行航迹的高质量解，针对现有算法容易陷入局部最优、收敛速度慢等问题，本文提出一种基于球面矢量和事件触发机制的改进灰狼优化算法。首先，通过球面矢量的仰角和方位角可以直接实现转弯和爬坡角的约束，进一步减少搜索空间，以提升搜索能力；其次，引入事件触发机制控制速度更新，确保在特定条件满足时能够自动触发，进行自适应加权速度更新，平衡算法的全局开发和局部搜索能力。
1. QUAV三维航迹规划模型
为了实现QUAV高效执行既定任务，安全可行的最优航迹路径需要根据外部环境和飞行约束条件进行提前规划。由于无人机是通过一个地面控制站 (ground control station, GCS) 来控制的，所以一条飞行路径
$ {P_i} $ 是通过包含$ N $ 个航迹点的列表来表示，每个航迹点都对应于搜索地图中带有坐标的路径节点$ {P_{i,j}}({x_{i,j}},{y_{i,j}},{{\textit{z}}_{i,j}}), $ $ j = 1,2, \cdots ,N $ 。1.1 环境建模
根据无人机的机动特性和相关飞行约束条件，本文引入球面矢量刻画飞行路径的生成，将一条飞行路径编码为一组球面矢量
$ \{ ({r_{i,j}},{\varphi _{i,j}},{\theta _{i,j}})\} $ ，其中3个分量分别为半径$ {r_{i,j}} \in (0,L) $ 、仰角$ {\varphi}_{i,j}\in \left(-\dfrac{\text{π} }{2},\dfrac{\text{π} }{2}\right) $ 和方位角$ {{\theta }_{i,j}} \in ( - \text{π} ,\text{π} ) $ ，向量$ ({r_{i,j}},{{\varphi }_{i,j}},{{\theta }_{i,j}}) $ 表示无人机从航迹点$ {P_{i,j}}({x_{i,j}},{y_{i,j}},{{\textit{z}}_{i,j}}) $ 到下一个航迹点$ {P_{i,j + 1}}({x_{i,j + 1}},{y_{i,j + 1}},{{\textit{z}}_{i,j + 1}}) $ 的运动，即$ {{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}} $ ，如图1所示。
图 1 基于球面矢量的航迹生成原理Fig. 1 Schematic diagram of spherical vector-based trajectory generation
下载:
全尺寸图片
因此，可以得到笛卡尔坐标系下各个航迹点的分量表达式为
$$ \left\{ {\begin{array}{*{20}{l}} {{x_{i,j + 1}} = {x_{i,j}} + {r_{i,j}}\sin {{\varphi }_{i,j}}\cos {{\theta }_{i,j}}} \\ {{y_{i,j + 1}} = {y_{i,j}} + {r_{i,j}}\sin {{\varphi }_{i,j}}\sin {{\theta }_{i,j}}} \\ {{{\textit{z}}_{i,j + 1}} = {{\textit{z}}_{i,j}} + {r_{i,j}}\cos {{\varphi }_{i,j}}} \end{array}} \right. $$ (1) 为了更准确地刻画实际飞行环境，本文采用数字高程模型 (digital elevation model， DEM) 数字化表达地形表面形态，通过数字阵列信息模型
$ (x,y,{\textit{z}}) $ 实现对地面地形的数字化模拟，描述地理空间中的地形高低起伏。QUAV执行指定任务时，其飞行路径受到禁飞区、恶劣天气区域、信号弱、建筑物等障碍区域的影响。本文利用圆柱体模型模拟障碍区域，障碍区域建模效果如图2。
图 2 三维地形及障碍物示意Fig. 2 3D terrain and obstacle schematic diagram下载:
全尺寸图片
第
$ k $ 个障碍区域$ {A_k}(x,y,{\textit{z}}) $ 的数学模型为$$ \left\{ {\begin{array}{*{20}{l}} {{{(x - {x_k})}^2} + {{(y - {y_k})}^2} = R_k^2 } \\ {{\textit{z}} \in [0,{h_k}]} \end{array} } \right. $$ (2) 式中
$ ({x_k},{y_k}) $ 、$ {R_k} $ 和$ {h_k} $ 分别代表第$ k $ 个障碍区域的中心坐标、半径和障碍物高度。此外，为了提高QUAV的飞行航迹规划效率和减少航迹成本，对QUAV的指定工作区域进行边界约束，即
$$ \left\{ \begin{gathered} {x_{i,j}} \in [1,{x_{\max }}] \\ {y_{i,j}} \in [1,{y_{\max }}] \\ {{\textit{z}}_{i,j}} \in [{h_{\min }}({\mathrm{DEM}},{\textit{z}}),{{\textit{z}}_{\max }}] \\ \end{gathered} \right. $$ (3) 式中：
$ ({x_{i,j}},{y_{i,j}},{{\textit{z}}_{i,j}}) $ 表示路径$ {P_i} $ 中第$ j $ 个航迹点的三维空间坐标，$ ({x_{\max }},{y_{\max }},{{\textit{z}}_{\max }}) $ 是指定空间区域的最大边界，$ {h_{\min }}({{\mathrm{DEM}}},{\textit{z}}) $ 表示基准地形的最低高度，DEM是数学高层模型。1.2 飞行航迹成本适应度函数
在QUAV三维航迹规划中，路径规划问题转化为飞行航迹成本最优化问题，将飞行航迹总成本函数作为适应度函数，则适应度值越小，飞行路径的代价越小，路径选择越优。本文综合考虑QUAV飞行路径长度优化、路径平滑性、安全性及可行性约束条件(包括飞行高度、碰撞以及无人机姿态角约束)等关键指标，构建一种飞行航迹成本适应度函数。
1.2.1 路径长度成本函数
路径长度对飞行时间和燃料消耗有直接的影响，是评估飞行航迹优劣的重要指标。假设每条飞行路径
$ {P_i} $ 中有$ N $ 个航迹点，根据航迹点坐标(式(1))，则路径长度成本函数可以表示为$$ {F_1}({P_i}) = \sum\limits_{j = 1}^{N - 1} {\left\| {{{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}}} \right\|} { = \sum\limits_{j = 1}^{N - 1} {{r_{i,j}}} } $$ (4) 1.2.2 飞行高度成本函数
在执行任务时，既要避免与基准地形或障碍物发生碰撞，又要满足特定任务要求，如在测量和搜索任务中，需要机载摄像机在特定的分辨率和视野下收集视觉图像数据，从而限制飞行高度。也就是说，QUAV的飞行高度经常被限制在给定的范围内，记最小飞行高度
$ {h_{\min }} $ 和最大飞行高度$ {h_{\max }} $ 。因此，相对于航迹点$ {{\boldsymbol{P}}_{i,j}} $ 的高度成本函数可以定义为$$ {f}_{i,j}({{\boldsymbol{P}}}_{i,j})=\left\{\begin{array}{ll}\left|{h}_{i,j}-\dfrac{{h}_{\mathrm{min}}+{h}_{\mathrm{max}}}{2}\right|, \qquad {h}_{\mathrm{min}}\leqslant {h}_{i,j}\leqslant {h}_{\mathrm{max}}\\ \infty , \qquad 其他\end{array}\right. $$ (5) 式中：
$ {h_{i,j}} $ 表示航迹点$ {{\boldsymbol{P}}_{i,j}} $ 相对于地面的距离。可以看出，$ {f_{i,j}}({{\boldsymbol{P}}_{i,j}}) $ 能够反映实际飞行高度的成本，并对超出范围的飞行高度进行惩罚。因此，假设每条飞行路径$ {P_i} $ 中有$ N $ 个航迹点，则飞行航迹的高度成本函数为$$ {{F_2}({P_i})} { = \sum\limits_{j = 1}^N {{f_{i,j}}} ({{\boldsymbol{P}}_{i,j}})} $$ (6) 1.2.3 飞行威胁成本函数
除了路径和高度优化外，航迹规划还需要引导无人机绕过操作空间中的障碍区域，确保无人机的安全运行。设
$ K $ 为所有障碍区域威胁的集合，假设每个威胁都对应一个规定的圆柱体区域，其在$ O - xy $ 平面上的投影为中心坐标$ {C_k} $ 和半径$ {R_k} $ ，对于给定路径$ {P_i} $ 中的一条子路径$ {{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}} $ ，其在$ O - xy $ 平面上的投影为$ {{\bar{\boldsymbol P}}_{i,j}}{{\bar{\boldsymbol P}}_{i,j + 1}} $ ，如图3所示，显然，相应的威胁成本与QUAV到威胁中心$ {C_k} $ 的距离$ {d_k} $ 成正比。
图 3 飞行威胁成本分析示意Fig. 3 Flight threat cost analysis schematic下载:
全尺寸图片
考虑QUAV的尺寸
$ {d_{{\mathrm{QUAV}}}} $ 和威胁区域到碰撞区的距离$ {d_{{\mathrm{threat}}}} $ ，对于障碍区域集$ K $ 和航迹子路径$ {{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}} $ 之间的威胁成本$ {T_k}({{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}}),(k = 1,2, \cdots ,K) $ 可以定义为$$ {T_k}({{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}}) = \left\{ \begin{gathered} {0,} \qquad {{d_k} \geqslant D} \\ {D - {d_k},} \qquad {d < {d_k} < D} \\ {\infty ,} \qquad {{d_k} \leqslant d} \\ \end{gathered} \right. $$ (7) 式中：
$ D = {d_{{\mathrm{QUAV}}}} + {d_{{\mathrm{threat}}}} + {R_k},d = {d_{{\mathrm{QUAV}}}} + {R_k} $ 。因此，该条路径的威胁成本函数可以表示为
$$ {F_3}({P_i}) = \sum\limits_{j = 1}^{N - 1} {\sum\limits_{k = 1}^K {{T_k}({{\boldsymbol{P}}_{i,j}}{{\boldsymbol{P}}_{i,j + 1}})} } $$ (8) 注1 在实际飞行路径规划过程中，需要注意的是
$ {d_{{\mathrm{QUAV}}}} $ 由无人机尺寸决定，而距离$ {d_{{\mathrm{threat}}}} $ 取决于应用、操作环境和定位精度等因素。例如，$ {d_{{\mathrm{threat}}}} $ 可以在具有良好GPS信号的静态环境中设定为几十米，或者在具有动态目标和弱定位GPS信号环境中设定为几百米[28]。1.2.4 路径平滑成本函数
为了避免快速飞行时姿态角度变化过大造成不稳定或碰撞，需对QUAV转弯角和爬升角附加约束，以规划出相对平滑的航迹，提高适航性。因此，平滑成本评估生成可行路径的转弯率和爬坡率是重要指标。
为了获得飞行航迹平滑成本，先计算QUAV在各航迹子路径上的转弯角和爬升角。如图1所示，转弯角
$ {{\phi }_{i,j}} $ 是投影向量$ {\bar{\boldsymbol{P}}_{{{i,j}} - {{1}}}} {\bar{\boldsymbol{P}}_{{{i,j}}}} $ 和$ {\bar{\boldsymbol{P}}_{{{i,j}}}}{\bar{\boldsymbol{P}}_{{{i,j}} + {{1}}}} $ 之间的夹角，即$$ {\phi _{i,j}} = \arctan \left(\frac{{||{{{\bar{\boldsymbol P}}}_{{{i,j}} - {{1}}}}{{{\bar{\boldsymbol P}}}_{{{i,j}}}} \times {{{\bar{\boldsymbol P}}}_{{{i,j}}}}{{{\bar{\boldsymbol P}}}_{{{i,j}} + {{1}}}}||}}{{{{{\bar{\boldsymbol P}}}_{{{i ,j}} - {{1}}}}{{{\bar{\boldsymbol P}}}_{{{i ,j}}}} \times {{{\bar{\boldsymbol P}}}_{{{i,j}}}}{{{\bar{\boldsymbol P}}}_{{{i,j}} + {{1}}}}}}\right) $$ (9) 类似地，如图1所示，爬升角
$ {{\psi }_{i,j}} $ 是航迹子路径向量$ {{\bar{\boldsymbol P}}_{{{i,j}}}}{{\bar{\boldsymbol P}}_{{{i,j}} + {{1}}}} $ 与其投影向量$ {{\bar{\boldsymbol P}}_{{{i,j}}}}{{\bar{\boldsymbol P}}_{{{i,j}} + {{1}}}} $ 之间的夹角，即$$ {\psi _{i,j}} = \arctan \left(\frac{{{{\textit{z}}_{i,j + 1}} - {{\textit{z}}_{i,j}}}}{{||{{{\bar{\boldsymbol P}}}_{{{i,j}}}}{{{\bar{\boldsymbol P}}}_{{{i,j}} + {{1}}}}||}}\right) $$ (10) 因此，该条路径的平滑成本函数定义为
$$ {{F_4}({P_i})} { = {p_1}\sum\limits_{j = 1}^{N - 2} {{{\phi }_{i,j}}} + {p_2}\sum\limits_{j = 1}^{N - 1} | { }{{\psi }_{i,j}} - {{\psi }_{i,j - 1}}|} $$ (11) 式中
$ {p_1} $ 和$ {p_2} $ 分别是对转弯角和爬升角的惩罚系数。1.2.5 航迹成本总体适应度函数
对于QUAV的三维航迹规划模型，本文通过自适应加权各成本函数获得总体适应度函数，进而提升算法的效率和航迹最优性。优化过程中，记录不同的最优个体的适应度值，根据其占总比例来自适应调整总体适应度函数，避免适应度函数过于单一或者过于复杂导致算法性能下降，从而提高算法的鲁棒性和泛化能力。
综上分析，飞行航迹成本总体适应度函数可以表示为
$$ F({P_i}) = \sum\limits_{k = 1}^4 {{w_k}} {F_k}({P_i}) $$ (12) 式中：
$ {w_k} (k = 1,2,3,4) $ 是自适应权重系数，其表达式为$$ {w_k} = \frac{1}{3}\left( {1 - \frac{{{F_k}({P_i})}}{{\displaystyle\sum\limits_{k = 1}^4 {{F_k}} ({P_i})}}} \right) $$ (13) 2. 基于ETGWO的QUAV航迹规划
2.1 灰狼优化算法
灰狼优化算法(grey wolf optimization，GWO)，受启发于自然界灰狼种群的领导层级和狩猎机制，进行优化搜索。灰狼种群分层任务分为4种类别，如
$ {\alpha }、{\beta }、{\delta }、{\omega } $ 用来模拟各个阶层(如图4所示)：$ {\alpha } $ 狼为最优解；$ {\beta } $ 狼负责协助$ {\alpha } $ 狼群，视为次优解；$ {\delta } $ 狼为末优解，执行$ {\alpha }、{\beta } $ 狼的命令和决策，适应度差的$ {\alpha }、{\beta } $ 狼自动降为$ {\delta } $ 狼；$ {\omega } $ 狼作为候选解，围绕三层狼群进行位置更新。灰狼种群围成包围圈追逐猎物，最终攻击猎物。
图 4 灰狼群体的等级结构Fig. 4 Hierarchical structure of gray wolf packs下载:
全尺寸图片
灰狼种群包围猎物的过程可以通过位置更新公式来实现：
$$ {\boldsymbol{D}} = C \cdot {\boldsymbol{X}}_{\rm{p}}^{{t}} - {{\boldsymbol{X}}^{{t}}} $$ (14) $$ {{\boldsymbol{X}}^{{{t}} + {{1}}}} = {\boldsymbol{X}}_{\rm{p}}^{{t}} - A{\boldsymbol{D}} $$ (15) 式中：
$ t $ 为当前迭代次数，$ {\boldsymbol{D}} $ 表示灰狼和猎物之间的距离。式(15)是灰狼个体三维位置更新公式，$ {\boldsymbol{X}}_{\rm{p}}^{{t}} $ 和$ {{\boldsymbol{X}}^{{t}}} $ 分别是猎物的位置向量和灰狼的位置向量。$ A $ 和$ C $ 为确定的系数，其计算公式分别为$$ \left\{ \begin{gathered} A = 2a \cdot {r_1} - a \\ C = 2{r_2} \\ \end{gathered} \right. $$ (16) 式中：
$ {r_1}、{r_2} $ 是取值在$ [0,1] $ 内的两个一维正态分布分数，收敛因子$ a $ 是一个平衡灰狼优化算法探索和开发能力的关键参数。当猎物不移动时，灰狼种群会攻击猎物，$ A $ 的取值受$ a $ 的影响，一般地，$ a $ 的取值随着迭代次数的增大从2到0线性递减，例如，收敛因子$ a $ 的表达式为$$ a = 2 - \frac{{2t}}{{{T_{\max }}}} $$ (17) 式中：
$ {T_{\max }} $ 为最大迭代次数，$ t $ 为当前迭代次数。注2 若
$ a $ 的取值越大则灰狼越远离猎物，进行全局搜索；若$ a $ 取值越小则灰狼越靠近猎物，进行局部搜索。记
$ {{\boldsymbol{D}}_\alpha }、{{\boldsymbol{D}}_\beta }、{{\boldsymbol{D}}_\delta } $ 分别代表灰狼个体到$ {\alpha } $ 、$ {\beta } $ 、$ {\delta } $ 狼的距离，则有$$ \left\{ \begin{gathered} {{\boldsymbol{D}}_\alpha } = \left| {{C_1} \cdot {{\boldsymbol{X}}_\alpha } - {\boldsymbol{X}}} \right| \\ {{\boldsymbol{D}}_\beta } = \left| {{C_2} \cdot {{\boldsymbol{X}}_\beta } - {\boldsymbol{X}}} \right| \\ {{\boldsymbol{D}}_\delta } = \left| {{C_3} \cdot {{\boldsymbol{X}}_\delta } - {\boldsymbol{X}}} \right| \\ \end{gathered} \right. $$ (18) 根据式(15)，进一步有灰狼个体位置更新方程：
$$ \left\{ \begin{gathered} {{\boldsymbol{X}}_1} = {{\boldsymbol{X}}_\alpha } - {A_1} \cdot {{\boldsymbol{D}}_\alpha } \\ {{\boldsymbol{X}}_2} = {{\boldsymbol{X}}_\beta } - {A_2} \cdot {{\boldsymbol{D}}_\beta } \\ {{\boldsymbol{X}}_3} = {{\boldsymbol{X}}_\delta } - {A_3} \cdot {{\boldsymbol{D}}_\delta } \\ \end{gathered} \right. $$ (19) 式中：
$ {{\boldsymbol{X}}_1}、{{\boldsymbol{X}}_2}、{{\boldsymbol{X}}_3} $ 分别代表在$ {\alpha } $ 、$ {\beta } $ 、$ {\delta } $ 狼指导下灰狼个体更新的位置，然后取三者的平均值表示灰狼更新后的位置，即$$ {{\boldsymbol{X}}^{t + 1}} = \frac{{{{\boldsymbol{X}}_1} + {{\boldsymbol{X}}_2} + {{\boldsymbol{X}}_3}}}{3} $$ (20) 2.2 事件触发GWO算法
本文将每条路径编码为一组球面矢量，每个矢量描述QUAV从一个航迹点到另一个航迹点的运动。因此，一条含有
$ n $ 个节点的飞行路径$ {P_i} $ 可以表示为$ 3n $ 维的超球面矢量：$$ {{\boldsymbol{P}}_i} = ({r_{i1}},{{\phi }_{i1}},{{\theta }_{i1}},{r_{i2}},{{\phi }_{i2}},{{\theta }_{i2}}, \cdots ,{r_{in}},{{\phi }_{in}},{{\theta }_{in}}),n = N - 2 $$ (21) 为了平衡算法的全局和局部搜索能力，引入基于事件触发机制[29]的灰狼个体位置更新速度来改进GWO算法的位置更新策略。将灰狼个体的位置描述为飞行路径
$ {P_i} $ 中第$ j $ 个子路径，记为球面矢量$ {{\boldsymbol{S}}_{i,j}} = ({r_{i,j}},{{\phi }_{i,j}},{{\theta }_{i,j}}) $ ，定义位置更新速度为$ {{\boldsymbol{V}}_{i,j}} = (\Delta {r_{i,j}},\Delta {{\phi }_{i,j}},\Delta {{\theta }_{i,j}}) $ 。注3 使用球面矢量的基本原理是通过矢量的幅度、高程和方位角分量与无人机速度、转弯角度和爬升角的关系，提高导航的安全性。因此，飞行航迹规划在构型空间而不是笛卡尔空间中寻找高质量解。此外，通过球面矢量直接实现转弯和爬坡角的约束，进一步减少搜索空间，以提升搜索能力。
2.2.1 改进的非线性收敛因子
原始GWO算法使用线性递减的控制参数
$ a $ ，但这种方法不能满足非线性或复杂搜索过程的需求。因此，学者们引入了非线性收敛因子[30]，如$$ a=\left\{\begin{gathered}2-\frac{15t}{2{T}_{\mathrm{max}}}, \qquad t \leqslant \frac{2{T}_{\mathrm{max}}}{15} \\ 2+ \cos \left(\frac{15\text{π} }{27{T}_{\mathrm{max}}}\left(t-\frac{2{T}_{\mathrm{max}}}{15}\right)+\frac{\text{π} }{2}\right), \qquad 其他 \end{gathered}\right. $$ (22) 显然，式(22)所生成的收敛因子在迭代前期线性递减，以快速开发全部区域，随后速度减慢，以提升局部搜索能力。
为了满足前期全局开发和局部搜索的要求，本文采用一种非线性控制参数策略，非线性收敛因子的表达式为
$$ a = {a_{\mathrm{m}}}\left[ {1 - {{\left( {\frac{{{{\mathrm{e}}^{\tfrac{t}{{{T_{{\text{max}}}}}}}} - 1}}{{{\mathrm{e}} - 1}}} \right)}^k}} \right]{\text{ }} $$ (23) 式中：
$ {a_{\mathrm{m}}} $ 为收敛因子的初始值；$ k $ 为调节参数，一般在(0,10]内取值。2.2.2 改进的GWO算法
为了减少计算成本并提高飞行航迹规划效率，引入事件触发机制控制速度更新，通过设置合适条件，确保在特定条件满足时能够自动触发速度更新。
记第
$ t $ 次迭代时$ {\alpha } $ 、$ {\beta } $ 和$ {\delta } $ 狼的适应度值分别为$ {E_1} = F({\alpha }),{E_2} = F({\beta }) $ 和$ {E_3} = F({\delta }) $ ,$ E = \displaystyle\sum\limits_{l = 1}^3 {{E_l}} $ ，则速度更新的自适应权重系数$ {{\tau }_l} $ 可以表示为$$ {{{\tau }_l}} { = \frac{{E - {E_l}}}{{2E}}, \quad l = 1,2,3} $$ (24) 从而，可以定义位置更新速度的表达式为
$$ \begin{gathered} {\boldsymbol{V}}_{i,j}^{t + 1} = {\lambda }{\boldsymbol{V}}_{i,j}^t + {{\tau }_1}{r_1}({{\boldsymbol{S}}_1} - {\boldsymbol{S}}_{i,j}^t) + \\ {{\tau }_2}{r_2}({{\boldsymbol{S}}_2} - {\boldsymbol{S}}_{i,j}^t) + {{\tau }_3}{r_3}({{\boldsymbol{S}}_3} - {\boldsymbol{S}}_{i,j}^t) \end{gathered} $$ (25) 式中：
$ {\lambda } $ 为惯性权重，$ {r_1}、{r_2}、{r_3} $ 是$ [0,1] $ 的随机数，$ {{\boldsymbol{S}}_1}、{{\boldsymbol{S}}_2}、{{\boldsymbol{S}}_3} $ 为第$ t $ 次迭代时灰狼个体受$ {\alpha } $ 、$ {\beta } $ 和$ {\delta } $ 狼指导之后更新的位置，其计算方法见式(19)。考虑到QUAV三维航迹规划的基本原则是要使得飞行航迹成本的总体适应度值尽可能小，因此，可以通过比较迭代前后
$ {\alpha } $ 狼的总体适应度值来选择是否进行速度更新。定义相邻两次迭代$ {\alpha } $ 狼的总体适应度值之间的差值为$$ e = {F^t}({\alpha }) - {F^{t - 1}}({\alpha }), \quad t \in [2,{T_{\max }}] $$ (26) 式中：
$ {F^t}({\alpha }) $ 和$ {F^{t - 1}}({\alpha }) $ 分别为第$ t $ 次和第$ t - 1 $ 次迭代时$ {\alpha } $ 狼的总体适应度值。因此，结合式(25)和(26)，设计基于事件触发机制的灰狼个体位置更新速度为
$$ {{\boldsymbol{V}}_{i,j}^{t + 1}}{ = \left\{ {\begin{array}{*{20}{l}} {{\boldsymbol{V}}_{i,j}^{t + 1},}&{e = 0} \\ {{\boldsymbol{V}}_{i,j}^t,}&{e \ne 0} \end{array}} \right.} $$ (27) 进而，可以得到灰狼个体的位置更新方程：
$$ {{\boldsymbol{S}}_{i,j}^{t + 1}} = {\boldsymbol{S}}_{i,j}^t + {\boldsymbol{V}}_{i,j}^{t + 1} $$ (28) 2.3 算法实现
本文所提出的ETGWO算法与其他变型GWO算法结构相似，包括参数初始化、灰狼个体生成和群演化，但在灰狼个体位置更新方程上不同。通过引入基于事件触发机制的位置更新速度，改进灰狼个体的位置更新策略。下面为ETGWO算法的伪代码。
输入 灰狼种群
$ S $ ，种群个体数量$ {N_s} $ ，问题维数$ {D_s} $ ，最大迭代次数$ {T_{\max }} $ ，约束条件$ C $ 。算法描述
初始化 获取搜索地图和初始路径规划信息；
for i=1:
$ {N_s} $ dofor j=1:
$ {D_s} $ do初始化灰狼种群；
end for
end for
计算灰狼个体适应度值，并选出
$ \alpha 、\beta 、\delta $ 狼；While t <
$ {T_{\max }} $ do根据式 (23)更新收敛因子a；
for i=1:
$ {N_{\textit{z}}} $ dofor j=1:
$ {D_{\textit{z}}} $ do根据式(18)和(19)计算
$ \boldsymbol{S}_1、\boldsymbol{S}_2、S_3 $ ；根据式(26)计算事件触发条件e；
If e = 0 then根据式(25)计算
$ {\boldsymbol{V}}_{i,j}^{t + 1} $ ；else 停止更新速度，即
$ {\boldsymbol{V}}_{i,j}^{t + 1} = {\boldsymbol{V}}_{i,j}^t $ ；end if 根据式(28)更新灰狼个体位置；
end for
end for
重新计算适应度值，并更新
$ \alpha 、\beta 、\delta $ 狼；t=t+1
end while
算法结束；
输出 全局最优解。
3. 仿真实验与对比分析
为了评估本文所提出的ETGWO算法的飞行航迹规划性能，将ETGWO算法与线性收敛因子GWO算法(sine-based linear grey wolf optimizer，SLGWO)、非线性收敛因子GWO算法(sine-based nonlinear grey wolf optimizer，SNGWO)、粒子群−灰狼混合算法(sine-enhanced hybrid grey wolf optimizer，SHGWO)3种改进的GWO算法在相同环境下进行对比仿真实验。仿真实验环境：Intel(R) Core(TM) i7-1165G7处理器、16 GB RAM配置计算机，Windows 10操作系统(64位)。
3.1 场景设置
用于评估的场景是基于由激光雷达传感器衍生的真实DEM地图。航迹规划操作空间为
1000 m×850 m×400 m，其中包括基准地形和障碍区域，障碍区域用6个不同颜色的圆柱体表示，障碍区域参数为$ (x,y,{\textit{z}}) $ ：{(380, 250, 150), (400, 600, 100), (500, 450, 150), (600, 250, 150), (650, 750, 150), (700, 550, 150)}，半径$ R $ ：{70, 80, 80, 70, 80 70}，起点坐标为(100, 100, 100)，终点坐标为(800, 800, 150)。3.2 实验结果对比分析
为了确保比较分析的公平性，所有变型GWO算法采用相同的参数集：灰狼种群个体数为500，最大迭代次数为200。在比较实验中，所有算法均运行20次，获得相应平均值(Mean)和标准差值(Std)。在对比实验中，分别设置航迹点个数为
$ n = 12 $ 和$ n = 22 $ ，对应的航迹子路径线段分别为10个和20个。所有算法都能够快速收敛，但其适应度值不同，表1结果也验证了ETGWO算法的优越性能。表 1 各算法生成航迹路径的适应度值Table 1 Fitness values of paths generated by each algorithm$ n = 12 $ $ n = 22 $ 算法 Mean Std 算法 Mean Std ETGWO 764.57 14.27 ETGWO 763.09 8.26 SHGWO 767.20 12.68 SHGWO 767.46 8.58 SNGWO 807.32 32.26 SNGWO 801.07 17.94 SLGWO 831.24 46.28 SLGWO 802.49 11.58 图5给出了生成的路径俯视图，可以看出，所有算法都能生成满足路径长度、威胁、转弯角度、攀爬、俯冲角度和高度要求的可行路径，但它们的最优性会因情况而异。
图 5 规划路径俯视图Fig. 5 Top view of the planned path下载:
全尺寸图片
图6给出了ETGWO算法以及其他对比算法的规划路径成本适应度值。无论设置多少航迹点，SLGWO和SNGWO算法产生的路径虽然快速收敛，但适应度值不再减小，且SHGWO算法的性能在中后期始终ETGWO差。可以看出，ETGWO算法的性能最好，因为它可以在灰狼个体属性和无人机的参数之间建立直接映射，从而在探索搜索空间时获得优势。图7给出了规划路径的三维视图，航迹点的数量不影响路径光滑有效，且飞行高度适合。
图 6 飞行航迹成本适应度值Fig. 6 Fitness values of the trajectory cost下载:
全尺寸图片
图 7 三维航迹正视图Fig. 7 Front view of the 3D trajectory下载:
全尺寸图片
综上所述，改进算法ETGWO能有效克服灰狼算法参数敏感和容易快速收敛到某个局部最优解的缺点。基于此，利用改进的事件触发灰狼优化算法规划路径能有效降低局部最优产生的概率，且能得到更短的路径长度、更好的环境适应性能以及更优的运行时间等。
4. 结束语
针对灰狼算法在三维飞行航迹规划时参数敏感且容易陷入局部最优的问题，提出了一种新的事件触发GWO算法(ETGWO)，并将该算法应用于QUAV三维路径规划。通过利用球面矢量描述飞行航迹的生成，保证所生成路径的安全性和可行性。飞行航迹成本函数的设计融合了航迹最优性以及安全性和可行性相关的约束条件。基于无人机的固有运动分量与搜索空间之间的对应关系，利用ETGWO算法进行航迹最优解的开发与搜索，在一定程度上削弱了参数敏感。对由DEM地图生成的基准测试场景及障碍区域进行飞行航迹规划的对比分析，实验结果表明ETGWO在大多数场景中都获得了最佳的高质量路径，并具有稳定的收敛性，与其他变型GWO算法的比较也证实了ETGWO具有更优越的规划性能。此外，三维空间环境复杂多变，如何使QUAV准确跟踪规划路径还有待进一步深入研究。
-
图 1 基于球面矢量的航迹生成原理
Fig. 1 Schematic diagram of spherical vector-based trajectory generation
下载:
全尺寸图片
图 2 三维地形及障碍物示意
Fig. 2 3D terrain and obstacle schematic diagram
下载:
全尺寸图片
图 3 飞行威胁成本分析示意
Fig. 3 Flight threat cost analysis schematic
下载:
全尺寸图片
图 4 灰狼群体的等级结构
Fig. 4 Hierarchical structure of gray wolf packs
下载:
全尺寸图片
图 5 规划路径俯视图
Fig. 5 Top view of the planned path
下载:
全尺寸图片
图 6 飞行航迹成本适应度值
Fig. 6 Fitness values of the trajectory cost
下载:
全尺寸图片
图 7 三维航迹正视图
Fig. 7 Front view of the 3D trajectory
下载:
全尺寸图片
表 1 各算法生成航迹路径的适应度值
Table 1 Fitness values of paths generated by each algorithm
$ n = 12 $ $ n = 22 $ 算法 Mean Std 算法 Mean Std ETGWO 764.57 14.27 ETGWO 763.09 8.26 SHGWO 767.20 12.68 SHGWO 767.46 8.58 SNGWO 807.32 32.26 SNGWO 801.07 17.94 SLGWO 831.24 46.28 SLGWO 802.49 11.58 -
[1] EL HAMMOUTI H, HAMZA D, SHIHADA B, et al. The optimal and the greedy: drone association and positioning schemes for Internet of UAVs[J]. IEEE internet of things journal, 2021, 8(18): 14066−14079. doi: 10.1109/JIOT.2021.3070209 [2] MASROOR R, NAEEM M, EJAZ W. Efficient deployment of UAVs for disaster management: a multi-criterion optimization approach[J]. Computer communications, 2021, 177: 185−194. doi: 10.1016/j.comcom.2021.07.006 [3] WU Yu, WU Shaobo, HU Xinting. Cooperative path planning of UAVs & UGVs for a persistent surveillance task in urban environments[J]. IEEE internet of things journal, 2021, 8(6): 4906−4919. doi: 10.1109/JIOT.2020.3030240 [4] CUI Guozeng, XU Hui, YU Jinpeng, et al. Fixed-time distributed adaptive attitude control for multiple QUAVs with quantized input[J]. Applied mathematics and computation, 2023, 449: 127933. doi: 10.1016/j.amc.2023.127933 [5] KHALID A, MUSHTAQ Z, ARIF S, et al. Control schemes for quadrotor UAV: taxonomy and survey[J]. ACM computing surveys, 2024, 56(5): 1−32. [6] JIANG Wei, LYU Yongxi, LI Yongfeng, et al. UAV path planning and collision avoidance in 3D environments based on POMPD and improved grey wolf optimizer[J]. Aerospace science and technology, 2022, 121: 107314. doi: 10.1016/j.ast.2021.107314 [7] AN V, QU Zhihua, CROSBY F, et al. A triangulation-based coverage path planning[J]. IEEE transactions on systems, man, and cybernetics: systems, 2020, 50(6): 2157−2169. doi: 10.1109/TSMC.2018.2806840 [8] RASEKHIPOUR Y, KHAJEPOUR A, CHEN S K, et al. A potential field-based model predictive path-planning controller for autonomous road vehicles[J]. IEEE transactions on intelligent transportation systems, 2017, 18(5): 1255−1267. doi: 10.1109/TITS.2016.2604240 [9] KARAMAN S, WALTER M R, PEREZ A, et al. Anytime motion planning using the RRT[C]//2011 IEEE International Conference on Robotics and Automation. Shanghai: IEEE, 2011: 1478−1483. [10] 郭娜, 李彩虹, 王迪, 等. 结合预测和模糊控制的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(8): 104−109. doi: 10.3778/j.issn.1002-8331.1907-0235 GUO Na, LI Caihong, WANG Di, et al. Path planning of mobile robot based on prediction and fuzzy control[J]. Computer engineering and applications, 2020, 56(8): 104−109. doi: 10.3778/j.issn.1002-8331.1907-0235 [11] SELIM S Z, ALSULTAN K. A simulated annealing algorithm for the clustering problem[J]. Pattern recognition, 1991, 24(10): 1003−1008. doi: 10.1016/0031-3203(91)90097-O [12] DENG Yong, CHEN Yuxin, ZHANG Yajuan, et al. Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment[J]. Applied soft computing, 2012, 12(3): 1231−1237. doi: 10.1016/j.asoc.2011.11.011 [13] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1): 269−271. doi: 10.1007/BF01386390 [14] SHI Kun, WU Zhengtian, JIANG Baoping, et al. Dynamic path planning of mobile robot based on improved simulated annealing algorithm[J]. Journal of the Franklin institute, 2023, 360(6): 4378−4398. doi: 10.1016/j.jfranklin.2023.01.033 [15] AGGARWAL S, KUMAR N. Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges[J]. Computer communications, 2020, 149: 270−299. doi: 10.1016/j.comcom.2019.10.014 [16] 杨旭, 王锐, 张涛. 面向无人机集群路径规划的智能优化算法综述[J]. 控制理论与应用, 2020, 37(11): 2291−2302. doi: 10.7641/CTA.2020.00105 YANG Xu, WANG Rui, ZHANG Tao. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization[J]. Control theory & applications, 2020, 37(11): 2291−2302. doi: 10.7641/CTA.2020.00105 [17] TANG Jun, LIU Gang, PAN Qingtao. A review on representative swarm intelligence algorithms for solving optimization problems: applications and trends[J]. IEEE/CAA journal of automatica sinica, 2021, 8(10): 1627−1643. doi: 10.1109/JAS.2021.1004129 [18] 辛建霖, 左家亮, 岳龙飞, 等. 基于改进启发式蚁群算法的无人机自主航迹规划[J]. 航空工程进展, 2022, 13(1): 60−67. XIN Jianlin, ZUO Jialiang, YUE Longfei, et al. Autonomous path planning for unmanned aerial vehicle(UAV) based on improved heuristic ant colony algorithm[J]. Advances in aeronautical science and engineering, 2022, 13(1): 60−67. [19] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN'95 - International Conference on Neural Networks. Perth: IEEE, 1995: 1942−1948. [20] 张毅, 杨光辉, 花远红. 基于改进人工鱼群算法的机器人路径规划[J]. 控制工程, 2020, 27(7): 1157−1163. ZHANG Yi, YANG Guanghui, HUA Yuanhong. Robot path planning based on improved artificial fish swarm algorithm[J]. Control engineering of China, 2020, 27(7): 1157−1163. [21] 魏永超, 邓岚, 李涛, 等. 采用改进细菌觅食优化算法的无人机航迹规划[J]. 电讯技术, 2021, 61(5): 560−566. doi: 10.3969/j.issn.1001-893x.2021.05.006 WEI Yongchao, DENG Lan, LI Tao, et al. UAV track planning with improved bacterial foraging optimization algorithm[J]. Telecommunication engineering, 2021, 61(5): 560−566. doi: 10.3969/j.issn.1001-893x.2021.05.006 [22] HEWAWASAM H S, IBRAHIM M Y, APPUHAMILLAGE G K. Past, present and future of path-planning algorithms for mobile robot navigation in dynamic environments[J]. IEEE open journal of the industrial electronics society, 2022, 3: 353−365. doi: 10.1109/OJIES.2022.3179617 [23] PHUNG M D, HA Q P. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization[J]. Applied soft computing, 2021, 107: 107376. doi: 10.1016/j.asoc.2021.107376 [24] XU Guiping, CUI Quanlong, SHI Xiaohu, et al. Particle swarm optimization based on dimensional learning strategy[J]. Swarm and evolutionary computation, 2019, 45: 33−51. doi: 10.1016/j.swevo.2018.12.009 [25] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advances in engineering software, 2014, 69: 46−61. doi: 10.1016/j.advengsoft.2013.12.007 [26] 王永琦, 江潇潇. 基于混合灰狼算法的机器人路径规划[J]. 计算机工程与科学, 2020, 42(7): 1294−1301. doi: 10.3969/j.issn.1007-130X.2020.07.019 WANG Yongqi, JIANG Xiaoxiao. Robot path planning using a hybrid grey wolf optimization algorithm[J]. Computer engineering & science, 2020, 42(7): 1294−1301. doi: 10.3969/j.issn.1007-130X.2020.07.019 [27] 曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768−1775. CAO Menglong, ZHAO Wenbin, CHEN Zhiqiang. Robot path planning by fusing particle swarm algorithm and improved grey wolf algorithm[J]. Journal of system simulation, 2023, 35(8): 1768−1775. [28] YU Zhenhua, SI Zhijie, LI Xiaobo, et al. A novel hybrid particle swarm optimization algorithm for path planning of UAVs[J]. IEEE internet of things journal, 2022, 9(22): 22547−22558. doi: 10.1109/JIOT.2022.3182798 [29] YAN Ziwei, HAN Liang, LI Xiaoduo, et al. Event-Triggered formation control for time-delayed discrete-time multi-agent system applied to multi-UAV formation flying[J]. Journal of the Franklin Institute, 2023, 360(5): 3677−3699. doi: 10.1016/j.jfranklin.2023.01.036 [30] 王海群, 邓金铭, 张怡, 等. 基于改进混合灰狼优化算法的无人机三维路径规划[J]. 无线电工程, 2024, 54(4): 918−927. doi: 10.3969/j.issn.1003-3106.2024.04.015 WANG Haiqun, DENG Jinming, ZHANG Yi, et al. UAV 3D path planning based on improved hybrid grey wolf optimization algorithm[J]. Radio engineering, 2024, 54(4): 918−927. doi: 10.3969/j.issn.1003-3106.2024.04.015
