Odometrie oder die Kunst einen Weg für den Roboter zu finden:
Definition Odometrie laut Wikipedia:
Odometrie oder auch Hodometrie (von griech. hodós, „Weg“ und métron, „Maß“ - also: „Wegmessung“) ist die Wissenschaft von der Positionsbestimmung eines mobilen Systems anhand der Daten seines Vortriebsystems. Durch Räder angetriebene Systeme benutzen hierzu die Anzahl der Radumdrehungen, während laufende Systeme (z. B. Roboter) die Anzahl ihrer Schritte verwenden. Ein Gerät, das die Odometrie zur Positionsbestimmung verwendet, ist ein Odometer. Die Odometrie ist im Zusammenspiel mit der Koppelnavigation ein grundlegendes Navigationsverfahren für bodengebundene Fahrzeuge aller Art (Kfz, Roboter), allerdings wird es auf Grund seiner Fehlereigenschaften selten als alleiniges Verfahren eingesetzt.
Schnell und einfach erklärt, aber was nun?
Klar, schaut man doch mal schnell unter Google nach, wer da mal was programmiert hat.
Aha ja, doch soviel :-)
Ok, ein Filter muss her:
- Ich mag nun mal klassisches C++ --> Immer noch nichts richtiges
- Hmm, Implementierung, Programmierung, „Pathfinding“
Die Liste könnte man nun recht lange ausführen.
Richtig gute Erklärungen findet man z.B. an Universitäten: Ausarbeitungen, Diplomarbeiten und allg. Studienunterlagen. Am Ende dieses Berichtes werde ich einige gute Ausarbeitungen auflisten, die ich selbst als sehr hilfreich empfunden habe.
Nun, die Verzweiflung war groß, also selbst ist der Mann, kann doch nicht schwer sein ein Programm zu schreiben bei dem ein Weg um Hindernisse gefunden wird.
Mittlerweile war mir klar, ich probier das mal zuerst am PC mit einem DOS- Fenster als Testumgebung aus, bevor ich den Roboter einmal zu oft gegen die Wand fahre :-)
Gemein wie ich mir das so vorstellte, war das Ziel „Z“ schön hinter den Hindernissen versteckt.
Hoppla, doch ein paar viele IF – IF ELSE - etc… Abfragen, um ein „X“ von Startpunkt „S“, um ein paar Hindernisse herum zu manövrieren. Geschweige denn, dass der Algorithmus, oder besser die Abfragen noch funktionieren wenn man mal das Hindernis in der Lage verändert.
ALLGEMEINE ERNÜCHTERUNG FOLGTE:
Also zurück ins Netz und Google. Ahhhhh, überall Hinweise die auf Pathfinding mit einem „A-Star“ Algorithmus hindeuten.
Häääh. Hey, ich bin 45 Jahre alt, arbeite hauptberuflich in einer Bank als Controller und meine C++ Kenntnisse und Syntax sind aus dem Jahr 1994, als ich meine Diplomarbeit geschrieben habe und nun soll ich verstehen was die Studenten von heute so programmieren. Übersetzer bitte … Also vergessen wir mal schnell die fertigen Programme (Source-Code) aus dem Internet.
Okay, man nehme sich die Algorithmusbeschreibung und programmiert das ganze mal in seinem eigenen Stil. Das hat dann auch geklappt und den Sourcecode habe ich an den Artikel angehängt U N D in meiner alten, schönen Syntax programmiert, so wie halt vor 20 Jahren hä, hä, hä ...
Ach ja, ob ich die Algorithmusbeschreibung richtig umgesetzt habe weiß ich nicht, aber mein PC Beispielprogramm hat einen Lösungsweg berechnet. Ist doch schon mal was und eine einfache C-Sourcecode Lösung lässt sich einfacher auf einen Mikrocontroller transferieren.
Gut: Wir haben jetzt eine Lösung, und sieht doch richtig hübsch aus, wie der PC den Weg zum Ziel findet. Berechnet wurden 450 Knoten.
Knoten, da war doch noch was: Der Algorithmus funktioniert nur, wenn der Weg von Startpunkt zu Zielpunkt in Knoten, oder auch Felder genannt, eingeteilt ist. Diese Knoten können Rechtecke sein oder auch Dreiecke, ist eigentlich egal.
- -) O D E R doch nicht :-)
Jetzt kommt nämlich der Teil mit dem Roboter und dem PC. Also auf einem PC war das ganz einfach zu programmieren (Naja, einfach…), eine zweidimensionale Matrix mit Feldern gefüllt „#“ als Hindernis und seitliche Begrenzungen / Ränder die den Wirkungsbereich eingrenzen.
Jetzt muss ich einmal sagen, dass meine „Life“ Testumgebung, auch verächtlich von meiner Freundin Wohnzimmer genannt, nun mal nicht in Felder eingeteilt ist. Ein Versuch der von meiner Freundin, unter Androhung eines Platzverweises, sabotiert wurde.
Was nun, wie erkenne ich den die Hindernisse?
Wo ist mein Startpunkt?
Wo ist mein Ziel?
Der Roboter hat nun mal nur Bumper und IR-Sensoren. GPS in der Wohnung geht auch nicht.
Also, entweder muss ein anderer Algorithmus her, oder die Möglichkeit, die Position des Roboters, des Ziels und der Hindernisse genau zu lokalisieren.
Es gibt solche Möglichkeiten z.B. IR Baken, oder eine Kamera an der Decke, die die Position der Hindernisse und des Roboters bestimmt. Klar, nur wie bekomme ich z.B. die Daten in den Roboter, der ja eigentlich autonom arbeiten soll.
Also wieder das Internet befragt, bzw. hatte ich in einigen der Ausarbeitungen etwas von Algorithmen gelesen, die ohne Knoten auskommen, dann aber nur die Hindernisse umfahren und keinen optimalen Weg suchen von Start zum Ziel.
Also fahren wir mal um ein Hindernis herum war das neue Ziel der Programmierung. Erst mal wieder auf dem PC verwirklichen, soweit war ich dann schon mal in den Überlegungen. Doch wie sollte es weitergehen.
Schließlich wurde ich fündig und der einfachste der Algorithmen mit dem hübschen Namen BUG2 (Bug engl. Kakerlake oder auch Fehler) hatte es mir angetan. Es gibt weitaus bessere Algorithmen, die aber auch wesentlich komplexer sind.
So als Abfallprodukt, beim lesen der Ausarbeitung gelernt: Wie kommt man eigentlich aus einem Labyrinth heraus? Ganz einfach z.B. die rechte Hand immer an der Wand des Labyrinth vorbeiführen, somit ständiger Kontakt mit der rechten Wand herrscht. Dauert halt lange, aber man kommt aus dem Labyrinth heraus.
Die Frage meiner Tochter (13 Jahre) gestellt, wie kommt man aus einem Labyrinth heraus. „Mann, Papa“ weiß doch jeder, rechte Hand an der Wand halten.
Woher wissen die Kids das heute so einfach, war vielleicht doch eine PISA-Frage ?!?
Der BUG2 Algorithmus, oder die Suche nach dem nicht immer optimalen Weg zum Zielpunkt.
Wie komme ich eigentlich von Punkt A nach Punkt B ohne eine Karte. Treffer und versenkt ! Hier wir es nämlich richtig schwierig, da wir uns auf dem Feld der Navigation tummeln müssen. Im Klartext, ich habe wieder das Problem, dass ohne ein GPS eigentlich nix richtig funktioniert.
ODER DOCH ?!
Es gab auch mal eine Zeit vor GPS und da hat man so ein komisches Ding mit Zahlen und einem immer nach Norden zeigender Nadel benutzt. Richtig, einen Kompass… Einen elektronischen Kompass für den Robby gibt es schon und auch gleich mit I²C Schnittstelle zum Datenaustausch.
So frisch ans Werk, was haben wir denn nun… Einen Kompass und einen Kompass ??? Ich kann also den Roboter genau in der Testumgebung (Wohnzimmer) in Richtung 180° fahren lassen, was dann Süden wäre. Toll, aber irgendwie auch ernüchternd, denn der Kompass weist nur die Richtung aber, verflixt noch mal wann soll der Roboter den aufhören zu fahren und zurück melden, Ziel erreicht. Die einfache Lösung, solange fahren bis er gegen das Ziel fährt … schlecht, wenn das z.B: eine Mingvase wäre, oder man doch die Katze über den Haufen fährt … da ist man dann schnell wieder bei dem Punkt Platzverweis! Was kann denn nun weiterhelfen. Hier kommen wieder die IR-Baken zum Einsatz. Wie bei der Navigation von Schiffen benötigen wir vermessene Fixpunkte (In der Seefahrt, markante Punkte an der Küstenlinie wie Leuchttürme oder Kirchtürme). Solche Punkte sind z.B. in Seekarten eingetragen. Die Umsetzung dieses Themas kommt in dem Teil zwei, wo wir uns mit der Navigation näher beschäftigen wollen. Jetzt zurück (ach ich liebe diese Abschweifungen) zum Problem der Realisierung eines BUG2 Algorithmus auf dem PC.
Allgemeine Beschreibung des BUG 2 Algorithmus
nach Vladimir Lumelsky & Alexander Stepanov: Algorithmica 1987
Vorraussetzungen:
1. Die Richtung (hier oft auch m-Line genannt) zum Ziel muss bekannt sein, z.B. durch einen Kompass
2. Es sind entsprechende Sensoren am Roboter vorhanden, die ein Hindernis durch Berührung oder auf Entfernung durch z.B. Infrarotsensoren erkennen können
3. Die Erkennung mittels IR Sensoren muss linear sein z.B. 10 – 80 cm entspricht einer Spannung von z.B. 1 – 5 Volt am Ausgangsport, sonst wird’s etwas holperig, aber nicht unlösbar
Grundsätzliches Vorgehen beim BUG 2 Algorithmus:
– Bewege dich gerade auf einer Linie Richtung Ziel
– Folge immer der Wand des Hindernisses (z.B. rechts herum)
Algorithmus-Beschreibung:
1) Folge der m-Line in Richtung des Ziels. Bewege dich gerade auf einer Linie Richtung Ziel
2) Wenn ein Hindernis im Weg ist, umfahre das Hindernis ( Folge der Wand ) bis Du wieder auf die m-Line triffst, welcher näher zum Ziel ist, sonst Abbruch
3) Verlasse das Hindernis und folge der m-Line weiter in Richtung Ziel
Prinzipelle Vorgehensweise als Zeichnung:
Der Roboter fährt um das Ziel herum bis er wieder auf die m-Linie trifft. Von dort aus weiter zum Ziel.
Das wäre der BUG2 Algorithmus.
Der Vorgängeralgorithmus BUG1 wurde so entworfen, dass er erst mal das ganze Hindernis umrundet, sich den Punkt merkt, wo er wieder auf die m-Linie trifft und von dort dann bei der zweiten Umrundung von dort weiter in Richtung ziel fährt. Die gefahrene Strecke ist somit größer als beim BUG2 Algorithmus. In den Ausarbeitungen (siehe Literaturliste) wird dann noch auf die Vor –und Nachteile der einzelnen Algorithmen eingegangen. Interessiert uns ja nicht, da wir den BUG2 Algorithmus gewählt haben :-):-):-)
Schauen wir uns nun mal die genannten Vorraussetzungen im Einzelnen an:
Richtungsvorgabe (m-Linie). Hier hatten wir einen Kompass gewählt. Glück gehabt, gibt es anschlussfertig zu kaufen.
Entfernungsmesser z.B. Infrarotmesser. Wichtig ist für meine Implementierung, dass der Entfernungsmesser analog ist, also die Entfernung misst und in Volt ausgibt.
Schauen wir uns die IR-Entfernungsmessung etwas genauer an. Im Bild wird die Funktionsweise deutlich. Ein Erkennen und anschließende Abtastung des Hindernis ist für den Roboter somit möglich.
In der Zeichnung des Roboters wird klar, dass man ständig die drei Sensoren abfragen muss, ob und wie weit das Hindernis entfernt ist. Ebenfalls müssen zwei weitere Parameter gespeichert, bzw. ausgewertet werden, bei der Veränderung der Richtung des Roboters. Die Richtung in die sich der Roboter auf Grund der Ergebnisse, die die IR-Sensoren liefern bei der Abtastung nach Hindernissen, bewegt. Ebenfalls benötigen wir die Information was die letzte gespeicherte Richtung war bevor ich eine neue Richtung einschlage.
WARUM: Bewege ich mich vom Ziel weg, ist es wichtig zu wissen
- wo her ich komme
- wohin gehe ich.
Ich denke das folgende Bild sollte das Problem erklären.
1) Der Roboter „sieht“ den Weg vor sich frei, kein Sensor signalisiert ein Hindernis.
2) Es ist klar, dass sich der Roboter drehen muss. Das kann man intelligent, wenn man weiß, dass die letzte Drehung in Richtung links war und nun nach links weiter muss, obwohl unsere Definition sagt, fahre per Default rechts herum.
3) Oder halt ohne die letzte Drehrichtung zu kennen auf den Defaultwert zurück zu fallen und nach rechts drehen. Damit landet man aber in einer Endlosschleife …
4) Endlosschleifen umgehen kann man auch, in dem man sich den Punkt merkt, an dem man die m-Line verlassen hat, um das Hindernis zu umfahren (manchmal auch HitPoint genannt). Also merken wir uns die Position beim Verlassen der m-Line. Im Computer-Testprogramm ganz einfach: HitPoint = X-Achsenwert (siehe Programm)
Nun muss man sich klar werden, welche Sensoren auf dem in blau eingezeichneten Weg an welchen Ecken angesprochen werden. Dazu ist es wichtig zu wissen aus welcher Richtung ich eigentlich komme. Im Computer- Testprogramm ist das die Variable „move_dir“. Eine weitere wichtige Variable ist „last_dir“. Diese Variable speichert den letzten Richtungswechsel.
Somit müssen folgende Variablen ausgewertet werden, beim Umfahren eines Hindernisses:
Sensor_links, Sensor_mitte, Sensor_rechts, move_dir und last_dir
