1. 起点搞错了全覆盖路径规划和“最短路径思维”是两码事先说一个我自己趟过的坑。大概两年前一个做小型清扫机器人的项目找到我说想用 A* 算法做路径规划我第一反应是“A* 不就是从点 A 到点 B 找最短路径吗有什么好规划的”。结果需求方说完具体要求我才意识到完全不是这么回事——他们要的不是“从 A 到 B”而是“这块区域的每一个格点都要走到”这就是全覆盖路径规划Complete Coverage Path Planning简称 CCPP问题。很多人跟我当初一样把 A* 算法、网格环境、最短路径这些概念捆在一起默认认为 A* 只能用来做点对点寻路。实际上在网格环境下的往返式全覆盖路径规划里A* 扮演的角色要微妙得多它并不负责生成整条覆盖路径而是负责处理“转移段”——也就是当前扫描路线被障碍物打断时怎么从当前位置跳到下一个可以继续扫描的位置。想清楚这一点整个项目的实现思路就清晰了。这篇文章适合这几类人看正在用 Matlab 做移动机器人路径规划发现单靠 Dijkstra 或 A* 解决不了“全图扫一遍”需求的同学做扫地机器人、割草机器人、水面清漂机器人这类“作业型”产品的工程师刚接触全覆盖路径规划想搞明白往返式弓字形扫描和 A* 到底怎么配合的入门选手。我会把往返式全覆盖的核心原理、Matlab 实现骨架、以及我实测过程中踩过的坑全部摊开讲尽量说人话保证你照着思路能自己写出来。1.1 点对点规划和全覆盖规划到底差在哪点对点路径规划的任务是给定起点 O 和终点 D在网格环境中找一条满足约束的路径通常以路径长度最短为目标。它的评价指标单一状态空间也单一——路径上每个点只需要回答“我通不通”。全覆盖路径规划的任务则是在给定区域内规划一条连续轨迹让搭载执行器刷头、割草刀盘、摄像头、机械臂末端的移动体扫过区域内的每一个可达自由格点。评价指标一下子多了覆盖率被扫过的自由格数量占全部可达自由格数量的比例通常是 100% 才算合格重复覆盖率重复走过的格数量占总覆盖格数量的比例越低越好转弯次数对割草机、扫地机器人这类非全向移动体来说一次原地转弯的时间很可能顶得上直行好几个格子的时间路径总长在满足上述约束的前提下越短越省能耗。我用一个生活化的类比来区分两者点对点规划像是“送货”我只需要把包裹送到某户人家门口全覆盖规划像是“扫地”客厅里每一寸地面都得过一遍。送货可以用最短路径扫地则要牺牲一部分“最短性”来换取“完整性”。1.2 为什么选 A* 而不是其他算法做全覆盖常见的全覆盖路径规划方法有随机覆盖法、模板覆盖法、人工势场法、遗传算法、强化学习还有我今天重点展开的往返式扫描法。随机覆盖不讲究效率纯靠概率把整个区域“撞”满人工势场在复杂凹形障碍物环境里容易陷入局部极小遗传算法和强化学习适合离线规划大区域但计算环境要求高工程落地相对繁琐。往返式扫描也叫弓字形扫描、牛耕式扫描boustrophedon path是工程上最稳的方案按行从左往右扫到边界后换下一行从右往左扫转弯次数少、覆盖逻辑清晰、代码容易实现。而 A* 在这个方案里的作用我后面会单独讲——它不做全局路径的生成而是充当“转场搜索器”。这个组合最大的好处是主体路径可控特殊场景下的处理又有最优性保障。扫描主体用确定性规则保证覆盖完整遇到障碍物打断行扫描时用 A* 在局部范围内找一条最优的转场路径避免“绕了远路还不知道”。两种思想配合实测下来路径质量很稳定。2. 把现实世界塞进矩阵覆盖率状态机与可达性预判网格环境下做覆盖规划第一步绝对是把环境建模做扎实。很多新手一上来就急着写 A* 的 open list、close list结果地图表示得模棱两可覆盖率算出来莫名其妙 95% 找不出原因。我的建议是先把地图和覆盖状态的数据结构定义清楚再谈算法。2.1 栅格地图的数据结构约定在 Matlab 里我习惯用两个等尺寸的二维矩阵来刻画环境。第一个矩阵是环境地图map存储固定不变的地形信息0自由格可以通行也是需要覆盖的目标格1障碍格不可通行不需要覆盖NaN或-1地图边界外的虚拟区域永远不考虑。第二个矩阵是覆盖进度covMap动态更新0自由格但尚未被覆盖1自由格且已被覆盖障碍格在covMap里直接置为NaN避免混入统计。两个矩阵分开维护看似麻烦但好处明显map是静态的跑算法时不用反复拷贝covMap只反映“谁扫过了”计算覆盖率时直接用covMap 1的数量除以map 0的总数即可不会出现“把障碍物也算进待覆盖格”的乌龙。2.2 覆盖率状态机的转换关系覆盖过程本质上是自由格从“未覆盖”到“已覆盖”的一次性状态迁移不存在逆过程初始状态机器人位于起始格起始格直接标记为已覆盖扫描状态机器人沿当前行进方向移动到下一个自由格该格标记为已覆盖转场状态机器人从当前格转移到下一个扫描行的起点转移路径上经过的全部自由格同样标记为已覆盖完成状态所有可达自由格都已被覆盖算法终止。这里有个容易搞混的细节转场状态经过的格子也是要标记为已覆盖的。机器人只要物理上碾过那个格点那个格点对执行器来说就算覆盖过了。很多实现把“扫描路径”和“转场路径”分开统计导致最终覆盖率明明显示 100%实跑路径却漏了一大片问题就出在这。2.3 可达性预判先做连通域分析再谈全覆盖覆盖率 100% 的前提是区域内所有自由格都“可达”。如果地图里有孤立的自由格区域比如一圈障碍物围出个密闭小空间入口还被堵死无论怎么规划都不可能以单起点扫遍全部格点。所以我做网格地图之后的第一件事不是写 A*而是做连通域标记。Matlab 自带bwlabel函数传入map 0的逻辑矩阵立刻能看到自由格分成了几块。如果连通域数量大于 1要么调整地图边界要么规划多个起点否则算法必然死循环或者失败。这一步的工程价值很大。实测中很多看似合理的房间地图因为墙角凸起一根柱子自由格被分成了一大一小两个连通域单起点全覆盖根本不可能完成。预判之后再决定要不要支持“多起点接力”比算法跑起来才发现跑不完要省时间得多。3. A* 在覆盖规划里的真正角色转场搜索而不是全图寻路现在回到核心算法本身。我得先把一个常见误解纠正过来有人在网格全覆盖里用 A从头到尾生成全覆盖路径那是在强行让 A干它不擅长的事**。A* 的搜索目标是单一目标节点而全覆盖规划的目标是整个节点集合状态空间指数级膨胀直接全局搜会慢到怀疑人生。那 A* 到底用在哪答案就三个字转场段。3.1 什么是转场段往返式扫描过程中机器人按行走扫正常情况下每行都能扫到左右边界。但现实环境里有障碍物可能出现以下几种情况机器人扫到某一行中部前方一格是障碍物行被拦腰截断机器人扫完一个连通块的某一行想进入下一行时发现下一行的入口被障碍物挡住机器人扫到一片凹形区域的底部上方和下方都被障碍物堵住当前连通域扫完了但地图角落还有一个未扫的连通域。这些情况下机器人不能继续按部就班地弓字形行走了它需要从当前位置“跳”到下一个策略位置。这个跳跃过程就是转场段。转场段的起点是当前扫描点终点是某个未覆盖区域的入口格中间路径由 A* 搜索得到。3.2 转场搜索的代价函数设计A* 的代价函数形式固定f(n) g(n) h(n)关键是g(n)的设计。在转场搜索里g(n)不能只算路径长度还要考虑一个额外因素重复覆盖的惩罚。如果转场路径完全看距离最短A* 很可能会原路返回让机器人碾过大量已覆盖的格子回到起点附近重复覆盖率直接爆表。所以我给g(n)加了权重g_new g_current 1 penalty * covMap(neighbor);其中covMap(neighbor)为 1 表示该邻居已被覆盖penalty取 0.5 到 1.5 之间的值。penalty越大A* 越倾向于绕开已覆盖区域但penalty过大又可能导致路径绕很远反而让总长度增加。我实测下来penalty 1是个比较稳妥的平衡点转场路径会尽量避免重复但也允许在无路可绕时短距离穿过已覆盖区域。3.3 启发函数的选择网格环境里启发函数的选择与移动方向数直接相关四邻域移动上下左右曼哈顿距离是最佳可采纳启发八邻域移动含对角切比雪夫距离Chebyshev distance或 octile 距离更精确。我推荐八邻域移动因为全覆盖路径里大量出现斜向转场只允许四邻域会显著延长转移距离。启发函数代码很简单h max(abs(goal_x - x), abs(goal_y - y)); % 切比雪夫距离注意一个细节如果允许斜跨障碍物角点即八邻域移动要求相邻格子中不能同时存在两个正交方向的障碍必须在检查邻居时增加约束。否则 A* 会输出一条“穿墙角”的路径实跑时机器人根本过不去。这是网格寻路里非常经典的一个隐蔽 bug。3.4 什么时候调用 A*调用几次往返式主循环里我规定只有以下条件同时满足时才触发 A* 转场搜索当前行扫描到尽头行尾边界或障碍物且下一行目标扫描起点不可直接到达扫描完成标记covMap更新后仍未覆盖全部自由格不存在其他可直接规划的邻接行起点。实际上大多数普通矩形地图跑下来A* 的调用次数只有个位数。真正的计算瓶颈不在 A*而在主循环里的状态更新和判定逻辑。如果发现 A* 被频繁调用往往意味着地图里有大量锯齿状的障碍区这时要先检查建模是否把噪声点误判为障碍物了。4. 往返扫描主循环弓字行进、障碍断行与死区逃生往返式覆盖规划的框架说白了就是“按行从左到右扫扫完换下一行从右到左”但工程实现里有一堆边界情况要处理。这一节我把主循环的完整逻辑拆开讲。4.1 基准策略按行弓字扫描先定义坐标系统矩阵行号对应地图的 y 坐标列号对应 x 坐标。机器人从起始格(startY, startX)出发默认行进方向为“向右”。具体步骤是沿当前方向逐格前进每步将当前格在covMap标记为已覆盖到达本行右边界前前方一格若为障碍物则进入断行处理到达右边界后向下移动一行y1若新行的起始位置可直接进入则切换方向为“向左”继续扫描左边界同理到达后向下换行切换方向“向右”重复以上过程直到所有可达格覆盖完毕。这里有一个非常关键的换行策略换行的前提是下一行当前扫描位置对应的格子是自由格。如果下一行对应位置是障碍物不能硬换行需要先沿着障碍物边缘滑到下一个可通行位置否则会漏掉整行。4.2 障碍物断行处理贴边滑行还是 A* 转场行扫描的中间遇到障碍物是全覆盖路径规划里最常见的场景。我的处理优先级是先尝试“贴边滑行”从当前格绕到障碍物的另一侧检查是否还有可走的自由格。具体做法是若前方为障碍分别检查当前格上方和下方的相邻自由格往其中一个方向滑动再尝试绕行。如果绕行后能回到同一行继续扫描则不需要 A*如果贴边滑行找不到一个可继续的位置说明该行已经被障碍物彻底截断此时记录当前行的“已覆盖部分”将该行标记为“断行”然后触发 A* 转场到下一个未覆盖区域。我在括号里说“已覆盖部分”是因为一行被截断后断点两侧不一定属于同一个连通可达域。比如一个“凹”字形障碍区从上往下扫的时候第 3 行的中间被柱子截断左右两段其实是连通的可以从第 4 行绕过去但如果障碍物是封闭的矩形第 3 行的左段和右段可能只在第 4 行中间有狭窄通道此时必须 A* 转场。这个判断逻辑写清楚之后代码反而简单。很多实现就是因为这里偷懒直接遇到障碍物就切换方向导致覆盖率只有七八成。4.3 死区逃生扫描到“绝路”怎么办死区指的是机器人当前位置周围的可通行自由格都已经扫过但地图上还存在未覆盖格且这些未覆盖格不在当前行延伸方向上。这种情况几乎必然出现在有凹形障碍物或走廊环岛的地图里。死区逃生的完整流程是扫描covMap找出所有未覆盖且可达的自由格集合对这个集合中的每一个格计算它到当前扫描点的曼哈顿距离选距离最近的未覆盖格作为 A* 的目标节点执行 A* 转场搜索沿转移路径更新covMap到达目标格后重新启动往返扫描主循环。你可能觉得“找最近的未覆盖格”太朴素了。实际上这个策略在绝大多数情况下都足够好因为往返扫描规划出来的未覆盖区域通常都是带状连续的最近的未覆盖格基本就在当前行上下几行的位置转场距离很短。只有在极端螺旋地形里才需要考虑更复杂的目标点选择比如“让未来扫描路径最短”的评价函数工程上优先级很低。4.4 终止条件的严谨定义全覆盖路径规划最怕“自我感觉覆盖完了实际还有漏网之鱼”。终止条件不能只靠当前位置周围没有自由格判断而要全局检查uncoveredCount sum(covMap(:) 0 map(:) 0); if uncoveredCount 0 break; endmap 0保证只统计自由格covMap 0筛出未覆盖格。把这个条件放在主循环的最前面每次迭代开头检查一次基本不会漏。5. Matlab 实现的代码骨架与参数调优笔记这一节给出可运行的逻辑骨架。完整工程代码太长不适合贴在博文里但核心结构搞明白之后剩下的只是细节填充。5.1 主循环骨架map loadMap(room.txt); % 障碍1, 自由0 covMap zeros(size(map)); covMap(map 1) NaN; start [2, 2]; % [row, col] covMap(start(1), start(2)) 1; dirRow 0; dirCol 1; % 初始向右移动 current start; targetTotal sum(map(:) 0); coveredCount 1; while coveredCount targetTotal % 1. 尝试继续沿当前方向前进 [canMove, nextPos] tryForward(current, dirRow, dirCol, map); if canMove current nextPos; if covMap(current(1), current(2)) 0 covMap(current(1), current(2)) 1; coveredCount coveredCount 1; end continue; end % 2. 确认是否已到本行边界 if isAtRowBoundary(current, dirCol, size(map, 2)) % 尝试换行 [couldSwitch, newPos, newDir] trySwitchRow(current, dirRow, dirCol, map); if couldSwitch current newPos; dirRow newDir(1); dirCol newDir(2); continue; end end % 3. 断行或死区找最近未覆盖格执行 A* 转场 goal findNearestUncovered(current, covMap, map); if isempty(goal) break; % 理论上不会发生预防死循环 end path aStarTransfer(map, covMap, current, goal); for i 1:size(path, 1) p path(i, :); if covMap(p(1), p(2)) 0 covMap(p(1), p(2)) 1; coveredCount coveredCount 1; end end current goal; end这段代码逻辑很直白能走就一直走走到边界就换行换行不成就转场。tryForward和trySwitchRow都是很简单的位置判定函数唯一要注意的是换行方向要根据当前扫描方向取反。5.2 A* 转场搜索核心实现function path aStarTransfer(map, covMap, start, goal) [rows, cols] size(map); openList containers.Map(KeyType,char,ValueType,any); closedSet zeros(rows, cols); gScore inf(rows, cols); fScore inf(rows, cols); cameFrom zeros(rows, cols, 2); key sprintf(%d,%d, start(1), start(2)); gScore(start(1), start(2)) 0; fScore(start(1), start(2)) heuristic(start, goal); openList(key) struct(pos, start, f, fScore(start(1), start(2))); while ~isempty(openList) % 取出 f 值最小的节点 keys openList.keys; fVals cellfun((k) openList(k).f, keys); [~, idx] min(fVals); k keys{idx}; node openList(k); openList.remove(k); if node.pos(1) goal(1) node.pos(2) goal(2) path reconstructPath(cameFrom, start, goal); return; end closedSet(node.pos(1), node.pos(2)) 1; % 八邻域遍历 for dr -1:1 for dc -1:1 if dr 0 dc 0, continue; end nr node.pos(1) dr; nc node.pos(2) dc; if nr 1 || nr rows || nc 1 || nc cols, continue; end if map(nr, nc) 1, continue; end if closedSet(nr, nc), continue; end % 墙角穿越检查 if abs(dr) 1 abs(dc) 1 if map(node.pos(1)dr, node.pos(2)) 1 ... map(node.pos(1), node.pos(2)dc) 1 continue; end end moveCost sqrt(dr^2 dc^2); repeatPenalty 0.8 * covMap(nr, nc); tentativeG gScore(node.pos(1), node.pos(2)) moveCost repeatPenalty; if tentativeG gScore(nr, nc) cameFrom(nr, nc, :) node.pos; gScore(nr, nc) tentativeG; fScore(nr, nc) gScore(nr, nc) heuristic([nr, nc], goal); nkey sprintf(%d,%d, nr, nc); openList(nkey) struct(pos, [nr, nc], f, fScore(nr, nc)); end end end end path []; end这里面repeatPenalty用了0.8的系数是我反复调出来的。直观解释就是转场路径多走一个已覆盖格子比多走 0.8 个新格子的“代价”差不多既不会导致 A* 疯狂重复覆盖也不会让它为了绕开一格已经覆盖的地方而绕一个巨大的弧形。5.3 可视化与调试日志全覆盖路径规划的可视化比点对点寻路要异步重要。因为覆盖率 100% 不代表路径质量好你得看着机器人一路扫过去才能发现哪里重复走多了、哪里转弯转得不合理。我的可视化做法很简单每一帧画一个imagesc把covMap的三种状态用三色表示未覆盖灰色已覆盖绿色障碍黑色覆盖路径则用一个逐渐加深的迹线来画。figure; imagesc(covMap); colormap([0.8 0.8 0.8; 0.2 0.8 0.2; 0 0 0]); % 灰、绿、黑 colorbar;另外我强烈建议在每次转场前打印日志当前坐标、目标坐标、已覆盖数、剩余未覆盖数、转场路径长度。调参阶段这些日志比任何调试器都好用。6. 实测中的三个坑漏角落、重复覆盖和原地打转写代码的阶段算法逻辑看着都对但真放到复杂地图里跑你就会发现各种“理论之外”的问题。我把踩过的坑集中在下面三块每一个都配有排查思路。6.1 地图角落漏覆盖一个 U 形地图机器人从左上角出发弓字扫到 U 形底部时左右两侧各有一个角落没扫到。原因在于换行策略里当下一行对应位置是障碍物时我直接滑到了左边界的下一个可通行格但中间那个凹槽内的自由格被跳过了。排查思路检查trySwitchRow函数。正确的换行策略不是“直接下移一行再继续扫”而是“先尽量沿当前行扫到底再判断下一行哪些自由格与当前行的已覆盖区域连通”。用连通域的思路来理解换行前先对下一行做一次局部可达性分析只跳到“下一个仍然在扫描方向上的连通自由段”。我的修复办法是换行前不自动移动而是先收集下一行的所有自由格按列顺序排列再从当前列的邻接位置开始依次判断是否能直接到达。能直接到的就作为换行位置不能到的就先跳过等该行其他段扫完后再通过 A* 转场解决。6.2 重复覆盖率莫名高于 20%理论上往返扫描的重复覆盖率应该接近 0除了转场路径但实测有时候会高于 20%。排查后发现了原因转场路径的惩罚系数设得太大导致 A为了不重复覆盖选择了一条弯弯绕绕的远路远路上反而经过更多已经扫过的区域*。这个反直觉的坑很值得注意。penalty 5时A* 宁可多走二十格新格子也不肯穿一格已覆盖格而这二十格新格子里有一半是已经扫过的因为地图总共就那么点自由格最终重复覆盖不降反增。我把penalty一降到1以内重复覆盖率立刻降到 8% 左右。所以这里的工程经验是不要对重复覆盖“零容忍”覆盖率主要靠扫描主体保证转场段引入少量重复是合理的不要试图用惩罚系数把重复压到绝对零那只会让路径整体劣化。6.3 算法卡死在“反复横跳”一个典型的凹形障碍区机器人从凹口左侧进入扫到凹底后A* 转场把机器人送到凹口右侧结果右侧扫完后又转场回凹底来回反复始终无法覆盖全部自由格运行时间翻了几十倍。根因在于每次findNearestUncovered找到的“最近未覆盖格”始终是同一个格点导致转场目标不变跳过去扫了几格就又跳回来。这是无记忆贪心策略的典型失效场景。修复方案是增加一个jumpHistory集合凡是被 A* 转场访问过的目标节点如果两轮内没有被实际覆盖掉即到达该点后一格格都没扫就继续触发转场就把该点加入“临时禁用列表”在下一次找目标时跳过。本质上就是给贪心策略加一个禁忌表简单但十分有效。7. 别停在这动态障碍、多分区和代价模型的进化方向写到这里往返式全覆盖路径规划的核心已经完整了。但工程上项目总有后续需求我再简单说说可以往哪些方向拓展。7.1 动态障碍下的重规划如果地图里的障碍物会移动比如扫地机器人遇到突然出现的玩具、宠物静态 A* 转场就不够用了。我的建议是不要上太复杂的算法直接沿用静态框架在每次移动前先检查前方一格是否被新障碍物占用被占用则触发一次局部重规划。因为全覆盖规划的转移段很短跑一次 A* 的开销在毫秒级完全来得及。更极端的需求比如动态拥挤环境下长时间运行才需要考虑 D* Lite 这类增量搜索算法。普通室内移动平台用不上。7.2 多机器人分区覆盖多机器人的常规做法不是共用一张地图直接跑全覆盖那样会互相干扰而且协调代价极高。更实际的是先把地图按连通域或面积均分切成若干子区域每个机器人负责一个子区域子区域内的往返扫描和 A* 转场完全独立。只在最后的“区域间转移”上做一次全局协调也就是让每个机器人知道自己扫完后去接应哪个机器人。分区本身可以用 K-means 对地图自由格坐标聚类但要注意保持分区连通性直接 K-means 很容易切出断块实测要加一个“断块合并”的后处理步骤。7.3 从长度最优走向能耗最优到现在为止我们的 A* 转场代价函数关注的是路径长度和重复覆盖惩罚。如果要更精细可以在代价函数里加入转弯代价让 A* 少走之字路线turnPenalty (newDir ~ oldDir) * 2.0;这个改动对四向移动的机器人尤其明显也能让最终路径更平滑、更贴合实际执行器的运动学约束。另外一个开放方向是“代价最优覆盖”即不仅要求覆盖全还希望覆盖的顺序让总收益最大比如农业生产中不同地块的不同优先级。这时候往返式扫描的确定性框架就不够了需要把全覆盖问题建模成带约束的优化问题用元启发式算法去求解。这已经是研究级的方向了做项目的话先不急着碰。8. 我个人做完这个项目后的几点建议这个全覆盖路径规划项目做完后我最深的体会是算法选型不重要问题分解才重要。A* 算法只是工具箱里的一个扳手它不是万能的但把它放在“转场段搜索”这个位置上它几乎是完美的——有最优性保障、实现简单、调试直观。而全覆盖的主体框架恰恰是那个看起来没什么技术含量的“弓字形扫描”。我给后来者几个实在的建议第一先画地图、先做可视化再写算法。地图都没画对算法再漂亮也是对着错误世界做推理。我的流程是用一张真实的房间 CAD 草图转成栅格地图文件再写可视化脚本把地图打印出来确认坐标方向一致后再动算法。第二保存每一次实验的日志和截图。覆盖率、重复率、运行时间、A* 调用次数这几个指标每次改参数都记录一遍。调参的时候你会感谢自己这个习惯。有一段时间我反复调penalty系数却看不到明显变化回看日志才发现是换行策略的 bug 主导了路径形态参数再怎么调都没用。第三在 Matlab 里善用profile定位性能瓶颈。我最初跑一张 100x100 的复杂地图耗时 12 秒profile 发现 70% 的时间花在containers.Map的键查找上。后来换用两个普通的双精度矩阵当优先队列就是用数组模拟二叉堆时间降到了 3 秒以内。A* 在 Matlab 里的瓶颈从来不是搜索本身而是数据结构。最后说一个彩蛋完成全覆盖并转场到终点后机器人停在最后一个覆盖格上。但实际产品比如割草机通常需要回充这一小段“返航路径”依然可以用 A* 搜索——这次是做它最拿手的点对点寻路。一个项目里把 A* 的两个角色都用上了也算是对这个经典算法的一种完整致敬吧。