Rampe und wie es weiter geht

Nachdem wir durch die Tiefensuche die Effizienz und Zuverlässigkeit des Roboters extrem steigern konnten, haben wir einige weitere kleinere Bugs beseitigt, darunter einige, die etwas mit der Rampe zu tun hatten.

Zum Einen werden nun auch die schwarzen Fliesen, die nicht vom Roboter überquert werden dürfen, richtig von der Tiefensuche umfahren. Diese wurden zu Beginn nicht richtig als nicht-befahren Fliesen vom Roboter erkannt (wir markieren ja jede befahrene Fliese, die schwarzen Flächen wurden nicht befahren, nicht markiert und die Tiefensuche dachte nun, das wäre die nächstgelegene, unbesuchte Fliese, der Roboter konnte aber keine Route dort hin finden (dürfen ja nicht befahren werden) und startete deshalb nach kurzer Zeit neu). Jetzt funktioniert das aber soweit. Auch der Ersatzsensor, der eingreift, wenn die Kamera versagt, funktioniert sehr gut und sehr zuverlässig.

Die Rampe sollte diese Saison universeller in die Karte eingezeichnet werden können, als letztes Jahr (da haben wir die Rampe einfach anhand der Position des Roboters erkannt; Das hat auch gut funktioniert, aber dieses Jahr sollte es ja egal sein, wo der Roboter startet; da kann man sowas deshalb nicht machen). Die Rampe wird nun mithilfe des Orientierungssensors erkannt und in die Karte eingezeichnet, unabhängig von der Position des Roboters. Der Roboter erkennt, wenn die Rampe zu Ende ist und wechselt in die obere Ebene des Speichers der Karte und macht dort normal weiter. Wenn er wieder runterfahren will, wird das nicht erneut über den Neigungssensor erkannt, sondern über die gespeicherte Position der Karte.
Wir betrachten die Rampe in der Karte als Verbindung der Ebenen. Wenn wir an einer Stelle in der Karte, an der sich die Rampe befindet, z.B. bei der Nachbarfliese abfragen, ob der Roboter dort bereits war, wird direkt der Wert der Fliese des oberen Rampenendes zurückgegeben. Auch, wenn wir den Roboter eine Fliese geradeaus fahren lassen und er dabei die Rampe überqueren muss, wird das wirklich nur als eine Fliese geradeaus gesehen. Die Rampe wird also quasi ignoriert und stellt im Programm eine Sprunganweisung zur nächsten Ebene dar.
Außerdem ist es nun möglich, den Roboter in der oberen Ebene starten zu lassen (wichtig, falls er, warum auch immer, oben neu starten sollte). Dann werden in der Karte die obere und untere Ebene vertauscht, wenn er die Rampe befahren hat.

Im Prinzip haben wir nun einen Wettbewerbsfähigen Roboter, von uns aus könnte es heute losgehen. :)
Als nächstes werden wir uns etwas damit beschäftigen, Hindernisse in die Karte einzuzeichnen und diese zu umfahren. Hindernisse können eine beliebige Form und Größe haben, sind aber mindestens 20cm groß und haben mindestens vier Ecken. Sie können überall platziert, es ist aber gewährleistet, dass der Roboter noch einen Weg um die Hindernisse finden kann. Ein Hindernis kann also auch so aussehen:

 

 

 

 

 

 

Wir haben schon einen Plan, wie wir sie in der Karte einzeichnen, aber dazu mehr, wenn wir den umgesetzt haben.

Im letzten Artikel haben wir auch etwas von Selbstortung erwähnt. An unserer Schule stehen die Facharbeiten an und ich werde mich etwas näher damit beschäftigen, einen Algorithmus zu entwickeln, der zum Einen erkennen kann, wenn die Position des Roboters nicht mehr mit der Karte übereinstimmt und zum Anderen ggf. sich selbst in der Karte wiederfindet und dann mit der Opfersuche weitermacht. Auch dazu aber mehr, wenn es soweit ist.

Vergleich: Tarry/Tiefensuche

Wir haben, nachdem wir die Tiefensuche erfolgreich implementiert haben, diese mit unserem alten Algorithmus (von Gaston Tarry) verglichen. Dazu haben wir eine kleine Testreihe gemacht: In einem 3×4 Fliesen großen Testlabyrinth haben wir den Roboter von 7 verschiedenen Positionen jeweils einmal mit dem alten und einmal mit dem neuen Algorithmus starten lassen und jedes mal die Zeit gemessen, die der Roboter dafür benötigte. Wir haben dann die Durchschnittszeit mit dem jeweiligen Algorithmus berechnet:

Wie man sieht, benötigt der Algorithmus von Gaston Tarry bei diesem Beispiellabyrinth also durchschnittlich 84 Sekunden, während die Kombination aus Tiefensuche und Rechte Hand Regel lediglich 60 Sekunden benötigt. Der Algorithmus von Gaston Tarry ist somit um 40% langsamer! Das gilt nicht nur für dieses Testlabyrinth, sondern wird sich generell in dieser Größenordnung bewegen, da der Algorithmus von Gaston Tarry jeden Übergang zwischen zwei Fliesen auf jeden Fall zwei Mal überfährt.

 

 

 

 

In diesen beiden Animationen sieht man in einem weiteren, kleinen Testlabyrinth den Unterschied deutlich:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Wie man sieht, fährt der der Roboter mit dem Algorithmus von Gaston Tarry fast schon kreuz und quer, während er mit der Tiefensuche strukturiert und logisch unbefahrene Fliesen sucht.

Meilenstein

Seit fast zwei Monaten gab es nun keinen neuen Artikel… Das lag sowohl daran, dass lange nichts großes passiert ist, aber auch daran, dass wir relativ wenig Zeit hatten und einige andere Dinge zu tun hatten. Wir versuchen nun, regelmäßiger neue Blogeinträge zu verfassen.

In diesen zwei Monaten (eigentlich in der letzten Woche) ist aber einiges passiert: Wir konnten unsere elementaren Fahranweisungen so verbessern, dass wir mit voller Geschwindigkeit durch den Parcours fahren können und das zusätzlich wesentlich präziser, als vorher. Zum Einen gab es einen Bug in der Geradeausfahrt, der erst nach genauer Analyse des Timings des gesamten Programms zum Vorschein kam: Die Geradeausfahrt wird nach genau 30cm beendet, ggf. wird zusätzlich zu Beginn, wenn sich eine Wand direkt hinter dem Roboter befindet, sich an dieser ausgerichtet, genau so am Ende der Geradeausfahrt, wenn sich nun eine Wand vor dem Roboter befindet. Wenn sich keine Wand vor dem Roboter befindet, bestimmen die Motorencoder, wann 30cm gefahren wurde. Wenn diese diesen bestimmten Schwellwert erreicht haben, wird der Status der dafür zuständigen Statemachine geändert. Das wurde unter Umständen allerdings erst ca. 150ms später von der übergeordneten Statemachine (die entscheidet, wie der Roboter nun weiterfahren soll) erfasst, weshalb der Roboter in diesen 100ms mit letzter Geschwindigkeit weiterfährt. Der Roboter ist in dieser recht kurzen Zeit aber schon ca. 1cm weitergefahren, was in Summe eine große Ungenauigkeit ergibt. Das Problem konnten wir einfach beheben, indem die Statemachine für diese Fahranweisung einfach selbst die Sollgeschwindigkeit nach 30cm Fahrt auf 0% setzt. Das hat zufolge, dass der Roboter nach jeder Fliese kurz anhält, was aber nicht so schlimm ist und eventuell sogar positiv zur Genauigkeit der Karte beiträgt (da bei diesem Stop die Karte aktualisiert wird).

Weiterhin konnte die Fahranweisung zum 90° Drehen optimiert werden: Nachdem der Roboter sich mithilfe des Orientierungssensors 90° gedreht hat, passt der Roboter sich an die Wand an (falls eine vorhanden ist), sodass er genau rechtwinklig dazu steht. Bis jetzt wurde sich einfach eine bestimmte Zeit lang angepasst, nun wird mit dem Programm schon fortgeführt, wenn der Roboter wirklich rechtwinklig zur Wand steht (der Timer war beim alten Roboter aufgrund der Trägheit der Geschwindigkeitsregelung notwendig).

Apropos Timer: Wir haben bei den Fahranweisungen viele Timer hinzugefügt, die nach einer bestimmten Zeit die aktuelle Aktion abbrechen (wenn der Roboter z.B. über einem Speedbump o.Ä. hängenbleiben sollte, versucht er nicht für immer, so lange geradeaus zu fahren, bis ein Schwellwert erreicht ist, sondern bricht nach einer bestimmten Zeit ab).

Kommen wir aber nun zur größten Änderung: Wir haben uns kurzfristig dazu entschieden, uns von dem bis jetzt verwendeten Labyrinthlösealgorithmus von Gaston Tarry zu trennen. Mit diesem Gedanken haben wir schon länger gespielt, aber einen konkreten Grund gab es bis jetzt noch nicht. Allerdings ist der Tarry Algorithmus unglaublich unflexibel, was mit den Markierungen, die am Boden gemacht werden, zu tun hat. Diese Markierungen entstehen quasi kreuz und quer und es ist nur schwierig zurückzuverfolgen, wann Markierungen gemacht wurden. Das ist wiederum wichtig, wenn ein LOP auftritt (was der Fall ist, wenn eine schwarze Fliese überquert wird) und der Roboter an den Anfang des Raumes gesetzt werden muss, dann lässt sich mit den Markierungen nämlich nichts mehr anfangen. Man könnte für jede Markierung den Zeitpunkt speichern, wann sie gemacht wurde, was jedoch einen immensen Speicherverbrauch mit sich ziehen würde und aufgrund des doch mit 8kB recht stark begrenzten RAMs für uns keine Option war. Wir brauchen also einen Algorithmus, der wesentlich flexibler ist und auch noch nach einer Positionsänderung alle noch nicht angefahrenen Fliesen, auf denen sich Opfer befinden kann, anfahren kann.
Wir haben uns letztes Jahr bei den deutschen Meisterschaften schon umgehört, wie die anderen Teams mit Navigation das so machen und ein Konzept, was auch schon ähnlich bei unserem Partnerteam bei der Weltmeisterschaft in Mexiko angewandt wurde, hat uns besonders gefallen: Eine Kombination aus rechte Hand Regel und einem Algorithmus, der im Labyrinth nach unbefahrenen Fliesen sucht und den Pfad dorthin berechnen kann. Das Konzept stand recht schnell und an einem Abend intensiver, konzentrierter Programmierarbeit war auch alles soweit implementiert, dass es bereits mit den ähnlichen Resultaten arbeitete, die der Roboter auch mit dem Tarry Algorithmus lieferte. Im Folgenden eine kleine Erläuterung des neuen Konzepts mit Bildern:

Man nehme das folgende, kleine Beispiellabyrinth mit Insel, die mit der rechten Hand Regel so nicht komplett untersucht werden kann.

Man nehme das folgende, kleine Beispiellabyrinth mit Insel, die mit der rechten Hand Regel so nicht komplett untersucht werden kann.

 

Der Roboter fährt nun mithilfe der rechten Hand Regel durch das Labyrinth, erstellt die Karte und markiert bereits besuchte Fliesen in der Karte.

Der Roboter fährt nun mithilfe der rechten Hand Regel durch das Labyrinth, erstellt die Karte und markiert bereits besuchte Fliesen in der Karte.

 

Wenn mithilfe der rechten Hand Regel eine bereits besuchte Fliese befahren werden würde, wird nach Nachbarfliesen gesucht, die noch nicht befahren wurden, ggf. werden sie nun befahren. Jetzt hat der Roboter aber keine Ausweichmöglichkeiten mehr, denn vorne und links befindet sich eine Wand und die Fliesen rechts und unterhalb des Roboters wurden bereits befahren.

Wenn mithilfe der rechten Hand Regel eine bereits besuchte Fliese befahren werden würde, wird nach Nachbarfliesen gesucht, die noch nicht befahren wurden, ggf. werden sie nun befahren. Jetzt hat der Roboter aber keine Ausweichmöglichkeiten mehr, denn im Norden und Westen befindet sich eine Wand und die Fliesen im Osten und Süden wurden bereits befahren (Himmelsrichtungen in Relation zum Roboter).

Mithilfe der Tiefensuche (Depth-First-Search Algorithmus) wird nun die nächstgelegene, unbefahrene Fliese gesucht. Dazu werden von der aktuellen Position des Roboters aus die Nachbarfliesen durchnummeriert, von da aus immer weiter (siehe rote Zahlen im Bild). Die erste, unbefahrene Fliese, die so erreicht wird, ist die nächstgelegene, unbefahrene Fliese, die der Roboter besuchen kann.

Mithilfe der Tiefensuche (Depth-First-Search Algorithmus) wird nun die nächstgelegene, unbefahrene Fliese gesucht. Dazu werden von der aktuellen Position des Roboters aus die Nachbarfliesen durchnummeriert, von da aus immer weiter (siehe rote Zahlen im Bild). Die erste, unbefahrene Fliese, die so erreicht wird, ist die nächstgelegene, unbefahrene Fliese, die der Roboter besuchen kann.

Von dieser nun gefundenen Fliese wird der Algorithmus umgekehrt angewandt, bis der Roboter erreicht wird. Der Roboter muss nun die Zahlen der Größe nach Verfolgen und gelangt so zur gesuchten, nächstgelegenen unbefahrenen Fliese. Der Roboter würde nun versuchen, mit der rechten Hand Regel fortzufahren, was hier allerdings nicht möglich ist. Es würde erneut die nächstgelegene, unbefahrene Fliese gesucht werden.

Von dieser nun gefundenen Fliese wird der Algorithmus umgekehrt angewandt, bis der Roboter erreicht wird. Der Roboter muss nun die Zahlen der Größe nach verfolgen und gelangt so zur gesuchten, nächstgelegenen, unbefahrenen Fliese um dort zu kontrollieren, ob sich Opfer an den Wänden befinden.
Der Roboter würde nun versuchen, mit der rechten Hand Regel fortzufahren, was in diesem Fall allerdings nicht möglich ist. Es würde nun erneut die nächstgelegene, unbefahrene Fliese gesucht werden.

So lassen sich sehr effizient und zuverlässig alle Fliesen des Labyrinths abfahren. Mit dem gleichen Algorithmus kann zudem zum Schluss, wenn alle Fliesen befahren wurden, zur Startfliese zurückgekehrt werden.

Weiterhin ermöglicht uns diese Art und Weise, das Labyrinth zu lösen, den Roboter einfach selbst korrigieren zu lassen (der Roboter könnte also in Zukunft erkennen, wenn seine Positionen von den Daten, die er bis jetzt in der Karte gesammelt hat, abweicht (wenn er z.B. irgendwo hängengeblieben ist) und sich selbst die eigentliche Position suchen. Bis das umgesetzt ist, wird allerdings noch einige Zeit vergehen, das ist erstmal auch nicht unser primäres Ziel 😉 ).

Soweit zum aktuellen Stand. Als nächstes müssen wir den Roboter im großen Testparcours der Schule testen, bald werden wir dann auch mal ein neues Video hochladen. Dann werden wir die Rampe implementieren, was recht kompliziert ist (auch der DFS-Algorithmus muss diese ja erkennen und nutzen können zum Berechnen des Pfades).

Insgesamt stehen wir sehr gut im Zeitplan (ansonsten wären wir auch nicht das Risiko eingegangen, unser altes Konzept zu verwerfen). Die Vorqualifikationen in Hannover beginnen in 45 Tagen, in dieser Zeit sollte es ohne Probleme möglich sein, unseren Roboter so weit zu verbessern, dass er gut bis sehr gut funktioniert.