覆盖路径规划：让机器人扫遍整个地面

和“抵达某处”完全不同的问题

A* 找的是通往一个目标的一条路线。覆盖规划器必须碰到每一个可达的方格，这彻底改变了目标函数：没有要靠近的目标，没有可以引导你的启发式，成功也不是非黑即白的。

取代它的度量指标是每平方米扫过的行驶距离。地面面积 A，工具宽度 w，一台完美的机器人把每格扫一次且从不重复：

d_optimal = A / w

一个 20 m² 的房间配一把 250 mm 的刷子，需要 80 m。下面每个数字都是它的倍数，因为倍数是唯一能跨越房间变化仍然成立的比较方式。

无图扫荡的支配定律

一台完全不知道自己去过哪里的机器人，覆盖新地面的速率与仍未覆盖的地面成比例。这是一个只有一个答案的微分方程：

covered(d) ≈ 1 − e^(−d / d_optimal)

从上面读出三个点，整个问题的形状就显现出来了：

**最后那 9% 比最初那 90% 更贵。**这就是经典的“集齐优惠券”问题装上了一把刷子，而它是解释你见过的每一台扫地机器人的唯一事实。

实际会发生什么

理论假设每一米都独立地落在选定的地面上。真实的机器人是沿直线开的，所以连续的米之间是相关的——它会反复重扫自己正站着的那块地面。在覆盖模拟器里对五个房间实测的结果是：

这张表里有三件事，比本文其余所有内容都更值得注意。

**在覆盖前一半地面时，什么都不重要。**到 50% 时三种策略彼此差距都在 20% 以内。一台没有感知也没有记忆的机器人，在这份工作的前半程里确实和规划器一样好——这正是那个廉价做法在商业上可行、也是随意观察永远看不出差别的原因。

**随机的表现比它自己的理论更差。**99% 处实测 6.76×，而理论预测 4.61×，因为直线反弹会反复回到刚刚扫过的地面上。把 1 − e^(−d) 当成乐观的上界，而不是估计值。

**规划器完不成。**它停在 90.4% 就待在那儿了，这不是缺陷。

规划器为什么会留下十分之一的地面

覆盖规划器必须让机器人的身体避开每一面墙和每一条桌腿，所以它按机器人半径加上余量把每个障碍膨胀掉，只在剩下的空间里规划。落在外面的，就是机器人永远开不到的地面。

在实测中，规划器漏掉的 133 个格子里有 130 个位于墙或某件家具的两格之内。只有三个是空旷地面。这些漏扫不是散落的——它们是房间中每个障碍周围的一圈环。

这就解释了每一台商用机器的两个特征：

• **侧刷从底盘侧面探出去。**刷子比会碰撞的那个东西更宽，所以它能扫到轮子永远到不了的地面。
• **沿墙走一遍。**这是一个单独运行的行为，因为系统性扫荡在结构上就做不了这件事。

随机反弹最终靠运气能碰到那些边缘，这也是它唯一做得更好的地方。

行距的选择

对系统性扫荡来说，唯一真正的参数是行间距。

行距正好等于刷宽，那么任何一点航向误差都会在两行之间留下一条没清干净的条带——而之后没有任何东西会再找到它，因为规划以为那块地面已经完成。重叠 10–20% 就能把这些条带闭上，代价恰好是那个百分比的距离。

那份重叠，加上绕过家具的转场距离，就是规划器 1.35× 的来源。它不是浪费，而是一份能经受真实机器人接触的规划所要付的价钱。

还有两个看起来没那么重要、实际更重要的选择：

• **沿房间长轴走行。**每次转弯都要花时间却不覆盖任何新地面，所以行数减半就意味着转弯开销减半。
• 在行段之间规划路径，不要直接开过去。当家具把一行切成两段时，机器人必须绕过去。把这段转场当成穿越空闲空间的最短路来规划，是“一份规划”和“一个愿望”之间的区别。

每种策略各自需要什么感知

这才是这三种策略都存在的真正原因。

**随机反弹只需要一比特。**我是不是撞到了什么。两个碰撞开关加一个随机数发生器就是整台机器人。不需要编码器，不需要地图，不需要定位，也没有任何东西会漂移。

螺旋需要知道走了多远——相对于当前螺旋中心的距离，也就是一个粗略的里程计——好到能用来扩大半径，但不够好到能闭合一个回路。

**计划扫荡需要知道自己在哪里。**笔直的行、已知的转角、一个刷宽的横向步进，全都是里程计的断言，而里程计会漂移。走出十行之后，这些行就不再平行了。这就是为什么做规划的商用机器还要带一个陀螺仪、一个顶置相机或一个信标——规划器很便宜，而它假定的定位并不便宜。

所以策略是按感知预算选的，不是按算法有多优雅。先把随机那版做出来：它能工作，只有二十行，而且给出一个规划器必须超越的基线。

折算成分钟要花多少

还是那个 20 m² 的房间、250 mm 的刷子，以及一台以 0.25 m/s 巡航的机器人：

电池就是一份距离预算。0.25 m/s 下一小时续航是 900 m，随机策略足以舒服地覆盖一个房间，但覆盖不了三个——而正是这件事，而不是任何算法上的洞察，把市场推向了建图机器人。

出问题时

在覆盖模拟器里让三种策略跑同一个房间——运行时拖动家具，数字会跟着变。然后去做房间覆盖机器人，它从那个什么都不需要的策略起步，只在测量说值得的地方加上感知。