基于A*和水母复合算法的无人机三维路径规划

张勰 ,  何福锋

科学技术与工程 ›› 2026, Vol. 26 ›› Issue (9) :3994-4005

PDF (11895KB)
科学技术与工程 ›› 2026, Vol. 26 ›› Issue (9) :3994-4005 DOI: 10.12404/j.issn.1671-1815.2503570
航空、航天

基于A*和水母复合算法的无人机三维路径规划

作者信息 +

UAV 3D Path Planning Based on A* and Jellyfish Composite Algorithm

Author information +
文章历史 +

摘要

针对无人机在复杂三维地形中的路径规划效率不高及可行性不足等问题,聚焦复杂自然地形场景的路径规划问题,以城市环境与动态障碍物场景作为未来研究方向,提出了一种结合A*算法与水母搜索算法的自适应混合优化方法。该方法引入自适应参数调整机制,有效提升了路径规划的效率和结果的可行性。利用航天飞机雷达地形测绘使命(shuttle radar topography mission,SRTM)实测地形数据及典型仿真环境开展实验,对比A*算法、粒子群优化算法、蚁群优化算法和鲸鱼优化算法等常用优化算法。实验结果表明,该方法在路径长度、计算时间及内存占用等多项指标上均取得显著优势。具体表现为路径整体更优化,规划速度更快,资源消耗更低,且在复杂地形环境下能够保证较高的路径可行性和安全性。此外,所采用的多约束动态协同策略及高效混合规划器架构进一步增强了算法对于不同地形和复杂约束情境的适应能力。研究结果为无人机在复杂环境下的自主路径规划提供了新的工程实现思路,具有重要的应用价值和推广前景。

Abstract

To address the issues of low efficiency and insufficient feasibility in path planning for drones in complex three-dimensional terrain, focusing on path planning in natural terrain scenarios, with urban environments and dynamic obstacle scenarios as future research directions, an adaptive hybrid optimisation method combining the A* algorithm and jellyfish search algorithm was proposed. The method introduces an adaptive parameter adjustment mechanism, which effectively improves the efficiency of path planning and the feasibility of the results. Experiments were carried out using shuttle radar topography mission(SRTM) measured terrain data and typical simulation environments to compare the commonly used optimisation algorithms such as A* algorithm, particle swarm optimisation algorithm, ant colony optimisation algorithm and whale optimisation algorithm. The experimental results show that the method achieves significant advantages in a number of indicators, such as path length, computation time and memory consumption. Specifically, it is shown that the overall path is more optimised, the planning speed is increased, the resource consumption is reduced, and the path feasibility and safety can be ensured under the complex terrain environment. In addition, the multi-constraint dynamic cooperative strategy and the efficient hybrid planner architecture further enhance the adaptability of the algorithm to different terrains and complex constraints. The results provide a new engineering implementation idea for autonomous path planning of UAVs in complex environments, which has important application value and promotion prospects.

Graphical abstract

关键词

无人机 / 三维路径规划 / 水母搜索算法 / A*算法 / SRTM地形数据

Key words

UAV / 3D path planning / jellyfish search algorithm / A* algorithm / SRTM terrain data

引用本文

引用格式 ▾
张勰, 何福锋. 基于A*和水母复合算法的无人机三维路径规划[J]. 科学技术与工程, 2026, 26(9): 3994-4005 DOI:10.12404/j.issn.1671-1815.2503570
ZHANG Xie, HE Fu-feng. UAV 3D Path Planning Based on A* and Jellyfish Composite Algorithm[J]. Science Technology and Engineering, 2026, 26(9): 3994-4005 DOI:10.12404/j.issn.1671-1815.2503570

登录浏览全文

4963

注册一个新账户 忘记密码

近年来,无人机在军事侦察、应急救援、农林监测等领域的广泛应用,使其在复杂三维环境下的高效路径规划成为仍需解决的关键技术问题[1]。无人机路径规划问题主要分为多旅行商问题(multiple travelling salesman problem,MTSP)、搜索问题、覆盖问题、避障及轨迹优化问题和其他问题五大类。无人机路径规划技术面临着多重挑战,需要在最优性、完备性、时间效率和能源效率等多个维度进行权衡[2]。当前研究主要集中在城市或其他简单地形环境中的无人机路径规划问题,以及提高算法的计算效率和路径质量[3]。在面对山地、峡谷等地形崎岖区域,传统路径规划算法往往难以兼顾计算效率、路径可行性与能耗优化。
当前三维地形重构依赖于离散地形采样数据,是实现地形可视化与路径优化的基础[4],而数字高程模型(digital elevation model,DEM)则能够准确和真实地反映地形特征[5]。宋睿等[6]针对高原森林灭火无人机路径规划问题,基于DEM数据,采用栅格法构建三维地理空间模型,建立多约束条件下无人机路径规划模型,设计基于欧几里得距离和切比雪夫距离的加权距离改进A*算法进行模型求解;但传统DEM数据存在不足,例如在某些偏远或特殊地区的DEM数据可能缺失或精度不足,同时在数据处理过程中插值操作可能引入误差,而航天飞机雷达地形测绘使命(shuttle radar topography mission,SRTM)数据恰好能够很好地弥补传统DEM的一些局限,提供更精确的数据和更广泛的应用。
以粒子群优化(particle swarm optimization,PSO)、蚁群优化(ant colony optimization,ACO)、水母搜索算法(jellyfish search algorithm,JSA)和鲸鱼优化算法(whale optimization algorithm,WOA)为代表的智能优化算法在寻优效率和全局搜索能力方面均有一定优势,但这类算法普遍存在参数设置依赖性过强、容易陷入局部最优、收敛性难以保证等固有缺陷,特别是在复杂三维环境下的机器人路径规划中,这些算法往往难以有效处理多约束条件,且计算效率随环境复杂度急剧下降,实时性难以满足实际应用需求[7-10]。因此,如何改进这些算法的收敛性能和环境适应性,成为当前研究的重点。
王飞等[11]针对传统PSO算法在城市物流无人机路径规划中易陷入局部最优、后期收敛效率低的问题,改进PSO算法,引入Singer混沌映射改善粒子初始分布,采用线性调整加速因子和最大速度进行扩大搜索,设计粒子位置更新策略和动态调整惯性权值的方法,有效解决传统PSO算法早熟收敛、搜索精度不足的问题;杜云等[12]针对传统PSO算法在多无人机航迹规划中存在的收敛速度慢、成功率不高、易陷入局部最优等问题,提出改进PSO算法,通过学习因子线性化调整实现粒子惯性和最优行为平衡,引入混沌初始化改善粒子分布质量,基于遗传变异思想设计取代策略,提出调速机制提升收敛速度,在满足多约束条件的情况下,实现规划成功率高、收敛速度快、航迹代价小的优化效果;张涛等[13]提出改进的自适应人工鱼群算法,引入自适应步长和视野范围的动态调整机制,结合全局最优位置和局部最优位置更新个体位置,有效解决传统人工鱼群算法收敛速度慢、易陷入局部最优的问题。
近年来,A*算法(A-star Algorithm)凭借其高效的启发式搜索能力,在二维及三维路径规划领域得到了广泛应用,但在高维空间和复杂约束条件下,常面临节点膨胀、实时性降低及内存消耗大的问题[14]。但由于A*算法具有广度优先搜索和最佳优先搜索的优点,在路径规划领域中具有广泛应用。孙宁等[15]优化A*算法代价函数,使改进后的A*算法规划出全局路径更平顺;赵晓等[16]在A*算法的基础上结合跳点搜索算法,使改进后的A*算法寻路速度较传统A*算法提高了约200%;闫少华等[17]针对城市物流无人机三维路径规划问题,提出一种改进的A*算法,引入动态步长、Bresenham算法思想及改进启发式函数,使改进后的A*算法相比传统A*算法路径规划时间降低24.84%,路径长度缩短2.89%,搜索节点减少82.81%。
现有优化往往聚焦于优化算法本身,很少融合其余算法,在算法应用过程中还需要考虑引入多目标协同,同时对算法效率进行评估。张伏等[18]为实现复杂车间环境下移动机器人高效路径规划,提出了一种融合改进A*与DW算法的混合路径规划方法,考虑障碍物密度、转弯次数和运动惯性因子的影响改进A*算法启发函数,同时改进DWA算法轨迹评价函数,将全局最优路径关键点作为目标点并引入距离、动态障碍物和路径跟踪代价三项评价子项。仿真结果表明,改进算法在路径长度、规划时间、扩展节点数和拐点数方面分别减少15.80%、81.20%、2.30%和74.10%;董翼宁等[19]为了实现自动引导车在路径规划中达到全局最优、实时避障的要求,提出了一种优化A*与优化DWA算法相融合的自动引导车路径规划方案,采用优化A*算法进行路径搜索,采用优化DWA算法进行动态障碍物避障,仿真结果表明,融合优化后的算法能减小搜索范围,提高了路径规划效率且能实现避障。
以上路径规划算法在特定环境中均有很好的效果。随着深度强化学习[20]与智能优化方法的融合应用进展,多智能体、多任务的无人机路径联合规划已成为研究热点。未来无人机路径规划技术正从传统算法向智能化、混合化方向演进:传统A*、Dijkstra算法适用静态环境,粒子群、遗传算法等智能优化算法成为主流,深度学习和强化学习代表前沿方向;技术发展呈现混合算法优化、多传感器融合自主决策、动态避障与多约束优化三大趋势[21]。针对复杂地形环境路径规划中存在内存占用大、搜索效率低的情况,现提出一种基于A*全局引导与多约束动态协同的自适应水母搜索算法(adaptive jellyfish search algorithm,AJSA)算法,考虑在SRTM地形数据下采用三维自适应分辨率网格的A*算法进行全局路径搜索,提高搜索效率;设计自适应参数调整机制[22]、动态权重因子和多种变异策略[23],增强AJSA算法的环境适应性和收敛性能。首先,通过SRTM数据进行环境建模,并引入A*算法进行初步路径搜索得到参考路径,其次以起点和终点为基础,通过线性插值和添加随机扰动生成初始种群,每条路径都经过约束修正,最后,在进化过程中,算法不断对种群进行优化和扰动,选出最优路径,并可根据多样性和收敛情况动态调整参数,最终输出一条平滑且安全的三维路径。以期为无人机在复杂环境下的自主路径规划提供新的工程实现思路。

1 三维路径规划与基础算法原理

在复杂三维地形环境下,无人机路径规划的核心是寻找一条从起点到终点的最优路径,同时满足多种约束条件。基于SRTM地形数据,构建了完整的三维路径规划问题模型。

1.1 问题建模

复杂三维路径规划的目标是在已知起点和终点、已知环境障碍物分布及无人机动力学约束条件下,生成一条安全、可行且高效的飞行路径。路径需满足避障、平滑、能耗低等要求,可抽象为如下优化目标。

(1)地形避障约束。保证路径点始终高于地形表面并具备安全裕度,防止碰撞。

${{z}_{i}}\ge {{z}_{\text{terrain}}}({{x}_{i}},{{y}_{i}})+{{h}_{\text{safety}}},\forall i\in \{1,2,\ldots ,n\}$

式(1)中:zterrain(xi,yi)为地形数字高程模型在该平面位置的高度;hsafety为安全飞行高度。

(2)坡度约束。路径相邻点间的坡度不得超过平台可承受的最大坡度。

$\left| \frac{{{\text{z}}_{\text{i}+1}}-{{\text{z}}_{\text{i}}}}{={{p}_{\text{i}+1,\text{xy}}}-{{p}_{\text{i},\text{xy}}}{{=}^{2}}} \right|\le {{\lambda }_{\max }},\forall i\in \{1,2,\ldots ,n-1\}$

式(2)中:zi为第i点飞行高度;pi,xy为第i点个路径点在水平面的投影坐标向量,不含高度;λmax为最大坡度差。

(3)高度变化约束。路径相邻点的高度变化有上限,以保证飞行平稳和可控。

$\left| {{z}_{i+1}}-{{z}_{i}} \right|\le \Delta {{z}_{\max }},\forall i\in \{1,2,\ldots ,n-1\}$

式(3)中:zi为第i点飞行高度;Δzmax为最大可接受高度变化。

(4)路径连续性约束。限制路径折线的转角不超过最大允许值,以提升路径平滑性和可行性。

${{\theta }_{i}}=ar\cos \left( \frac{{{v}_{i-1}}{{v}_{i}}}{\left| {{v}_{i-1}} \right|\left| {{v}_{i}} \right|} \right)\le {{\theta }_{\max }}$

式(4)中:θi为第i点在路径上的转角,即两相邻段的夹角;θmax为最大可接受转角;vi、vi-1分别为从上一段、当前路径点指向下一路径点的方向向量;分别通过两个相邻段向量的夹角来衡量拐弯程度。

(5)边界约束。路径点需位于规划区间,包括水平和垂直范围。

$\left\{\begin{array}{ll}{x}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {x}_{i}\le {x}_{\mathrm{m}\mathrm{a}\mathrm{x}},& \forall i\in \{\mathrm{1,2},\dots,n\}\\ {y}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {y}_{i}\le {y}_{\mathrm{m}\mathrm{a}\mathrm{x}},& \forall i\in \{\mathrm{1,2},\dots,n\}\\ {z}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {z}_{i}\le {z}_{\mathrm{m}\mathrm{a}\mathrm{x}},& \forall i\in \{\mathrm{1,2},\dots,n\}\end{array}\right.$

式(5)中:xmin、xmax、ymin、ymax为地形区域的水平边界;zmax、zmin为飞行高度的上下限。

本文研究的边界是通过地形数据的范围隐式定义的。

(6)多目标成本函数。路径优化采用加权目标函数。

$ J={{\beta }_{1}}{{J}_{\text{distance}}}+{{\beta }_{2}}{{J}_{\text{elevation}}}+{{\beta }_{3}}{{J}_{\text{smoothess}}}+{{\beta }_{4}}{{J}_{\text{slope}}}+{{\beta }_{5}}{{J}_{\text{energy}}}$

式(6)中:Jdistance为衡量路径总长度;Jelevation为衡量路径的垂直高度变化;Jsmoothess为衡量路径的曲率;Jslope为惩罚超过最大坡度的部分;Jenergy为综合考虑水平与垂直飞行的能耗;权重β1、β2、β3、β4、β5根据实际需求设定,且权重和为1,针对多目标数值存在的不同量级问题,采用最大-最小归一化方法来解决这个问题,将所有目标函数值映射到[0,1]区间内,确保不同目标在优化过程中具有相同的影响权重。

(7)无人机性能约束。根据无人机型号对飞行性能进行约束。

飞行速度约束:

${{C}_{\text{speed-min}}}\le \left| \frac{\|{{p}_{i}}-{{p}_{i-1}}\|}{\Delta t} \right|\le {{C}_{\text{speed-max}}}$

式(7)中:Cspeed-min、Cspeed-max分别为无人机最小、最大巡航飞行速度;pi为无人机第i点的位置向量;Δt为时间差。

爬升率约束:

$\left| \frac{{{z}_{i}}-{{z}_{i-1}}}{\text{ }\!\!\Delta\!\!\text{ }t} \right|\le {{C}_{\text{climb}}}$

式(8)中:zi为第i点飞行高度;Cclimb为最大爬升速度。

滚转角约束:

$\frac{\left| {{\theta }_{\text{g}}}\left( t \right)-{{\theta }_{\text{g}}}\left( t-1 \right) \right|}{\text{ }\!\!\Delta\!\!\text{ }t}\le {{\omega }_{\text{gmax}}}$
${{\theta }_{g}}\le {{\theta }_{\max }}$

式中:θg、θmax分别为当前滚转角和最大滚转角;θg(t)、ωgmax分别为t时刻滚转角和最大滚转角变化率。

1.2 水母搜索算法原理

水母搜索算法(jellyfish search algorithm, JSA)是一种受水母群体觅食行为启发的元启发式优化方法。该算法通过模拟水母在海洋中的两种典型运动——被动漂移(洋流运动)和主动游动(群内运动),实现全局与局部搜索的动态切换。初期以全局搜索为主,后期逐步增强局部开发能力,从而提升寻优效率和收敛速度。JSA凭借全局与局部搜索的有机结合,在复杂优化问题中表现出良好的全局寻优能力和收敛速度。

水母的寻优运动主要分为两类。一类是基于洋流的运动,另一类是基于种群个体的运动。控制不同种类运动的函数表达式为

$C\left(t\right)=\left|\left(1-\frac{t}{{t}_{\mathrm{m}\mathrm{a}\mathrm{x}}}\right)\left[2\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\right(\mathrm{0,1})-1]\right|$

当C(t)≥0.5时,考虑水母在洋流的作用下的运动。其数学模型表示为

${{X}_{i}}(t+1)={{X}_{i}}(t)+\text{rand}(0,1)[{{X}_{best}}-\text{ }\!\!\alpha\!\!\text{ rand}(0,1)\bar{X}]$

式(12)中:t为迭代的次数;Xbest为水母的最佳位置值;$\overline{X}$为水母种群中个体位置的平均值;α为常系数。

当C(t)<0.5时,种群个体中水母的运动,包含水母的被动形式和主动形式的运动。在寻优的初期水母会以被动形式进行运动,后期将转变为主动运动的形式。对前后期加以区分的运动表达式如式(9)所示。当C(t)>0.5且rand(0,1)>1-C(t)时,水母进行被动运动,位置更新公式为

${{X}_{i}}(t+1)={{X}_{i}}(t)+\beta \text{rand}(0,1)({{X}_{\max }}-{{X}_{\min }})$

式(13)中:β为常系数;Xmax、Xmin分别为搜索空间的最大值和最小值。

当C(t)>0.5且rand(0,1)≤1-C(t)时,水母进行主动运动,在这一阶段的数学公式表示为

$\left\{\begin{array}{l}{X}_{i}(t+1)={X}_{i}\left(t\right)+\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\left(\mathrm{0,1}\right)\\ \mathrm{\Delta }S=\alpha [{X}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-{X}_{i}(t\left)\right]\end{array}\right.$

如图1所示为水母搜索算法流程图。

1.3 传统A*算法原理

A*算法是一种启发式搜索算法,通过评估函数f(n)=g(n)+h(n)指导搜索过程,其中f(n)表示从起始点经过节点n到终点的总成本;g(n)表示从起点到当前节点n的实际成本;h(n)表示通过启发函数对节点n到终点的估计成本值。启发函数的选择直接影响路径规划的效果。常用三维启发函数包括曼哈顿距离、欧几里得距离和切比雪夫距离。采用欧几里得距离,并结合地形信息加权[24],以提升搜索效率。

在三维地形环境中实现A*算法时,需要考虑以下几个关键点。

(1)三维网格表示:将三维空间离散化为网格,每个网格点表示一个可能的路径点。

(2)邻居节点生成:在三维空间中,每个节点有26个邻居(上、下、左、右、前、后及对角线方向)。

(3)地形约束处理:检查节点是否满足地形避障约束,不满足则不将其加入开放列表。

A*算法能够高效地在复杂三维环境中搜索可行路径,但在大规模空间或复杂约束下易受启发函数和搜索空间规模影响。

2 基于A*全局引导的自适应水母搜索算法的设计与实现

2.1 算法整体框架

自适应水母搜索算法(AJSA)融合了A*全局引导和自适应参数调整机制,针对三维复杂环境下无人机路径规划,兼顾路径平滑性、安全性和能效。算法包括A*全局引导、混合初始化、自适应参数调整和多约束处理4个模块,协同实现高效路径搜索,在多约束处理模块引入适应度评估,将成本目标函数转化为适应度函数,利用倒数关系进行评估,使得路径适应度越低目标函数越优异[25]。AJSA算法伪代码如表1所示,整体框架如图2所示。

2.2 A*全局引导策略

采用自适应分辨率三维栅格地图,A*算法结合欧氏距离、高度差和地形复杂度等多因素启发式函数,生成全局参考路径,为后续优化提供有效引导。自适应分辨率三维栅格地图如图3所示。

为提高A*算法在三维环境中的搜索效率,设计了一种综合启发式函数,如式(15)所示。

h(n)=ω1hdist(n)+ω2helev(n)+ω3hterr(n)

式(15)中:hdist(n)为节点n到目标点的欧几里得距离;helev(n)为高度差异代价,考虑了垂直方向的能量消耗;hterr(n)为地形复杂度代价,反映了地形的起伏程度;ω1、ω2和ω3为权重系数,满足ω1+ω2+ω3=1。

这种综合启发式函数不仅考虑了空间距离,还考虑了高度变化和地形特征,使A*算法能够生成更加合理的初始参考路径。这种综合启发式函数不仅考虑了空间距离,还考虑了高度变化和地形特征,使A*算法能够生成更加合理的初始参考路径。对于量级问题,采用统一量级的处理方法,将高度差异和地形复杂度都转换为与距离相同的量级单位,确保启发式函数各项贡献的合理性,在高度差异和地形复杂度方面引入高度惩罚因子和地形惩罚因子,将高度差异转换为等效水平距离,地形复杂度转换为等效绕行距离,统一量级,避免某项主导,保持了物理意义的清晰性。

2.3 自适应水母搜索优化

2.3.1 混合初始化策略

融合A*参考路径、线性插值及随机扰动,保证种群的多样性和可行性。混沌初始化策略的数学表达式如式(12)所示,混沌初始化策略示意图如图4所示。

${X}_{i}^{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}$=αXA*+(1-α)Xlinear+βN(0,σ2)

式(16)中:${X}_{i}^{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}$为第i个水母的初始位置;XA*为A*算法参考路径;Xlinear为线性插值路径;α为A*算法引导权重,在[0,1]范围内随机生成;β为扰动强度,根据种群多样性需求动态调整;N(0,σ2)为均值为0、方差为σ2的高斯噪声。

2.3.2 自适应参数调整机制

自适应参数调整机制是AJSA算法的核心创新之一,该机制能够根据搜索状态和地形特征动态调整关键参数。自适应参数调整机制的数学表达式如式(17)~式(19)所示。

探索率调整:

r(t)=rmin+(rmax-rmin)${\mathrm{e}}^{-\alpha \frac{t}{T}}$+βΔf

A*引导权重调整:

ωA*(t)=${\omega }_{\mathrm{A}\mathrm{*}}^{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}{e}^{-\gamma \frac{t}{T}}$

多样性评估:

D(t)=$\frac{1}{N(N-1)}\stackrel{N}{\sum _{i=1}}\stackrel{N}{\sum _{j=i+1}}$d(Xi,Xj)

式中:t为当前迭代次数;T为最大迭代次数;rmin和rmax分别为最小和最大搜索率;α为探索率衰减系数;β为适应性调整系数;Δf为最近几次迭代的成本函数改善程度;${\omega }_{\mathrm{A}\mathrm{*}}^{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}$为初始A*引导权重;γ为引导权重衰减系数;D(t)为第t次迭代的种群多样性;d(Xi,Xj)为第i个和第j个水母之间的距离;N为种群大小。

2.3.3 算法参数体系

本文算法涉及四类参数。

(1)收敛控制参数。

最大迭代次数Nmax:控制算法探索深度。

收敛阈值∈conv:判定算法收敛的精度要求。

收敛计数器阈值∈count:防止过早收敛的稳定性机制。

(2)探索引导参数。

初始噪声尺度σinit:控制初始探索范围。

收敛阈值λnoise:平衡探索与利用的关键参数。

梯度敏感性ωgrad:结合梯度信息的引导强度。

(3)成本权重参数。

路径权重ωdist:路径长度优化的重要性。

平滑度权重ωsmooth:路径质量的权衡因子。

障碍物权重ωobs:安全约束的惩罚系数。

高度范围权重ωrange:安全飞行高度的重要权衡因子。

(4)物理约束参数。

最大转弯角θmax:基于无人机运动学的约束。

安全飞行高度hsafe:地形回避的最小高度。

网格分辨率Δg:环境离散化的精度设置。

2.4 算法实现与优化

为提升算法在大规模三维地形数据下的实际应用能力,在实现过程中采用了多项工程优化措施,包括高效的内存管理、并行计算、函数缓存和数值计算加速等。这些优化手段显著提升了算法的运行效率和可扩展性,使其能够在有限的计算资源下完成复杂路径规划任务。以A*算法[15]和蚁群优化算法(ACO)[8]等经典路径规划方法为例,它们在求解大规模三维地形环境中的无人机路径优化时,既需要保证路径的全局最优性,又面临着高维空间下计算量激增的问题。

3 仿真实验与分析

3.1 实验环境与数据

为考察算法在多类型三维环境的路径规划能力,实验基于SRTM地形数据构建复杂地形场景,后续研究将进一步纳入城市或人工环境数据。各类对比算法(A*、PSO、ACO、WOA及本文算法AJSA)均在相同的初始环境和障碍地图条件下测试,以保证实验结果的公平和公正。本文研究中的障碍物通过地形特征自动提取,未引入外部人工数据,以确保算法在真实自然地形中的泛化能力。

以典型中小型固定翼巡检无人机为参考平台(巡航速度20~25 m/s,持续爬升率约为5 m/s,翼展1.8 m,最大起飞重量为4.0~4.2 kg,任务常规海拔0~800 m,相对地形起伏<300 m。此类平台咋测绘、巡检任务中广泛使用,通常持续爬升率为4~6 m/s,安全滚转角控制在25°~35°以维持图像质量与气动效率。

所有算法的关键参数初步均参考国内外公开文献中常用最优或推荐值,并对主要参数进行多组实验,选取表现最佳的参数组[26]。后续实验过程中,除共同参数外其余各项对比算法的关键参数均采用最佳参数组进行对比实验。实验过程中,所有算法均在同一硬件(Intel i7-9750H,16 GB内存,Windows 10)与软件Pycharm平台上独立多次运行,结果以实际运行值统计,确保对比客观。仿真场景三维形态及地形特征示意图如图5所示。

3.2 参数设置

3.2.1 统一参数

为了得到公正的实验结果,将共同的参数设置为一致,具体包括:最大迭代次数Nmax=70,种群规模Psize=150,安全高度hsafe=150 m,相邻最大高度变化hmax=150 m,最大坡度λmax=0.27,最大转弯角θmax=45°,网格分辨率Δg=50 m,收敛阈值∈conv=0.05,距离权重ωdist=3.0,高程变化权重ωelev=0.5,平滑度权重ωsmooth=2.0,坡度权重ωslope=1.0,高度范围权重ωrange=0.8,障碍物权重ωobs=150,梯度敏感性ωgrad=25,收敛计数器阈∈count=5,最大巡航速度Cspeed-max=25 m/s,最小巡航速度Cspeed-min=20 m/s,最大爬升速度Cclimb=5 m/s,最大滚转角Abank=35°,翼展Wwing=1.8m,最大起飞重量Wmax=4.2 kg。

3.2.2 AJSA算法参数

AJSA算法参数如表2所示,关键参数通过敏感性分析进一步优化,保证算法收敛性和结果优质。

3.3 路径规划实验与结果

为全面评测算法性能,设定3组起点和终点,以路径长度、总成本、计算时间、内存占用为评价指标。所有结果均为多次独立实验平均值。3组实验的起点和终点如表3所示,3组实验的3D路径场景、高度剖面对比如图6~图8所示,3组实验的计算时间、路径长度、内存占用、总成本如表4~表6所示。

根据图6~图8、表4~表6实验结果显示,本文算法AJSA在各项指标均表现突出,计算速度、路径最优性及资源消耗显著优于其余算法。A*算法虽然用时较短,但路径和成本不优,PSO、WOA虽能改善路径,但求解速度极慢,难以满足实时性需求。AJSA则兼顾优质路径、低计算与低资源消耗,具有最佳综合性能。

3.4 消融实验

去掉A*算法全局引导、去掉自适应参数调整机制情况下,3D路径场景、高度剖面、计算时间、路径长度、内存占用分别如图9、图10所示。

消融实验使用第三种起始点参数作为对照,实验结果表明,尽管A*算法全局引导和自适应参数调整机制对最终路径长度的影响相对有限,但它们对路径的平滑性和可行性有显著提升作用。通过对比图8(b)与图9(b),可以观察到缺失全局引导后,路径趋于杂乱,在穿越复杂地形时更易出现冗余回转和局部震荡;而引入A*全局引导后,路径整体更加合理、趋于直线,显著提高路径平滑性。同时,通过图8(b)与图10(b)对比可以发现,缺少自适应参数调整时,搜索过程中收敛速度变慢,部分路径段呈现不均匀幅度变化,影响了路径的连续与可控性,引入后则能有效提升算法整体的稳定性和可行性。

综上所述,A*全局引导有助于提升路径全局合理性,自适应参数机制增强了算法的适应能力和收敛效果,进一步验证了所提混合算法各关键模块设计的合理性与必要性。

3.5 算法参数敏感性与调优

为了找出对AJSA算法性能影响最大的参数,对关键参数进行了敏感性分析,参数敏感度热力图如图11所示。

热力图(11)结果分析表明,以下参数对算法性能影响最大:迭代次数(num_iterations);梯度敏感性(gradient_weight);噪声衰减率(smoothness_weight)。参数敏感性分析表明,梯度敏感性对路径长度影响最大,噪声衰减率主导收敛速度。

3个参数的敏感度对比图如图12所示。

通过对3个关键参数的敏感度分析,确定了AJSA算法的最优参数组合:梯度敏感性为40.0,噪声衰减率为0.7,迭代次数为60。这组参数在保证算法收敛性的同时,能够生成最短路径。参数敏感度分析还表明,迭代次数对路径长度的影响最为显著,其次是梯度引导权重,而噪声衰减率的影响相对较小。这一发现为实际应用中的参数调优提供了重要指导。

3.6 显著性和收敛性验证

3.6.1 显著性验证

通过对比实验,采用独立样本t检验(α=0.05),对各算法的运行时间进行了统计分析。以AJSA算法为参照组,将A*、PSO、ACO、WOA等算法的耗时与其进行比较。结果如表7所示。

表7中展示了A*、PSO、ACO、WOA和本文算法AJSA在路径规划任务中的平均耗时、耗时标准差、平均路径长度及路径长度标准差。以AJSA为对比基准,A*、PSO、ACO、WOA 4种算法的耗时均与AJSA存在显著性差异(P< 0.000 1)。其中,AJSA的平均耗时最低,路径长度也最短,且结果稳定性较好(标准差较小)。A*算法的路径长度标准差为0,说明其为确定性算法,每次输出一致。PSO、ACO、WOA智能优化算法由于存在随机性,路径长度标准差略高。

3.6.2 收敛性验证

通过收敛性实验,统一采用了基于最优路径成本变化的收敛性判定方法。在每次迭代之后,算法会记录当前最优路径的成本值,形成收敛历史,收敛性判定采用滑动窗口标准差法:设定一个窗口长度(如5~10次),计算窗口内最优值的标准差,当标准差低于预设阈值(如0.01),即认为算法已收敛。此外,部分算法还会结合相对改进率等多重标准,进一步提高判定的鲁棒性。

A*算法属于启发式搜索算法,本质是一次性从起点搜索到终点,不存在多轮进化或优化过程,因此无需进行收敛判定。WOA算法由于最近几次最优值的标准差小于阈值,被认为已经收敛,提前停止。收敛性验证图像如图13所示。

由图13可见,不同优化算法在100次迭代过程中表现出不同的收敛特性,从收敛曲线的变化趋势来看,PSO、ACO、WOA、AJSA算法的适应度值随着迭代次数增加逐渐降低,说明各算法均具有一定的全局搜索能力。其中,AJSA在前期收敛速度较快,并在后期表现出更好的稳定性和更低的适应度值,表明其不仅能够有效避免早熟收敛问题,还具有更强的寻优能力和收敛精度。对比而言,经典算法如PSO、WOA的收敛速度存在一定差距,部分算法在优化后期易陷入局部最优,而ACO因为早停收敛机制很早便结束了收敛且不具备优异结果。综合来看,AJSA在所研究问题中的优化性能优于其他对比算法,更加适合解决类似的复杂优化问题。

4 结论

(1)提出了一种基于A*算法全局引导与多约束动态协同的改进型水母搜索算法(AJSA),通过A*引导、自适应参数机制、多约束和高效混合规划器,有效提升了无人机在复杂三维环境下的路径规划性能,在路径质量、效率和鲁棒性等方面优于传统方法。

(2)实验结果表明,AJSA能够有效避免局部最优,提高收敛速度,路径长度平均缩短15%,计算效率提升30%,并显著增强了路径的安全性、平滑度和能效。

(3)在动态障碍物场景以及对比算法上存在局限性,未来将研究动态障碍物避障、实时重规划、多无人机协同、深度学习融合、硬件加速及实际飞行验证,进一步拓展应用和提升性能。随着深度强化学习[25]与智能优化方法的融合应用进展,多智能体、多任务的无人机路径联合规划已成为研究热点。未来无人机路径规划技术正从传统算法向智能化、混合化方向演进:传统A*、Dijkstra算法适用静态环境,粒子群、遗传算法等智能优化算法成为主流,深度学习和强化学习代表前沿方向;技术发展呈现混合算法优化、多传感器融合自主决策、动态避障与多约束优化三大趋势[26]。

参考文献

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

赵畅, 刘允刚, 陈琳, 等. 面向元启发式算法的多无人机路径规划现状与展望[J]. 控制与决策, 2022, 37(5): 1102-1115.
[2]

Zhao Chang, Liu Yungang, Chen Lin, et al. Current status and prospects of multi-UAV path planning for metaheuristic algorithms[J]. Control and Decision, 2022, 37(5): 1102-1115.
[3]

Aggarwal S, Kumar N. Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges[J]. Computer Communications, 2020, 149: 270-299.
[4]

彭艺, 唐剑, 杨青青. 复杂山区环境下的应急无人机路径规划[J]. 吉林大学学报(理学版), 2025, 63(2): 585-594.
[5]

Peng Yi, Tang Jian, Yang Qingqing. Emergency UAV path planning in complex mountainous environments[J]. Journal of Jilin University (Science Edition), 2025, 63(2): 585-594.
[6]

成毅. 基于DEM的三维地形建模及集输管道路径优化研究[D]. 大庆: 东北石油大学, 2019.
[7]

Cheng Yi. Research on DEM-based 3D terrain modeling and optimization of gathering pipeline routing[D]. Daqing: Northeast Petroleum University, 2019.
[8]

郭敬磊. 基于DEM数据的三维地形地类可视化研究[D]. 南京: 东南大学, 2016.
[9]

Guo Jinglei. DEM data-based 3D terrain and land type visualization[D]. Nanjing: Southeast University, 2016.
[10]

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

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

Kennedy J, Eberhart R. Particle swarm optimization[C]// Proceedings of ICNN’95-International Conference on Neural Networks. Piscataway, NJ: IEEE, 1995, 4: 1942-1948.
[13]

Dorigo M, Gambardella L M. Ant colonies for the travelling salesman problem[J]. Biosystems, 1997, 43(2): 73-81.
[14]

Chou J S, Truong D N. Multiobjective optimization inspired by behavior of jellyfish for solving structural design problems[J]. Chaos, Solitons & Fractals, 2020, 135: 109738.
[15]

Mirjalili S, Lewis A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67.
[16]

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

Wang Fei, Yang Qingping. Urban logistics UAV path planning based on improved particle swarm optimization algorithm[J]. Science Technology and Engineering, 2023, 23(30): 13187-13194.
[18]

杜云, 彭瑜, 邵士凯, 等. 基于改进粒子群优化的多无人机协同航迹规划[J]. 科学技术与工程, 2020, 20(32): 13258-13264.
[19]

Du Yun, Peng Yu, Shao Shikai, et al. Multi-UAV cooperative trajectory planning based on improved particle swarm optimization[J]. Science Technology and Engineering, 2020, 20(32): 13258-13264.
[20]

张涛, 李少波, 张安思, 等. 基于改进人工鱼群算法的复杂地貌无人机三维路径规划[J]. 科学技术与工程, 2023, 23(10): 4433-4439.
[21]

Zhang Tao, Li Shaobo, Zhang Ansi, et al. Three-dimensional path planning of UAV in complex terrain based on improved artificial fish swarm algorithm[J]. Science Technology and Engineering, 2023, 23(10): 4433-4439.
[22]

Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
[23]

孙宁, 胡云雷, 陈宇飞. 基于改进A*算法的轮式巡检机器人路径规划方法[J]. 湖南大学学报自然科学版), 2025, 52(8): 103-110.
[24]

Sun Ning, Hu Yunlei, Chen Yufei. Path planning method for wheeled inspection robot based on improved A* algorithm[J]. Journal of Hunan University (Natural Sciences), 2025, 52(8): 103-110.
[25]

赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.
[26]

Zhao Xiao, Wang Zheng, Huang Chengkan, et al. Path planning for mobile robot based on improved A* algorithm[J]. Robot, 2018, 40(6): 903-910.
[27]

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

Yan Shaohua, Shi Xingyu, Zhang Zhaoning. Three-dimensional path planning of urban logistics UAV based on improved A* algorithm[J]. Science Technology and Engineering, 2024, 24(29): 12781-12788.
[29]

张伏, 韩伟东, 鲍若飞, 等. 融合改进A*与DWA算法的车间移动机器人路径规划[J]. 吉林大学学报(工学版), 2025, 55(9): 3020-3031.
[30]

Zhang Fu, Han Weidong, Bao Ruofei, et al. Path planning of workshop mobile robots integrated with improved A* and DWA algorithms[J]. Journal of Jilin University (Engineering and Technology Edition), 2025, 55(9): 3020-3031.
[31]

董翼宁, 曹景胜, 李刚. 融合 A-Star 与 DWA 双优化算法的自动引导车路径规划[J]. 科学技术与工程, 2023, 23(30): 12994-13001.
[32]

Dong Yining, Cao Jingsheng, Li Gang. AGV path planning with dual optimization algorithms integrating A-Star and DWA[J]. Science Technology and Engineering, 2023, 23(30): 12994-13001.
[33]

孙艳萍, 王道通, 张丹, 等. 基于改进遗传算法的气田无人机巡检调度优化[J]. 科学技术与工程, 2025, 25(27): 11668-11675.
[34]

Sun Yanping, Wang Daotong, Zhang Dan, et al. Optimization of UAV inspection scheduling in gas field based on improved genetic algorithm[J]. Science Technology and Engineering, 2025, 25(27): 11668-11675.
[35]

张其文, 尉雅晨. 独立自适应调整参数的粒子群优化算法[J]. 计算机科学与探索, 2020, 14(4): 637-648.
[36]

Zhang Qiwen, Wei Yachen. Particle swarm optimization algorithm with independent self-adaptive parameter adjustment[J]. Computer Science and Exploration, 2020, 14(4): 637-648.
[37]

张荣霞, 武长旭, 孙同超, 等. 深度强化学习及在路径规划中的研究进展[J]. 计算机工程与应用, 2021, 57(19): 44-56.
[38]

Zhang Rongxia, Wu Changxu, Sun Tongchao, et al. Deep reinforcement learning and its research progress in path planning[J]. Computer Engineering and Applications, 2021, 57(19): 44-56.
[39]

陈亚青, 郑稀元, 韩丹, 等. 民用无人机发展管理现状及路径规划研究进展[J]. 科学技术与工程, 2022, 22(15): 5951-5966.
[40]

Chen Yaqing, Zheng Xiyuan, Han Dan, et al. Current situation of civil UAV development and management and research progress of path planning[J]. Science Technology and Engineering, 2022, 22(15): 5951-5966.
[41]

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

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

曾宪阳, 梁远生, 于浩, 等. 基于改进Voronoi骨架图与DWA融合的移动机器人路径规划算法[J/OL]. 电子测量与仪器学报, 1-15[2026-01-05]. https://kns.cnki.net/kcms/detail/11.2488.tn.20251224.1709.090.html.
[44]

Zeng Xianyang, Liang Yuansheng, Yu Hao, et al. A mobile robot path planning algorithm based on improved Voronoi skeleton diagram and DWA fusion[J/OL]. Journal of Electronic Measurement and Instrumentation, 1-15[2026-01-05]. https://kns.cnki.net/kcms/detail/11.2488.tn.20251224.1709.090.html.
[45]

Goerzen C, Kong Z, Mettler B. A survey of motion planning algorithms from the perspective of autonomous UAV guidance[J]. Journal of Intelligent and Robotic Systems, 2010, 57(1/4): 65-100.

基金资助

国家自然科学基金联合基金(U2133210)

国家自然科学基金(52202404)

中央高校基本科研业务费中国民航大学专项(3122018D026)

PDF (11895KB)

85

访问

0

被引

详细
导航
相关文章

/

〈 〉

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