Planung und Kartierung: Von Flood Fill zu SLAM
Du kannst eine Route durch ein bekanntes Raster planen, bei neuen Hindernissen umplanen und erklären, wie ein Roboter die Karte baut, auf der er plant.
Reaktive Navigation bringt einen Roboter durch einen Raum, ohne je zu wissen, wo er ist. Das endet schnell: Ein rein reaktiver Roboter lässt sich kein fahr in die Küche sagen und dreht in einem hufeisenförmigen Raum fröhlich ewig Runden. Planung ist die Antwort – und sie braucht etwas, das reaktive Regelung nie hat: eine Karte.
Dieser Pfad beginnt dort, wo die Karte gratis ist. In einem Labyrinth flutet Flood Fill Entfernungen vom Ziel nach außen und der Roboter läuft einfach bergab – mit sofortiger Umplanung, sobald er eine Wand entdeckt, die er offen vermutet hatte. Dann wird die Welt unordentlicher: A* plant über ein Belegungsraster, in dem Zellen Kosten haben, Hindernisse aufgebläht werden müssen und die Heuristik entscheidet, ob dein Planer schnell oder bloß korrekt ist.
Die letzte Station ist die ehrliche. Jeder Planer oben setzt voraus, dass du eine Karte hast – und ein echter Roboter muss eine bauen, während er auf Rädern fährt, die ihn anlügen. SLAM ist das, was geschieht, wenn Kartierung und Lokalisierung sich weigern, getrennt zu werden – und Loop Closure verhindert, dass sich die Karte verbiegt, während die Odometrie driftet. Eine IMU verdient sich hier aus demselben Grund ihren Platz: Sie misst Drehung direkt, was rutschende Räder schlicht nicht können.
Bevor du beginnst
Du solltest dich mit zweidimensionalen Arrays und algorithmischem Denken wohlfühlen – Queues und die Idee, Zellen in einer Reihenfolge zu besuchen. Der Motorsteuerungspfad lohnt sich vorher, denn jeder Planer hier setzt voraus, dass der Roboter eine befohlene Bewegung ausführen und grob melden kann, wie weit er kam.
Was du danach kannst
- Ein Raster mit Entfernungen von einem Ziel fluten und dem Gradienten hinab zum Ziel folgen.
- A* mit einer Heuristik fahren, von der du zeigen kannst, dass sie nie überschätzt – und erklären, warum genau diese Eigenschaft das Ergebnis kürzest macht.
- Entfernungsmessungen per Raycasting in ein Belegungsraster verwandeln – freie und belegte Zellen getrennt aktualisieren.
- Sagen, warum reine Odometrie über lange Strecken keine brauchbare Karte liefern kann und was SLAM hinzufügt.
Wo die meisten feststecken
Eine überschätzende Heuristik. A* garantiert den kürzesten Pfad nur, wenn die Heuristik nie eine größere Entfernung behauptet als die wahren Restkosten. Euklidische Distanz auf 4er-Raster oder eine hochskalierte Heuristik für schnellere Suche liefern lautlos Pfade, die nicht kürzest sind.
Für einen punktförmigen Roboter planen. Der Pfad wird durchs Raster gerechnet, aber der Roboter hat Breite. Eine Route, die eine Ecke streift, ist geometrisch gültig und physisch eine Kollision. Hindernisse vor der Planung um den Roboterradius aufblähen – und das Problem verschwindet.
Unbekannt als frei behandeln. Eine Zelle, die nichts beobachtet hat, ist nicht leer – sie ist ungemessen. Als Freiraum hindurchplanen, und der Roboter fährt selbstbewusst in das, was nie gesehen wurde. Unbekannt ist ein dritter Zustand und muss ein dritter Zustand bleiben.
Diagonalzüge kosten eins. Auf einem 8er-Raster deckt ein Diagonalschritt √2 Zellen ab, nicht eine. Als eins berechnen erzeugt Pfade, die Treppen bevorzugen, und Entfernungen, die schlicht falsch sind.
Annehmen, der Roboter sei dort, wo die Odometrie sagt. Jeder Planer hier operiert auf einer Pose. Radodometrie driftet unbegrenzt – ein perfekter Plan wird also von einer Position aus ausgeführt, die zunehmend fiktiv ist. Diese Lücke ist die gesamte Motivation für die letzte Station dieses Pfads.
Was du brauchst
| Was | Warum dieser Pfad es braucht | Hinweise |
|---|---|---|
| Sicherheit mit 2D-Arrays und Queues | Jeder Algorithmus hier ist eine Schleife über ein Raster | Keine höhere Mathematik; Queue und verschachtelte Schleife sind der ganze Werkzeugkasten |
| Ein Roboter, der befohlene Bewegungen ausführt | Ein Plan ist wertlos, wenn der Roboter ihn nicht fahren kann | Der Motorsteuerungspfad bringt dich dorthin |
| Ein Gyro oder eine IMU | Räder können keine Drehung messen, durch die sie gerutscht sind | MPU-6050; die Kartierungsstationen hängen am Kurs |
| Ein Entfernungssensor, idealerweise schwenkend | Zellen werden nur durch Messung bekannt | Ein servogeschwenkter Sonar reicht für ein grobes Raster |
| Etwas, um ein Raster darzustellen | Einen Planer durch Roboterbeobachten zu debuggen ist fast unmöglich | ASCII auf seriell ausgeben oder die Labore dieses Pfads nutzen |
Die beiden Labore laufen vollständig im Browser – die Flood-Fill- und Abdeckungsstationen gehen also ganz ohne Hardware.
Warum der Pfad in dieser Reihenfolge läuft
Das Labyrinth kommt zuerst, weil die Karte gratis ist. In einem Micromouse-Labyrinth ist die Welt konstruktionsbedingt ein Raster – Zellen haben bekannte Größe, Wände liegen auf Zellgrenzen, die Roboterposition ist immer ein Zellindex. Das beseitigt jedes Wahrnehmungsproblem auf einmal und lässt nur die Planung übrig – das, wofür du hier bist. Flood Fill in bekanntem Raster ist die sauberstmögliche Einführung in „Distanzfeld berechnen, dann bergab laufen“.
A* kommt als Zweites, weil es die Labyrinth-Annehmlichkeiten einzeln entfernt. Zellen haben nun Kosten statt bloß Wänden. Das Raster ist größer – alles zu expandieren ist verschwenderisch und eine Heuristik lohnt sich. Der Roboter hat Breite – Hindernisse müssen aufgebläht werden. Und Zellen können unbekannt sein – eine wirklich neue Idee, die das Labyrinth nie brauchte.
Belegungsraster kommen als Drittes, weil dort die Karte aufhört, gegeben zu sein. Raycasting verwandelt eine Entfernungsmessung in Evidenz über viele Zellen auf einmal – alles entlang des Strahls ist eher frei, der Endpunkt eher belegt –, und diese beiden getrennt zu aktualisieren ist die ganze Technik.
Die IMU sitzt hier absichtlich. Sie kommt genau an der Station, wo Kursfehler anfangen, sich in die Karte zu schreiben – denn ein Gyro misst Drehung direkt und rutschende Räder schlicht nicht.
SLAM kommt zuletzt, weil es das Eingeständnis ist, dass die vorherigen Stationen etwas Falsches annahmen. Jeder Planer oben operiert auf einer Pose, und jede Pose oben kam aus unbegrenzt driftender Odometrie. SLAM ist das, was geschieht, wenn man aufhört so zu tun, als ließen sich Kartierung und Lokalisierung getrennt lösen.
Abdeckung schließt den Pfad, weil sie das Problem ist, das am offensichtlichsten eine Karte braucht und am offensichtlichsten nicht reaktiv lösbar ist. „War ich überall?“ ist eine Frage, die nur Gedächtnis beantworten kann.
Kontrollpunkte: Woran man merkt, dass eine Stufe sitzt
| Stufe | Die Prüfung | Wie Bestanden aussieht |
|---|---|---|
| Flood Fill | Das Distanzfeld für ein kleines Labyrinth ausgeben | Das Ziel ist 0, Werte wachsen nach außen, und Wände erzeugen die erwarteten Umwege |
| Umplanung | Eine Wand aufdecken, die der Roboter offen vermutet hatte | Das Feld aktualisiert sich und der nächste Zug des Roboters ändert sich – ohne Neuerkundung |
| A*-Korrektheit | Auf einem Raster fahren, dessen Antwort du von Hand kennst | Jedes Mal dieselbe Länge wie der handgerechnete kürzeste Pfad |
| Zulässigkeit | Deine Heuristik absichtlich um 2× hochskalieren | Die Suche wird schneller und der Pfad länger – jetzt hast du den Zielkonflikt gesehen |
| Diagonalkosten | Über Freiraum auf 8er-Raster planen | Der Pfad ist eine gerade Diagonale, keine Treppe; Diagonalen kosten √2 |
| Hindernisaufblähung | An einer Ecke vorbei planen, Aufblähung aus, dann an | Aus streift der Pfad die Ecke; an hält er den Roboterradius Abstand |
| Belegungsraster | Einen Sensor über eine Türöffnung schwenken und das Raster rendern | Freiraum erscheint entlang der Strahlen, belegte Zellen an den Enden, Unbekanntes hinter Wänden |
| Unbekanntes behandeln | Deinen Planer in unkartierten Raum routen lassen | Er verweigert oder verpflichtet sich bewusst – beides in Ordnung, Raten nicht |
| Drift | Eine geschlossene Runde fahren und Kartenanfang gegen Kartenende vergleichen | Die Karte schließt nicht – diese Lücke ist exakt das, wofür Loop Closure existiert |
| Abdeckung | Eine geplante Kehrfahrt und einen Zufallslauf gleich lang fahren | Die geplante Kehrfahrt deckt weit mehr ab, und du kannst beide Prozentzahlen nennen |
Wo dieser Pfad endet
Dieser Pfad plant in einer statischen, zweidimensionalen, Größen-bekannten Welt. Jedes dieser Worte ist eine benennenswerte Grenze.
Statisch. Nichts hier behandelt eine Person, die durch den Plan läuft. Dynamische Hindernisse brauchen einen lokalen Planer unter dem globalen, der weit schneller umplant, als A* über ein ganzes Raster kann.
Zweidimensional. Ein Raster aus freien und belegten Zellen ist ein Grundriss. Es kann keinen Tisch darstellen, unter den man fahren, aber nicht hindurchfahren kann – weshalb ernsthafte Roboter 3D-Repräsentationen oder geschichtete Costmaps nutzen.
Rasterbasiert. Sampling-Planer wie RRT und RRT* behandeln hochdimensionale Räume – etwa den Gelenkraum eines Roboterarms –, in denen ein Raster hoffnungslos ist. Sie handeln die Kürzest-Pfad-Garantie gegen die Fähigkeit, überhaupt zu arbeiten.
Der Pfad deckt auch keine Partikelfilter oder Monte-Carlo-Lokalisierung ab – so findet sich ein Roboter in einer Karte zurecht, die ihm gegeben wurde, statt einer, die er baut. Das ist das einfachere und weit häufigere Problem – und gut zu wissen, dass es existiert, bevor man zum vollen SLAM greift.
Lern-Roadmap
Der Pfad
Folge den Knoten der Reihe nach – jeder schaltet den nächsten frei, sobald du ihn erledigt hast. Dein Fortschritt wird auf diesem Gerät gespeichert.
0 / 9 erledigt
Häufige Fragen
Häufig gestellte Fragen
Was ist der Unterschied zwischen Flood Fill und A* in der Roboterpfadplanung?
Flood Fill berechnet die Entfernung vom Ziel zu jeder Zelle des Rasters – der Roboter kann dann von überall, wo er gerade ist, bergab laufen. A* sucht von einem einzelnen Start zu einem einzelnen Ziel und expandiert nur Zellen, die eine Heuristik als vielversprechend vorschlägt. Flood Fill ist die richtige Wahl im Micromouse-Labyrinth, weil der Roboter ständig neue Wände entdeckt und alle paar Zellen von neuer Position umplanen muss – mit bereits berechneten Entfernungen jeder Zelle ist das gratis. A* ist die richtige Wahl auf einem großen Raster, wo man einmal von bekanntem Start plant und das Expandieren der ganzen Karte verschwenderisch wäre.
Warum schneidet mein A*-Pfad Hindernisecken?
Weil du für einen Punkt geplant hast und der Roboter Breite hat. Der Pfad ist geometrisch gültig durchs Raster und physisch eine Kollision – der Planer wusste nie, dass der Roboter mehr als eine Zelle belegt. Die Standardlösung: Jedes Hindernis vor der Planung um den Roboterradius aufblähen – belegte Zellen nach außen wachsen lassen –, damit jeder gefundene Pfad automatisch frei für den echten Roboter ist. Das ist viel einfacher und zuverlässiger, als während der Suche Freiraum prüfen zu wollen.
Was macht eine A*-Heuristik zulässig, und warum zählt das?
Eine zulässige Heuristik überschätzt die wahren Restkosten zum Ziel nie. Genau diese eine Eigenschaft garantiert, dass A* den kürzesten Pfad liefert – irgendwo überschätzen, und die Suche kann sich auf eine Route festlegen, die sie hätte verwerfen müssen. Die gängigen Arten, das zu brechen: euklidische Distanz auf 4er-Raster verwenden, wo die wahren Kosten Manhattan sind und immer mindestens so groß, sowie die Heuristik absichtlich hochskalieren, um die Suche zu beschleunigen. Letzteres ist eine echte Technik – sie handelt die Kürzest-Pfad-Garantie weg, und man sollte wissen, dass man handelt.
Brauche ich SLAM für einen Hobbyroboter?
Nur wenn der Roboter über eine lange Fahrt wissen muss, wo er ist, in einem Raum, für den ihm keine Karte gegeben wurde. Lässt sich eine Karte liefern, ist reine Lokalisierung viel einfacher. Ist der Raum klein genug, dass Odometriedrift erträglich bleibt – ein Labyrinth, ein einzelner Raum, wenige Minuten Fahrt –, braucht man es ebenfalls nicht. SLAM verdient seine Komplexität, wenn beide Bedingungen gleichzeitig scheitern – und das ist eine echte Schwelle, kein Abzeichen: Viele wirklich fähige Roboter brauchen es nie.
Warum verbiegt sich meine Belegungskarte während der Fahrt?
Weil Odometriedrift in die Karte geschrieben wird. Jeder Scan landet an der Pose, die der Roboter zu haben glaubte – ein langsam rotierter Kursschätzwert malt also einen geraden Korridor als Kurve in die Karte. An der Kartierung ist nichts falsch: Sie zeichnet treu eine Pose auf, die Fiktion ist. Genau das behebt Loop Closure: erkennen, dass der Roboter an einem Ort war, an dem er schon war, und die gesamte Trajektorie korrigieren, damit beide Beobachtungen übereinstimmen.
Warum dürfen unbekannte Zellen nicht als Freiraum behandelt werden?
Weil eine Zelle, die nichts beobachtet hat, ungemessen ist, nicht leer – und der Unterschied entscheidet, ob der Roboter in Dinge fährt, die er nie sah. Unbekannt als frei behandeln, und der Planer routet fröhlich durch ein Gebiet, das kein Sensor je abgedeckt hat – was meist genau dort ist, wo die Möbel stehen, denn verdeckter Raum und belegter Raum korrelieren stark. Unbekannt als eigenen dritten Zustand neben frei und belegt behalten – und bewusst entscheiden, ob ein gegebener Planer hindurchrouten darf.