全覆盖路径规划算法解析：往返式扫描与A*转移路径的工程实现

做机器人全覆盖路径规划最难的不是“怎么把每一块地方都走到”而是“怎么让机器人花最少的时间、走最短的路把整个空间扫干净”。无论是扫地机器人、割草机器人还是仓储盘点、无人机巡检只要涉及“自动扫一遍”就绕不开全覆盖路径规划Complete Coverage Path Planning, CCPP这个核心问题。这篇文章要讲的就是把两类经典思路做一次组合用“往返式”策略保证覆盖率用A*算法解决换行和绕障的转移路径。整个方案在Matlab里实现核心代码逻辑完整适合做毕设、课程设计也适合刚接触路径规划的开发者当作第一个完整项目来练手。先说结论这套方案真正解决的是“牛耕式覆盖遇到障碍物之后怎么办”的问题。传统往返式也叫弓字形、boustrophedon扫描在无障碍的时候非常高效但环境一复杂每个转弯和换行点都有可能是不可达的硬走会撞墙随机选点又会造成大量重复覆盖。把A加进来本质上是给往返式策略装了一个“摆渡导航器”每次从当前行终点前往下一行起点时都让A算一条最短安全路线而不是简单直线走。这样既保留了往返式覆盖的规整性又避免了局部规划的盲目性。下面我把这个问题从环境建模到Matlab实现逐步讲透。1. 内容整体设计与思路拆解1.1 全覆盖路径规划到底难在哪先想一个最简单的情况一块没有任何障碍的矩形场地机器人从左上角出发要怎么全覆盖答案大家都懂从左往右走完一行下来再从右往左走下一行依次往复所有区域都被覆盖路径也足够短。这就是典型的往返式覆盖也是目前工业界扫地机器人最常用的底层策略。但真实的场景从来不是一块白板。房间里有桌子椅子、草坪里有树和花坛、仓库里有货架这些障碍物把原本规整的区域切割成若干个不规则的连通块。这时问题就来了第一行走到一半碰到障碍你必须绕过它绕过去之后要不要继续原方向下一行的起点选在哪里如果直接从当前点硬拉一条线到下一行起点很可能穿过障碍物或者墙壁。全覆盖策略负责的是“按什么顺序扫每一块区域”但把“怎么从一个区域安全转移到另一个区域”的问题留给了路径搜索。这就解释了为什么要引入A算法。A是网格地图上最经典、也最适合做全局最短路径搜索的算法它在栅格化的环境里可以稳定地求出一条从起点到终点的无碰撞最短路径。在往返式覆盖的框架下A*负责的是“行间转移”从当前已覆盖行的终点走到下一行待覆盖的起始点用一条最优曲线把两段弓字覆盖衔接起来。1.2 为什么选网格环境加Matlab网格栅格环境本身是路径规划里最常用的离散化方式把连续空间切成一个个方格每个格子要么是自由空间要么是障碍物这样无论是覆盖状态的记录还是A的节点搜索都变得非常直观。用Matlab做这个方案有几个好处首先是矩阵操作天然适配地图数据一个二维0-1矩阵就是完整的地图不用额外写复杂的数据结构其次是Matlab的绘图功能让路径可视化非常轻松每一帧机器人的位置、每个已覆盖格子的状态都能直观画出来最后是代码可读性好A虽然逻辑不复杂但在别的语言里要手写优先队列一类的结构在Matlab里用结构体数组加排序也能轻松凑合出来更适合教学和验证算法。当然Matlab的代码效率不算高如果地图规模很大比如几千乘几千的栅格纯Matlab跑A*会明显变慢。但作为研究和验证用途这个组合够用且出图漂亮这也是我为什么最终选择在Matlab里实现整套逻辑。1.3 整体方案的结构设计整个程序可以拆成三个模块。第一个是环境构建模块负责生成地图、设置障碍物、做边界膨胀处理第二个是全覆盖策略模块实现往返式扫描逐行推进维护一个“已覆盖”标记矩阵第三个是A转移模块在需要换行或避障时调用A搜索计算当前点和目标点之间的最短路径。三个模块之间通过一个主循环串联覆盖策略发现下一个覆盖点不可直达时就发起一次A规划A返回一条路径机器人沿着路径走到目标点然后继续往返式扫描。直到所有可达的格子全部被覆盖程序结束并输出统计指标比如覆盖率、路径总长度、重复覆盖面积。2. 网格环境的建模与预处理2.1 栅格地图的数据结构在Matlab里一张栅格地图就是一个二维逻辑矩阵我习惯用map(row, col)表示第row行第col列的格子值为0代表自由空间值为1代表障碍物。这里的“行”对应地图的纵向“列”对应横向和坐标系的x-y轴有对应关系但要注意区分。举一个最简单的例子一张10x10的地图中间放一个3x3的方形障碍物代码大概是这样的map zeros(10, 10); map(4:6, 4:6) 1;这就能生成一张带正方块障碍的地图。实际的复杂地图可以从图片二值化、坐标点列表或者随机生成算法得到但最终都要转成这种0-1矩阵因为后面所有操作——覆盖检测、A*搜索——都只对这个矩阵做运算。还有一个容易忽略的点是坐标系方向。图像显示时第1行在顶部行号增大向下但在路径规划的习惯里我们通常希望y轴向上。虽说这不影响算法本身但在显示轨迹和计算实际距离时要保持一致否则画出来的路径会上下颠倒。我一般在代码开头就统一用“行号从上到下递增”作为坐标系统所有格子的位置用(row, col)表示避免转换来转换去。2.2 障碍物膨胀处理地图建好之后第一件事不是规划而是膨胀。为什么因为栅格地图中的每个格子通常代表机器人中心点可到达的位置如果机器人本身有尺寸它的外轮廓就不能进入障碍物周围的格子。最简单也最稳妥的处理方式是把所有障碍物格子向外扩张机器人工作半径对应的格子数。膨胀操作可以用形态学膨胀实现也可以用双重循环实现。Matlab里直接用imdilate最方便但考虑到这是路径规划项目我建议自己写一个简单的膨胀函数逻辑更透明function map_inflated inflate_map(map, radius) [rows, cols] size(map); map_inflated map; [obs_r, obs_c] find(map 1); for k 1:length(obs_r) r_min max(1, obs_r(k)-radius); r_max min(rows, obs_r(k)radius); c_min max(1, obs_c(k)-radius); c_max min(cols, obs_c(k)radius); map_inflated(r_min:r_max, c_min:c_max) 1; end endradius表示机器人半径对应的格子数量。假如栅格分辨率是0.1米/格机器人半径是0.2米那radius就是2。膨胀完成后原本贴着障碍物的格子会被标记为不可通行A*搜索时就不会规划出擦边甚至穿墙的路径。这里要提醒一句膨胀不是越狠越好。半径设得太大会把狭窄通道完全堵死导致原本可以通过的区域变成不可达设得太小又有碰撞风险。实际使用时要根据机器人的真实尺寸和地图分辨率权衡并且膨胀后的地图应该单独可视化一眼确认没有把关键通道封死。2.3 地图中的起点与终点设置全覆盖路径规划里起点是用户指定的终点理论上是最后一个被覆盖的格子由算法输出。起点如果选在障碍物上程序第一步就会报错所以初始化时一定要检查map(start_row, start_col) 0。目标点不是固定的而是在运行过程中动态生成每次往返式扫描遇到障碍或一行结束就要选一个新的“待覆盖起始点”这个点可能在地图任意位置。因此A*模块要支持“每次动态计算目标点”不能把终点写死。2.4 已覆盖状态的记录方式除了地图矩阵还需要一个同样尺寸的矩阵来记录覆盖进度。我通常叫它covered初始化全0当机器人经过某个格子或者A*转移路径经过某个格子时就把相应的位置改成1。这个矩阵有三个用途一是判断全覆盖是否完成covered0且map0的格子是否还存在二是计算覆盖率已覆盖自由格子数/总自由格子数三是让往返式扫描知道哪些行还需要扫。还有一个进阶用法在A的代价值里对已覆盖的格子加上额外的代价系数。比如自由格子代价是1已覆盖格子代价是5这样A在规划转移路径时会倾向于走未覆盖区域从而在转移过程中顺便完成部分覆盖减少重复路径。这个技巧在后面会再讲属于很实用的小优化。3. 往返式全覆盖的核心逻辑3.1 牛耕式扫描的基本流程往返式全覆盖思路很简单从上往下逐行扫描机器人沿着当前行一直走到地图边界或者遇到障碍物然后跨到相邻的下一行反向继续走。因为路径像牛耕地时来回犁田的样子所以叫牛耕式boustrophedon路径。在无任何障碍的理想矩形地图上核心伪代码是current_pos start current_dir 1 % 1表示向右-1表示向左 for row start_row : rows if row 所在行存在未覆盖自由格子: 从 current_pos 沿 current_dir 方向扫过整行 到达行末端后row1current_dir 取反 end其中“扫过整行”的含义是从当前格逐列移动把每一格标记为已覆盖直到遇到障碍物或者地图边界。下一行起点自然就是上一步停下来的那个点。这种策略的优点是路径规整、覆盖率100%、实现简单缺点是遇到复杂障碍时完全不够用——所以需要A*介入。3.2 遇到障碍物时的换行策略往返式扫描在遇到障碍物时有几种处理方式。最简单的一种是“当前行扫到障碍前就停直接换到相邻下一行”。例如机器人从左上角出发向右扫第3行第5列是障碍那就走到第3行第4列停下然后尝试转移到第4行的某个未覆盖起点。这里的关键问题是第4行的这个“未覆盖起点”怎么选我常用的策略是选择机器人当前所在列附近、第4行上从当前列到行边界方向第一个未覆盖的自由格子。如果当前列旁的格子是障碍物或者已经被覆盖那就往两边搜索最近的一个可行点。找到这个点之后不一定能直线走过去这时就要调用A*规划转移路径。选择相邻行作为下一行扫描好处是局部性强换行距离短坏处是障碍物较多时可能下一行根本与当前行连通需要绕很远才能到达。如果出现这种情况可以放宽条件不只搜相邻行而是往下扫描若干行选择最近的包含未覆盖自由格子的行作为目标行。这种“最近未覆盖行”策略能显著降低转移路径长度。3.3 死区与凹形区域的覆盖顺序全覆盖路径规划里最让人头疼的是凹形障碍也就是C形或U形区域。机器人一旦从缺口进入凹槽内部覆盖完里面的区域后往往需要原路退出来这个“退出来”的动作本身会产生重复覆盖。往返式策略对凹形区域的处理方式是缺口处的行可能被障碍物断开需要多次换行来覆盖断开的片段。假设一个U形障碍物机器人先覆盖了左侧竖条然后进入凹槽内部覆盖横条最后需要绕到右侧竖条这个转移路径很可能要绕一个大圈。此时A*的价值就体现得很充分——它能找到一条从凹槽底部绕到右侧竖条的无碰撞路径虽然这条路径不可避免地会经过部分已覆盖区域但至少路径是安全的。如果希望进一步减少这类重复覆盖可以考虑“区域分解”的思路把地图按障碍物边界切分成多个子区域每个子区域内部独立做牛耕式覆盖子区域之间用A*连接。这个做法更接近当前学术界比较认可的牛耕式分解算法但实现复杂度会高不少。本文介绍的方案不引入区域分解但读者理解了之后可以自己往这个方向扩展。3.4 全覆盖完成判定的实现细节全覆盖完成的判定条件并不复杂遍历所有自由格子看是否所有格子都已经被标记为已覆盖。但实际运行中有一个细节容易踩坑——如果地图存在不可达区域也就是周围全是障碍物的孤岛机器人无论如何都不可能覆盖到这些格子程序会无限循环寻找下一个未覆盖点。我的处理方式是在主循环外先做一次连通域分析用bwlabel找出起点所在的连通区域只要求覆盖起点所在的连通区域内的所有自由格子。其他孤立区域自动视为不可达不计入覆盖率分母。这也是为什么在最终的统计指标里“覆盖率”是基于可达区域的而不是基于全图自由格子的这样指标才科学。4. A*算法在行间转移中的角色4.1 A*的基本原理回顾A算法本质上是Dijkstra算法的启发式优化版。在网格地图中每个格子是一个节点相邻格子之间有边相连。A对每个节点维护两个值g是从起点走到当前节点的实际代价h是当前节点到目标节点的估计代价启发函数总代价f g h。算法每次从待扩展列表OPEN表中取出f值最小的节点进行扩展直到扩展到目标节点或者OPEN表为空。由于h的引入A的搜索范围远比Dijkstra小只要启发函数满足一致性条件A求出的就是最短路径。在网格环境中节点扩展就是考察当前格子周围的邻居格子。如果只允许上下左右四个方向移动那邻居就是4个如果允许斜向移动邻居就是8个。启发函数的选择也要和移动方式匹配。四方向移动一般用曼哈顿距离八方向移动用切比雪夫距离或欧几里得距离这样估计代价才不过度偏离实际代价。4.2 为什么选择A*而不是Dijkstra或贪心算法有人会问行间转移规划用Dijkstra不行吗用贪心算法不行吗当然可以但各有各的问题。Dijkstra是A在启发函数h0时的特例它一定能找到最短路径但搜索范围是向四周均匀扩散的地图一大搜索的节点数非常多速度明显更慢。贪心算法只依据h选择节点搜索速度快但容易陷入局部死路只能找到次优甚至非最优路径。A正好在两者之间取得平衡——h给搜索提供方向性g保证已经走过的路不会绕远。在栅格地图这种离散空间里A*的搜索效率高、路径质量好、实现也不复杂所以它一直是网格路径规划的首选。我在这套覆盖方案里还会用到一个变体在计算g值时给已覆盖格子加上额外的代价。这样A*的转移路径就会更倾向于从尚未覆盖的区域穿过而不是直接重复已经扫过的路线。这个调整在代码实现上几乎不增加成本但对降低整体重复率帮助很大。4.3 邻域选择和移动代价网格中A*的移动代价设置要仔细。四邻域时的代价很简单上下左右走一步代价都是1。八邻域时斜向移动的代价是sqrt(2)也就是约1.414。如果你的机器人是全向型的八邻域更灵活路径更短如果机器人只能前后左右走那八邻域规划出来的斜线路径实际走不了会产生额外麻烦。对于全覆盖场景我倾向于使用八邻域因为覆盖环境中的机器人通常是可原地转向的全向底盘或者差速底盘也能走蛇形斜线。但有一个隐患八邻域搜索时如果只判断目标邻居不是障碍物就允许移动机器人可能从两个障碍物之间的对角缝里“挤”过去这在物理上是不成立的。解决办法是在斜向移动前加一个判断确认与当前格和目标格相邻的另外两个格子至少有一个是自由空间也就是不能“切角穿墙”。4.4 行间转移的完整算法流程将这部分的完整逻辑整理成一个清晰的流程。当往返式覆盖在某一行遇到障碍或者边界需要转移时执行以下步骤记录当前机器人的位置current_pos。从下一行开始向下查找找到第一个包含未覆盖自由格子的行。在该行中选择一个距离current_pos最近的未覆盖自由格子作为target_pos。调用A*搜索函数输入膨胀后地图、current_pos、target_pos。若A*返回路径成功则机器人依次沿路径上的每个格子走经过的格子标记为已覆盖若失败则继续向下搜索下一行。到达target_pos后更新扫描方向继续做往返式覆盖。这个流程保证了每次转移都是一次“有目的的规划”而不是拍脑袋选方向。A*被反复调用但每次搜索都是局部的小范围搜索整体计算开销是可接受的。顺带一提A*搜索过程中如果目标点本身不可达比如目标点被障碍物包围OPEN表耗尽后算法会返回失败。此时程序要具备回退能力也就是跳过这个目标点换下一个候选点重试。这个机制我在后面的常见问题部分还会提到。5. Matlab实现的关键细节与代码结构5.1 程序骨架与模块划分完整的Matlab工程建议按模块拆成几个文件方便调试也方便复用main.m主程序设定地图参数和起始点调用各模块结束后统计指标。generate_map.m生成环境地图支持手动设置障碍物和随机障碍物两种模式。inflate_map.m障碍物膨胀处理。astar.mA*路径搜索函数输入地图、起点、终点输出路径坐标数组。boustrophedon_cover.m往返式覆盖主循环内部调用astar完成转移。plot_map.m可视化地图、覆盖过程和最终路径。主程序首先建图、膨胀、初始化记录矩阵然后调用boustrophedon_cover最后输出结果。把流程拆开的好处是后面想换环境、换策略、换搜索算法只需要改对应模块不需要动整个程序。5.2 A*核心代码解析Matlab版本的A*可以不用优先队列写法比较朴素但逻辑清晰。核心代码如下function path astar(map, start, goal) [rows, cols] size(map); open struct(pos, [], g, [], h, [], f, [], parent, []); open(1).pos start; open(1).g 0; open(1).h heuristic(start, goal); open(1).f open(1).g open(1).h; open(1).parent []; closed false(rows, cols); came_from zeros(rows, cols, 2); g_score inf(rows, cols); g_score(start(1), start(2)) 0; while ~isempty(open) % 找到open列表中f值最小的节点 f_values [open.f]; [~, idx] min(f_values); current open(idx); open(idx) []; if isequal(current.pos, goal) path reconstruct_path(came_from, goal); return; end closed(current.pos(1), current.pos(2)) true; neighbors get_neighbors(current.pos, rows, cols); for k 1:size(neighbors, 1) npos neighbors(k, :); if closed(npos(1), npos(2)) || map(npos(1), npos(2)) 1 continue; end move_cost norm(npos - current.pos); tentative_g current.g move_cost; if tentative_g g_score(npos(1), npos(2)) g_score(npos(1), npos(2)) tentative_g; came_from(npos(1), npos(2), :) current.pos; h_val heuristic(npos, goal); open(end1) struct(pos, npos, g, tentative_g, ... h, h_val, f, tentative_g h_val, parent, current.pos); end end end path []; end这段代码有几个地方可以进一步优化。每次从open列表取出节点时用线性扫描这在节点少时没问题地图很大时建议换成二叉堆。came_from用三维数组记录父节点取用都方便但内存开销略大也可以改成两个二维数组分别存父节点行列号。另外get_neighbors里要加入对边界的判断避免索引越界。对于全覆盖场景我建议在A*里加入一个已覆盖代价的处理。在计算tentative_g时加上额外项if covered(npos(1), npos(2)) 1 tentative_g tentative_g 5; % 对已覆盖格子的额外惩罚 end这样算法会更倾向于穿越未覆盖区域转移路径顺带完成覆盖整体路径效率更高。5.3 往返式扫描主循环代码主循环的代码同样不长核心逻辑是把之前讲的策略用Matlab实现出来function [route, covered, stats] boustrophedon_cover(map, start) [rows, cols] size(map); covered false(rows, cols); covered(start(1), start(2)) true; route start; current_pos start; direction 1; % 1表示向右-1表示向左 max_iter rows * cols * 10; % 防止死循环的保险 for iter 1:max_iter % 先沿当前方向尽量覆盖当前行 [current_pos, covered] scan_row(current_pos, direction, map, covered); route [route; current_pos]; % 寻找下一行可覆盖起点 next_pos find_next_start(current_pos, direction, map, covered); if isempty(next_pos) break; % 所有可达区域已覆盖完毕 end % 判断是否可以直接走不能则用A* if is_straight_reachable(current_pos, next_pos, map) transfer_path [current_pos; next_pos]; else transfer_path astar(map, current_pos, next_pos); if isempty(transfer_path) % 下一步不可达继续寻找更远的行 continue; end end % 沿转移路径移动并标记覆盖 for k 2:size(transfer_path, 1) covered(transfer_path(k,1), transfer_path(k,2)) true; end route [route; transfer_path(2:end, :)]; current_pos next_pos; direction -direction; % 换行后反向扫描 end stats.covered_ratio sum(covered(:)) / sum(map(:) 0); stats.path_length sum(sqrt(sum(diff(route).^2, 2))); end代码里scan_row负责沿一行扫描直到障碍物或地图边界find_next_start向下寻找包含未覆盖自由格子的行并选一个起点。这两个函数的实现细节不长但要注意处理“当前行已经完全覆盖”和“所有行都已覆盖”两种情况。一个容易忽略的地方是在转移路径中更新covered时起点current_pos已经在上一轮标记过不能重复添加所以从transfer_path的第二行开始标记。如果疏忽了这点统计覆盖面积时会多算。5.4 可视化与运动过程展示Matlab做可视化的优势在这里体现得很明显。我习惯用三个图层叠加显示底图是障碍物用黑色填充覆盖区域用浅绿色填充随着扫描过程逐格刷绿机器人当前位置和运动轨迹用红色实线。画障碍物很简单imagesc(map)配个灰白黑colormap就行。覆盖区域的动态展示可以这样figure; hold on; for k 1:size(route, 1) covered(route(k,1), route(k,2)) true; if mod(k, 10) 1 clf; imagesc(map); colormap(gray); hold on; [row_c, col_c] find(covered); plot(col_c, row_c, ., Color, [0.5 0.9 0.5]); plot(route(1:k, 2), route(1:k, 1), r-, LineWidth, 1.5); plot(route(k, 2), route(k, 1), bo, MarkerSize, 6); drawnow; end end这里要注意坐标轴方向问题。imagesc默认第1行显示在顶部而plot的y轴默认向上直接叠加会导致图像上下颠倒。解决办法是在plot之后执行axis ij让y轴向下递增或者统一把地图和路径都转换到同一坐标系再画。这个问题我第一次跑代码时折腾了好一会儿提醒大家提前处理。5.5 指标统计与结果评估程序跑完后要有几项指标来衡量路径规划的效果覆盖率已覆盖自由格子数 / 可达自由格子总数。设计良好的全覆盖算法这个值应达到100%。路径总长度把路线数组相邻两点距离累加单位是格子数乘以栅格分辨率。重复覆盖率路径经过的格子里被访问次数大于1的格子数占总覆盖格子的比例。这个值越低说明路径越高效。转移次数调用A*的次数。转移次数越少说明覆盖策略本身越连贯规划越高效。计算重复覆盖率时可以再开一个visit_count矩阵每经过一个格子加1结束后统计visit_count 1的格子比例。这个指标非常直观能看出往返式扫描和A*转移之间的衔接是否顺畅。6. 常见问题与排查技巧实录6.1 死循环与程序卡死的处理我在调试这个程序时遇到过最典型的问题就是主循环里找不到下一个可覆盖的起点但全覆盖判定又还没结束程序一直空转。排查后原因通常是当前行扫完换行后find_next_start选到了一个已经覆盖完的行导致一直死循环。解决办法是在find_next_start函数里加一个“查找范围限制”沿着扫描方向检查一个窗口内的行如果窗口内没有未覆盖的自由格子就直接终止程序并输出覆盖率。另外主循环里那个max_iter保险参数非常有用不能省一旦循环次数超过估计上限强制退出并输出已覆盖情况方便排查问题。这样至少不会出现“程序永远跑不完”的尴尬局面。还有一类死循环来自A内部如果目标点不可达astar会一直扩展OPEN表直到空在巨大地图上非常耗时。解决方法是给A加一个迭代上限比如最多扩展节点数不超过地图总格子数一旦超限就返回空路径主循环再换下一个目标点。6.2 路径穿墙与对角穿越的处理如果发现规划出的路径有“擦边”甚至“穿墙”现象第一个检查膨胀半径是否设置正确第二个检查八邻域的对角移动判断是否完善。我之前跑过一个场景地图上两个障碍物呈对角摆放机器人从左上角斜穿到右下角。实际上这两个障碍物之间的间隙只有0.1米左右机器人根本过不去但A*依然规划出了一条“从两障碍物角点之间穿过”的路径。原因就是在get_neighbors函数里只检查了对角格子是否为障碍物没有检查与之相邻的正交格子。解决方法是按我前面提到的方式在斜向移动前加一个条件确保当前格子与目标格子之间的两个相邻正交格子至少有一个为自由空间。这个细节虽然小但直接影响路径的物理可行性。6.3 重复覆盖偏高的优化方向如果统计结果里重复覆盖率偏高比如超过20%那就要看看A*转移路径是不是频繁经过已覆盖区域。这通常意味着find_next_start选择的起点离当前位置太远或者覆盖行顺序不够合理转移被迫绕大圈。优化的思路有两个层次。第一个层次是修改下一行起点的选择策略不选“最近的未覆盖格子”而是选“距离当前位置最近且与当前行在同类连通域内的未覆盖格子”。第二个层次是给A*的已覆盖格子加惩罚代价让转移路径主动“承担覆盖任务”。这两种方式可以叠加使用。我实测在20x20的随机障碍地图上只用第一种方法能把重复覆盖率从24%降到17%再加上第二种方法能进一步降到12%左右效果还是比较明显的。另外如果地图里凹形区域特别多建议直接升级方案采用区域分解 往返式覆盖的组合这正好是牛耕式分解算法解决的核心问题。在现有代码框架上做这个升级不用推翻重写只需要在覆盖策略外面套一层区域划分逻辑即可。6.4 Matlab特定环境下的调试经验最后说几个Matlab环境下的实操经验。第一用profile查看运行耗时如果A函数占总耗时比例过高优先优化A的数据结构和邻居扩展函数而不是优化覆盖策略。第二生成随机地图后最好每次都固定随机种子也就是rng(0)这样调试时能复现同样的问题不然每次跑出来的结果都不一样问题不好定位。第三代码里写注释时尽量用英文或者ASCII字符避免中文注释在某些Matlab版本里变成乱码保存文件时选择UTF-8编码也能减少这类问题。这套方案后续还可以往几个方向扩展把A替换成JPS跳点搜索来提升大尺度地图下的搜索速度把二维栅格扩展成三维体素地图做无人机全覆盖或者在A的f值中加入与覆盖状态相关的权重实现动态自适应路径规划。我在实际使用中发现这套“往返式覆盖 A*转移”的设计思想并不过时它真正把“覆盖”和“导航”两个问题解耦了无论底层地图怎么变、搜索算法怎么换这个框架都能稳定运转。最后再分享一个小技巧在跑完一次完整的规划后把route、covered和地图矩阵都保存到.mat文件里后续分析或者写实验报告可以直接加载不用重新计算一遍。如果你也正在做类似的路径规划项目希望这篇文章能帮你少走一些弯路。