Embedded Software
Der Weg ist das Ziel
Die Software kombiniert Floodfill-Suche, Pfadkompensation und Kurvenoptimierung, damit aus einem unbekannten Labyrinth eine schnelle Rennlinie wird.
Floodfill & Debugging
In der ersten Wettbewerbsphase erkundet die Maus das Labyrinth. Innerhalb von 10 Minuten sucht sie den kürzesten bzw. schnellsten Weg zum Ziel.
Floodfill-Algorithmus
Es gibt verschiedenste Möglichkeiten, ein Labyrinth zu lösen: Rechte-Hand-Regel, rekursives Rücksetzverfahren, shortest-way-finder und weitere Ansätze.
Durchgesetzt hat sich der Floodfill-Algorithmus. Da die Zielposition immer in der Mitte liegt, kann die Micromouse diese Information ausnutzen und mit möglichst wenigen Bewegungen den kürzesten Weg herausfinden. Das spart Zeit und senkt die Fehlerrate.
Funktionsweise
Zu Beginn wird das Feld initialisiert. Die Maus erhält ein Grundgerüst, das immer gleich aussieht: Alle Außenwände sind gesetzt und die Felder werden mit ihrem Abstand zur Zielposition durchnummeriert, als wären keine Wände vorhanden.
Danach werden die folgenden Schritte wiederholt, bis das Ziel erreicht ist:
- Wände scannen
- Zahlenwerte der Felder aktualisieren
- Zum kleinsten Zahlenwert fahren
Wurde das Ziel erreicht, wird geprüft, ob der kürzeste Weg bereits gefunden wurde. Falls nicht, probiert die Micromouse noch andere Wege, bis einer dieser Wege wieder zum Anfang vom Labyrinth führt.
Danach ist das Scannen des Labyrinths abgeschlossen und die Micromouse kann mit der schnellen Durchfahrt beginnen.
Verbesserungen im Masterprojekt
Der Floodfill-Algorithmus wurde bereits im Bachelorprojekt implementiert. Es traten jedoch noch Bugs auf, insbesondere im Zielbereich, wenn mehrere Möglichkeiten bestanden, das Ziel zu erreichen.
Der Floodfill-Algorithmus ist darauf ausgelegt, den kürzesten Weg zwischen zwei Punkten zu finden. Das Ziel umfasst jedoch vier Felder. Nachdem das Ziel mit dem Floodfill-Algorithmus gefunden wurde, wird intern ein Pfad vom Start zum Ziel berechnet, den die Maus anschließend abfährt. Ergibt sich währenddessen ein neuer, kürzerer Pfad, wählt die Maus diesen. Dadurch kann sich jedoch das Zielfeld ändern. Um dieses Problem zu lösen, wurde ein Kompensationsalgorithmus entwickelt, der die Maus im Zielbereich neu positioniert und korrekt ausrichtet.
Der nächste Schritt war die Erkennung von Streckensegmenten: lange Geraden, 90°-Kurven, 180°-Kurven und Diagonalen. Der kürzeste Pfad wird dabei als Folge von X- und Y-Koordinaten gespeichert. Anhand dieses Pfades können anschließend die einzelnen Streckensegmente bestimmt werden.
Geschwindigkeitsoptimierung
Voraussetzungen für schnelleres Fahren waren ein zuverlässig funktionierender Regler sowie ein korrekt berechneter Weg zum Ziel.
- Zu Beginn wurde die Strecke Feld für Feld abgefahren. Vor und nach jedem Feld hielt die Maus an und führte anschließend die folgende Bewegung aus.
- Im nächsten Schritt wurden mehrere aufeinanderfolgende Geraden zu einer langen Geraden zusammengefasst und ohne Unterbrechung durchfahren. Dadurch konnte die Geschwindigkeit auf den Geraden deutlich erhöht werden.
- Dynamisches Durchfahren von Kurven. Die Schwierigkeit war, Regler, Position, Algorithmus, Geschwindigkeit und Beschleunigung korrekt aufeinander abzustimmen.
- Dynamische Übergänge zwischen Geraden und Kurven. Die Geschwindigkeit nach einem Segment wird nicht auf 0 gesetzt, sondern direkt auf die Geschwindigkeit, die im nächsten Segment benötigt wird.
- Erkennung und Optimierung verschiedener Kurvensegmente. So werden beispielsweise mehrere aufeinanderfolgende 90°-Kurven als diagonale Strecke mit kleinen Übergangskurven gefahren. Zwei 180°-Kurven können hingegen als 135°-Kurve, gefolgt von einer Geraden und einer 135°-Kurve in die entgegengesetzte Richtung, umgesetzt werden.
- Analyse und Test unterschiedlichster Kombinationen von Streckensegmenten. Besonders kritisch sind kurze Geraden mit anschließenden präzisen Kurvensegmenten, da der Maus nur wenig Zeit bleibt, sich auf der Geraden korrekt auszurichten.
Bei allen Optimierungen musste stets zwischen maximaler Geschwindigkeit und sicherem Fahrverhalten abgewogen werden. Bei zu hohen Geschwindigkeiten konnte sich die Maus selbst auf langen Geraden nicht mehr ausreichend ausrichten, wodurch ein Crash in den nachfolgenden Kurven nahezu unvermeidbar wurde. Zudem spielte bei hohen Geschwindigkeiten auch Staub auf der Fahrbahn eine wichtige Rolle. Vor schnellen Durchläufen musste dieser daher entfernt werden, um eine zuverlässige Fahrt zu gewährleisten.