★ FEATURED ARTICLE SSA三维路径规划这词在无人机相关技术群里出现频率很高不少刚接触群体智能优化算法的朋友上来就想把麻雀搜索算法直接套到路径规划上。实际做下来这个方向比想象中更有嚼头。它本质上不是单纯的寻路问题而是把三维空间中的飞行轨迹设计转化成带约束的连续优化问题再用SSA逐代迭代逼近最优解。这篇文章就来聊聊这套方案从环境建模、目标函数设计到SSA参数配置的全过程以及我个人调试时踩过的坑希望给正在跑仿真或者准备做论文对比实验的同学一点参考。1. 问题建模与方案架构1.1 三维路径规划到底在优化什么三维路径规划不是传统意义上的迷宫寻路它不是在一个离散网格里找一条可行路径而是在连续三维空间中寻找一条既能满足空间高度约束与威胁区规避约束又让飞行代价尽可能小的平滑曲线。换句话说优化变量是路径上的若干个中间点坐标优化目标是综合航程代价、威胁代价、高度代价和平滑代价的加权和。这看起来很简单但实际做起来有三个难点第一三维地形本身是非凸的多山峰叠加以后适应度函数会出现大量局部极值很多传统优化算法很容易陷入山坳里第二路径必须避开威胁区这些区域通常是不规则的在目标函数里加惩罚项时惩罚系数设置不好就会带来适应度函数数量级失衡第三路径点数目越多维度越高SSA在高维搜索时的收敛速度会明显下降。这三件事是互相牵扯的优化变量维度决定的不仅仅是搜索难度还决定了威胁区惩罚能不能被有效传递回种群更新过程。1.2 复杂环境的地形与威胁区建模大多数做无人机路径规划的论文里复杂环境都是用数学曲面叠加出来的。山峰地形一般用高斯函数来模拟多个山峰聚合在一起就能形成连绵起伏的山脉效果。我常用的是这样的形式% 生成多山峰地形 [X, Y] meshgrid(0:1:100, 0:1:100); Z zeros(size(X)); peaks [ 25, 25, 12, 6; 50, 50, 15, 7; 70, 30, 10, 5; 80, 75, 14, 6; 30, 70, 11, 5 ]; for i 1:size(peaks, 1) Z Z peaks(i,3) * exp(-((X - peaks(i,1)).^2 (Y - peaks(i,2)).^2) / (2 * peaks(i,4)^2)); end每个山峰有四个关键参数中心坐标x、y山峰高度h以及宽度系数sigma。峰值高度和宽度决定了地形起伏特征。如果你想要更复杂的山地效果可以把山峰数量加到十几个或者用正弦波叠加产生撕裂状的高频地形。我个人更建议先用5个左右山峰做实验因为地形过于复杂以后SSA适应度函数会变得极度非凸不利于算法本身性能分析也不利于判断威胁区约束是否真正生效。威胁区的建模方式就比较多样了常见的是用圆柱体或者球形来简化。在二维视角上是半径为r的圆在三维空间里就是柱状禁区。通常威胁区可以设置成三种情况禁飞区不允许穿越、高威胁区穿越时增加代价、信号干扰区增加定位误差。在基础路径规划里把威胁区定义成禁飞区加惩罚项就够了threats [ 60, 60, 10; 20, 80, 8; 90, 45, 12 ]; % 每一行是威胁区中心的x, y以及半径要判断某个路径点是不是进入威胁区只需要计算这个点与威胁区中心在水平面上的距离即可。如果距离小于威胁半径就认为进入了威胁躲避范围。真实的无人机飞行高度和地形高度之间的关系也要在目标函数里体现。如果无人机飞得太低太大意贴近山峰飞得太高则容易被探测到且增加油耗所以高度代价项一般处理成“期望巡航高度与实际高度的差值”的平方形式。1.3 为什么选麻雀搜索算法做路径规划选择SSA而不是遗传算法或者粒子群是因为它在跳出局部最优和收敛速度之间有一个比较好的平衡。SSA的种群内部有分工一部分麻雀负责广域搜索一部分麻雀跟随最优位置觅食还有一部分麻雀负责预警和跳出局部区域。这个机制保证了种群在迭代前期探索范围足够广在后期又能够围绕优秀解进行精细开发。可能有人会问粒子群不也差不多吗粒子群最大的问题是信息传递太单一所有粒子都同时朝向当前全局最优和个体最优飞行一旦全局最优附近是局部极值整个种群容易被带走。麻雀搜索算法的发现者机制和危险预警机制就不同它在全局最优附近解探测到危险信号时种群会散开重新搜索。这个“散开机制”在二维和三维非凸地形上非常实用。不过如果你用的是基础SSA跑路径规划还是需要注意一个现实问题高维环境下SSA的加入者更新方式相对简单它主要朝最优麻雀位置移动缺乏个体之间的信息交换。所以后面很多人会研究各种改进SSA比如引入莱维飞行、混沌映射初始化、反向学习、精英保留等。如果你做实验是为了发论文改进算法部分是重头戏如果你只是拿SSA做个路径对比基准那标准SSA足够用。2. 麻雀搜索算法核心机制剖析2.1 发现者、加入者、侦察者的分工逻辑标准麻雀搜索算法将种群分成三个角色。发现者负责全局探索它们拥有较高的能量储备搜索范围大负责找到食物丰富的区域加入者负责在发现者附近继续搜索它们跟随当前最优位置更新同时也观察其他发现者有没有找到更好的位置侦察者数量最少它们负责危险预警一旦发现周围环境不再安全就会做出反方向跳跃或者向安全区域转移的动作。角色比例一般固定发现者占种群20%左右侦察者占10%左右剩下的都是加入者。这三个角色不是一成不变的每一代迭代结束后适应度好的个体会从加入者转化为发现者适应度差的发现者则会被降级。这种动态调整机制是SSA的核心优势所在。2.2 发现者的位置更新公式发现者在迭代过程中既需要扩大搜索范围又需要确保最后收敛到全局最优附近。它的位置更新包括两种模式根据预警值R2和安全阈值ST判断。当R2小于ST时意味着周围没有威胁发现者可以进行大范围搜索当R2大于等于ST时说明有捕食者接近所有麻雀需要迅速飞往安全区域。具体公式是这样的假设当前是第t次迭代第i只麻雀的第j维分量[ X_{i,j}^{t1} \begin{cases} X_{i,j}^{t} \cdot \exp\left(-\frac{i}{\alpha \cdot T_{max}}\right), R_2 ST \ X_{i,j}^{t} Q \cdot L, R_2 \geq ST \end{cases} ]其中(\alpha)是(0,1]之间的随机数Q是服从正态分布的随机数L是全1向量。前半部分体现了发现者在安全环境下进行精细搜索的过程后半部分是遇到威胁后跳出当前区域的避险行为。2.3 加入者和侦察者的更新策略加入者的行为是两个方向。适应度排名靠后的一半个体它们意识到自己搜索能力差会直接飞向当前全局最优位置附近继续搜索。如果排名相对靠前则会在当前最优位置附近随机扰动搜索[ X_{i,j}^{t1} \begin{cases} X_{best}^{t} |X_{i,j}^{t} - X_{best}^{t}| \cdot A^{} \cdot L, i n/2 \ X_{i,j}^{t} \exp\left(\frac{X_{worst}^{t} - X_{i,j}^{t}}{i^2}\right), i \leq n/2 \end{cases} ]侦察者的更新核心是利用全局最优位置和最差位置之间的差异结合自身适应度和全局最优适应度的关系来决定移动方向这里就不把公式全部罗列了。它的关键作用是防止整个种群在某个局部解周围停滞。这个机制放到路径规划里可以直观理解成侦察者负责探测“前方山谷是不是死胡同”一旦发现前方地形不适合继续飞行就会触发全种群散开重搜。2.4 标准SSA主循环结构标准SSA的主循环一般按照这样几步走初始化麻雀种群每条路径编码为一个个体计算每个个体的适应度记录全局最优和最差位置按适应度排序区分发现者与加入者更新发现者位置更新加入者位置随机抽取部分个体作为侦察者更新位置边界处理将超出地图范围的坐标拉回边界重新计算适应度更新全局最优判断是否达到最大迭代次数否则重复步骤2到8SSA本身不复杂参数也不算多。真正让路径规划结果千差万别的是适应度函数的构建方式和路径编码方式。这两个地方处理不好算法再先进也没有用。3. 路径规划问题到SSA的完整映射3.1 路径编码方式的选择与优化路径编码是把一条完整的路径表示成算法可以搜索的解这是整个方案设计的核心。常见思路是在起点和终点之间选取P个中间点每个点包含x、y、z三维坐标那么一条路径就是3P维向量。直接把所有中间点作为决策变量SSA搜索维度就是3P。但是我在实际调试中发现这种三维坐标全优化的编码方式效果很普通。因为x、y、z完全自由以后路径点很容易出现来回折返、绕路甚至倒退的现象优化效率很低。更好的做法是固定x方向坐标等间隔分布只优化y和z坐标。把起点和终点在x方向上的跨度均匀切分成P段每一段对应一个中间点这个中间点的x坐标是确定的SSA只需要搜索对应y和z两个维度。这样决策变量从3P降到2P搜索空间大幅缩小而且从结构上就保证了路径不会倒退。这种编码思路在很多比较落地的工程化路径规划代码里都在用。3.2 目标函数设计航程、威胁、高度与平滑的组合目标函数设计是路径规划的重头戏它直接决定了遗传算法、粒子群、SSA这类群体智能算法能不能收敛到一条真正可飞的路径。我的目标函数一般这样设计[ J w_1 \cdot L_{path} w_2 \cdot T_{threat} w_3 \cdot H_{height} w_4 \cdot S_{smooth} ]航程代价(L_{path})用相邻路径点之间欧氏距离之和来表示。威胁代价(T_{threat})的计算方式是统计路径上有多少个点落入了威胁区或者计算路径段与威胁区中心的距离落入威胁区范围内则累加一个固定惩罚值。高度代价(H_{height})是让无人机尽量贴近某一期望巡航高度高度偏差做平方惩罚。平滑代价(S_{smooth})用相邻三个路径点的夹角来衡量转角太大则惩罚。这里有一个重要的经验威胁代价不能和航程代价直接加在一起因为两者的数量级可能差得非常远。如果航程代价值大约在几十左右而威胁代价直接给5000适应度函数就会被威胁项主导SSA会优先保证躲避威胁其他一切代价都不考虑了。更好的做法是归一化处理或者给威胁代价设定一个阈值封顶值。很多初学者的结果不好看不是算法不行是目标函数权重搭配出了问题。3.3 约束条件与不可行解的处理路径规划是带约束的优化问题约束主要包括三类地形高度约束、威胁区约束、飞行高度边界约束。地形高度约束路径点的高度z不能低于该点对应地形高度。如果低于山峰高度直接认为路径撞山了。威胁区约束水平投影上任意路径点到威胁中心的距离不能小于威胁半径。飞行高度边界约束z值不能超过设定上限也不能低于零。在SSA框架下处理约束的通用方式是罚函数法。对违反约束的路径点在适应度函数里加惩罚项。但我个人建议对于纯禁飞区采用“硬性标志位”的思想一旦某个点进入威胁区该个体适应度直接赋一个极大值相当于宣告这条路径不可行。这种方法虽然粗暴但在路径规划里反而比软惩罚好用。因为软惩罚虽然让路径慢慢绕开威胁区但在迭代早期会有一堆个体在威胁区边缘“疯狂试探”浪费迭代次数。3.4 路径平滑与可飞性判断SSA直接输出的是离散路径点序列这些点用折线连接虽然也能看但无人机飞行讲究的是平滑转弯。做完路径寻优之后还需要对离散点做平滑处理。通常可以用三次样条插值或者用B样条曲线拟合路径点。三次样条插值的优点是所有路径点都会被曲线穿过飞行误差小缺点是如果曲线被插得太深可能在某些局部位置下探到山峰高度以下。所以插值完成以后还需要重新检查插值后路径上的每一个点是否满足地形高度约束如果不满足就需要加大惩罚系数重新运行或者在三维空间里对曲线做垂直方向上移。就我做的项目来看直接对SSA输出的路径点进行B样条拟合的效果更好B样条具有局部支撑性可以用来避让局部障碍区域。不过B样条拟合会出现曲线不穿过原始路径点的情况需要控制拟合误差。4. Matlab实现的关键环节与代码细节4.1 SSA主程序的Matlab实现框架如果你手头已经有一套Matlab代码核心结构通常是这样的% 参数初始化 SearchAgents_no 50; % 种群大小 Max_iteration 200; % 最大迭代次数 dim 2 * P; % 决策变量维度P个中间点每个点优化y和z lb [zeros(1, P), ones(1, P) * z_min]; ub [ones(1, P) * map_y_max, ones(1, P) * z_max]; % 初始化种群 X initialization(SearchAgents_no, dim, ub, lb); % 计算初始适应度 for i 1:SearchAgents_no Fitness(i) CalFitness(X(i, :)); end初始化函数我一般用混沌映射做初始化取代纯随机生成。标准的随机初始化在三维路径规划这种大规模搜索空间里往往覆盖不均匀混沌映射可以让初始解更均匀地分布在地图空间里。这里建议用Logistic混沌映射或者Tent混沌映射代码实现不复杂效果提升明显。适应度函数(CalFitness)接收一条路径的y、z编码向量重建出完整的路径点序列然后依次计算航程、威胁、高度和平滑代价。4.2 适应度函数的设计示例适应度函数内部的核心逻辑可以分为三步。第一步把决策变量解码成路径点坐标第二步遍历每个路径点判断是否进入威胁区或者低于地形高度第三步累加各项代价并加权求和。伪代码结构如下function fitness CalFitness(yz) global P start_point target_point threats terrain_z; y yz(1:P); z yz(P1:2*P); x linspace(start_point(1), target_point(1), P2); path zeros(P2, 3); path(1, :) start_point; path(end, :) target_point; path(2:end-1, 1) x(2:end-1); path(2:end-1, 2) y; path(2:end-1, 3) z; % 航程代价 length_cost sum(sqrt(sum((diff(path)).^2, 2))); % 威胁代价 threat_cost 0; for i 1:P2 for j 1:size(threats, 1) dist_h norm(path(i, 1:2) - threats(j, 1:2)); if dist_h threats(j, 3) threat_cost threat_cost 500; % 硬惩罚 end end end % 高度代价 height_cost sum(abs(path(:, 3) - target_altitude)); % 平滑代价 smooth_cost 0; for i 2:P1 vec1 path(i, :) - path(i-1, :); vec2 path(i1, :) - path(i, :); cos_angle dot(vec1, vec2) / (norm(vec1) * norm(vec2) eps); smooth_cost smooth_cost max(0, cos_angle); end % 地形碰撞惩罚 terrain_cost 0; for i 1:P2 terrain_h interp2(X_map, Y_map, Z_map, path(i, 1), path(i, 2)); if path(i, 3) terrain_h terrain_cost terrain_cost 1000; end end fitness w1 * length_cost w2 * threat_cost w3 * height_cost w4 * smooth_cost terrain_cost; end4.3 主循环迭代更新的关键操作SSA主循环在更新完发现者、加入者和侦察者之后必须对越界的变量做处理。这一步很容易被忽略。路径规划问题里y、z变量都有边界如果麻雀个体飞到了边界之外需要把它拉回边界内。常用的方式有越界重置和边界吸收。边界吸收的收敛速度更快但容易出现大量个体集中在边界上的情况越界重置可以维持多样性但收敛慢。我在路径规划里更倾向于使用边界吸收加随机扰动的组合方式。还有一个重要细节是侦察者的比例。标准SSA中侦察者比例比较小但在路径规划这种高维优化问题中我建议适当提高侦察者比例到15%左右。增加侦察者能够更频繁地把陷入局部收敛的个体“打散”代价是收敛速度下降。如果你跑出来的路径总是绕远路且长期稳定不变可以试试提高侦察者比例。4.4 参数配置建议一组我在多山峰场景下实测比较稳的参数搭配可以给到大家参考种群规模50最大迭代200发现者比例0.2侦察者比例0.1到0.15安全阈值ST0.8路径中间点数量P8到12。地图范围100乘100最大飞行高度设定为40期望巡航高度在15左右。权重方面航程权重0.4威胁权重0.3高度权重0.2平滑权重0.1。这个配置在单次运行中可能不是最优的比如你想得到更平滑的轨迹可以增加平滑权重到0.2代价是路径的航程会略微增加你要是更看重安全就把威胁权重调高。但要注意权重总和必须归一化不然整体数量级会漂移后面你很难判断某个改动到底是改善了目标还是改变了数量级。5. 实操中的常见问题与调试经验5.1 路径点太多导致维度爆炸初学者最容易犯的一个错误就是把中间路径点设得特别多比如设30个点维度直接到60。维度越高SSA搜索空间指数级增长收敛速度急剧下降最后得到的路径往往是一团乱线。我之前遇到过一个朋友他把路径点设成20个跑出来的结果完全不像一条路径很多中间点东拐西拐。后来我让他把路径点减到8个先用SSA找粗路径再用样条插值加密问题马上解决了。路径点数量够用就行精度交给平滑处理这个思路在工程上非常关键。5.2 威胁区惩罚太轻或太重威胁区惩罚太轻SSA会觉得穿越威胁区更省事结果路径直接穿心而过惩罚太重整个适应度函数会被威胁代价主导路径为了绕开一个威胁区可能绕出很夸张的远路。我的调试建议是先跑一次基础实验统计一下所有个体在不考虑威胁代价时的航程平均值是多少然后把威胁代价设置成这个平均航程的一半到两倍之间。这样既能保证威胁区被避开又不会让路径过度绕路。5.3 多山峰地形的局部极值问题多山峰地形的适应度函数表面非常不平滑。SSA虽然比其他群体智能算法能更好地跳出局部极值但在山峰数量比较多的情况下依然可能陷入局部解。表现为每次运行结果差异不大但是所有路径都贴着某座山峰绕看起来并不理想。此时可以采取三种改进方案。第一在初始化阶段引入反向学习生成反向种群然后从中选出适应度好的个体第二在每轮迭代结束以后对全局最优个体增加一次随机扰动重搜第三把侦察者更新公式改成基于最优位置的莱维飞行扰动增加跳跃能力。如果你目的是做对比实验强烈建议把改进版和标准版的收敛曲线画在一起这样视觉上的提升会更明显。5.4 适应度函数效率太低Matlab的循环计算本来就比较慢如果你的适应度函数里嵌套了地形插值和威胁区判断每次评估可能要花好几毫秒。SSA每轮迭代要计算几十个个体的适应度乘以200轮迭代整体运行时间就比较可观。优化方式有两个。一个是把地形高度数据预先生成好并保存成矩阵避免每次插值而是通过取整索引直接读矩阵另一个是路径平滑代价可以采用向量化计算减少循环。实测下来这个方法能让整体运行时间缩短一半以上。5.5 收敛曲线不下降是什么原因如果你的收敛曲线从一开始就不下降基本可以判断是适应度函数计算有bug最典型的是威胁区坐标和地形坐标的坐标系混了。比如地形x范围是0到100但威胁区中心设置成了几百那所有路径都不可能进入威胁区算法其实是在无威胁环境下搜索路径。还有一种情况是初始种群全部生成为不可行解适应度都相同算法没法区分好坏导致所有更新方向失效。遇到收敛曲线是一条直线的时候不要急着调参先单独把几条初始路径画出来看看是否合理再检查每个代价项的输出值数量级是否正常。6. 扩展思路与我的个人心得这套SSA多山峰威胁区三维路径规方案做完以后还可以往两个方向扩展。第一个方向是动态威胁区让威胁区中心随时间或迭代次数移动算法处理起来更复杂也更接近真实战场或物流场景第二个方向是无人机编队路径规划每条麻雀个体不只是代表一条路径而是代表整个编队的多条路径组合维度上升更快这时候标准SSA就不够用了需要引入协同进化或分解协调策略。我个人做了这么多组实验之后的感受是SSA真正难的不是算法实现而是目标函数怎么构建、维度怎么压缩、约束怎么处理。群体智能算法本身原理并不复杂它更像是一个搜索框架真正决定结果上限的是你如何把实际问题映射到这个框架里。路径规划是一个非常适合检验这个映射能力的问题因为它可视化程度高、约束明确、评判标准直观。如果有朋友刚开始接触这个方向我的建议是先拿一个简单的双峰地形跑通整个流程把目标函数的每一个代价项量级都打印出来仔细看看再逐步改成复杂地形和威胁区。这套流程跑顺了后面无论是换算法还是换场景要调整的都只是参数和约束条件而整个框架的架构可以一直沿用下去。
阅读完成 · 觉得有帮助？
