面向扫地机器人的覆盖路径规划模拟器

控件

策略用来在三种策略之间切换。房间会被重建，运行立即重新开始， 因为一个覆盖率数字只有放在它被测量的那个房间旁边才有意义。

用指针拖动任意一件家具，或者按 1–4 选中一件再用方向键移动。 拖动时运行会重新开始。在地板中央放一张桌子，看着计划扫荡的距离往上涨、 而覆盖率往下跌。

新房间会重新撒一遍家具。运行速度在平顺和耐心之间做交换—— 随机策略需要几千次移动才能跑完，所以一开始把它调快。

原理

路径规划器回答的是我怎么到那里。覆盖规划器回答的是我怎么把它全碰到， 而这两者几乎没有共同之处。

唯一诚实的衡量标准是一台完美机器人所需要的距离。对于面积为 A 的地面 和宽度为 w 的刷子，把每一格都扫到一次且从不重复，需要：

d_optimal = A / w

实验台报告的一切都是这个数字的倍数。一个 1.2× 的策略，把它 20% 的生命 花在重走已经扫过的地面上；一个 8× 的策略则花掉了其中八分之七。

**随机反弹有一个闭式解，而且它不令人鼓舞。**一台没有地图的机器人 碰到新地面的比例正比于尚未覆盖的部分，所以未覆盖面积按指数衰减：

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

这就是图上那条虚线。从它上面读三个点：一个最优距离之后覆盖 63% 的地面， 2.3 倍之后 90%，4.6 倍之后 99%。房间里最后那十分之一花掉的代价， 是前面四分之三的两倍——集邮难题，只不过拿刷子去做。

系统性覆盖是线性的，所以它在 1× 加上行距和转弯带来的额外开销处结束。 在这个实验台里，那部分开销大约是 35%。

实测的运行结果与理论相当接近，而偏离的方向也正是你预期的： 一次真实的随机游走会重访附近的地面，而不是瞬移过去， 所以它比独立采样曲线所暗示的略微更差。

算法

**随机反弹。**直行。撞到东西时，随机挑一个新航向并检查它是通畅的。 整个策略就这么多，它只需要一比特感知，完全不需要记忆。

**先螺旋，再重新定位。**转过一个与“自中心以来走了多远”成反比的角度， 这样就描出一条不断扩大的螺旋。撞到东西时，直线冲一段固定距离， 然后开始一条新的螺旋。在空旷地面上表现优异——螺旋几乎没有重叠—— 而在杂乱房间里却束手无策，因为每条螺旋转上几圈就被截断了。

**规划式蛇形扫掠。**三个步骤，而第二步是人们常跳过去的那一个：

1. **膨胀。**把每个障碍按机器人半径加上安全裕量扩大。剩下的是机器人中心可以到达的区域。
2. **切片。**在膨胀后的地图上按相隔一个刷子宽度的行往下走。每一行变成一段或多段自由区间。
3. **连接。**按蛇形顺序访问这些区间，并在相邻区间之间用一条穿过自由空间的最短路径来规划路线，让机器人是绕过沙发而不是撞上它。

距离上的额外开销正是来自第 3 步，这也是为什么杂乱房间对规划器的惩罚 比空房间更重。

源代码

随机策略是最值得先在真实机器人上做的一个，因为它只需要你手上已有的感知：

// Random-bounce coverage. Two bump switches, no map, no encoders.
const uint8_t BUMP_L = 2, BUMP_R = 3;
const uint16_t CRUISE = 170;      // PWM
unsigned long turnUntil = 0;
int turnDir = 1;

void loop() {
  bool left  = digitalRead(BUMP_L) == LOW;   // switches are active-low with pull-ups
  bool right = digitalRead(BUMP_R) == LOW;

  if (millis() < turnUntil) {                 // still executing a bounce
    drive(turnDir * CRUISE, -turnDir * CRUISE);
    return;
  }

  if (left || right) {
    // Back off first — turning while wedged against a chair leg does nothing.
    reverseFor(320);
    // A random turn between 90 and 270 degrees. The randomness is what stops the
    // robot tracing the same closed loop around the room forever.
    turnDir = right ? -1 : 1;
    turnUntil = millis() + random(420, 1250);
    return;
  }

  drive(CRUISE, CRUISE);
}

反弹角必须是随机的。一个固定的反射角会把房间变成一张台球桌， 而台球桌上的球在矩形桌里会描出一条闭合路径，永远漏掉大部分桌面。

规划扫掠需要上面那道膨胀—切片—连接的流程，再加上足以保持直线行走的 里程计，而那是另一个级别的机器人。先在这里做原型——在这里位置 在构造上就是精确的——再决定你的硬件扛不扛得住。

假设与硬件差异

实验台给了机器人完美的里程计、一张完全已知的地图、瞬时的原地转弯， 以及一把能刷出一个干净圆形的刷子。真实机器一样都没有。

轮子打滑和陀螺漂移会让行与行在大概十行之内就散开，这就是商用机器人 要靠墙面、天花板特征或信标来重新定位的原因。转弯要花时间， 而这个实验台不为此收取任何距离。而且刷子覆盖的不是一个圆—— 它覆盖的是机器人后方的一个矩形，所以在你已经扫过的地面上倒回去 什么也清理不掉。

策略之间的差距在这一切之后依然存在。如果一个规划器在这里比随机反弹 好 3 倍，那么在真实硬件上大概也好 2 倍；排序不会变。

电路图

感知干净地分成三件事，而只有第一件是必需的。

**碰撞。**弹簧式前保险杠上的两个微动开关，接成低电平有效， 接到支持中断的引脚上并打开内部上拉。这是让随机反弹成为可能的感知， 也是最后才会失效的那一个。

**悬崖。**装在前角的朝下反射传感器，每次循环都读一次。 一次覆盖运行会走遍所有地方，其中包括楼梯顶端—— 关于机器人越过边缘后还能走多远才停得下来的算术， 这里已经算好了。

**位置。**两个轮子上的正交编码器，如果你希望各行保持平行再加一个陀螺仪。 只有规划策略需要这一项，而需要它正是另外两项存在的全部理由。

要看把这些覆盖策略做成一台机器，见房间覆盖机器人； 至于它们底下的那层反应式逻辑，避障模拟器 讲了停车阈值和扫描。