搞机器人导航和传感器布点的人几乎都会撞上两个绕不开的术语路径规划和传感器覆盖而解决它们最常见的武器就是智能优化算法。路径规划听上去简单无非是从 A 点到 B 点找一条路但真把动态障碍、车辆运动学、多机协同叠进来难度立刻翻倍。传感器覆盖也容易被人低估摄像头和雷达怎么摆、怎么走才能既没有盲区又不浪费资源同样是个硬骨头。我做了几年相关项目后越来越确信这两类问题在数学上其实是同一副面孔——都是在一个巨大的可行解空间里找一个让目标函数最优的组合方案。面对这种没有梯度、不连续、还动辄几十个变量的优化问题智能优化算法几乎是绕不开的工具。这篇文章就围绕这两个问题从建模思路、算法选型、实操案例到踩坑经验把东西讲透。适合正在做机器人导航、无人机巡检、AGV调度、传感器网络部署或者单纯想搞清楚智能优化算法怎么落地的朋友。1. 先把问题说清楚为什么路径规划和传感器覆盖是同一类难题1.1 从使用场景到数学描述路径规划的输出是一条可执行轨迹输入是地图、起点终点、障碍物和车辆约束。传感器覆盖的输出是传感器位置或者移动设备的工作路径输入是监控区域、感知半径、数量限制和连通性要求。表面看完全不同但把两个问题写成优化模型骨架几乎一模一样。路径规划可以抽象成决策变量路径点序列或连续的控制输入序列目标函数路径总长度最短、能耗最小、时间最短、或者多个指标的加权和约束条件不能穿过障碍物、满足最大转弯角、满足加速度限制、不能超时、不能超航程等。传感器覆盖问题可以抽象成决策变量每个传感器的坐标、朝向、工作状态或者移动传感器在不同时刻的位置目标函数覆盖率最大、覆盖冗余最小、网络连通性最强、覆盖均匀性最好约束条件传感器数量固定、部署位置有禁区、感知半径有限、供电能力有限等。一旦写成这种形式解法和工具就通用了。路径规划里的 A*、RRT 再牛也解决不了多目标、多约束、连续空间的组合优化传感器覆盖里的贪心布局再简单遇到不规则区域和动态负载时也会失灵。而智能优化算法不要求目标函数可导不要求凸性只要你能把解编码成一个“个体”或者“粒子”就能塞进遗传算法、粒子群、蚁群这些框架里去折腾。1.2 经典方法在哪里掉链子看过太多人一上来就纠结“A* 是不是最优的”其实在简单静态栅格里 A* 确实好用它保证启发式搜索的最优性栅格粒度合适时效率也够。可一旦环境变成连续空间、路径点要求满足车辆运动学、目标不止一个、或者在动态障碍里实时重规划A* 就力不从心了。原因是 A* 依赖离散的搜索空间网格细了爆炸粗了路径不现实而且它只服务单一目标。RRT 和 RRT* 能处理连续空间但随机采样出来的路径往往很粗糙拐弯多、不满足非完整约束还需要大量后处理。传感器覆盖问题更直接传统几何扫描摆放法在规则矩形区域里能算但遇到带遮挡的室内环境、异构传感器、多优先级覆盖区域就只能靠人工经验和反复试错。智能优化算法适合的正是这种“没有解析解、精确算法求不动”的场景。它用种群迭代逼近最优虽然不保证找到全局最优但工程上足够好。所谓“足够好”就是能在几秒到几分钟内给出比人工设计好得多、且稳定可复现的方案。因此后面所有内容都围绕这个前提展开。2. 算法池子怎么选遗传、粒子群、蚁群和它们的变体2.1 常用智能优化算法的特性对比智能优化算法不是只有一种。做路径规划和传感器覆盖时最常用的有这几类我按自己的使用感受给它们做个画像。算法优点缺点适用场景遗传算法 GA全局搜索强能处理离散和连续混合编码适合组合优化参数多、收敛慢、算力消耗大路径点序列优化、任务分配、多机协同覆盖粒子群 PSO收敛快、实现简单、连续优化效果好容易早熟离散编码不如 GA 自然传感器坐标部署、无人机航迹参数优化蚁群 ACO对 TSP 类路径顺序问题有天然优势收敛慢、参数敏感、需要图结构遍历顺序优化、多目标点访问顺序模拟退火 SA实现简单能跳出局部最优单点搜索效果依赖降温策略小规模覆盖布局、后处理平滑差分进化 DE连续优化效果稳变异策略丰富对离散问题需要额外映射连续参数优化、传感器半径和角度优化实际项目里我不会只用一种。比如无人机多目标点路径规划先用聚类给每架无人机分配任务再用蚁群优化访问顺序最后用遗传算法调整每个路径点的精确坐标三个算法各管一段。很多人喜欢追求新算法像什么鲸鱼算法、蜜獾算法、飞蛾扑火算法说实话大部分是已有算法的变体新瓶装旧酒。我见过不少论文在基准测试上吹得天花乱坠一上真实场景就翻车。与其追新不如把 GA、PSO、ACO 这三个基本功吃透再按问题结构去改算子和编码效果远比换一个花哨算法实在。2.2 怎么组合和改进才不会变成拍脑袋智能优化算法的核心不是算法框架本身而是两件事解的编码方式和适应度函数设计。编码方式决定搜索空间的形状适应度函数决定搜索方向。如果这两件没想清楚用什么算法都是白搭。先说编码。路径规划里常见的编码有栅格序号编码、坐标点序列编码、B样条控制点编码、速度指令序列编码。我一般建议用 B样条控制点编码路径因为样条天然平滑随机扰动控制点之后生成的路径仍然可执行不需要额外修复。相比之下如果用栅格序号编码交叉变异之后很可能产生不连通路径还得写修复算子烦得要命。传感器覆盖则简单些一个粒子就是一个数组里面顺序存放每个传感器的 x、y、朝向角、感知半径视觉上非常直观。适应度函数也有讲究。路径规划里最直接的适应度是路径长度加碰撞惩罚但只加一个惩罚系数很容易被优化器钻空子。比如惩罚系数太大算法会优先绕远路躲避一切潜在碰撞结果路径长到离谱惩罚系数太小又会出现贴着障碍墙走的危险路线。我的经验是碰撞惩罚要分段设计离障碍物越近惩罚增长速度越快而不是线性增加。传感器覆盖里的适应度更要注意优先级重点区域权重是普通区域的几十倍否则算法必然先顾着最大化全域覆盖率把角落里的关键摄像头漏掉。改进算法也不是无脑杂交。我比较认可的思路是结合问题先验。比如基于 A* 改进路径规划先用 A* 搜出一条基础路径再用遗传算法去优化控制点进一步压缩长度、减少转折而不是让 GA 从零开始在连续空间里裸搜。动态避障小车路径规划也是同理全局规划负责大方向局部算法负责实时反应智能优化可以用在全局轨迹的平滑和局部参数的自适应上。先有结构再有优化这才是工程里靠谱的做法。3. 路径规划中的实战从 A* 到动态避障再到无人机三维航迹3.1 基于 A* 的改进思路让全局路径从“能走”变成“好走”很多路径规划入门者从 A* 开始学但做产品时 A* 直接输出的路径很难用。栅格地图下的路径是由一格一格拼起来的存在大量 45 度、90 度折线AGV 或者小车按这种路径走每到一个拐点都得减速停顿效率很低。我的常规处理流程是三条A* 搜索得到粗路径后用 Douglas-Peucker 算法抽稀去掉多余的转折点只保留必要拐点再用三次 B样条曲线对转折点做平滑保证曲率连续最后用遗传算法优化控制点位置在路径长度和障碍距离之间取平衡。这里遗传算法的适应度我通常这样设计路径长度所有路径段的长度之和碰撞安全检测路径与障碍物的最小距离若小于安全阈值则施加指数惩罚平滑度计算相邻路径段之间的夹角变化夹角变化越大惩罚越大。用这种“A* 初解 GA 精炼”的组合路径长度通常能比原始 A* 缩短 10%-15%转向次数减少一半以上。而且由于 GA 是在 A* 提供的优质解附近搜索收敛速度快很多一般二三十代就稳定了。相比之下如果让 GA 从头搜整个地图跑几百代都不一定找到一条可行路径因为可行解在连续空间里占比太小。3.2 动态避障小车路径规划全局规划与局部优化的配合动态环境中障碍物位置实时变化全局规划不能频繁重跑否则卡顿和抖动会把人逼疯。业内最常见的方案是 ROS 里 move_base 框架global_planner 负责全局路径local_planner 负责局部避障。局部避障里 DWA 是经典中的经典核心思想是在速度空间采样然后对每组速度模拟出一条轨迹用评价函数选最优。DWA 看起来简单但它的采样范围是离散网格步长和采样数量是固定的遇到拥挤场景容易陷入局部最小值。我在 AGV 项目里做过一个改进把 DWA 的固定采样改成粒子群优化在速度空间里搜索。每帧控制周期内用上一帧优化结果作为初始粒子群在当前速度约束范围内迭代十来代适应度函数包括障碍距离、目标朝向、速度大小和加速度限制。实测下来平均绕障时间比传统 DWA 短一些更重要的是避障轨迹更平滑不会出现反复横摆的情况。当然代价是计算量上升。小车控制器如果是普通工业 PC 还好要是嵌入式平台就得谨慎。我的建议是粒子数控制在 20 到 30迭代不超过 15 代评估轨迹时用简化运动模型不要在这么短的控制周期里去求精确碰撞检测。动态避障本来就是一个“有限感知、有限计算、有限反应”的问题优化算法只是帮你把有限资源用到极致。3.3 无人机与泊车场景高维约束下怎么求解无人机路径规划算法比地面小车复杂一个维度因为加入了高度变化、爬升角限制、转弯半径限制、最大航程限制甚至还要考虑禁飞区和气流。三维空间搜索比二维难得多传统 A* 在三维栅格里的节点数经常上亿算力根本顶不住。于是很多项目转向智能优化直接把一条三维航迹参数化为一组控制点控制点坐标就是优化变量粒子群或者差分进化都能跑。设计适应度时无人机航迹的约束要拆清楚航迹是否穿过障碍物碰撞惩罚相邻控制点之间的爬升角是否超过机体限制超限惩罚整条航迹总长度是否超过最大航程路径是否足够平滑要不要照顾到相机云台的稳定性。权重不要平均分配碰撞是硬约束建议使用大惩罚系数爬升角和航程属于软约束可以适当放宽。我之前做过一个巡查项目用 PSO 配合 B样条参数化在 500m×500m×200m 的空间里规划巡检航迹种群规模 60迭代 200 代跑一次约 8 秒结果比人工打点规划的路径短了差不多四分之一而且全部满足飞机动力学约束。泊车路径规划算法则是另一个极端。车辆在低速泊车时几乎只受运动学约束车不能侧移转弯半径有下限所以混合 A* 配合 Reeds-Shepp 曲线始终是主流。智能优化在泊车里的定位不是直接实时规划而是离线生成参考轨迹。比如针对特定车位类型用遗传算法优化轨迹的关键点目标函数是泊入误差最小、方向盘转角变化率最小。生成的参考轨迹存成地图线上再用 MPC 跟踪既满足实时性又保留了优化带来的舒适性。4. 传感器覆盖问题部署、k 覆盖与覆盖路径规划4.1 覆盖模型和评价指标传感器覆盖问题的第一步不是选算法而是定义什么是“被覆盖”。业内常用两类模型。栅格覆盖模型把目标区域离散成均匀网格每个网格要么被覆盖、要么没被覆盖简单直观适合摄像头、红外传感器。概率覆盖模型则考虑距离和遮挡的影响覆盖概率随距离衰减适合无线传感器节点。有了覆盖模型还需要指标。覆盖率是最基本的就是被覆盖面积除以总面积。但只看覆盖率会出问题因为区域边缘的传感器经常出现大面积重叠覆盖冗余度很高浪费资源。所以实际项目中我会引入三个一起看的指标覆盖率总覆盖面积占比冗余度每个覆盖点平均被几个传感器同时覆盖重要区域覆盖率重点区域单独计算不许打折。约束方面传感器数量、感知范围、安装高度、视线遮挡、无线网络连通性统统要写成罚函数加到适应度里。比如传感器之间距离太远信号连不上那就加连通性惩罚。这个处理方式和路径规划的约束处理完全一致所以熟悉一边另一边很快能上手。4.2 多传感器部署粒子群优化的标准用法传感器部署问题是粒子群算法最舒服的场景因为决策变量天然是一串连续坐标。举个例子一个 80m×60m 的仓库要布置 20 个摄像头每个摄像头的感知范围是一个半径为 8m 的扇形朝向可调。目标是覆盖率最高且重点货架区域覆盖率不低于 90%。每个粒子的位置是 60 维向量表示 20 个摄像头的 x、y、朝向角。适应度计算时把仓库地图网格化对每个网格点计算是否被任意摄像头覆盖加权求和得到覆盖率。重点区域权重设为 10普通区域设为 1然后减去重叠惩罚。粒子群参数我常用这些粒子数 100惯性权重从 0.9 线性降到 0.4学习因子 c1、c2 都取 1.5迭代次数 300。实际跑下来覆盖率从初始随机的 62% 提升到 91%重点区域覆盖从 74% 提升到 96%。关键技巧是覆盖率评估非常耗时如果地图网格分辨率设到 0.1m一次评估要计算几十万个点迭代 300 次根本受不住。我的经验是把网格分辨率设成传感器半径的五分之一到十分之一比如半径 8m 就用 1m 网格计算量降低上百倍覆盖率的误差却只有一两个百分点完全够用。4.3 覆盖路径规划把“走到哪里”变成“覆盖到位”传感器覆盖不止静态布点移动机器人、无人机巡检、扫地机器人还需要规划出一条路径让传感器沿路覆盖整个目标区域这叫覆盖路径规划。经典做法是牛耕式往复扫描或者螺旋式扩展但遇到复杂多边形和障碍物时直接扫描会漏掉大片区域。我的做法分两步。第一步用 Boustrophedon 单元分解算法把不规则区域切分成几个凸子区域第二步把子区域的遍历顺序看成一个 TSP 问题用蚁群算法或者遗传算法优化访问顺序。这里要特别说明区域之间的过渡路径也是成本不能只看子区域内部的覆盖长度。多无人机协同巡检时还要再加一层任务分配相当于“哪个飞机去哪些子区域”和“以什么顺序访问”两个问题一起解。这种问题用遗传算法分层编码非常合适第一层基因是子区域到无人机的分配第二层是每架无人机的访问顺序适应度函数就是总飞行时间加覆盖遗漏惩罚。喷漆路径规划本质上也是覆盖路径规划但多了一个工艺约束涂层要均匀不能厚一块薄一块。所以优化变量除了路径方向还有喷枪高度、移动速度、喷幅重叠度。稍微改一下适应度就能套用同一套框架。增材制造里的 BM 切片和路径规划软件也是一样填充路径要在空驶距离短和热变形小之间做权衡说白了还是智能优化能发挥价值的组合优化问题。5. 一个能跑的案例用遗传算法做多无人机任务区的覆盖路径规划5.1 问题建模与编码纸上谈兵讲再多不如动手跑一个仿真。我设计过这样一个案例大家可以照着复现一块 1000m×800m 的区域里面有 5 个障碍区要求 3 架无人机以最短总航程完成巡检。无人机从同一起点起飞各自负责若干个航点每架无人机最大航程 600m航点总数 45 个。这个问题其实由两部分组成把 45 个航点分配给 3 架无人机以及规划每架无人机的访问顺序。分别对应任务分配和 TSP用遗传算法一起优化会非常复杂所以我采用分层方法第一层用 k-means 按坐标把航点就近聚类成 3 组让每架无人机负责一组第二层对每组内的航点用遗传算法求解访问顺序适应度是飞行距离第三层如果某组超航程就把最远的航点调整到另一组再重新优化直到满足约束。这种方法不是全局最优但工程上非常稳定。遗传算法编码采用航点序号排列比如一组有 15 个航点个体就是 1 到 15 的一个排列。适应度是顺序经过所有航点的总欧氏距离。交叉我用部分映射交叉变异用两点交换这样能保证每个个体始终是合法排列不需要修复算子。5.2 参数设置与结果分析我跑遗传算法时参数是这样设置的种群规模200迭代代数500交叉概率0.85变异概率0.1选择方式锦标赛选择锦标赛规模为 3。优化前我把每架无人机负责的航点按编号顺序飞总航程 1287m其中第二架超航程达到了 731m明显不可用。经过遗传算法优化最终总航程降到 934m平均每架约 311m远小于 600m 限制。更重要的是第二架的航程被压缩到 352m钳制在了约束以内。结果可以通过收敛曲线来分析前 100 代适应度下降非常快后面趋于平缓从 250 代开始基本没有大幅变化。这说明算法在 250 代左右已经收敛。当然遗传算法有随机性我建议每次跑至少 10 个随机种子记录最优值、平均值和最差值不要只看一次结果。5.3 仿真中用到的核心伪代码我把核心逻辑整理成下面这段伪代码方便大家对着理解def fitness(chromosome, points, uavs, max_range): clusters decode_chromosome(chromosome) total_length 0 max_len 0 for uav in uavs: route_points [points[i] for i in clusters[uav]] route_length solve_tsp(route_points) total_length route_length max_len max(max_len, route_length) penalty 0 if max_len max_range: penalty 1000 * (max_len - max_range) return total_length penalty把每个航点的归属编号拼起来就是染色体解码后就能得到每架无人机的航点集合。这里我用了一个贪心 TSP 求解器来快速评估适应度真正要精细结果时也可以再用一次蚁群算法。因为适应度评估要跑很多遍TSP 求解不能太慢贪心加 2-opt 局部搜索是个不错的折中。5.4 这个案例扩展出去的更多玩法这个案例的框架直接可以扩展到更多场景。比如把“航点”换成“区域”每架无人机负责一片区域的覆盖路径规划就能变成多无人机面积覆盖。把“无人机”换成“救援车辆”目标函数从总航程换成救援时间最小化就是救援路径规划算法的一种雏形。把“航点”换成“需要喷漆的面片”加上喷幅宽度和速度约束就是喷漆路径规划。我甚至用类似的编码处理过开源增材制造里的切片路径排序问题。3D 打印的每一层切片都有大量线段打印头如果按顺序依次走空驶距离很长。把它看成 TSP 后用遗传算法优化线段的访问顺序可以减少空驶距离提升打印效率。本质上还是同一套思路只是目标函数换了一下。6. 工程落地中的常见问题和我的经验6.1 实时性不足怎么办智能优化算法最被诟病的就是计算慢。确实一个需要反复评估成百上千个体的问题很难做到每一帧毫秒级响应。但我用过几个实用招数离线与在线分离。把难的任务放到离线阶段生成参数表或参考轨迹在线阶段只做轻量查询和跟踪热启动。上一帧优化结果直接作为下一帧初始种群粒子群尤其适合因为粒子在目标附近只需要小范围搜索粗粒度先跑。先用低分辨率地图、简化模型求一个大概区域再用精细模型局部细化限制种群和迭代数。实时规划里种群 20、迭代 10 代可能比种群 200、迭代 100 代更有用因为前者一帧内算得完后者根本来不及。动态避障小车路径规划里我用过热启动 PSO效果比冷启动好很多因为小车运动是连续的上一时刻的最优解大概率离当前最优解不远。6.2 评价函数设计比算法本身更重要我不敢说这是绝对真理但从经验看大部分失败项目不是算法不行而是评价函数写歪了。评价函数没写对再牛的算法也只能朝着错误的方向疯狂迭代。评价函数设计要特别注意几点约束必须可量化。碰撞、超航程、断连这些问题不能靠“差不多”要用连续函数表达最好还能显示出危险程度惩罚要分梯度。贴近障碍和离障碍五米是两码事惩罚曲线要陡峭才能引导算法远离危险区域指标之间要归一化。路径长度和覆盖率数值范围差很多不加权直接相加小数被大数淹没优化等于白做权重不是一次定死的。先跑小规模样例观察行为再调整权重别一上来就追求全局最优。我在传感器部署里吃过亏。刚开始适应度用覆盖率减去重叠率但重叠率的数值范围远小于覆盖率导致优化器完全不关心重叠。后来我把重叠率乘以 5 再加进目标才看到明显改善。6.3 关于稳定性、复现和验收智能优化算法随机性强同一段代码跑两次结果可能不同。这在工程项目里很麻烦因为现场验收要求你证明方案有效而不是说“概率有效”。我的做法是固定随机种子。先在仿真里确定一个表现良好的种子作为默认配置多次试验记录统计量。每次调参后跑 20 次记录最优、平均和最差三个指标都acceptable才允许进下一步加后处理。对优化结果做平滑和约束校验确保输出轨迹或部署方案直接能下发执行留人工检查接口。毕竟智能优化是辅助决策最后加一道人工确认环节可以让项目少背很多锅。印象最深的是一个传感器布点项目算法给出的方案覆盖率高但有两个摄像头被柱子完全挡住适应度里因为我没有建模遮挡关系所以算法觉得没问题。后来我在覆盖检测里加了视线遮挡判断重新优化后布点方案才真正能落地。所以不管算法多聪明物理模型的真实性永远是底线。我自己做下来最大的体会是智能优化算法不是银弹它更像一个放大器——你的建模和评价函数如果是对的它能放大出非常好的结果如果你对问题本身理解不到位它也会放大错误而且速度很快。真正值钱的能力是把工程问题翻译成优化问题的能力。能把路径规划和传感器覆盖背后的共同结构看透这套方法就能迁移到很多想象不到的领域。