German Open 2014: Was wir planen zu tun…

Nachdem wir bei den Vorqualifikationen in Hannover den 2. Platz belegt haben, bereiten wir uns auf die deutschen Meisterschaften „German Open“ 2014 in Magdeburg vor.

Bis heute waren wir noch mit unseren Facharbeiten beschäftigt (dazu bald mehr :) ), weshalb recht wenig bis gar keine Zeit für den Roboter blieb. Generell wollen wir aber soweit nichts mehr ändern, der Roboter hat schließlich gut funktioniert. Lediglich in Richtung Kollisionserkennung wollen wir etwas Neues anfangen. Probleme gab es, wenn der Roboter recht nah an einer Wand war, er also noch keine Gelegenheit hatte, sich optimal anzupassen, und sich an der Wand ein Opfer befindet:

Roboter Problem

Wenn der Roboter schräg (auf das rot markierte Opfer [Fall 2] oder generell eine Wand [Fall 1]) aufkommt, bleibt er unter Umständen daran hängen und er verliert die Orientierung in der Karte. Um das Problem zu beheben, wollen wir mehr mit den nach vorne zeigenden Entfernungssensoren arbeiten. Wenn diese auf einmal eine sehr niedrige Distanz erkennen, muss der Roboter etwas nach links bzw. rechts korrigieren.

Diese Problematik hat uns schon letztes Jahr die Qualifikation zur WM gekostet und soll deshalb dieses Jahr vermieden werden. :)

Das sollte auch recht schnell implementiert sein und den Roboter nochmal etwas zuverlässiger machen.

Tag 2: Vorqualifikationen in Hannover: Erste Wettläufe

Heute standen die ersten beiden der drei Wertungsläufe an, nachdem wir noch etwas Zeit zum weiteren Testen des Roboters hatten. Der Roboter lief beim Testen sehr zuverlässig, wenn auch das ein oder andere Mal etwas recht knapp war. Hoffen und Bangen, dass nun ausgerechnet beim Wertungslauf etwas schief läuft, gibt es also immer 😉 Der erste Wertungslauf war dann perfekt, abgesehen davon, dass der Schwellwert für die Zeilenkamera zum Erkennen der schwarzen Flächen nicht richtig eingestellt war, weshalb die schwarzen Flächen einmal durchfahren wurden. Der Roboter muss dann an den Anfang des Raumes gesetzt werden; Nach aktuellen Regeln darf dem Roboter manuell die neue Position in der Karte mitgeteilt werden. Normalerweise würde der Roboter dann erneut durch die schwarzen Fliesen fahren, weil der Schwellwert und der berechnete Wert genau so wie vorher sind, allerdings haben wir hier einen Vorteil mit der Karte, denn der Roboter fährt dann normalerweise nicht erneut auf besuchte Fliesen. Insgesamt hatten wir so 230 von 250 möglichen Punkte, ein gutes Ergebnis.

Der zweite Wertungslauf verlief ohne besondere Vorkommnisse und wir konnten die in dem Parcours maximal mögliche Punktzahl von 250 Punkten erreichen. 😀 Aktuell stehen wir auf dem zweiten Platz. Der dritte Platz folgt mit einem Abstand von 100 Punkten.

Morgen ist noch der Finallauf (gewertet werden die besten 2 aus 3 Läufe) und dann war es das auch schon. Fotos folgen dann im Laufe der Woche, da die Internetverbindung hier recht langsam ist…

Tag 1: Vorqualifikationen in Hannover: Setup

Wie versprochen hier der Artikel für den ersten Tag. :)
Heute war Setup und es nicht so viel Besonderes passiert. Wir konnten einfach den ganzen Tag den Roboter testen. Am Anfang hat es noch hier und da gehakt, was aber einfach mit den Feineinstellungen des Roboters zusammenhing, die noch für den Parcours der Schule angepasst waren. Ein weiteres Problem gab es mit einem vorderen Entfernungssensor, der uns plötzlich nur noch Entfernungen bis ca. 20cm ausgegeben hat. Wir haben diesen Sensor dann testweise gegen einen der neuen Entfernungssensoren ausgetauscht, die bis zu 50cm funktionieren. Das war recht schnell erledigt, der Roboter hat dann auch schon super funktioniert.

Die Rampe war das größte „Problem“, aber auch das war nach Einstellen der Parameter behoben.

Insgesamt war der Tag wenig Ereignisreich. Morgen ist unser erster Wertungslauf um 11:50 Uhr, mal gucken, was dabei rumkommt :)

Vorbereitungen: Qualifikationsturniere in Hannover

Montag beginnt nun der Wettbewerb in der Saison 2014 für uns. In den letzten beiden Wochen haben wir uns, nachdem wir die Fehler in den Entfernungssensoren behoben haben, auf die Optimierung in Sachen Genauigkeit beim Fahren, besonders aber in Sachen Schnelligkeit konzentriert. Der Roboter fährt nun, obwohl die Sensoren früher drei mal schneller abgefragt werden konnten, genau so gut wie bevor die Probleme mit den Sensoren aufgetreten sind. Bei letzten Tests am Donnerstag ist unser Roboter leider die viel zu steile Rampe runtergerutscht und hat einen Plexiglaschaden erlitten, der aber einfach zu kleben sein sollte und die Funktion des Roboters nicht beeinträchtigt. Insgesamt sieht es sehr gut aus. :) Wir freuen uns auf den Wettbewerb.

Montag ist erst noch den ganzen Tag Setup, wir können also am Parcours unter Wettbewerbsbedingungen testen und Dienstag beginnt der Wettbewerb. Mittwoch sind dann die Finalläufe und die Siegerehrung. Wir werden versuchen, Euch via Twitter auf dem aktuellsten Stand zu halten, jeden Abend wird aber auch ein neuer Artikel erstellt. Versprochen 😉

Entfernungssensoren und ihre Tücken…

Nachdem es im letzten Monat große Fortschritte gab, ging es diesen Monat leider so gut wie gar nicht voran (deshalb gab es auch keine neuen Beiträge…).

Verursacht wurde diese Verzögerung durch die Entfernungssensoren des Roboters. Wir benutzen die analogen Sharp IR-Entfernungssensoren mit einer Reichweite von 4cm – 30cm. Diese Sensoren arbeiten optisch, nach dem Prinzip der Triangulation (mehr dazu hier). Vorteil dieser Sensoren ist, dass sie zum Einen sehr präzise sind (genau definierter Messpunkt (ca. 5mm Durchmesser, Auflösung ca. 3mm)) und zum Anderen sehr schnell neue Werte liefern (ca. alle 50ms Aktualisierung des analogen Ausgangs eines Sensors).
Wenn man bestimmte Dinge allerdings nicht beachtet (wie wir :/ ), hat man nichts davon; Die Werte rauschen und springen dann ohne Ende, sodass man nicht mehr vernünftig mit ihnen arbeiten kann (was fatal ist, denn ohne Entfernungssensoren geht gar nichts).

Wir mussten also die Ursache für das Rauschen finden: Nachdem wir die Hardware des Roboters als Ursache ausschließen konnten, haben wir näher direkt bei den Sensoren gesucht. Wir haben recht schnell herausgefunden, dass die Sensoren zum Einen bei Sonnenlicht nicht funktionieren (beim Wettbewerb kann uns das egal sein, denn erstens findet dieser in einer Halle statt und zweitens würden alle anderen Teams dann auch Probleme bekommen). Aber auch, wenn die Sonne nicht schien, lieferten die Sensoren unbrauchbare Werte. Die Sensoren müssen sich also irgendwie gegenseitig beeinflussen. In Frage kam da zu Beginn nur das Plexiglaschassis, welches den Strahl des Sensors vielleicht ungünstig reflektiert. Die Probleme traten allerdings auch auf, nachdem die Sensoren weiter nach unten gesetzt wurden und eine Reflexion durch das Plexiglas ausgeschlossen werden konnte.

Wir haben uns dann den Analogausgang der Sensoren genau auf einem Oszilloskop angesehen:

Rauschen
Das Rauschen und die Spikes sind wieder klar zu erkennen. Man sieht aber auch, dass sie periodisch auftreten. Nach einigem Hin- und Her und Tappen im Dunkeln haben wir die Ursache dann gefunden:

Schwingungen

Wie im Bild erläutert, beeinflussen sich die Sensoren gegenseitig (Interferenzen). Um das zu prüfen, haben wir einfach immer nur einen Sensor pro Richtung „sehen“ lassen und die anderen zugedeckt. Das Ergebnis ist das obere Bild.
Das periodische Rauschen tritt auf, weil die LED der Sensoren mit einer bestimmten Frequenz moduliert wird. Der Sensor reagiert dann nur auf Licht, das mit der gleichen Frequenz wieder beim Sensor ankommt. So soll ausgeschlossen werden, dass Umgebungslicht den Sensor stört (das Sonnenlicht hat allerdings ein sehr breites Spektrum, weshalb das dann nicht so gut funktioniert).
Man muss sich dann einmal das „aufgenommene“ Bild aus Sicht der Sensoren sehen. Ein Sensor sieht im Schlimmsten Fall dann drei Punkte auf einer Fläche (den eigenen Messpunkt und dem der anderen Sensoren) und kann nicht unterscheiden, welcher Messpunkt von ihm kommt. Die Messpunkt werden allerdings nur in periodischen Abständen sichtbar, weil die Modulationsfrequenz von Sensor zu Sensor minimal voneinander abweicht und nur in diesen periodischen Abständen identisch ist.

Eine erste Idee war dann eine Abschattung der Sensoren gegenseitig, sodass der Sensor nur noch einen eigenen Messpunkt sieht. Das hat leider nur für einen bestimmten Bereich funktioniert. Die einzige Lösung ist also, dass der Roboter pro Messung nur einen Sensor pro Richtung aktiviert. Das ist nicht optimal, aber leider gibt es keine andere Lösung. Dazu haben wir vor jeden Sensor in die Versorgungsspannung einen Transistor gebaut und die entstandenen Steuerleitungen von jedem Sensor zum Controllerboard geführt:

Steuerleitungen

Benötigt werden nur drei Pins am Mikrocontroller, da ja in jede Richtung ein Sensor gleichzeitig an sein darf. Nach einiger Programmiererei (da das ganze seeeehr zeitkritisch ist, weil wir ja so schnell wie möglich die neuen Werte der Sensoren haben wollen und die Kamera auch so schnell wie möglich ausgelesen werden muss) haben wir dann aber 100%ige Werte bekommen, ohne Rauschen.

Im folgenden Bild stellt das blaue Signal den Analogausgang eines Sensors dar und das gelbe Signal den Zeitpunkt, zu dem die Analog/Digital Wandlung im Mikrocontroller durchgeführt wird:

Wandlung

Man sieht, dass das Ausgangssignal zunächst ca. 3,5V liegt (der Sensor ist dann ausgeschaltet (!)). Der Sensor wird dann eingeschaltet (Signal fällt auf 0V) und der Sensor braucht ca. 45ms (rauschendes Signal, ca. 3V) bis er seinen Analogausgang wieder aktualisiert hat (Signal fällt) und der Mikrocontroller das Signal auslesen kann. Direkt danach wird der Sensor bzw. die Sensorgruppe wieder abgeschaltet und die nächste Sensorgruppe aktiviert. Da sieht das dann genau so aus.

Da wir so maximal drei Sensoren pro Seite abfragen, brauchen wir insgesamt 150ms, bis alle 10 Sensoren am Roboter einmal abgefragt wurden. Das ist auch das Maximum, wenn der Roboter länger brauchen würden, müsste die Geschwindigkeit, mit dem er durch den Parcours fährt, reduziert werden, weil er sonst zu träge reagiert.

Ein weiteres (kleineres) Problem, was wir dann beobachtet haben, ist, dass Sensoren einer Seite unter Umständen bei gleicher Entfernung nicht das gleiche Signal ausgeben, was zu Folge hat, dass sich der Roboter über die Differenz zweier Sensoren nicht mehr an der Wand anpassen kann. Deshalb haben wir für jeden Sensor noch eine Messreihe genommen und bekommen die Werte nun fast Millimetergenau und linear.

Nachdem wir das Problem endlich lösen konnten, werden wir uns nun weiter der Optimierung und ich mir meinem Facharbeitsthema widmen, bei dem ich mich ja mit der Implementation von SLAM auf unserem Roboter beschäftige… Mal sehen, was daraus wird, weitere Informationen dazu kommen noch. :)

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.

 

Viele, kleine Verbesserungen

Dieses Wochenende haben wir genutzt, um unser Programm mal etwas aufzuräumen und generell die Programmteile etwas zusammenzufügen. Im laufe der Zeit haben wir immer mal ein paar kleinere Teile z.B. von der Rampenerkennung oder dem Algorithmus zum Wiedereinsetzen eingebaut, was wir am Wochenende nun zu einem ganzen Teil zusammengeflickt haben. Hier eine kleine Liste, was genau wir verändert haben:

  1. Struktur (C-/Headerdateien): Unser Programm ist, wie es sich für jedes große Projekt gehört, in zahlreiche, einzelne Dateien aufgespalten, jede Datei für eine bestimmte Aufgabe (je nachdem, wie komplex die Aufgabe ist). Wir haben für die Zeilenkamera eine eigene Datei, für den Labyrinthlösealgorithmus und die Kartenzeichnung eine, für das Display mehrere etc. Diese Dateien sind miteinander verknüpft, sie bauen aufeinander auf (jede Datei hat noch eine eigene „Interface”-Datei, in der steht, auf welche Variablen und Unterprogramme andere Dateien zugreifen können). Da wir sowas zum ersten Mal machen und wir keine richtige IDE, die das normalerweise übernimmt, sondern einen Texteditor mit Syntaxhighlighting nutzen, war das Ganze nicht von Anfang an 100%ig sauber, was auch dazu geführt hat, dass wir Standard-C-Bibliotheken nicht richtig einbinden konnten, was wiederum zu wilden, nicht nachvollziehbaren Fehlermeldung beim Kompilieren geführt hat, weshalb wir das Ganze deshalb etwas aufgeräumt haben. Nun funktioniert das Einbinden von beliebigen Bibliotheken wieder 100%ig.
  2. Datenstrukturen: Wir haben die Übersichtlichkeit bzw. die Verständlichkeit weiter verbessert, indem wir einige neue Datenstrukturen eingeführt haben. Besonders, wenn es von einigen Dingen mehrere im Roboter gibt mit gleichen Eigenschaften, zum beispiel die Motoren oder die Temperatursensoren, ist das sinnvoll. Zuvor hatten wir Variablen die z.B. speed_l oder enc_r hießen. Zusammengefasst haben wir das Ganze mit Variablen, die nun mot.l.speed.to (Sollgeschwindigkeit des linken Motors) oder mot.r.enc (Encoder des linken Motors) heißen.
  3. Pointer: Pointer sind für uns recht neu, wir nutzen sie in unserem RoboCup Projekt bewusst erst seit Beginn dieser Saison. Durch der Nutzung von Pointern konnten wir die Dauer eines Hauptschleifendurchlaufs um 5 ms verbessern und liegen nun bei 16 – 18ms.
  4. Algorithmus zum Wiedereinsetzen: Algorithmus kann man das vielleicht nicht ganz nennen, aber gewissermaßen ist es das schon: Angenommen, der Roboter verfährt sich, weil er irgendwo hängenbleibt und die Karte stimmt nicht mehr. Damit die Karte nicht völlig zerstört wird, kann man für einen Punktabzug bei einem Wertungslauf eingreifen und den Roboter an eine neue Position setzen (alternativ würden wir ihn einfach machen lassen, er fährt dann mehr oder weniger zufällig umher und kann noch Opfer finden und startet irgendwann neu, muss man dann abwägen, was innvoller ist), die neue Position darf ihn dabei mitgeteilt werden. Problem ist dann nur der recht „dumme“ Algorithmus, den der Roboter zum Lösen des Labyrinths nutzt, der auf Markierungen in der Karte basiert. Damit der Roboter sich nach einem Eingriff nicht nur an einer neuen Position befindet, sondern auch an der Stelle mit dem Erkunden des Labyrinth weitermacht, müssen die Markierungen bis zu dem Zeitpunkt bzw. der Stelle rückgängig gemacht werden bzw. die danach ignoriert werden. Dazu speichert der Roboter einfach auf jeder Fliese eine fortlaufende Nummer, wenn die Position geändert wird, wird automatisch die Nummer auf der Fliese übernommen und alle Markierungen, die sich auf Fliesen mit einer höheren Zahl befinden, ignoriert. Theoretisch funktioniert das, praktisch muss das noch intensiv am Testparcours in verschiedenen Situationen getestet werden.
  5. Rampe: Dazu können wir noch nicht so viel sagen. Die Rampe soll sich dieses mal an jeder beliebigen Stelle befinden können (letztes Jahr haben wir die Rampe einfach anhand der Position des Roboters erkannt, was den Roboter besonders nach einem Neustart sehr unflexibel macht). Das Einzeichnen und Bewältigen der Rampe funktioniert auch, wenn der Roboter in der unteren Ebene des Parcours gestartet wird, allerdings noch nicht, wenn er oben gestartet wird (also als erstes eine Rampe nach unten gefahren werden muss und nicht nach oben; das ist wichtig, wenn der Roboter in der oberen Hälfte des Parcours neustarten sollte). Das werden wir auch weiter am großen Testparcours testen.
  6. Und wieder einmal haben wir die Fahrfunktionen des Roboters verbessert. Bei der Geradeausfahrt von einer Fliese wird nun, wenn sich unmittelbar hinter dem Roboter eine Wand befindet sich erst von der Entfernung her diese angepasst, genau so, wenn sich unmittelbar vor dem Roboter eine findet (dann entsprechend, nachdem bereits eine Fliese gefahren wurde). Das ist wichtig, damit Ungenauigkeiten, die beim Drehen des Roboters auf der Stelle aufgetreten sind ausgebessert werden.

Soweit, so gut. Morgen wird getestet, mal sehen, wie es aussieht.

Problem gelöst: Optimierungen der Fahranweisungen

Heute hatten wir wieder die Gelegenheit, den Roboter am großen Übungsparcours der Schule zu testen. Nachdem wir einige Fehler aus der Erkennung der Sackgassen beseitigt haben und diese nun auch perfekt funktioniert, haben wir uns wie geplant wieder mal den Fahranweisungen zugewandt und nach sorgfältiger Analyse des Verhalten des Roboters (Was macht der Roboter falsch? Warum macht der Roboter das falsch? Was könnte besser funktionieren? Wie kann man das Problem beheben?) endlich die Lösung zu einem elementaren Problem gefunden, das wir so ähnlich auch schon letztes Jahr hatten und was uns große Probleme bereitet hat: Wie man in dem letzten Video sehen kann, fährt der Roboter öfters mal frontal gegen die Wände. Das liegt daran: Intern fragen wir nicht ab, ob ein Sensor eine Wand sieht, sondern wir fragen in der Karte ab, ob sich vor dem Roboter eine Wand befindet, da eine Wand eine Fusion der Sensordaten ist (eine Wand wird nur eingezeichnet, wenn mehrere Sensoren mit unterschiedlichen Prioritäten die Wand erkennen) und diese Information somit zuverlässiger als der Wert eines einzelnen Sensors ist. Dazu gibt es für jeden Sensor einen Schwellwert. Gleichzeitig gibt es unserer Fahranweisung für die Geradeausfahrt einer Fliese eine normale Schwellwertabfrage für einen Sensor, die verhindern soll, dass der Roboter gegen eine Wand fährt. Wenn der Schwellwert in der Fahrfunktion nun höher definiert ist, als in der Kartenzeichnung, wird der Roboter die Fahrfunktion abbrechen, wenn er eine Wand sieht, aber noch keine Wand an der Stelle eingezeichnet haben. Er denkt sich also, dass er noch eine Fliese geradeaus fahren kann. Die Fahrfunktion bricht aber nicht sofort ab, sondern bedingt durch eine Statemachine und dem Scheduler erst nach ca. 100ms. Zusammen mit der Geschwindigkeitsregelung und der Trägheit des Roboters fährt der Roboter also erst noch ca. 200ms geradeaus, bevor er erneut abbricht und nun auch der Schwellwert aus der Kartenzeichnung für eine Wand zutrifft und diese somit eingezeichnet wird.
Wir haben die Statemachine in der Fahranweisung nun verbessert, sodass sofort abgebrochen wird, ohne erst etwas zu fahren, obwohl sich eine Wand vor dem Roboter befindet. Außerdem haben wir die Schwellwerte in der Karte geändert, sodass definitiv auch eine Wand eingezeichnet wird, wenn die Fahranweisung eine Wand erkennt und abbricht. Hört sich komplizierter an, als es. Es ist eigentlich eine total simple Änderung bzw. Anpassung, wir haben nur sehr lange gebraucht, bis wir auf diese Idee gekommen sind. Die ganze Sache wurde erschwert durch einen defekten Entfernungssensor, der nur noch in einem Bereich von 3 – 10cm anstatt 3 – 30cm Werte lieferte. Nun fährt der Roboter aber nahezu perfekt.
Als nächstes werden wir uns nun um die Rampe und den Algorithmus zum Ändern der Position kümmern. Wahrscheinlich haben wir dann vor dem Wettbewerb auch noch mehr als genug Zeit, um eine zuverlässige Erkennung von Hindernissen einzubauen.