Abdeckungsplaner-Simulator für Saugroboter

Steuerung

Strategie schaltet zwischen den dreien um. Der Raum wird neu aufgebaut und der Lauf sofort neu gestartet, denn eine Abdeckungszahl bedeutet nur etwas neben dem Raum, in dem sie gemessen wurde.

Ziehe jedes Möbelstück mit dem Zeiger oder wähle mit 1–4 eines und bewege es mit den Pfeiltasten. Der Lauf startet beim Ziehen neu. Stelle einen Tisch in die Raummitte und beobachte, wie die Distanz des geplanten Durchgangs steigt, während seine Abdeckung fällt.

Neuer Raum streut die Möbel erneut. Laufgeschwindigkeit tauscht Ruhe gegen Geduld — die Zufallsstrategie braucht mehrere tausend Züge, starte sie also schnell.

Theorie

Ein Pfadplaner beantwortet Wie komme ich hin. Ein Abdeckungsplaner beantwortet Wie berühre ich alles, und beide haben fast nichts gemein.

Der einzige ehrliche Maßstab ist die Distanz, die ein perfekter Roboter bräuchte. Bei Bodenfläche A und Bürstenbreite w braucht einmaliges Kehren ohne Wiederholung:

d_optimal = A / w

Alles, was das Labor meldet, ist ein Vielfaches dieser Zahl. Eine Strategie bei 1,2× verbringt 20 % ihres Lebens auf bereits bearbeitetem Boden; eine bei 8× sieben Achtel.

Zufallsprall hat eine geschlossene Form, und sie macht wenig Mut. Ein Roboter ohne Karte deckt neuen Boden proportional zum Rest ab, die unbedeckte Fläche klingt also exponentiell ab:

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

Das ist die gestrichelte Kurve im Diagramm. Lies drei Punkte ab: 63 % des Bodens nach einer Optimaldistanz, 90 % nach 2,3 und 99 % nach 4,6. Das letzte Raumzehntel kostet doppelt so viel wie die ersten drei Viertel — das Sammelbilderproblem mit Bürste.

Systematische Abdeckung ist linear und endet bei 1× plus Overhead für Reihenabstand und Wenden. In diesem Labor beträgt dieser Overhead etwa 35 %.

Die Messläufe liegen nahe an der Theorie, und wo sie abweichen, dann erwartbar: Ein echter Zufallslauf besucht nahen Boden erneut statt zu teleportieren, liegt also etwas schlechter als die Kurve unabhängiger Stichproben.

Algorithmus

Zufallsprall. Geradeaus fahren. Beim Anstoßen zufällig neue Fahrtrichtung wählen und prüfen, dass sie frei ist. Das ist alles und braucht ein Bit Sensorik und keinerlei Gedächtnis.

Spirale, dann versetzen. Um einen Winkel drehen, der umgekehrt proportional zur seit Zentrum gefahrenen Strecke ist — das zeichnet eine expandierende Spirale. Beim Anstoßen ein festes Stück geradeaus fahren und neue Spirale beginnen. Exzellent auf freier Fläche — eine Spirale überlappt fast nicht — und hilflos im vollgestellten Raum, wo jede Spirale nach wenigen Runden abbricht.

Geplante Schlangenlinien. Drei Schritte, und der zweite wird gern übersprungen:

1. Aufblähen. Jedes Hindernis um Roboterradius plus Sicherheitsabstand wachsen lassen. Was bleibt, darf die Robotermitte befahren.
2. Schneiden. Die aufgeblähte Karte in Reihen eine Bürstenbreite auseinander ablaufen. Jede Reihe wird zu einem oder mehreren freien Abschnitten.
3. Verbinden. Abschnitte in Schlangenreihenfolge besuchen und aufeinanderfolgende per kürzestem Pfad durch den Freiraum routen, sodass der Roboter ums Sofa herum statt hinein fährt.

Schritt 3 verursacht den Distanz-Overhead — darum straft ein voller Raum den Planer stärker als ein leerer.

Quellcode

Die Zufallsstrategie gehört zuerst auf einen echten Roboter, denn sie läuft mit vorhandener Sensorik:

// 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);
}

Der Prallwinkel muss zufällig sein. Feste Reflexion macht den Raum zum Billardtisch, und eine Billardkugel auf rechteckigem Tisch zeichnet eine geschlossene Bahn, die den Großteil der Fläche für immer verfehlt.

Der geplante Durchgang braucht obigen Aufbläh-Schneide-Verbinde-Lauf plus Odometrie, die eine gerade Reihe hält — eine andere Roboterklasse. Prototypisiere ihn hier, wo Position konstruktionsbedingt exakt ist, bevor du entscheidest, ob deine Hardware ihn trägt.

Annahmen und Unterschiede zur Hardware

Das Labor gibt dem Roboter perfekte Odometrie, perfekt bekannte Karte, instantanes Drehen auf der Stelle und eine Bürste, die einen sauberen Kreis deckt. Eine echte Maschine hat nichts davon.

Schlupf und Gyrodrift biegen die Reihen nach etwa zehn Zeilen auseinander — darum relokalisieren kommerzielle Roboter an Wänden, Deckenmerkmalen oder Baken. Wenden kostet Zeit, für die dieses Labor keine Distanz berechnet. Und die Bürste deckt keinen Kreis — sie deckt ein Rechteck hinter dem Roboter, Rückwärtsfahren über bearbeiteten Boden reinigt also nichts.

Der Abstand der Strategien überlebt alles. Schlägt ein Planer Zufallsprall hier um 3×, schlägt er ihn auf echter Hardware vielleicht um 2×; die Reihenfolge ändert sich nicht.

Schaltplan

Die Sensorik teilt sich sauber in drei Aufgaben, nur die erste ist Pflicht.

Bumper. Zwei Mikroschalter an vorderer Federstoßstange, aktiv-low an interruptfähige Pins mit internen Pull-ups verdrahtet. Diese Sensorik ermöglicht Zufallsprall und fällt als Letztes aus.

Abgrund. Abwärts-Reflexionssensoren an den vorderen Ecken, jeden Schleifendurchlauf gelesen. Ein Abdeckungslauf besucht überall — auch die Treppenoberkante. Die Arithmetik, wie weit der Roboter über die Kante fährt, bevor er stoppen kann, ist hier hergeleitet.

Position. Quadratur-Encoder an beiden Rädern, dazu ein Gyroskop, wenn Reihen parallel bleiben sollen. Nur die geplante Strategie braucht das — und das Brauchen ist der ganze Grund, warum die beiden anderen existieren.

Für die Abdeckungsstrategien als Bauvorhaben siehe den Raumabdeckungs-Roboter; für die reaktive Schicht darunter behandelt der Hindernisvermeidungs-Simulator Stopp-Schwellen und Abtastung.