Liste der Anhänge anzeigen (Anzahl: 12)
Navigation für autonome mobile Roboter mit BirdsEye-View und effektiver Routenplanung
Ich moechte hier das im Rahmen meiner Bachelorarbeit entstandene Roboterprojekt zum Thema autonome Navigation vorstellen:
Im Rahmen dieser Arbeit sollte die mobile Roboterplattform "Eddie" (https://www.parallax.com/product/28992) um eine Bird-Eye-View Funktionalität erweitert werden.
Dazu soll der RGB-Bildframe der verwendeten Microsoft Kinect-Kamera, unter Verwendung der OpenNI und OpenCV Bibliotheken, wie des libfreenect Treibers, entsprechend eingelesen, transformiert und ausgewertet werden. Mit Hilfe dieser neu gewonnenen Perspektive soll der Roboter später in der Lage sein, sich im Rahmen seiner Möglichkeiten in unbekanntem Terrain zu bewegen, Hindernisse zu erkennen und ihnen auszuweichen. Zudem soll es ihm möglich sein, einen vorher definierten Zielpunkt zu lokalisieren, eine effektive Route zu diesem zu berechnen und diese unter Echtzeitkontrolle abfahren zu können. Zusätzlich sollen die verschiedenen Perspektiven und Sichtfilter über einen Client als Livestream abrufbar sein, sowie ein Eingreifen oder Fernsteuern in die Bewegungsabläufe durch den Anwender ermöglicht werden.
Diese Implementierungen sollen auf einem Laptop bzw. PC mit einem Linux OS (Ubuntu 14.04 LTS), sowie später auch als eingebettetes System, auf einem ZedBoard von Xilinx mit Linux OS (Linaro 12.04) mit der Hochsprache C++ umgesetzt und genutzt werden können:
|
PC |
Laptop |
ZedBoard |
| OS |
Ubuntu 14.04 |
Ubuntu 14.04 |
Linaro 12.04 |
| Prozessor |
Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz |
Intel Core 2 Duo processor T8300 @ 2.4GHz |
Xilinx®XC7Z020-1CLG484CZynq-7000 AP SoC Dual Corex-A9 Processing System @ 667MhZ |
| Arbeitsspeicher |
4GB DIMM DDR2 |
2GB DDR2 |
512MB DDR3 |
Grundidee dieser Steuerung ist der effektive Umgang der von der Kinect-Kamera gewonnen RGB-Bilddaten (kein Tiefenbild) und die Umwandlung derer in eine Bird-Eye-View Perspektive. Unter Verwendung dieser Informationen soll ein vorher festgelegtes Beispielszenario erfolgreich absolviert werden können, sowie ein Nutzen der einzelnen Steuermodule für etwaige andere zukünftige Projekte ermöglicht werden. Der Roboter soll in der Lage sein, seine Umgebung mit seinen Mitteln (eingeschränkt) wahrnehmen zu können und eigenständig Lösungswege, z.B. bei der Navigation, vorzuschlagen und diese letztendlich auch ausführen können.
Für diese Arbeit wurde ein Beispielszenario entwickelt:
Anhang 30989
Ein Ziel (hier grün markiertes Feld) soll im Raum beliebig platziert werden können. Dieses Ziel soll vom Roboter erkannt werden und es soll eine effektive Route berechnet werden, mit der sich das Ziel ohne große Umwege erreichen lässt. Zusätzlich gibt es Hindernisfelder (hier violett markierte Felder), welche für den Roboter nicht befahrbares Terrain darstellen, welche ebenfalls beliebig im Raum, idealerweise zwischen Ziel und Ausgangsposition, platziert werden können. Die Position des Zieles und/oder der Hindernisse sollen während der Laufzeit verändert werden können, um so mehr Realitätsbezug zu schaffen. Das Testszenario gilt als erfolgreich abgeschlossen, wenn der Roboter sich auf dasZielfeld manövriert hat. Weitere Störeinflüsse, wie Lichtverhältnisse, andere Arten von Hindernissen und dgl., sollen hierbei außer Acht gelassen werden.
Um das oben gestellte Szenario erfolgreich bewerkstelligen zu können, stellen sich an die Steuerung folgende Anforderungen:
- Zuerst muss der Roboter die Bildinformationen aus der Kinect-Kamera einlesen und verarbeiten können.
- Er muss in der Lage sein, ein vorher definiertes Ziel stets und aus jedem Blickwinkel überhaupt als solches zu erkennen. Das Gleiche gilt für die Hindernisfelder.
- Die Hindernis- und Zielerkennung muss regelmäßig aktualisiert werden, um auf Veränderungen zur Laufzeit reagieren zu können.
- Der Roboter muss Ziel und Hindernisse in Bezug zueinander setzen, beispielsweise in einer internen Karte, und er muss seinen eigenen Standpunkt in dieser Karte kennen.
- Der Roboter muss die Größenverhältnisse der relevanten Objekte, besonders seine eigenen, einigermaßen genau abschätzen können, um zu evaluieren, ob ein Durchgang z.B. breit genug ist oder wie weit gefahren werden muss, um einen bestimmten Punkt auf der Karte anfahren zu können.
- Er muss vorher festgelegte Winkel und Strecken ausreichend genau ab/anfahren können.
- Er muss unter Verwendung der ermittelten Daten mit seiner generierten Karte einen effektiven Weg berechnen können, der an den Hindernissen vorbei, zuverlässig zum Ziel führt und erkennen, falls keine gültige Wegberechnung möglich ist.
- Er muss relevante Punkte auf seiner Route bestimmen können, die nötige Distanz und den nötigen Positionswinkel dazu berechnen und diese Punkte, unter oben genannten Anforderungen, bis zum Ziel abfahren.
- Während dem gesamten Ablauf soll ein Livebild gestreamt werden können, sodass der Anwender jederzeit das Geschehen aus Sicht des Roboters mit verfolgen und ggf. eingreifen kann.
Bereits relativ früh machten sich Einschränkungen bemerkbar, die verhinderten, den Ablauf wie ursprünglich geplant umzusetzen. Nach einigen darauf folgenden Versuchen ließen sich folgende Hauptproblematiken bei der Konzeptumsetzung identifizieren:
- Der Roboter besitzt aufgrund der Kameraposition und seiner Beschaffenheit einen toten Winkel. Er kann erst ab einer Entfernung von ca. 25cm seine Umgebung unmittelbar vor ihm wahrnehmen. Das bedeutet, dass Hindernisse in unmittelbarer Nähe, wie aber auch das Ziel, wenn es direkt vor ihm liegt, unter Umständen nicht erfasst werden können. Dies muss zwingend bei der Implementierung des Objektidentifizierungsmoduls, des Wegberechnungsmoduls und des Wegverfolgungs/Echtzeitfahrkorrekturmoduls berücksichtigt werden, indem z.B. grundsätzlich von einer größeren Robotergrundfläche ausgegangen wird, sodass der Roboter sich möglichst nie so positioniert, dass der tote Winkel relevant wird. Zudem müssen gewisse Strecken, wie jene, welche abgefahren werden muss, um sich auf dem Ziel zu positionieren, blind gefahren werden, was erst gemacht werden darf, wenn sichergestellt ist, dass es kein Hindernis im Weg mehr gibt
- Aufgrund der variierenden Akkuleistung, verschiedener Bodenbeschaffenheiten, nicht genau und identisch ansteuerbarer Räder, sowie weiterer bauartbedingter Ungenauigkeiten, ist es nicht möglich, einen vorher definierten Winkel, aber insbesondere eine vorher festgelegte Strecke, sicher und zielgenau an- bzw. abzufahren. Daraus ergibt sich ein zentrales Problem und zwar, dass eine berechnete (optimale) Route nie exakt genutzt werden kann. Nach jedem Wendepunkt und jedem gefahrenen Stück Strecke würden sich die Ungenauigkeiten aufsummieren, sodass nie das Ziel sicher angefahren, geschweige denn den Hindernissen ausgewichen werden kann. Somit muss diese Vorstellung verworfen und ein neuer Ansatz erarbeitet werden, um den Roboter zielsicher navigieren zu können. Es bietet sich daher an, lediglich den ersten Wegpunkt (erste Wendestelle) der Route anzufahren, sich dann wieder zum Ziel auszurichten und erneut eine Route zu berechnen. Nur so können die Fahrungenauigkeiten minimiert und durch eine stete Neuberechnung einigermaßen kompensiert werden. Da es aber auch Schwierigkeiten gibt, den ersten Punkt sicher anzufahren, ergibt sich für das Echtzeitfahrkorrekturmodul eine neue Aufgabe: Es muss dafür sorgen, dass bei z.B. einem "Fahr 100 Längeneinheiten geradeaus" Befehl der Roboter nicht, aufgrund eines Fahrdralls oder ungenauem Stellwinkels, sich einer Hindernisfläche schräg nähert oder gar frontal auf diese zufährt. Dieses Modul muss in der Lage sein, eine drohende Kollision mit einem Hindernis rechtzeitig zu erkennen und Gegenmaßnahmen, wie eine Kurskorrektur oder eine Notbremsung, einzuleiten. Ist es in der Lage, diese Anforderungen zu bewältigen, wird es auch in der Lage sein, eine Umgebungsveränderung in Echtzeit zu analysieren, da es dann keinen Unterschied macht, ob der Roboter auf ein neu hinzugekommenes Hindernis steuert oder ob er aufgrund der Ungenauigkeiten ein bekanntes Hindernis ungewollt anfährt. Wichtig ist nur die entsprechende richtige Reaktion darauf. Daraus folgt aber auch, dass, um Zeitaufwand bei der rechenintensiven Operation der Wegfindung zu sparen, diese so selten wie möglich angewandt werden sollte, also möglichst weite Strecken zurückgelegt werden müssen, bevor sich wieder neu ausgerichtet werden muss. Dazu muss die berechnete Route auf wirklich wichtige Wendepunkte reduziert werden und nicht wie vorher auch jeden kleine Schlenker oder Richtungsänderungen berücksichtigen. Es ergibt sich allerdings auch der Vorteil, dass die Route durch dieses Problem etwas ungenauer, bzw. gröber sein kann, da eine perfekte Route eh nicht entsprechend genutzt wird. So kann bei der Berechnung auf eine "akzeptabel" genaue Route zu deutlich schnellerer Laufzeit zurückgegriffen werden, was dem steigenden Zeitaufwand bei der Wegberechnung durch seine häufige Wiederholung entgegenwirkt. Letztendlich kann die angefahrene Position im besten Fall aber nur als Wahrscheinlichkeitsverteilung um die angestrebte Koordinate herum angesehen werden.
- Aufgrund verschiedener Lichtverhältnisse, Sichtwinkel und Bildverzerrungen variiert das Farbspektrum eines z.B. grünen Feldes auf dem Bild so, dass dies im RGB (Red Green Blue) Farbbild nicht immer, bzw. nur sehr umständlich, als Grün erkannt werden kann. Auch fällt dadurch die Justierung sehr umständlich aus. Daher bietet sich eine Konvertierung zu einem HSV (Hue Saturation Value) Bild an, welches zur Definition einer Farbe nicht auf das Mischverhältnis zwischen Rot Grün und Blau setzt, sondern auf das zwischen Farbwert, Farbsättigung und Helligkeitswertes. Darüber lässt sich viel einfacher ein Definitionsbereich für besagtes Grün finden, welcher auch unter den gegebenen Ungenauigkeiten sicherer als solches zu erkennen ist.
- Die BEV-Transformation ist nicht 100%ig genau, in Bezug zu einer echten Vogelperspektive, umzusetzen, sodass bei der Darstellung, wie auch bei der darauf aufbauenden Berechnung, Ungenauigkeiten und perspektivische Verzerrungen auftreten, die das Endergebnis verfälschen. Dies wird jedoch dadurch kompensiert, dass von Anfang an davon ausgegangen wird, eine Wegstrecke nicht genau abfahren zu können, somit muss die Route nicht absolut genau sein. Wenn die Verzerrung ein gewisses, über Parameter regelbares Maß, nicht überschreitet, kann sie ignoriert werden.
- Da der Roboter aufgrund oben genannter Fahrungenauigkeiten seine Position im Raum nicht zuverlässig angeben kann, kann sich auch die Position des Zielpunktes nicht sicher gemerkt werden, wenn er dieses aus den Augen verliert. Dies beutet, dass keine Routen erfolgreich berechnet werden können, wenn Ziel und der Weg zum Ziel nicht aus einem Blickwinkel zu erkennen sind, was die Möglichkeiten und Komplexität der zu bewältigenden Hindernisse erheblich einschränkt. Um dieses Problem zu lösen, muss der Roboter also entweder in der Lage sein, sich das Ziel sicher in einer relativ genauen Karten zu merken, was aufgrund oben genannter Faktoren vorerst nicht möglich ist, oder einen Weg finden sein Sichtfeld soweit zu erweitern, dass er auch großflächigere und komplizierter aufgebaute Hindernisszenarien bewältigen kann. Für diesen Zweck wurde das Objektidentifizierungsmodul um eine Funktionalität erweitert, welche den Sichtwinkel des Roboters virtuell verdoppelt, ohne dass er dafür seine Position im Raum verändern muss.
Im folgenden werde ich nur grob auf die Kernelemente des Projektes eingehen da die genauen Ausfuehrungen und Erklaerungen zu umfangreich sind und den Rahmen eines uebersichtlichen Threads sprengen.
Bei Interesse kann ich auf Nachfrage gerne die vollstaendige Arbeit mit allen detaillierten Informationen als PM verschicken.
Die Bird-Eye-View Funktionalität beschreibt die Umwandlung des von der Kinect-Kamera aufgenommenen RGB-Bildes in eine Vogelperspektive unter Zunahme der OpenCV Bibliotheken:
Anhang 30990
Zur Routenplanung wurde als Basis de A*-Algorithmus verwendet um eine effektive Route von der eigen Position zu dem erkannten Zielmarker an den Hindernissfeldern vorbei zu berechnen.
Da zudem von geringer Hardwareressourcen ausgegangen wird, wurde der A* dahingehend ueberarbeitet und optimiert um mit moeglichs minimalem Rechenaufwand eine maximal effektive Route zu berechnen.
Dazu wurde z.B. die Sortierung der internen Punkteliste ueber einen Binaryheap realisiert und der A* dahingehend veraendert dass er nichtmehr die effektivste Route (mit relativ hohem Rechenaufwand) berechnet sondern lediglich eine "gute" Route (die aber idR extrem nah an der Optimalen liegt) die fuer den aber eh nicht optimal "sauber" fahrenden Roboter vollkommen ausreichend ist und ihn stets zuverlaessig zum Ziel navigiert. Zu verifizierung der A* Modifikation wurden diverse Testszenarien unter verschiedenen Platformen hingehend auf Laufzeit und Effektivitaet der Route getestet:
Anhang 30991
Anhang 30992
Abschliessend konnte mit diesen Optimierungen eine ausreichend genaue und zielsichere Route fuer den Roboter mit 90%geringer Laufzeit berechnet werden im Vergleich zur klassischen A* Implementierung (ohne Binaryheap und ohne der "nicht optimalste Route"-Modifizierungen). Diese Modifizierung des A*-Algorithmus (extended A*) sowie weitere Elemente des Projektes sind in einen Paper veroeffentlicht worden und sind detailliert unter diesem Link einzusehen: http://radio-project.eu/downloads/publications/rettkowski_etal-2015.pdf
Anhang 30993
Ein weiterer zentraler Punkt war die Problematik des eingeschraenkten Sichtfeldes sodass einige Hinternisse nicht in ihrer Gaenze ueberblickt und somit keine Route gefunden werden konnte:
Anhang 30994 Anhang 30995
Um dem entgegen zu Wirken wurde zusaetzlich eine Sichtfelderweiterung implementiert bei der der Roboter sich ein Stueck um seine eigene Achse dreht dabei Einzelbildaufnahmen macht und diese per Image-Stitching zusammenfuegt, das Ergebnis perspektivisch anpasst und erst danach die BEV Transformation und dann den extended A* darauf anwedet und so in der Lage ist sein Sichtwinkel von ca ~61,5° auf 110° zu erweitern ! (Gleiche Position des Roboters bei den Bildern oben und unten lediglich mit und ohne Verwendung der Sichtfelderweiterung, rote Linie: Interpolation der errechneten Wegpunkte die der Roboter versucht abzufahren)
Anhang 30996 Anhang 30997 Anhang 30998
Damit der Roboter die errechneten Wegpunkte auch im Rahmen seiner Möglichkeiten zielsicher anfahren kann, gibt es die follow() Methode. Diese berechnet als erstes den Winkel zwischen der Roboterposition im Bild (feste Koordinaten) und dem ersten Wegpunkt des A* Ergebnisses zusätzlich zur relativen Länge, die dazwischen liegt. Diese Parameter werden der turn() und move() Funktion übergeben. Die turn() Funktion versucht den übergebenen Winkel, aufbauend auf Erfahrungswertenbezüglich der Zeit, die sich der Roboter mit einer bestimmten Geschwindigkeit drehen muss, um einen bestimmten Winkel einzunehmen, umzusetzen. Ist dieser Vorgang abgeschlossen, versucht die turn() Funktion, ebenfalls auf experimentell ermittelte Werte aufbauend, die relative Länge in cm umzuwandeln und diese dann abzufahren.
Diese Werte müssen stets auf den verwendeten Roboter, Reifen- und Bodenbeschaffenheit u.v.m. angepasst werden. Da weniger bei der Winkelumsetzung, als bei dem Fahren einer geraden Strecke, die Fahrungenauigkeiten Einfluss auf die Umsetzung der Befehle nehmen, muss an dieser Stelle die Echtzeitfahrkorrektur Funktion mit dem Namen pathCorrection() eingreifen. Diese Funktion wird innerhalb der move() Funktion aufgerufen, in der Schleife, die, nachdem ein Fahrbefehl an das Control Board weitergeleitet wurde, die proportional zur umzusetzenden Strecke zu wartende Zeit umsetzt. Wird eine Fahrbefehl der Strecke x gegeben, so wird i mal die usleep(30000) Funktion aufgerufen (i~x). Innerhalb eines Wartezyklus wird dabei auch die pathCorrection() Funktion aufgerufen. Diese generiert als erstes eine neue Homographie anhand veränderter Bezugspunkte zum Originalbild, sodass eine deutlich stärkere und genauere BEV-Transformation ausgeführt wird, die jedoch nur in relativ geringem Abstand (~50cm) aufgrund der stärkeren Verzerrung, aussagekräftig ist. Ziel dessen ist eine detailliertere Analyse der unmittelbaren Umgebung. Die Funktion überprüft die Anzahl nicht begehbarerer Felder im Binärbild in direkter Nähe. Dabei unterscheidet die Funktion in linkem, rechtem und mittleren Teilbereich. Überschreitet beispielsweise im linken Teilbereich die Anzahl nicht begehbarer Bildpunkte einen Schwellwert, wobei der mittlere und rechte Bereich weitestgehend frei von solchen sind, wird dies als schräge Annährung eines Hindernisses auf der linken Seite interpretiert. Entsprechend wird eine leichte Kurskorrektur nach rechts eingeleitet, um den Roboter wieder auf eine gerade Bahn, im Verhältnis zur angestrebten Fahrstrecke und der Hindernisposition, zu bringen:
Anhang 30999
Im folgenden wird nocheinmal die Hauptsteuerroutine dargestellt die die einzelnen Funktionsbloecke beinhaltet und dessen Verbindungen und Abhaengigkeiten erlaeutert:
Anhang 31000
Das Ergebnis kann in diesem Beispielvideo eingesehen werden: https://www.youtube.com/watch?v=6-XNB06wvF8
In dieser Arbeit wurde eine Robotersteuerung entwickelt und vorgestellt, welches die Bird-Eye-View Perspektive nutzt, um ein Ziel in unbekannter Umgebung lokalisieren und unter Vermeidung von Kollisionen mit Hindernissen, effektiv und zielsicher anfahren zu können. Diese auf dem PC, Laptop und schlussendlich auch ZedBoard implementierte Steuerung wurde für den Eddie Roboter konfiguriert und ließ ihn das am Anfang festgelegte Szenario unter Realbedingungen erfolgreich absolvieren.
Der Roboter kann die verwendeten Kinect-Kamera nutzen, um eine BEV-Perspektive zu generieren, innerhalb derer der dafür speziell modifizierte A* Wegfindungsalgorithmus eine, auf die Möglichkeiten des Roboterszugeschnittene, Route zum Ziel berechnet.
Diese Route kann aufgrund der geschilderten Fahrungenauigkeiten nur im gewissen Rahmen genau abgefahren werden, sodass die Implementierung einer zusätzlichen Echtzeitfahrkorrektur nötig war. Mit Hilfe dieser Echtzeitkorrektur kann der Roboter nun trotz seines Handicaps dem berechneten Weg folgen und unter stetiger Aktualisierung und Neuausrichtungen den Zielpunkt erreichen. Der Roboter versucht mitmöglichst geringem Rechenaufwand die Problemstellung zu lösen, indem er zuerst mit rechentechnisch sparsameren Methoden beginnt und nur bei Bedarf Fähigkeiten, wie die aufwändigere Sichtfelderweiterung, aktiviert. Die Steuerung agiert dabei als Zusammenspiel zwischen berechneten und optimierten Abläufen wie der effizienten Wegplanung und intuitivem Handeln, als Reaktion auf unvorhergesehene oder spontane Ereignisse wie auftauchende Hindernisse oder ein umpositionieren des Zielmarkers.
Die vorgestellten Modifikationen und Erweiterungen ermöglichten dem Roboter neue Perspektiven (BEV, Sichtfelderweiterung) und Fähigkeiten (Wegberechnung, Echtzeitfahrkorrektur und Remotezugriff) die nicht zuletzt dank der Laufzeitoptimierungen auch erfolgreich auf das ZedBoard portiert und dort in ausreichend schnellen Ausführzeiten angewendet werden konnte. Im Vergleich zu derzeit etablierten Vorgehensweisen wurden die Vorteile sich bewährter Methoden, wie dem A* als Basis oder einer BEV-Perspektive für die Navigation genutzt. Die vorgestellte Steuerungen mit ihren Eigenschaften und Fähigkeiten ist nicht optimal, schöpft aber die zur Verfügung stehenden Ressourcen gut aus, sodass weitere Projekte durchaus auf den erstellten Funktionsmodulen aufbauen können. Alternative Ansätze, wie schnellere und genauere Wegfindungsalgorithmen oder bessere Kamerasysteme können als Inspiration für weitere Verbesserungen oder Umsetzungen dienen.
Fuer weitere Fragen und Kritiken stehe ich gerne zur Verfuegung !
