改进PID搜索算法的山地多无人机路径规划

彭艺 ,  雷云揆 ,  杨青青 ,  李辉 ,  王健明

科学技术与工程 ›› 2026, Vol. 26 ›› Issue (13) :5742-5754

PDF (14465KB)
科学技术与工程 ›› 2026, Vol. 26 ›› Issue (13) :5742-5754 DOI: 10.12404/j.issn.1671-1815.2503873
航空、航天

改进PID搜索算法的山地多无人机路径规划

作者信息 +

Improved PID Search Algorithm for Multi-UAV Path Planning in Mountainous Terrain

Author information +
文章历史 +

摘要

针对复杂山地环境下巡检无人机的路径规划问题,提出了一种基于球面坐标系下混合遗传算法的PID搜索算法(hybrid PID search algorithm, HPSA)。通过引入加权精英引导机制,并融合了遗传算法中的交叉操作,增强了算法的全局探索能力和跳出局部最优解的能力。采用B样条曲线对生成的路径进行平滑处理,使规划的路径更适合无人机飞行。在CEC2017测试函数集及不同复杂度的多无人机路径规划场景中,分别将HPSA与5种算法进行了对比实验。实验结果表明,HPSA在CEC2017测试函数集上表现出更优的寻优性能,在多无人机路径规划任务中能够有效规划出总成本函数最小的飞行路径,提升了多无人机在复杂山地环境下路径规划的能力。

Abstract

To address the path planning problem of inspection UAVs in complex mountainous environments, a PID search algorithm based on a hybrid genetic algorithm in a spherical coordinate system, termed HPSA, was proposed. The global exploration capability and the ability to escape local optima were enhanced by introducing a weighted elite-guided mechanism and integrating the crossover operation from genetic algorithms. The generated path was smoothed using B-spline curves to make the planned trajectory more suitable for UAV flight. Comparative experiments were conducted between HPSA and five other algorithms on the CEC2017 benchmark function set and in multi-UAV path planning scenarios with varying complexities. The experimental results indicated that HPSA exhibits superior optimization performance on the CEC2017 test set. In multi UAV path planning tasks, flight paths with the minimum total cost function are effectively obtained, thereby improving the path planning capability of multiple UAVs in complex mountainous environments.

Graphical abstract

关键词

无人机 / 路径规划 / PID搜索算法 / 山地环境

Key words

UAV / path planning / PID search algorithm / mountainous environments

引用本文

引用格式 ▾
彭艺, 雷云揆, 杨青青, 李辉, 王健明. 改进PID搜索算法的山地多无人机路径规划[J]. 科学技术与工程, 2026, 26(13): 5742-5754 DOI:10.12404/j.issn.1671-1815.2503873
PENG Yi, LEI Yun-kui, YANG Qing-qing, LI Hui, WANG Jian-ming. Improved PID Search Algorithm for Multi-UAV Path Planning in Mountainous Terrain[J]. Science Technology and Engineering, 2026, 26(13): 5742-5754 DOI:10.12404/j.issn.1671-1815.2503873

登录浏览全文

4963

注册一个新账户 忘记密码

近年来,无人机技术迅猛发展,广泛应用于洪水监测[1]、应急救援[2]、物流配送[3]等领域。无人机具备高灵活性、低成本、远程控制及多任务执行能力,适用于复杂、危险的环境。然而,随着应用场景的复杂化和多样化,对无人机在任务执行的效率、安全性提出了更高要求。因此,无人机在复杂环境中需要有效地规划出安全的飞行路径来满足任务要求。
无人机路径规划是典型的NP-hard问题,解决方法主要可分为经典算法、机器学习算法、启发式算法及混合算法四大类[4]。经典路径规划算法如分层快速搜索随机树算法[5]、自适应步长快速搜索随机树算法[6]以及维诺图(Voronoi diagram)算法等[7],在二维场景中具有良好的效果,但在处理三维复杂地形时往往面临计算复杂度高和适应性差的问题。为增强算法的适应能力,部分研究引入了机器学习的方法,如双深度Q网络(dueling double deep q-network, D3QN)算法用于城市环境中的无人机协同路径规划[8];用于搜索救援无人机路径规划的自适应转换速度Q-learning算法(adaptive conversion speed q-learning algorithm)[9];将人工神经网络和局部规划算法结合在动态环境下的路径规划也表现出一定优势[10]。但这类方法存在训练时间长、泛化性差等问题。
启发式算法因具有较强的全局搜索能力和对问题结构的适应性,已成为解决无人机路径规划的主流方法。当前研究主要集中在两个方向,一是对现有算法进行改进,二是对不同算法进行策略性融合。在算法改进方面,宋睿等[11]对A*算法进行了改进,应用于无人机高原森林灭火路径规划;王飞等[12]改进了粒子群算法,使其更适用于城市物流无人机路径规划;吴学礼等[13]改进了麻雀搜索算法,提高了路径求解的精度与稳定性;Huang等[14]在圆柱坐标系下提高了粒子群算法的地形适应性;Zhang等[15]针对无人机应急物资分配问题,提出了具备更快收敛速度的改进型差分进化算法;王文涛等[16]结合多策略机制,改进了人工兔优化算法以满足三维路径规划任务的需求。在算法融合方面,研究者们也取得了丰硕的成果,Tu等[17]提出了基于对立学习和差分进化的海洋捕食者混合算法;Liu等[18]提出混合人工兔算法;Yu等[19]提出强化学习改进的布谷鸟搜索算法,提高算法在灾害场景下无人机路径规划的求解精度;Wang等[20]提出了一种融合强化学习与热传导搜索策略的优化算法,在山地森林地形中进行多无人机路径规划。
尽管上述研究推动了无人机路径规划技术的发展,但在地形复杂、约束条件苛刻的山地多无人机巡检任务中,对算法的求解精度、收敛速度提出了更严峻的挑战,这要求算法不仅要有强大的全局搜索能力,还要在处理高维、强约束问题时保持良好的收敛性能。为此,现选取基于比例-积分-微分控制思想构建的启发式算法——PID搜索算法(PID search algorithm, PSA)[21],并将其应用于山地环境下的多无人机路径规划。该算法因具备较强的寻优能力和良好的稳定性,已在其他高维约束优化问题中得到成功应用。例如,Liu等[22]将PSA与强制调度策略相结合,实现了制造系统中的调度性能优化;谢志远等[23]利用PSA算法优化了中压电力线载波通信中的自适应阻抗匹配,实现了元件参数的最优配置。上述研究表明,PSA在解决复杂工程问题时具有良好的泛化能力和稳定性。
针对复杂地形下的多无人机应急巡检难题,现将PSA算法引入该领域进行研究。然而,面对地形起伏剧烈、禁飞区密集以及多机约束强的高维规划问题,标准PSA仍面临搜索精度不足、易陷入局部最优和收敛速度慢等挑战。建立面向复杂山地环境的多无人机路径规划模型。采用球面坐标编码与B样条曲线平滑,将飞行地形、飞行距离、物理机动限制及多机防碰撞等转化为约束优化问题,有效解决高维空间下的多机规划难题。提出一种混合遗传机制改进的PID搜索算法(hybrid PID search algorithm, HPSA)。针对标准PSA在高维搜索空间中探索能力不足的问题,引入加权精英引导机制与遗传交叉操作,显著增强算法的全局搜索与跳出局部最优的能力。以期实现复杂山地环境下安全与高效的路径规划。

1 方法模型

在复杂山地环境下的无人机巡检路径规划中,需要从出发点到目的地确定最优的飞行路径,在保证无人机安全到达的同时,满足较小的飞行路径、飞行高度和飞行转角要求。假设无人机从起点到终点的飞行路径包含N个航路点,则无人机的飞行路径点集合可以表示为

$\mathit{W}=\{{\mathit{w}}_{\mathit{S}},{\mathit{w}}_{1},\dots,{\mathit{w}}_{\mathit{N}},{\mathit{w}}_{\mathit{E}}\}$

式(1)中:wS为无人机飞行的起点位置;wE为无人机飞行的终点位置。

1.1 路径成本

无人机飞行的路径可以分为多个离散的节点,通过计算各节点之间的距离来确定飞行路径的总长度,M架无人机飞行的路径长度计算公式为

$\begin{array}{l}{\mathit{f}}_{1}=\sum _{\mathit{i}=1}^{\mathit{M}}\sum _{\mathit{n}=1}^{\mathit{N}-1}[{\mathit{x}}_{\mathit{i},\mathit{n}+1}-{\mathit{x}}_{\mathit{i},\mathit{n}}{)}^{2}+({\mathit{y}}_{\mathit{i},\mathit{n}+1}-{\mathit{y}}_{\mathit{i},\mathit{n}}{)}^{2}+\\ ({\mathit{z}}_{\mathit{i},\mathit{n}+1}-{\mathit{z}}_{\mathit{i},\mathit{n}}{)}^{2}{]}^{1/2}\end{array}$

式(2)中:f1为所有无人机从起点到终点的总飞行路径长度;M为无人机的数量;i为无人机编号;N为路径点总数;n为路径点编号;第i架无人机在第n个路径点的三维位置坐标记为(xi,n,yi,n,zi,n)。

1.2 高度成本

假设无人机飞行的最高高度和最低高度为Hmax和Hmin,最佳飞行高度为最高与最低飞行高度总和的一半,飞行高度成本计算公式为

${\mathit{f}}_{2}=\left\{\begin{array}{ll}\sum _{\mathit{i}=1}^{\mathit{M}}\sum _{\mathit{n}=1}^{\mathit{N}}\left|\frac{{\mathit{H}}_{\mathit{m}\mathit{a}\mathit{x}}+{\mathit{H}}_{\mathit{m}\mathit{i}\mathit{n}}}{2}-{\mathit{z}}_{\mathit{i},\mathit{n}}\right|,& {\mathit{H}}_{\mathit{m}\mathit{i}\mathit{n}}\le {\mathit{z}}_{\mathit{i},\mathit{n}}\le {\mathit{H}}_{\mathit{m}\mathit{a}\mathit{x}}\\ \mathit{\infty },& \mathrm{其}\mathrm{他}\end{array}\right.$

式(3)中:f2为无人机从出发点到终点的高度成本;zi,n为第i架无人机在第n个节点相对于地面的飞行高度。

1.3 避障成本

在无人机飞行过程中,必须考虑障碍物对无人机带来的威胁,确保无人机能安全地执行飞行任务。在障碍物约束中,避障成本随着无人机到障碍中心点的距离减小而增大。环境中出现的障碍区由圆柱体表示。对于所有障碍区,无人机飞行的避障成本计算公式为

${\mathit{f}}_{3}=\left\{\begin{array}{ll}\sum _{\mathit{i}=1}^{\mathit{M}}\sum _{\mathit{l}=1}^{\mathit{L}}\mathit{\alpha }({\mathit{R}}_{\mathit{l}}+\mathit{\rho }-{\mathit{d}}_{\mathit{l}}),& {\mathit{R}}_{\mathit{l}}{\mathit{d}}_{\mathit{l}}\le {\mathit{R}}_{\mathit{l}}+\mathit{\rho }\\ \mathit{\infty },& {\mathit{d}}_{\mathit{l}}\le {\mathit{R}}_{\mathit{l}}\end{array}\right.$

式(4)中:f3为无人机从起点到终点之间的避障成本;α为惩罚系数;Rl为第l个障碍物的威胁半径;dl为无人机到障碍物中心的距离;ρ为障碍缓冲区,避障成本随飞入该区域的距离增大而增大,设置该区域范围为10 m。

1.4 平滑成本

无人机飞行过程中,需考虑其转角,使得无人机在飞行时尽可能地保持平稳。平滑成本由水平转角和垂直爬升角组成,无人机水平转角的公式为

${\mathit{\varphi }}_{\mathit{i},\mathit{n}}=\mathit{a}\mathit{r}\mathit{c}\mathit{t}\mathit{a}\mathit{n}\frac{\left|{\mathit{y}}_{\mathit{i},\mathit{n}+1}-{\mathit{y}}_{\mathit{i},\mathit{n}}\right|}{\left|{\mathit{x}}_{\mathit{i},\mathit{n}+1}-{\mathit{x}}_{\mathit{i},\mathit{n}}\right|}$

垂直爬升角的公式为

${\mathit{\theta }}_{\mathit{i},\mathit{n}}=\mathit{a}\mathit{r}\mathit{c}\mathit{t}\mathit{a}\mathit{n}\frac{\left|{\mathit{z}}_{\mathit{i},\mathit{n}+1}-{\mathit{z}}_{\mathit{i},\mathit{n}}\right|}{\sqrt{({\mathit{x}}_{\mathit{i},\mathit{n}+1}-{\mathit{x}}_{\mathit{i},\mathit{n}}{)}^{2}+({\mathit{y}}_{\mathit{i},\mathit{n}+1}-{\mathit{y}}_{\mathit{i},\mathit{n}}{)}^{2}}}$

飞行过程中的转角成本为

${\mathit{f}}_{4}=\sum _{\mathit{i}=1}^{\mathit{M}}\sum _{\mathit{n}=1}^{\mathit{N}-2}{\mathit{\varphi }}_{\mathit{i},\mathit{n}}+\sum _{\mathit{i}=1}^{\mathit{M}}\sum _{\mathit{n}=1}^{\mathit{N}-1}({\mathit{\theta }}_{\mathit{i},\mathit{n}}-{\mathit{\theta }}_{\mathit{i},\mathit{n}-1})$

式(7)中:f4为无人机从起点到中间之间的平滑成本,无人机的水平转角和垂直爬升角的约束为

$0\le \mathit{\varphi }\le {\mathit{\varphi }}_{\mathit{m}\mathit{a}\mathit{x}}$
$0\le \mathit{\theta }\le {\mathit{\theta }}_{\mathit{m}\mathit{a}\mathit{x}}$

式中:${\mathit{\varphi }}_{\mathit{m}\mathit{a}\mathit{x}}$为无人机的最大水平转角;θmax为无人机的最大爬升角。

1.5 多无人机安全距离成本

在复杂山地中执行飞行任务时,各无人机应在整个飞行过程中始终保持不小于设定的安全距离ds,以防止航线交叉或互相间的干扰。

设第i架无人机在第n个节点的位置为wi,n,第i架无人机和第j架无人机在第n节点之间的距离可以表示为

${\mathit{d}}_{\mathit{i},\mathit{j},\mathit{n}}=\Vert {\mathit{w}}_{\mathit{i},\mathit{n}}-{\mathit{w}}_{\mathit{j},\mathit{n}}\Vert $

当该距离小于安全距离ds时,说明无人机之间的距离过近,在碰撞成本中加入惩罚项;当该距离为零时,表示两架无人机轨迹在相同节点重合,发生碰撞。综合考虑以上情况,多无人机之间的安全成本可以表示为

$C_{i, j, n}=\left\{\begin{array}{ll} \alpha\left(d_{\mathrm{s}}-d_{i, j}\right), & 0<d_{i, j, n}<d_{\mathrm{s}} \\ \infty, & d_{i, j, n}=d_{\mathrm{s}} \\ 0, & d_{i, j, n}>d_{\mathrm{s}} \end{array}\right.$

式(11)中:α为惩罚系数。

所有无人机之间的安全距离成本为

${\mathit{f}}_{5}=\sum _{\mathit{n}=1}^{\mathit{N}}\sum _{\mathit{i}=1}^{\mathit{M}-1}\sum _{\mathit{j}=\mathit{i}+1}^{\mathit{M}}{\mathit{C}}_{\mathit{i},\mathit{j},\mathit{n}}$

式(12)中:f5为多无人机之间的安全距离成本。

1.6 目标函数

无人机路径规划中的最佳轨迹通常与起始点之间的直线航迹有关,考虑飞行距离、高度、安全性和稳定性成本,将无人机轨迹规划问题转化为优化问题,优化的目标函数定义为

$\mathit{m}\mathit{i}\mathit{n}\mathit{f}={\mathit{\omega }}_{1}{\mathit{f}}_{1}+{\mathit{\omega }}_{2}{\mathit{f}}_{2}+{\mathit{\omega }}_{3}{\mathit{f}}_{3}+{\mathit{\omega }}_{4}{\mathit{f}}_{4}+{\mathit{\omega }}_{5}{\mathit{f}}_{5}$

式(13)中:ω1,ω2、ω3、ω4、ω5为加权系数,表示路径长度、高度、避障、平滑成本和多无人机安全距离的权重,对其进行归一化处理,满足ω1+ω2+ω3+ω4+ω5=1。

1.7 球坐标路径编码

在球面坐标系下能更好地满足无人机的机动特性,因此用球面坐标系代替三维空间中的笛卡尔坐标系来表示无人机的路径点[24]。球坐标下的路径点可以表示为$(\mathit{r},\mathit{\theta },\mathit{\varphi })$,无人机飞行距离$\mathit{r}\in (0,{\mathit{F}}_{1}),$爬升角$\mathit{\theta }\in (-\mathit{\pi }/2,\mathit{\pi }/2)$,方位角$\mathit{\varphi }\in (-\mathit{\pi },\mathit{\pi })$。将算法中解在球面坐标系下进行编码,可以描述出一个点到下一个点的运动轨迹,使运动轨迹满足平滑成本中的转向角和爬升角约束,由N个节点组成的飞行路径球面向量表示为

${\mathit{\Omega }}_{\mathit{i}}=({\mathit{r}}_{\mathit{i}1},{\mathit{\theta }}_{\mathit{i}1},{\mathit{\varphi }}_{\mathit{i}1},{\mathit{r}}_{\mathit{i}2},{\mathit{\theta }}_{\mathit{i}2},{\mathit{\varphi }}_{\mathit{i}2},\dots,{\mathit{r}}_{\mathit{i}\mathit{N}},{\mathit{\theta }}_{\mathit{i}\mathit{N}},{\mathit{\varphi }}_{\mathit{i}\mathit{N}})$

球坐标系和笛卡尔坐标系的转换为

$\left\{\begin{array}{l}{\mathit{x}}_{\mathit{i},\mathit{n}}={\mathit{x}}_{\mathit{i},\mathit{n}-1}+{\mathit{r}}_{\mathit{i},\mathit{n}}\mathit{s}\mathit{i}\mathit{n}{\mathit{\theta }}_{\mathit{i},\mathit{n}}\mathit{c}\mathit{o}\mathit{s}{\mathit{\varphi }}_{\mathit{i},\mathit{n}}\\ {\mathit{y}}_{\mathit{i},\mathit{n}}={\mathit{y}}_{\mathit{i},\mathit{n}-1}+{\mathit{r}}_{\mathit{i},\mathit{n}}\mathit{s}\mathit{i}\mathit{n}{\mathit{\theta }}_{\mathit{i},\mathit{n}}\mathit{s}\mathit{i}\mathit{n}{\mathit{\varphi }}_{\mathit{i},\mathit{n}}\\ {\mathit{z}}_{\mathit{i},\mathit{n}}={\mathit{z}}_{\mathit{i},\mathit{n}-1}+{\mathit{r}}_{\mathit{i},\mathit{n}}\mathit{c}\mathit{o}\mathit{s}{\mathit{\theta }}_{\mathit{i},\mathit{n}}\end{array}\right.$

式(15)中:(xi,n-1,yi,n-1,zi,n-1)和(xi,n,yi,n,zi,n)为第i架无人机的飞行路径点Wn-1和Wn。

1.8 基于B样条曲线的轨迹规划

直接生成的无人机路径通常是不平滑的,会导致无人机飞行姿态不稳定,增加无人机飞行的危险性。因此,引入三次样条曲线来对生成的路径进行平滑处理[25]。B样条曲线由贝塞尔曲线(Bézier curve)演变而来,既继承了贝塞尔曲线的几何不变性、保凸性等优点,又可独立于控制点数目,且允许局部控制曲线。

B样条可以根据无人机飞行的节点W生成连续且平滑的曲线,B样条曲线表示为

$\mathit{W}\left(\mathit{u}\right)=\sum _{\mathit{i}=0}^{\mathit{N}}{\mathit{w}}_{\mathit{i}}{\mathit{B}}_{\mathit{i},\mathit{k}}\left(\mathit{u}\right)$

式(16)中:wi为曲线的控制点,即无人机飞行的航路点;Bi,k(u)为k阶B样条在节点i上的基函数,k为阶数,通常情况下,k越大,曲线的平滑程度越高,但计算的复杂度也会增大,为平滑无人机在飞行过程中的轨迹,采取3次B样条曲线平滑路径。B样条曲线基函数表示为

$\left\{\begin{array}{l} B_{i, k}(u)=\left\{\begin{array}{ll} 1, & u_{i} \leqslant u \leqslant u_{i+1} \\ 0, & \text { 其他 } \end{array}\right. \\ B_{i, k}(u)=\frac{u-u_{i}}{u_{i+k}-u_{i}} B_{i, k-1}(u)+\frac{u_{i+k+1}-u}{u_{i+k+1}-u_{i+1}} B_{i+1, k-1}(u) \end{array}\right.$

2 PID搜索算法

PID搜索算法是一种基于增量式的PID算法,通过连续调整系统偏差,使整个种群收敛到最优状态的算法。PSA算法将种群的历史最优个体抽象为目标值,并将每个个体抽象为真实值,模拟了PID的调节过程,校正其余个体相对于最佳个体的偏差,使整个种群达到更好的状态。

PSA算法的初始化过程可以表示为

${\mathit{X}}_{\mathit{i},\mathit{j}}={\mathit{r}}_{1}({\mathit{u}}_{\mathit{j}}-{\mathit{l}}_{\mathit{j}})+{\mathit{l}}_{\mathit{j}}$

式(18)中:Xi,j为第i个个体的第j个维度;r1为0~1的随机数,uj、lj分别为第j个维度的上限和下限。

PSA算法将种群的历史最佳个体记为目标值,然后模拟PID的调节过程,修正其他个体相对于最佳个体的偏差,迭代次数为t处的总体偏差表示为

${\mathit{e}}_{\mathit{k}-1}\left(\mathit{t}\right)={\mathit{e}}_{\mathit{k}}(\mathit{t}-1)+\mathit{x}\mathit{\text{'}}\left(\mathit{t}\right)-\mathit{x}\mathit{\text{'}}(\mathit{t}-1)$

式(19)中:x'(t)为迭代次数为t时的最优个体。

PSA算法调节的输出值为

$\begin{array}{l}\mathit{\Delta }\mathit{u}\left(\mathit{t}\right)={\mathit{K}}_{\mathit{p}}{\mathit{r}}_{2}\left[{\mathit{e}}_{\mathit{k}}\right(\mathit{t})-{\mathit{e}}_{\mathit{k}-1}(\mathit{t}\left)\right]+{\mathit{K}}_{\mathit{i}}{\mathit{r}}_{3}{\mathit{e}}_{\mathit{k}}\left(\mathit{t}\right)+\\ {\mathit{K}}_{\mathit{d}}{\mathit{r}}_{4}\left[{\mathit{e}}_{\mathit{k}}\right(\mathit{t})-2{\mathit{e}}_{\mathit{k}-1}(\mathit{t})+{\mathit{e}}_{\mathit{k}-2}(\mathit{t}\left)\right]\end{array}$

式(20)中:Δu(t)为PID调节的输出值;r2、r3和r4为n行一列的随机数;Kp为比例系数;Ki为积分系数;Kd为微分系数。随着迭代的增加,如果不调整被控对象,真值很快将不等于设定值,通常在原始调节值上加上一个值,称为零输出调节因子,表示为

$\mathit{o}\left(\mathit{t}\right)=\left[\mathit{c}\mathit{o}\mathit{s}\right(1-\mathit{t}/\mathit{T})+\mathit{\lambda }{\mathit{r}}_{5}\mathit{L}]{\mathit{e}}_{\mathit{k}}\left(\mathit{t}\right)$

式(21)中:r5为n行d列的随机数;λ为调整系数,在算法前期随迭代次数的增大缓慢减小,后期接近最大迭代次数时快速下降,表示为

$\mathit{\lambda }=\left[\mathit{l}\mathit{n}\right(\mathit{T}-\mathit{t}+2)/\mathit{l}\mathit{n}\mathit{T}]$

L为莱维飞行函数,每一个元素表示为

${\mathit{L}}_{\mathit{i}\mathit{j}}=\frac{{\mathit{\mu }}_{\mathit{i}\mathit{j}}}{{\left|{\mathit{\nu }}_{\mathit{i}\mathit{j}}\right|}^{\frac{1}{\mathit{\beta }}}}{\left\{\frac{\mathit{\Gamma }(1+\mathit{\beta })\mathit{s}\mathit{i}\mathit{n}\left(\mathit{\pi }\right.\mathit{\beta }/2)}{\mathit{\Gamma }\left[\right(1+\mathit{\beta })/2]\mathit{\beta }{2}^{(\mathit{\beta }-1)/2}}\right\}}^{\frac{1}{\mathit{\beta }}}$

式(23)中:μij和νij为独立的正态分布随机量,μij∼N(0,σ2),νij∼N(0,1)。

由PID控制的更新公式为

$\mathit{x}(\mathit{t}+1)=\mathit{x}\left(\mathit{t}\right)+\mathit{\eta }\mathit{\Delta }\mathit{u}\left(\mathit{t}\right)+(1-\mathit{\eta })\mathit{o}\left(\mathit{t}\right)$
$\mathit{\eta }={\mathit{r}}_{6}\mathit{c}\mathit{o}\mathit{s}(\mathit{t}/\mathit{T})$

式(25)中:r6为n行1列的随机数。

3 混合PID搜索算法

3.1 精英引导搜索

PSA算法依靠单个个体来更新种群状态,在面对高维复杂问题时,可能会导致局部信息利用不足,或过早收敛至局部最优。为了提高算法的探索性,提出了精英引导搜索,考虑多个优秀个体的位置,获得更具代表性的指导方向,避免依赖单一个体可能带来的局部偏差。

在当前种群中取k个最优个体,分别记为${\mathit{x}}_{1},{\mathit{x}}_{2},\dots,{\mathit{x}}_{\mathit{k}}$,其对应的适应度函数表示为${\mathit{F}}_{1},{\mathit{F}}_{2},\dots,{\mathit{F}}_{\mathit{k}}$,其中较低的Fi表示个体的表现更好,取k为3。为了使优秀的个体在引导中的贡献更大,构造了以下权重分配策略,表达式为

$\mathit{\omega }\mathit{\text{'}}{\mathit{ }}_{\mathit{i}}=\frac{1}{{\mathit{F}}_{\mathit{i}}},\mathit{ }\mathit{i}=\mathrm{1,2},\dots,\mathit{k}$

式(26)中:ω' i为适应度为Fi的个体对应的权重值,归一化权重计算公式为

${\mathit{\omega }}_{\mathit{i}}=\frac{\mathit{\omega }\mathit{\text{'}}{\mathit{ }}_{\mathit{i}}}{\sum _{\mathit{j}=1}^{\mathit{k}}\mathit{\omega }\mathit{\text{'}}{\mathit{ }}_{\mathit{j}}}=\frac{1/{\mathit{F}}_{\mathit{i}}}{\sum _{\mathit{j}=1}^{\mathit{k}}1/{\mathit{F}}_{\mathit{i}}},\mathit{i}=\mathrm{1,2},\dots,\mathit{k}$

由多个最优个体构造后的位置为

$\stackrel{-}{\mathit{x}}=\sum _{\mathit{i}=1}^{\mathit{k}}{\mathit{\omega }}_{\mathit{i}}{\mathit{x}}_{\mathit{i}}$

式(28)中:$\stackrel{-}{\mathit{x}}$为新的加权位置,假设新位置的适应度值较低,则为算法更新最优个体的位置,否则采用原始的最优位置,表达式为

$\mathit{x}\mathit{\text{'}}=\left\{\begin{array}{ll}{\mathit{x}}_{\mathit{i}},& \mathit{F}\left({\mathit{x}}_{\mathit{i}}\right)\le \mathit{F}\left(\stackrel{-}{\mathit{x}}\right)\\ \stackrel{-}{\mathit{x}},& \mathit{F}\left({\mathit{x}}_{\mathit{i}}\right)\mathit{F}\left(\stackrel{-}{\mathit{x}}\right)\end{array}\right.$

通过精英引导搜索能够让PSA算法在搜索过程中综合多条较优搜索路径的信息,为下一步最优解的更新提供更全面的信息。

3.2 融合遗传算法

遗传算法(genetic algorithm, GA)是经典的启发式算法,模拟了自然界生物进化过程中染色体的交叉和遗传。提出一种精英遗传策略,将PSA算法和遗传算法中的交叉操作相结合,使得提出的算法同时具有PSA和GA算法的优点。对3.1节中的精英个体进行交叉策略,可以增强算法的探索性,而且精英个体的信息也可以传递给下一代,避免了无指导性、随机性的缺点。

精英个体在进行交叉操作时会产生新的个体,表达式为

${\mathit{x}}_{\mathit{i},\mathit{d}}^{\mathit{n}\mathit{e}\mathit{w}}={\mathit{r}}_{7}{\mathit{x}}_{\mathit{i},\mathit{d}}+(1-{\mathit{r}}_{5}){\mathit{x}}_{\mathit{j},\mathit{d}}+{\mathit{c}}_{1}({\mathit{x}}_{\mathit{i},\mathit{d}}-{\mathit{x}}_{\mathit{j},\mathit{d}})$
${\mathit{x}}_{\mathit{j},\mathit{d}}^{\mathit{n}\mathit{e}\mathit{w}}={\mathit{r}}_{8}{\mathit{x}}_{\mathit{j},\mathit{d}}+(1-{\mathit{r}}_{6}){\mathit{x}}_{\mathit{i},\mathit{d}}+{\mathit{c}}_{2}({\mathit{x}}_{\mathit{j},\mathit{d}}-{\mathit{x}}_{\mathit{i},\mathit{d}})$

式中:${\mathit{x}}_{\mathit{i},\mathit{d}}^{\mathit{n}\mathit{e}\mathit{w}}$和${\mathit{x}}_{\mathit{j},\mathit{d}}^{\mathit{n}\mathit{e}\mathit{w}}$分别为由xi,d和xj,d在d维度下,经过交叉操作产生的新位置;r7和r8为0~1的随机数;c1和c2为-1~1的随机数。

在对个体进行交叉操作之后,采用贪婪策略保留适应度最低的个体。精英交叉策略选取种群中的精英个体进行交叉,增强了算法的全局开发能力,有助于避免算法陷入局部最优解。

3.3 混合PID搜索算法

通过将PSA算法和GA算法相结合,提出了混合PID搜索算法。针对原PSA算法中仅靠单个最优个体更新种群状态,提出了精英引导搜索策略,考虑多个优秀个体的搜索信息,增强算法的探索性;引入GA算法中的交叉操作,对精英个体进行交叉,获得新个体,通过贪婪策略保留最优解。HPSA算法的具体实现步骤如下。

4 仿真实验与分析

4.1 数值实验

为全面评估所提出HPSA算法的性能,在CEC2017测试函数集上进行了数值实验。测试集包含两个单峰函数(F1,F3)、7个多峰函数(F4~F10)、10个混合函数(F11~F20)和10个复合函数(F21~F30)。由于F2函数的结果波动较大,稳定性较差,大多数研究已不再将其纳入性能评估范围。

为确保算法对比的公平性,所有算法在相同设置下运行,最大迭代次数为500、种群规模为30,问题维度为100(dim=100),每种算法独立运行30次,所有算法的参数设置均与原始文献保持一致。实验平台为Intel Core i5-13490F处理器2.5 GHz、32 GB内存,仿真环境为MATLAB R2021a。选取了5种具有代表性的对比算法:粒子群优化算法(particle swarm optimization, PSO)、遗传算法(genetic algorithm, GA)、蜣螂优化算法(dung beetle optimizer algorithm, DBO)[26]、哈里斯鹰优化算法(harris hawk optimization algorithm, HHO)[27]和PSA算法,与所提出的HPSA算法进行对比分析。评估指标包括最优值、平均值和标准差,并采用Wilcoxon秩和检验对结果的统计显著性进行分析,各测试函数的最优结果以粗体标注。

表1统计了各算法在100维CEC2017测试函数集上的平均值、最优值和标准差等,从表1中的结果可以看出,HPSA的综合优化能力最好。在单峰函数中,HPSA在F1上获得了最小的最优值、平均值和标准差,显著优于其他算法,显示出较强的收敛速度与精度,但在F3上,其性能略逊于HHO;在多峰函数F4~F10中,HPSA在全部7个函数上求解的平均值、最优值均为最小,表明其在多峰函数中具有良好的跳出局部最优能力。在混合函数F11~F20中,HPSA在所有函数上求解的平均值和标准差最小,仅在F14函数最优值仅小于PSO,反映出算法具有较强的鲁棒性与求解稳定性。在复合函数F21~F30中,HPSA在所有函数上求解的平均值和最优值最小,展现出HPSA在复杂度函数中高效的求解能力。

根据表1中Wilcoxon秩和检验的统计结果,HPSA相较于PSO、GA和PSA在全部测试函数上取得了显著优势;相较于DBO和HHO,HPSA在28个函数上也展现出显著的优势,验证了所提出改进策略在提升算法优化能力与稳定性方面的有效性。

为了更加直观地展示HPSA算法在不同类型优化问题中的收敛特性,图1给出了各算法在CEC2017测试函数集上部分代表函数在问题维度为100(dim=100)下的收敛曲线。选取了一个单峰函数(F1)、一个多峰函数(F10)、一个混合函数(F20)和一个复合函数(F30)进行了分析。可以明显看出HPSA具有更出色的求解能力和较快的收敛速度。其他对比算法在不同类型的函数上均出现早期收敛或陷入局部最优的现象,收敛速度和精度均明显不及HPSA。各类函数的平均收敛曲线清晰地说明了HPSA通过结合精英引导和交叉机制,有效提升了PSA算法的全局搜索能力和跳出局部最优解的能力。在解决不同类型的优化问题,HPSA均能获得良好的效果,从而进一步验证了所提出改进方法的有效性与适用性。

4.2 多无人机路径规划

实验场景基于数字高程模型(digital elevation model,DEM),路径规划地图尺寸为1 500 m×1 500 m×400 m,无人机与地面之间的最低飞行高度为100 m,最高飞行高度为200 m,最大转弯角和最大爬升角为45°。目标函数中各成本项分配的权重系数参考了相关研究[16,24],其设置原则旨在平衡任务性能与飞行安全,将路径长度与平滑度指标作为任务性能优化项;将避障、无人机间距离成本作为飞行安全约束项,主要依靠惩罚机制对其进行限制。具体的实验参数设置如表2所示。比较算法包括SPSO[24]、GA、DBO[26]、HHO[27]和PSA。将每个算法独立运行30次,设置种群数为500,最大迭代次数为200,记录各算法的最优值、平均值等,所有参与比较的算法都采用1.7节的球坐标路径编码。

为测试HPSA算法在无人机路径规划中的性能,设置了两个不同复杂度的场景,威胁区域用圆柱体表示,相关信息如表3所示。

场景1中各算法的统计结果如表4所示。除了平均高度代价大于HHO以外,HPSA的其他统计指标均为最小。在场景1中只有HHO算法产生了威胁代价,其他算法的威胁代价均为0;与PSA算法相比,HPSA在场景1下的平均收敛精度提高了6.8%,标准差方面减小了27.15%。对于场景1,各算法规划的无人机飞行轨迹如图2所示,可以看出,SPSO、PSA和HPSA规划的路径较好,HPSA规划出的飞行路径最短,转角代价最小,较好地避开了障碍区,GA、DBO和HHO算法生成的路径长度较长,飞行轨迹较曲折。

对于场景2,飞行环境的复杂性有所增加,障碍区域增多。各算法的统计结果如表5所示,HPSA的所有统计指标均为最小,除HPSA、PSA和DBO之外,其他算法都产生了威胁代价,其中HHO的威胁代价最大;与PSA算法相比,HPSA在场景2下的平均收敛精度提高了7.27%,标准差降低了31.53%。图3展示了各算法规划的无人机飞行轨迹的三维图,HPSA算法规划出的飞行路径最好,其他算法规划的路径比较曲折并且靠近障碍区域。

6种算法在场景1下的平均收敛曲线如图4(a)所示,HPSA算法的收敛速度和求解能力优于其他算法,SPSO和PSA算法的差距较小,GA和HHO陷入了局部最优解,平均收敛曲线结果较差。实验结果表明,所提出的HPSA算法在简单场景中能引导多无人机安全地到达目标点。6种算法在场景2下的平均收敛曲线如图4(b)所示,HPSA算法的收敛速度和求解能力同样优于其他算法。实验结果表明,所提出的HPSA算法在保证安全的前提下能以最小成本路径引导多无人机在复杂环境下到达目标点,在复杂环境下HPSA算法的优势更加明显。

在场景2中,将无人机数量拓展到六架,各算法的性能统计如表6所示。结果表明,在所有对比算法中,仅HPSA和DBO的平均安全代价为0,保证了路径的安全,且HPSA在总成本上显著优于DBO;与PSA算法相比,HPSA的平均收敛精度提高了12.63%,标准差降低了35.50%,验证了其解的质量与稳定性均有提升。图5展示了HPSA算法规划的三维路径,图6的算法收敛曲线也证明,即便是在复杂的多无人机任务中,HPSA算法的收敛速度和寻优能力仍领先于其他对比算法。随着多无人机系统规模和环境复杂度的提升,本文提出的HPSA算法能够可靠生成安全协同的路径,并且在保障安全的前提下,其路径综合成本最优。

4.3 实例分析

为进一步验证HPSA算法在实际工程环境中的适应性,选取了云南省玉溪市新平县嘎洒镇的真实数字高程模型作为测试场景。该区域地形以山谷和陡峭山岭为主,海拔落差大,地形复杂度高,实验设置6架无人机执行协同巡检任务,要求无人机编队穿越复杂山区,并到达指定位置。为了验证算法性能,选取了提出的HPSA算法、PSA算法以及实验中表现较优的SPSO算法进行对比测试。

各算法的性能统计结果如表7所示。在安全性方面,3种算法均未产生安全代价,满足无冲突要求。在优化指标上,HPSA的最优值、平均值、标准差、平均飞行距离和转角代价在所有对比算法中均为最小。与基准PSA算法相比,HPSA的平均收敛精度提高了10.27%,标准差降低了39.95%,证明了其在复杂山区环境中的优越性与鲁棒性。

HPSA算法在该地形下的三维规划结果如图7所示。该算法规划出的路径平滑度高,在有效避开陡峭山体和禁飞区的基础上,减少了飞行距离成本和飞行转角成本。各算法的收敛曲线如图8所示,HPSA在求解精度和收敛速率上均明显优于其他对比算法,展现出更强的寻优能力。

上述实验结果表明,HPSA算法能够有效应对真实地理环境中的高维约束挑战,为复杂山地背景下的多无人机协同巡检提供了可靠的技术支撑。

5 结论

对山地环境下的应急巡检无人机路径规划问题展开研究,得到以下结论。

(1)构建了面向复杂山地环境的应急巡检多无人机路径规划模型。将规划问题转化为多目标约束优化问题,综合考虑了路径长度、飞行高度、轨迹平滑度、障碍物规避以及无人机间安全距离。

(2)提出了一种混合遗传机制改进的PID搜索算法(HPSA)。通过引入加权精英引导机制增强了种群的探索性并加快收敛,同时结合遗传算法的交叉操作,有效提升了算法跳出局部最优解的能力。

(3)在CEC2017标准测试函数集上的验证实验表明,HPSA算法具备卓越的数值优化性能。在与多种启发式算法的对比中,HPSA在单峰、多峰、混合及复合等多种复杂函数上的求解精度、收敛速度和稳定性指标上均表现出显著优势。

(4)在多无人机山地路径规划仿真实验中,HPSA展现了其解决实际问题的强大能力和可扩展性。在复杂的六无人机场景下,多数对比算法难以保证飞行安全,HPSA能够稳定规划出无冲突安全路径并获得最低的综合路径成本,证明了其在解决高维、强约束协同规划问题中的实际应用价值。

参考文献

原文顺序 | 出版日期 | 本文引用
[1]

Ma Y, Wei X, Zhao H, et al. UAV-based emergency treatment plan for flood disasters at the Hongyanhe nuclear power plant[J]. Ecological Indicators, 2023, 154: 110676.
[2]

Wandelt S, Wang S, Zheng C, et al. AERIAL: a Meta review and discussion of challenges toward unmanned aerial vehicle operations in logistics, mobility, and monitoring[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(7): 6276-6289.
[3]

闫少华, 石星雨, 张兆宁. 基于改进A*算法的城市物流无人机三维路径规划[J]. 科学技术与工程, 2024, 24(29): 12781-12788.
[4]

Yan Shaohua, Shi Xingyu, Zhang Zhaoning. Three-dimensional path planning of urban logistics UAVs[J]. Science Technology and Engineering, 2024, 24(29): 12781-12788.
[5]

Jiang Y, Xu X, Zheng M, et al. Evolutionary computation for unmanned aerial vehicle path planning: a survey[J]. Artificial Intelligence Review, 2024, 57(10): 267.
[6]

Guo Y, Liu X, Jia Q, et al. HPO-RRT*: a sampling-based algorithm for UAV real-time path planning in a dynamic environment[J]. Complex & Intelligent Systems, 2023, 9(6): 7133-7153.
[7]

刘文倩, 单梁, 张伟龙, 等. 复杂环境下基于改进Informed RRT*的无人机路径规划算法[J]. 上海交通大学学报, 2024, 58(4): 511-524.
[8]

Liu Wenqian, Shan Liang, Zhang Weilong, et al. Unmanned aerial vehicle path planning algorithm based on improved Informed RRT* in complex environment[J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 511-524.
[9]

Huang C, Du B, Chen M. Multi-UAV cooperative online searching based on Voronoi diagrams[J]. IEEE Transactions on Aerospace and Electronic Systems, 2024, 60(3): 3038-3049.
[10]

Zhao Y, Ni J, Tang G, et al. Improved D3QN with graph augmentation for enhanced multi-UAV cooperative path planning in urban environments[J]. International Journal of Machine Learning and Cybernetics, 2024, 16(4): 2315-2333.
[11]

Wu J, Sun Y, Li D, et al. An adaptive conversion speed q-learning algorithm for search and rescue UAV path planning in unknown environments[J]. IEEE Transactions on Vehicular Technology, 2023, 72(12): 15391-15404.
[12]

Niu Y, Yan X, Wang Y, et al. 3D real-time dynamic path planning for UAV based on improved interfered fluid dynamical system and artificial neural network[J]. Advanced Engineering Informatics, 2024, 59: 102306.
[13]

宋睿, 朱培, 张剑高, 等. 面向高原森林火灾的灭火无人机路径规划[J]. 科学技术与工程, 2024, 24(34): 14863-14870.
[14]

Song Rui, Zhu Pei, Zhang Jiangao, et al. Path planning of fire fighting UAV for plateau forest fires[J]. Science Technology and Engineering, 2024, 24(34): 14863-14870.
[15]

王飞, 杨清平. 基于改进粒子群算法的城市物流无人机路径规划[J]. 科学技术与工程, 2023, 23(30): 13187-13194.
[16]

Wang Fei, Yang Qingping. Route planning of urban logistics unmanned aerial vehicle based on improved particle swarm optimization algorithm[J]. Science Technology and Engineering, 2023, 23(30): 13187-13194.
[17]

吴学礼, 王超, 赵俊棋, 等. 改进麻雀算法的无人机三维路径规划[J]. 科学技术与工程, 2024, 24(15): 6534-6542.
[18]

Wu Xueli, Wang Chao, Zhao Junqi, et al. Improved sparrow algorithm for UAV 3 D path planning[J]. Science Technology and Engineering, 2024, 24(15): 6534-6542.
[19]

Huang C, Zhou X, Ran X, et al. Adaptive cylinder vector particle swarm optimization with differential evolution for UAV path planning[J]. Engineering Applications of Artificial Intelligence, 2023, 121: 105942.
[20]

Zhang M, Han Y, Chen S, et al. A multi-strategy improved differential evolution algorithm for UAV 3D trajectory planning in complex mountainous environments[J]. Engineering Applications of Artificial Intelligence, 2023, 125: 106672.
[21]

王文涛, 叶晨, 田军. 基于多策略改进人工兔优化算法的三维无人机路径规划方法[J]. 电子学报, 2024, 52(11): 3780-3797.
[22]

Wang Wentao, Ye Chen, Tian Jun. A 3D UAV path planning method based on multi-strategy improved artificial rabbit optimization algorithm[J]. Acta Electronica Sinica, 2024, 52(11): 3780-3797.
[23]

Tu B, Wang F, Han X. 3D path planning for UAV based on a hybrid algorithm of marine predators algorithm with quasi-oppositional learning and differential evolution[J]. Egyptian Informatics Journal, 2024, 28: 100556.
[24]

Liu B, Cai Y, Li D, et al. A hybrid ARO algorithm and key point retention strategy trajectory optimization for UAV path planning[J]. Drones, 2024, 8(11): 644.
[25]

Yu X, Luo W. Reinforcement learning-based multi-strategy cuckoo search algorithm for 3D UAV path planning[J]. Expert Systems with Applications, 2023, 223: 119910.
[26]

Wang W, Li X, Tian J. UAV formation path planning for mountainous forest terrain utilizing an artificial rabbit optimizer incorporating reinforcement learning and thermal conduction search strategies[J]. Advanced Engineering Informatics, 2024, 62: 102947.
[27]

Gao Y. PID-based search algorithm: a novel metaheuristic algorithm based on PID algorithm[J]. Expert Systems with Applications, 2023, 232: 120886.
[28]

Liu Z, Huang Y, Kang Q, et al. Optimal operation of CCHP system with duality operation strategy considering hydrogen trading and carbon capture[J]. Sustainable Cities and Society, 2024, 115: 105881.
[29]

谢志远, 曹通. 基于PSA的中压电力线载波通信自适应阻抗匹配[J]. 电力系统保护与控制, 2024, 52(18): 45-52.
[30]

Xie Zhiyuan, Cao Tong. Adaptive impedance matching of medium voltage power line carrier communication based on PSA[J]. Power System Protection and Control, 2024, 52(18): 45-52.
[31]

Phung M, Ha Q. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization[J]. Applied Soft Computing, 2021, 107: 107376.
[32]

Sun W, Sun P, Ding W, et al. Gradient-based autonomous obstacle avoidance trajectory planning for B-spline UAVs[J]. Scientific Reports, 2024, 14(1): 14458.
[33]

Xue J, Shen B. Dung beetle optimizer: a new meta-heuristic algorithm for global optimization[J]. The Journal of Supercomputing, 2022, 79(7): 7305-7336.
[34]

Heidari A, Mirjalili S, Faris H, et al. Harris hawks optimization: algorithm and applications[J]. Future Generation Computer Systems, 2019, 97: 849-872.

基金资助

国家自然科学基金(62461030)

云南省基础研究重点项目(202401AS070105)

PDF (14465KB)

43

访问

0

被引

详细
导航
相关文章

/

〈 〉

京ICP备05035734号-4
版权所有 © 《科学技术与工程》编辑部
地址： 北京市海淀区学院南路86号 《科学技术与工程》编辑部　邮编：100081
电话：(010)62118920 　E-mail：stae@vip.163.com
技术支持：北京玛格泰克科技发展有限公司 　
网站管理员登录