Abdeckungsplanung: Einen ganzen Boden kehren

Ein anderes Problem als Ankommen

A* findet eine Route zu einem Ziel. Ein Abdeckungsplaner muss jedes erreichbare Quadrat berühren – was das Ziel völlig ändert: kein Ziel in der Nähe, keine Heuristik, die führt, und Erfolg ist nicht binär.

Das Maß, das es ersetzt, ist Strecke pro gekehrtem Quadratmeter. Mit Fläche A und Werkzeugbreite w kehrt ein perfekter Roboter jedes Quadrat einmal und wiederholt nie:

d_optimal = A / w

Ein 20-m²-Raum mit 250-mm-Bürste braucht 80 m. Jede Zahl unten ist ein Vielfaches davon – denn ein Vielfaches ist der einzige Vergleich, der einen Raumwechsel überlebt.

Das Gesetz, das Kehren ohne Karte regiert

Ein Roboter ohne Ahnung, wo er war, deckt neuen Boden proportional dazu ab, wie viel Boden noch unbedeckt ist. Das ist eine Differenzialgleichung mit einer Antwort:

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

Drei Punkte daraus ablesen und die Form des ganzen Problems erscheint:

Die letzten 9 % kosten mehr als die ersten 90 %. Das ist das Sammelbilderproblem mit angebauter Bürste – und die einzelne Tatsache, die jeden Staubsaugerroboter erklärt, den man je beobachtete.

Was wirklich geschieht

Theorie nimmt an, jeder Meter lande auf unabhängig gewähltem Boden. Ein echter Roboter fährt gerade Linien – aufeinanderfolgende Meter sind also korreliert: Er kehrt weiter den Fleck, auf dem er bereits steht. Vermessen über fünf Räume im Abdeckungssimulator:

Drei Dinge in dieser Tabelle wiegen mehr als der Rest dieser Seite.

Für die erste Bodenhälfte zählt nichts. Alle drei Strategien liegen bei 50 % innerhalb 20 % beieinander. Ein Roboter ohne Wahrnehmung und ohne Gedächtnis ist für die erste Jobhälfte wirklich so gut wie ein Planer – genau weshalb der billige Ansatz kommerziell tragfähig ist und beiläufige Beobachtung den Unterschied nie zeigt.

Zufall liegt unter seiner eigenen Theorie. 6,76× gegen vorhergesagte 4,61× bei 99 % – denn ein Geradenabprall besucht weiter Boden, den er gerade tat. 1 − e^(−d) als optimistische Schranke behandeln, nicht als Schätzung.

Der Planer wird nie fertig. Er stoppt bei 90,4 % und bleibt dort – und das ist kein Fehler.

Warum der Planer ein Zehntel des Bodens liegen lässt

Ein Abdeckungsplaner muss den Roboterkörper von jeder Wand und jedem Tischbein freihalten – bläht also jedes Hindernis um Roboterradius plus Marge auf und plant in dem, was übrig bleibt. Was außerhalb fällt, ist Boden, zu dem der Roboter nie fahren kann.

Im vermessenen Lauf lagen 130 der 133 Quadrate, die der Planer verfehlte, innerhalb zweier Zellen einer Wand oder eines Möbels. Nur drei waren offener Boden. Die Fehlstellen streuen nicht – sie sind ein Ring um jedes Hindernis im Raum.

Was zwei Merkmale jeder kommerziellen Maschine erklärt:

• Die Seitenbürste, die das Chassis überragt. Die Bürste ist breiter als das, was kollidiert – erreicht also Boden, zu dem die Räder nie gelangen.
• Die Wandfolgefahrt. Sie ist ein separates Verhalten, separat gefahren – denn die systematische Kehrfahrt kann sie strukturell nicht.

Zufallsabprall erreicht diese Kanten irgendwann, per Glück – das eine, worin er besser ist.

Reihen wählen

Für eine systematische Kehrfahrt ist der einzige echte Parameter der Reihenabstand.

Reihen exakt eine Bürstenbreite auseinander legen, und jeder Kursfehler überhaupt lässt einen ungereinigten Streifen dazwischen – und nichts später findet ihn, denn der Plan glaubt, dieser Boden sei fertig. 10–20 % überlappen lassen und die Streifen schließen sich – zum Preis von exakt diesem Prozentsatz an Strecke.

Diese Überlappung plus Transitstrecke um Möbel ist der Ort, woher die 1,35× des Planers kommen. Keine Verschwendung; der Preis eines Plans, der Kontakt mit einem echten Roboter überlebt.

Zwei weitere Wahlen, die mehr zählen, als sie aussehen:

• Reihen entlang der Raumlängsachse fahren. Jede Drehung kostet Zeit und deckt keinen neuen Boden ab – die Reihenzahl zu halbieren halbiert also den Drehaufwand.
• Zwischen Spannen routen, nicht fahren. Teilt Mobiliar eine Reihe in zwei Spannen, muss der Roboter herum. Diesen Transit als kürzesten Pfad durch Freiraum zu planen ist der Unterschied zwischen Plan und Wunsch.

Die Wahrnehmung, die jede Strategie verlangt

Das ist der echte Grund, warum alle drei existieren.

Zufallsabprall braucht ein Bit. Bin ich wo angestoßen. Zwei Bumper und ein Zufallszahlengenerator sind der ganze Roboter. Keine Encoder, keine Karte, keine Lokalisierung, nichts zum Driften.

Spiralen muss wissen, wie weit sie gefahren ist seit der Spiralenmitte – eine grobe Odometrie: gut genug, einen Radius wachsen zu lassen, nicht gut genug, eine Schleife zu schließen.

Eine geplante Kehrfahrt muss wissen, wo sie ist. Gerade Reihen, bekannte Drehwinkel und ein Seitwärtsschritt von einer Bürstenbreite sind alles Odometriebehauptungen – und Odometrie driftet. Zehn Reihen später sind die Reihen nicht mehr parallel. Darum tragen kommerzielle Maschinen, die planen, auch ein Gyro, eine Deckenkamera oder eine Bake – der Planer ist billig und die Lokalisierung, die er voraussetzt, nicht.

Die Strategie wählt also das Wahrnehmungsbudget, nicht die Algorithmeneleganz. Erst die zufällige bauen: Sie funktioniert, umfasst zwanzig Zeilen und liefert eine Basislinie, die der Planer schlagen muss.

Was es in Minuten kostet

Jenen 20-m²-Raum nehmen, eine 250-mm-Bürste und einen Roboter mit 0,25 m/s Marsch:

Ein Akku ist ein Streckenbudget. Eine Stunde Laufzeit bei 0,25 m/s sind 900 m – was einen Raum im Zufall bequem abdeckt und drei nicht abdeckt: und das, statt irgendeiner algorithmischen Einsicht, trieb den Markt zu kartierenden Robotern.

Wenn es schiefgeht

Alle drei gegen denselben Raum im Abdeckungssimulator fahren lassen – die Möbel verrücken, während er läuft, und die Zahlen wandern mit. Dann den Raumabdeckungsroboter bauen, der mit der Strategie beginnt, die nichts braucht, und Wahrnehmung nur dort ergänzt, wo die Messung sagt, dass sie sich lohnt.