Odometrie oder die Kunst einen Weg für den Roboter zu finden: Unterschied zwischen den Versionen

Version vom 20. August 2011, 10:52 Uhr

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.