1. 传统A*研究的是“点到点”全覆盖规划要的是“面到面”1.1 两种问题的定义差异以及为什么标题里它们能共处我最早接触A算法是做机器人走迷宫那时候觉得这算法挺有魔力——从起点到终点绕开所有障碍还能拿到一条最短路径。后来导师丢了一个课题过来让一个清扫机器人在未知障碍的房间里走完全覆盖路径。我第一反应是愣住的A算出来是一条细线可我最后要的是一片区域的覆盖轨迹。这里有个特别容易混淆的点很多初学者把全覆盖路径规划理解成“让A去遍历整张地图”这是不对的。A算法解决的是单源单目标的最短路径问题它的目标函数是min sum(cost)而全覆盖路径规划的目标函数是“所有可达且可作业的网格都被访问至少一次”同时希望总路径越短越好、重复覆盖越少越好。这两者的定义差异决定了A*不是用来生成覆盖主路线的它是用来解决覆盖任务中“当前位置到下一个作业位置”的转移问题的。换句话说全覆盖规划是一层“大循环”A*是这层循环里被反复调用的“导航子程序”。这个分工一旦理清楚整个Matlab实现就不会写拧巴了。1.2 全覆盖任务拆开看就是一连串“到未覆盖区”的寻路我后来做了几次不同场景的实验发现全覆盖路径可以抽象成一个状态序列机器人当前在某个已覆盖区域的边界上它需要找到离自己最近的、还处于“未覆盖状态”的网格集合然后规划一条从当前位置到那个目标区域的路径走过去再展开新一轮往返式覆盖。这个“走到目标区域”的动作正好就是A的活。你用A算出的转移路径不要求覆盖任何新网格它允许穿越已覆盖区域只要路径总代价尽可能低就行。真正的新覆盖动作交给往返式扫描来完成。所以一个完整的全覆盖系统内部其实有两层逻辑底层是一遍遍“扫”顶层是“扫到哪了、接下来去哪扫”。A在底层不参与在顶层全程参与。理解了这一层再去看标题里的“基于A算法的网格环境下往返式全覆盖路径规划”你就会明白A*不是被改造了而是被合理地嵌进了全覆盖框架里。1.3 这个方案实际能放到的场景这类算法的应用场景比大多数人想象的要宽得多。我做过的案例至少包括这么几类室内扫地机器人环境被栅格化成0.1~0.2米的小格往返式覆盖负责“弓字形清扫”A*负责跨房间转移光伏电站面板清扫每块面板是一个规则的矩形区域往返式覆盖天然贴合面板轮廓A*负责在不同面板之间寻找连接路径仓储盘点机器人需要在货架间的通道里来回走覆盖目标变成了“通道区域”的全覆盖A*负责从一个通道口绕到另一个通道口植保无人机的地块路径地块往往是不规则多边形需要先做简单的区域分解然后每个凸子区域做往返覆盖子区域之间用A*连接。这几个场景的共同点是任务空间能栅格化机器人有明确的作业宽度且环境中存在障碍物或不可通行区域。满足这三条A*加往返式全覆盖这套组合就值得一试。2. 往返式覆盖为什么值得当作“基本盘”来用2.1 牛耕法在网格环境里的直观形态往返式覆盖算法其实就是常说的牛耕法Boustrophedon名字听着修辞感很强原理却非常简单像农民犁地一样把目标区域按固定条带宽度分为一行一行从一侧边界开始走到另一侧边界后平移一个条带宽度再反向走回来如此反复直到整个区域扫完。在纯矩形、无障碍的环境里这个策略的路径长这样起点在左下角先沿X轴方向走到右边界然后沿Y轴方向上移一个条带宽度再沿-X方向走回左边界再上移一个条带宽度沿X方向走……这样来回折叠最终形成的轨迹是一个连续的“弓”字。在Matlab里这种轨迹生成只涉及两个向量运算每一行的y坐标固定x坐标在左右边界之间交替取端点。真正麻烦的是环境里有障碍物或者区域不是凸多边形这时候一行扫描会被打断成好几段。处理分段的方式是把当前行上所有“可扫描连续段”都标记出来每段单独当成一条子扫描线执行段与段之间用A*连接。2.2 遇到凹区域怎么办区域分解的最小可行方案碰到L形、U形这类凹区域直接做全图往返扫描会出现一个问题扫描线会横穿障碍物所在的区域导致生成的路径不可行。我的处理办法是做一个极简版本的区域分解。具体来说先扫描栅格地图找出所有“凹角”所在的列或行把地图沿这些位置切开得到若干个凸多边形子区域。每个子区域内部按矩形网格做往返式覆盖子区域之间再规划转移路径。这一步在Matlab里不需要太复杂的几何算法用形态学操作加连通域标记就能完成使用bwlabel标记所有可达区域对每个连通区域求凸包再判断凸包面积和原区域面积是否接近若凸包面积明显更大说明该区域是凹的需要按凹角位置切成多个子块。当然做区域分解时要注意子区域不能切得太碎否则频繁转移会让路径总长急剧膨胀。我一般把面积小于3个条带面积的小块合并到相邻子区域去。2.3 折返点与条带宽度的计算逻辑往返式覆盖的重复率、漏扫率和转折次数几乎都卡在“条带宽度”这一个参数上。条带宽度的物理含义是机器人沿一个方向前进时能有效覆盖的宽度范围。如果机器人是扫地机这个宽度接近滚刷宽度如果是割草机就是刀盘直径如果是无人机喷洒就是喷幅。条带宽度设计不是简单等于作业宽度我实际踩过的坑是如果条带宽度刚好等于作业宽度相邻两条扫描路径之间没有任何重叠直线误差、导航误差、传感器误差稍微一叠加就会出现漏扫细缝。所以条带宽度通常取作业宽度的0.8~0.9倍也就是预留10%~20%的搭接量。搭接量可以用一个重叠系数α表示条带间距 作业宽度 × (1 - α)α取0.1~0.2比较合理。α太小漏扫风险上升α太大重复覆盖增多总路径变长效率肉眼可见地下降。折返点的计算逻辑则更简单设扫描方向沿X轴当前扫描线的y方向坐标为y_c则下一行扫描线的坐标为y_next y_c 条带间距折返点是当前行左端点或右端点取决于扫描方向。需要注意的是在网格地图里折返点上会有一次180度掉头动作实际代价不能按普通步长算。后面讲A*时我会把这个代价写进转移路径的评估里。3. A*在往返覆盖里的核心设计启发函数、邻域和转移路径3.1 启发函数设计既要引导方向也要能处理“绕路”A*的经典评估函数是f(n)g(n)h(n)g(n)是从起点到当前节点的实际代价h(n)是当前节点到终点的启发式估计代价。这里的关键点在h(n)的选取。在网格环境里h(n)最常见的有两种取法曼哈顿距离和欧氏距离。如果允许四邻域运动曼哈顿距离是严格可采纳且一致的如果允许八邻域运动欧氏距离更合适因为斜对角移动一步的代价是√2倍的单位步长欧氏距离的描述更贴近真实距离。我做全覆盖转移路径时环境一般允许八邻域运动所以h(n)直接用欧氏距离h(n) sqrt((x_n - x_goal)^2 (y_n - y_goal)^2)这里有一个值得注意的小技巧为了让A更有“进攻性”减少扩展节点数可以用加权A把启发函数乘一个大于1的系数wf(n) g(n) w × h(n)w在1.1到1.5之间取值。w越大搜索越快但得到的路径可能不是严格最短。在全覆盖任务里转移路径本身不要求绝对最优只要接近最优就行所以w取1.2是我在多数场景下的默认值。3.2 邻域选择4邻域还是8邻域取决于运动约束很多人写A*时会默认选8邻域因为扩展节点多、路径更灵活。但我做全覆盖转移路径时会先问一个问题这个机器人能不能真的斜着走差速驱动、全向轮底盘能原地掉头斜向运动完全没问题8邻域合理。但四轮前轮转向的车辆式底盘斜向运动意味着横着蹭转向机构并不支持履带式底盘转向代价特别大频繁斜走动效率太低。对这种机器人4邻域更贴近实际运动能力。实际工程经验是我是按“转移路径长度优先、但不鼓励过多转角”来设计代价的。具体做法是把每个节点的移动代价分成两部分——步长代价和转角代价沿当前方向直行代价1相对当前方向转45度或90度再走代价基础步长转角惩罚系数。转角惩罚系数可以取0.5~1.5视机器人实际原地转向耗时而定。这一步很多人会忽略导致A*给出的转移路径画在纸面上很漂亮但机器人实际跑起来总时间反而更长因为一路上全是之字形转向。3.3 区域之间的转移路径怎么生成才不破坏覆盖效果转移路径最理想的状态是从当前位置出发沿着已覆盖区域的边缘走不穿越未覆盖区域这样不会把“还没扫”的地方变成“已经被走过”的地方也不会在转移过程中不经意间漏掉一些未覆盖又无法再覆盖的角落。但现实中完全沿着已覆盖区域边缘走往往绕路太多A算出的最短转移路径很可能直接穿过尚未覆盖的空白区域。这种情况下需要权衡允许穿越未覆盖区域但要给这类网格额外加一个惩罚项让A优先选择已覆盖区域通行。在Matlab里实现很直接维护一张cost_map已覆盖网格的基础代价为1未覆盖网格的基础代价为1.5障碍网格代价为inf。A*在搜索时自然就会尽量走已覆盖区域。有人会问穿过未覆盖区域不是也算“覆盖”了吗严格来说走过去确实经过了但由于没有按往返式方向作业留下的路径只是一条孤立的单线如果后续往返式扫描以这条线为基准仍可能产生漏扫。所以宁可让转移路径稍微绕一点也要避免横穿未覆盖区域。这部分的完整教训是转移路径不能只看“能不能走过去”还要看“走过去之后会不会给后续全覆盖制造麻烦”。这也是“往返式全覆盖”和“A*转移”两个模块不能完全解耦的原因所在。4. Matlab实现地图、主循环、A*函数三步走4.1 栅格地图建模与机器人尺寸膨胀Matlab里的栅格地图我习惯用二值矩阵表示1表示障碍物0表示可通行。为了调动代码实现时视图更直观同时保留后续绘制路径的底图也可以直接用binary occupancy map也就是Robotics System Toolbox里的occupancyMap类。不过我自己的项目最常用的是纯矩阵版本因为不需要额外工具箱依赖更少。这里有一个必须做的前处理步骤——按机器人尺寸对障碍物区域做膨胀。原因是A*路径规划里机器人被抽象成一个点如果地图上障碍物只是“细胞的原始轮廓”点路径可能会贴着障碍物边缘穿过但真实机器人有体积就会撞上墙角或者擦到桌腿。膨胀方法用图像处理里的imdilate实现% 假设机器人半径对应r个栅格 se strel(disk, r, 0); map_inflated imdilate(map_original, se);膨胀半径建议在机器人半径基础上额外加上一个栅格的安全余量。注意膨胀完之后一定要再检查一下确保机器人的出发点没有被膨胀成障碍物否则A*的开闭列表里起点就是非法节点整条路径生成会直接失败。4.2 往返覆盖主循环的骨架我实现的往返回覆盖主循环一般长这样% 参数初始化 step 2; % 条带间距栅格数 direction 1; % 1表示向右扫-1表示向左扫 current_pose start_pose; % 当前坐标 visited_count zeros(size(map_inflated)); % 记录每个格子被覆盖次数 while coverage_rate target_rate % 在当前行上找到本段可扫描的连续区域 segment find_scan_segment(map_inflated, current_pose, direction); % 沿该行往返扫描并更新visited_count [current_pose, visited_count] scan_line(segment, visited_count); % 判断是否还有下一行 if has_next_line(map_inflated, current_pose, direction) next_start compute_next_line_start(current_pose, step, direction); current_pose next_start; direction -direction; else % 本行扫完且没有下一行则寻找最近未覆盖区域 target find_nearest_uncovered(visited_count, map_inflated, current_pose); if isempty(target) break; % 全部覆盖完成 end % 用A*规划转移到target起点的路径 transfer_path astar_path(map_inflated, current_pose, target, visited_count); current_pose target; end end这个骨架里最核心的一点是每扫完一段都要更新visited_count覆盖率也由visited_count实时算出。这个矩阵同时承担“记忆到底哪块地还没扫过”的角色是后续寻找目标区域的依据。4.3 A*核心函数与优先队列的使用A*的核心实现有很多现成代码但直接抄网上的版本在小地图上没问题地图一大就慢得让人怀疑人生。原因在于很多示例代码用未排序的数组当openList每轮都要O(n)找最小f值地图超过200×200时扩展节点一多整套逻辑就崩了。我的建议是使用优先队列。Matlab原生没有C那样的priority_queue但可以用java.util.PriorityQueue这是Matlab能直接调用的Java类性能足够好pq java.util.PriorityQueue(); pq.add([f_value, node_index]);当然如果你不想引入Java依赖也可以手写一个二叉堆或者用Matlab的containers.Map加排序来做。我的经验是500×500网格下Java优先队列的速度大约是数组扫描法的20到30倍这个提升还是很可观的。A*函数内部我按这样组织function [path] astar_costmap(cost_map, start, goal) % 初始化gScore、fScore、cameFrom % 将start加入优先队列 % 循环取出f值最小的节点若为goal则回溯路径 % 对每个邻居计算新g值若更优则更新并加入优先队列 % 循环结束无解则返回空 end这里再看一个细节cost_map不仅仅是0/1它还携带了“已覆盖/未覆盖”的代价信息。转移路径A*从cost_map里取值算出的路径会自动偏向已覆盖区域这比我再额外写一个“禁止穿越未覆盖区域”的判断语句高效得多。4.4 覆盖率与重复率的实时计算我习惯在覆盖主循环的每个扫描段结束之后及时计算两个指标覆盖率visited_count 0 的栅格数 / 可通行且可作业的栅格总数重复覆盖率(sum(visited_count(visited_count0)) - 覆盖栅格数) / 覆盖栅格数 × 100%。这两个公式看着简单但有一个边界情况要提前约定好分母“可作业栅格数”到底是排除了障碍物之后的全部0值栅格还是只算真正能到达的连通区域。在地图存在封闭障碍物区域时两者会差不少。我建议把分母限制在“起点可达的连通区域”内不然覆盖率永远达不到100%最后循环会跳不出来。Matlab里判断连通性用bwlabel提取连通域后判断终点是否与起点同标记即可这个步骤在预处理阶段就完成不占用主循环时间。coverage_rate sum(visited_count(:) 0) / numel(reachable_free_cells); repetition_rate (sum(visited_count(:)) - sum(visited_count(:) 0)) / sum(visited_count(:) 0);这两行代码在循环里实时更新能帮你快速发现“是不是卡在某个死角里反复扫”这类问题。5. 关键参数怎么定栅格粒度、条带宽度和转移策略5.1 栅格粒度对路径质量的影响栅格粒度也就是每个格子对应的实际边长是整套参数里最影响全局的。你把它定得太粗比如机器人宽0.4米你用0.5米一个格那地图里一条0.9米宽的通道就会被表示成2个格还能勉强通行但如果通道只有0.95米膨胀后就直接不可达了。这类失真会让全覆盖路径出现莫名其妙的“漏扫区域”和“绕远路”。反过来栅格粒度太细也会出问题。我用过0.02米一个格的毫米级地图一条5米长的路径规划出来要扫上百万个节点A*每次转移都要算两三秒覆盖任务里转移次数又多用户体验非常差。我的经验法则是栅格边长取机器人特征尺寸的1/2到1/3。比如扫地机直径取0.4米栅格边长在0.15~0.2米之间就够用。这样既保证了窄通道的建模精度又不会让搜索空间爆炸。5.2 条带宽度与重复率的关系条带间距直接决定路径折叠的密度。我统计过一组典型数据在一个20m×20m的无障碍方形区域里作业宽度取1.2米α从0变化到0.2重叠系数α条带间距(m)转折次数总路径长度(m)重复率01.20334000%0.101.083744511.3%0.200.964250025.0%可以看到α从0.1增加到0.2重复率翻倍还多路径长也涨了12%。所以α不是越大越安全过大的重叠量会让机器人白跑大量重复线路。我实际项目里优先取α0.1如果定位精度差再调高到0.15一般不到万不得已不会上0.2。另外要注意条带间距最好和栅格边长保持整数倍关系。比如栅格0.2米条带间距1.0米就是5格。如果算出条带间距是1.05米映射到栅格时会变成5.25格取整后折返点位置漂移重复率和漏扫率都会变得不可预测。5.3 转移策略何时“硬折返”何时“绕过去”往返式覆盖里最常见的转移情况是一行扫到一半前方出现障碍物本段扫描结束。此时有两种选择一是退出去绕到障碍物另一侧继续本行二是跳过该行剩余部分平移到下一行再扫。我的经验是如果障碍物宽度小于2个条带间距优先选择跨行转移把被障碍物阻断的另一侧放到这个区域覆盖顺序的末尾再处理如果障碍物宽度很大甚至是个挡在中间的长墙就必须绕过去继续本行的另一段不然后续会出现大块孤立未覆盖区。这个判断逻辑要写在主循环里不要依赖A自动去“发现”绕行方案。A解决的永远是“从A到B的最短代价路径”但它不会主动告诉你“这个B值不值得现在去”。决策层不做这个判断覆盖效率会明显下降。5.4 一组便于写进论文/报告的量化评估指标如果你的目的是写论文或者做结题报告建议把这几项指标都跑出来覆盖率目标区域被覆盖的百分比重复率重复覆盖栅格数占覆盖栅格数的比例转折次数路径方向发生180度翻转的次数路径总长全部走过的距离总和含转移路径计算耗时覆盖主循环从开始到结束的Matlab运行时间。其中“总路径长度”和“转折次数”在论文里可以合并成一个“覆盖效率”指标覆盖效率 理论最短全覆盖路径长度 / 实际路径总长理论最短全覆盖路径长度可以用“区域面积除以作业宽度”估算。这个指标适合拿去对比不同策略之间的优劣比如A*往返式对比贪心式全覆盖或者对比随机式覆盖差距很快就能拉出来。6. 调试过程中最常翻车的四类问题以及我的处理方式6.1 转移路径“穿墙角”的问题我第一次跑通A*全覆盖时发现转移路径偶尔会贴着障碍物的角斜穿过去看起来像“走捷径”但实际机器人运动半径根本不允许这种走法。这个问题的根源在于地图膨胀时只考虑了机器人半径但8邻域扩展允许从障碍物的斜角格穿到对角格两个障碍角点之间留出的理论通行宽度小于机器人体宽。解决办法有两个方向。一个是把邻域扩展限制为4邻域路径只走正交方向安全性立刻提升但路径长度会变长另一个是保留8邻域但在扩张地图时额外对障碍物角点做一次“凸角膨胀”也就是把障碍物周围斜角位置的栅格也标记为不可通行。我后来大多数项目里直接选4邻域因为全覆盖任务中转移路径占比不高长一点没关系稳定可靠优先。6.2 覆盖完发现漏了一块“孤岛”区域在一个带圆形花坛的庭院地图里跑完一遍主循环覆盖率卡在94%再也上不去。检查后发现花坛后面有一片窄长区域被往返式扫描线“跳过去”了。虽然它和主区域是连通的但条带间距刚好让扫描线的端点落在了窄通道边界上往返式覆盖天然扫不进去。后来我在主循环结束前加了一个“补漏”阶段找出所有覆盖率仍为0的可达栅格按离当前机器人位置从近到远排序逐个用A*规划转移路径到达后以该点为起点执行局部往返覆盖。这个补漏阶段的代码并不复杂但回报很大能把覆盖率从94%拉到99%以上。需要注意补漏阶段容易产生高重复覆盖计算指标时我一般把它和主循环的指标分开记录。6.3 重复覆盖率高不一定全是坏事我讲过条带重叠带来重复覆盖是可控的。但还有一种重复覆盖来自A*转移路径本身每次转移都要从头覆盖区域走到未覆盖区域途中会经过已覆盖区域这些格子会被再次记为“访问过”。转移越频繁这种重复就越多。这也是为什么我坚持在cost_map里给未覆盖区域加额外代价、让转移路径尽量走已覆盖区的原因。重复覆盖发生在已覆盖区通常可以接受但如果转移路径每次都横穿一大片未覆盖区重复率会变得很难看。判断标准我可以给个经验值主覆盖阶段重复率控制在15%~25%以内算合理超过30%优先怀疑条带重叠系数太大或者转移路径设计有问题。6.4 真机落地时还要注意的转向次数与时间开销仿真图很好看不代表真机能跑出同样效果。全覆盖任务里最吃时间的是折返动作——180度掉头。掉头时机器人基本要减速、原地旋转、再加速一次掉头的时间相当于直行五六步的时间。A*给的转移路径里如果频繁出现转向即便路径短实际执行时间也很长。我在代码里加过这么一个小统计将折返次数按“每次折返平均耗时2秒直行每步耗时0.5秒”折算成等效时间代价然后拿这个时间去对比不同参数下的路径优劣。这个做法帮助我很快发现了一个反直觉的结论在某些窄长环境里多绕一点路走平滑大弯比频繁做直角转向更省时间。如果你要写真实落地的报告建议把这种“时间代价模型”也写进去评审会觉得你考虑到了执行层的问题而不只是停留在仿真层。调试这些问题的过程比我一开始跑通Demo收获大得多。全覆盖路径规划真正的难点不在于某一个算法本身而在于把路径生成、转移导航、覆盖记忆、参数耦合这些模块捏合到一起。A*在其中只是承担了转移导航这一环但正是这一环决定了整套系统在复杂环境下能不能收好尾。