Echtzeit-Lernverfahren zur Fehlerbegrenzung und Driftkorrektur für Odometrie-basierte Lokalisationsverfahren

Ralf Der, Thomas Pantzer

Zusammenfassung:

Positionsbestimmung und Navigation sind essentielle Grundaufgaben im Forschungsgebiet ``autonome Roboter''. Die Koppelnavigation (Odometrie) ist ein bekanntes und mit geringem Hardwareaufwand zu realisierendes Verfahren zur lokalen Positionsbestimmung. Eine indoor-Umgebung, eines der häufigsten Einsatzgebiete von Robotern, ist meist durch orthogonale Strukturen geprägt. Der im folgenden Dokument beschriebene Algorithmus macht sich diese Eigenschaften zunutze, um einen Korrekturbeitrag für die fehlerbehaftete Koppelnavigation zu geben. Es werden mit einem Echtzeit-Lernverfahren Vorzugsrichtungen (Kanten) extrahiert, die u.a. auch zur Generierung topologischer Karten benutzt werden können.

1. Einleitung

1.1 Odometrie

Bei der Odometrie, in der Literatur auch als Koppelnavigation oder engl. ``dead reckoning'' bezeichnet, werden Signalgeber an den Rädern benutzt, um den zurückgelegten Weg des Fahrzeugs (Roboter) messen zu können. Die Odometrie ist eine relative Positionsbestimmung. Die neue Position wird dabei aus einer vorher bekannten Position plus zurückgelegter Wegstrecke errechnet. Die Odometrie kann auf kurzen Distanzen sehr genaue Ergebnisse liefern. Allerdings entstehen auch Fehler, die mit zunehmender Entfernung wachsen. Die Räder können rutschen (Schlupf), unrund sein oder unterschiedliche Durchmesser haben (Reifenluftdruck), oder es können durch Bodenunebenheiten falsche Entfernungen gemessen werden. In der Literatur [2], [3] und [4] sind weitere Ansätze zur Selbstlokalisation ausführlich beschrieben.

1.1.1 Formeln

In Abbildung 1 ist die Positionsveränderung

Abbildung 1: Odometrie

eines zweirädrigen Fahrzeugs im Koordinatensystem schematisch dargestellt. Die Position des Roboters ist durch das Tupel gegeben, die Werte und werden direkt von den Radwegsensoren (Umdrehungszähler) abgelesen.

Der Drehwinkel ist die Wegdifferenz des rechten und linken Rades geteilt durch den Radabstand .

$$\Delta \alpha =\frac{\Delta R-\Delta L}{D}$$ (1)

Die Wegstrecke ist der mittlere Weg

$$\Delta s=\frac{\Delta L+\Delta R}{2}$$ (2)

Die Positionsveräderung bei Geradeausfahrt ( ) ist

$$\Delta x=\Delta R*\cos \left( \alpha \right)$$ (3)

$$\Delta y=\Delta L*\sin \left( \alpha \right)$$ (4)

Die Positionsveräderung bei Kurvenfahrt ( und ) ist

$$\Delta x=\frac{\Delta s}{\Delta \alpha }*\left( \cos \left( ... ...ha \right) +\cos \left( \alpha -\frac{\pi }{2}\right) \right)$$ (5)

$$\Delta y=\frac{\Delta s}{\Delta \alpha }*\left( \sin \left( ... ...ha \right) +\sin \left( \alpha -\frac{\pi }{2}\right) \right)$$ (6)

1.2 Roboter und Welt

Unsere Robotik-Experimente führten wir mit einem Modell des Khepera-Roboters durch. Dieser Roboter mißt ca. 50 mm im Durchmesser und besitzt 8 auf den Umfang verteilte Umgebungssensoren die im günstigsten Fall ungefähr 25 mm Reichweite haben. Angetrieben wird der Roboter durch zwei unabhängig steuerbare Schrittmotoren. Die Schrittweite beträgt ca. 0,08 mm.

Prinzipskizze des Roboters

zurückgelegter Weg des Roboters in einfacher Umgebung

Das Versuchsgelände bestand aus vier rechtwinklig angeordneten Wänden. Der Roboter wurde mit einem einfachen Controller zur Wandverfolgung programmiert.

2. Der Algorithmus

2.1 Differentialgleichungen beschreiben Kurvenformen

Bei Betrachtung des zurückgelegten Weges eines Roboters ist festzustellen, daß sich die Bahnkurve aus Elementen einfacher Kurvenformen zusammensetzen läßt. Die einfachste von ihnen ist die Gerade. Mit dem Anstieg der Geraden ist zugleich eine ganz charakteristische Eigenschaft dieser Spezialform einer ``Kurve'' in nur einem einzigen Wert repräsentiert. Dazu werden noch die Koordinaten eines einzigen Punktes (Startpunkt) und die Länge des Wegstückes benötigt, um diesen Teil der Bahnkurve eindeutig festzulegen.

Wenn dieser Ansatz auf das Prinzip ``Differentialgleichungen beschreiben Kurvenformen'' verallgemeinert wird, können komplizierte Kurvenformen dargestellt und in den meist beschränkten Speichermedien der Roboter-CPU effektiv abgespeichert werden. So kann zum Beispiel während der Verfolgung einer geraden Wand die Lage bzw. die Ausrichtung dieser Wand im Koordinatensystem oder bei der Umrundung eines Hindernisses sein Durchmesser festgestellt werden. Die Odometriedaten des Roboters werden dabei gleichzeitig gemittelt, um eventuelle Schlängelbewegungen des Wandfolgealgorithmus auszugleichen. Der aus den Odometriedaten resultierende Fehler kann klein angenommen werden, da nur die relative Positionsveränderung betrachtet wird.

2.2 Wettbewerb zwischen Differentialgleichungen

Die Basis des Algorithmus bildet ein Differentialgleichungsobjekt . Es enthält einen Vektor mit allen Ableitungen, zum Beispiel , , die Wahrscheinlichkeit , daß genau dieses Objekt beim nächsten Update berücksichtigt wird, und die aktuelle Fitness bzw. den momentanen Fehler . Mehrere Differentialgleichungsobjekte , eine Abstandsfunktion und die durchschnittliche Fitness bilden nun einen Pool , aus dem in jedem Schritt immer ein Objekt herausgegriffen und einem Update unterzogen wird. Das Objekt mit der höchsten Wahrscheinlichkeit gewinnt den Update seiner Parameter. Die Wahrscheinlichkeiten der einzelnen Objekte werden nach ihren Fitnesswerten bzw. Fehlern eingestellt. Dazu wird mit der geeignet gewählten Abstandsfunktion festgestellt, wie gut eine Differentialgleichung auf das gerade zurückgelegte Wegstück paßt und der zugehörige Fehler ermittelt. Wenn mehrere Differentialgleichungsobjekte annähernd gleich gut repräsentiert sind, soll kein Update vorgenommen werden. Nach ausreichend vielen Updateschritten sind die Koeffizienten konvergiert und die Differentialgleichungen widerspiegeln die geometrischen Eigenschaften der abgelaufenen Wegstücke.

3. Formalisierung am Beispiel

3.1 Differentialgleichung für Geraden

Die Differentialgleichung in der Form ist für unsere Zwecke ungünstig, da werden kann, wenn die Gerade parallel zur y-Achse des Koordinatensystems verläuft. Deshalb wird von der gebräuchlichen Form zur Parameterdarstellung der Gerade übergegangen. Die Variable ist in diesem Fall die Länge des zurückgelegten Weges auf der Geraden.

$$y=sa_{y}+y_{0}$$ (7)

$$x=sa_{x}+x_{0}$$ (8)

Nach Differentation erhalten wir

$$\frac{\Delta y}{\Delta s}=a_{y}$$ (9)

$$\frac{\Delta x}{\Delta s}=a_{x}$$ (10)

Diese Gleichungen sind nun genau dann erfüllt, wenn der Roboter sich auf einer Geraden bewegt, die durch die Parameter und beschrieben wird. Die Werte , und können direkt aus den Odometriedaten des Roboters entnommen werden. Da es sich um relative Koordinaten handelt, ist der zu erwartende Fehler auch entsprechend klein. Um die Parameter und in kleinen Schritten auf einen gewünschten Wert hinzuführen, benötigt man eine Fehlerfunktion als Maß der Abweichung des aktuell zurückgelegten differentiellen Wegstücks und den intern angenommenen Werten .

3.1.1 Fehlerfunktion und Fitness

Mit den Beziehungen aus 9 und 10 läßt sich die folgende Fehlerfunktion formulieren.

$$E_{i}=\left( \frac{\Delta x}{\Delta s}-a_{x,i}\right) ^{2}+\left( \frac{\Delta y}{\Delta s}-a_{y,i}\right) ^{2}$$ (11)

Der Index bezieht sich auf das -te Differentialgleichungsobjekt. Die Fitness dieses Objektes ergibt sich einfach aus

$$\Phi _{i}=-\frac{E_{i}}{4}$$ (12)

Die mittlere Fitness über alle betrachteten Differentialgleichungsobjekte beträgt

$$\overline{\Phi }=\sum ^{n}_{i=1}p_{i}\Phi _{i}$$ (13)

3.1.2 Fisher-Eigen-Dynamik

Die Fisher-Eigen-Dynamik [1] beschreibt die Selektionsdynamik in einem Pool von Individuen unterschiedlicher Fitness und Wahrscheinlichkeit . Dabei werden die Wahrscheinlichkeiten so verändert, daß nach hinreichend langer Zeit das Individuum mit der höchsten Fitness selektiert wird, d.h.

$$p_{i}=\left\{ \begin{array}{cl} 1, & falls\, i=i^{*}\\ 0, & sonst \end{array}\right\}$$

In jedem Zeitschritt wird ein Update für alle Wahrscheinlichkeiten der Differentialgleichungsobjekte im Pool durchgeführt (Fitness nach Gleichung 12, ist Anzahl der Differentialgleichungen).

$$\Delta p_{i}=\eta *\left( \Phi _{i}-\overline{\Phi }\right) *p_{i}$$ (14)

Die Wahrscheinlichkeiten werden normiert. Es gilt und . Die Geschwindigkeit, mit der die Wahrscheinlichkeiten umschlagen können, kann mit dem Parameter eingestellt werden ( ).

3.1.3 Information und Update

Gleichzeitig mit dem Update der Wahrscheinlichkeiten erfolgt ein Update der Koeffizienten der Differentialgleichungsobjekte zur Minimierung des Fehlers . Die Größe des Updateschrittes für das Objekt wird proportional zur Wahrscheinlichkeit gewählt.

$$\Delta a_{j,i}=\varepsilon *p_{i}*\left( \frac{\Delta x}{\Delta s}-a_{j}\right) \, \, \, \, \, \, j=\{x,y\}$$ (15)

Bessere Ergebnisse werden erzielt, wenn die Wahrscheinlichkeit durch eine monoton wachsende Funktion der Gestalt

$$\sigma (p_{i})=1-\frac{1}{1+e^{\left( p-p_{0}\right) *\chi }}$$ (16)

ersetzt wird, wobei und gewählt wird.

Wird der Algorithmus einige Zeit aktiviert, während der Roboter an einer längeren geraden Wand entlang läuft, werden die Parameter und sukzessive nachgeführt und spiegeln schließlich den Verlauf der Geraden wider. Der Vektor aus den gelernten Koeffizienten ist dann ein Einheitsvektor entlang dieser Geraden.

Die Information nach SHANNON [5] dient dazu, Updates zu unterdrücken, falls mehrere Differentialgleichungen ein bestimmtes Wegstück gleich gut repräsentieren.

$$I=-\frac{1}{n}\sum ^{n}_{i=1}p_{i}log(p_{i})$$ (17)

Ein Update der Koeffizienten wird grundsätzlich nur dann durchgeführt, wenn kleiner als ein vorgegebener Schwellwert ist. Günstige Werte für diese Schwelle liegen bei . In Abbildung 4 ist der Verlauf

Verlauf der Information		Weg des Roboters

der Information über der Zeit bei einer Rundfahrt des Roboters (Trajektorie Abbildung 5) gezeigt. In die Roboterumgebung wurden vier unterschiedlich lange Kanten, ein Innen- und ein Außenradius eingebaut. Jede Nadelspitze beim Wert der Information markiert eine Richtungsänderung des Roboters. Der Wert der Information erreicht seinen tiefsten Wert beim Entlangfahren an der längsten Kante.

4. Anwendung in der Praxis

4.1 Das Umschaltproblem

4.1.1 Verzögerter Anfang des Updates

Wird der Update der Differentialquotienten nicht in einem Schritt vorgenommen, und das ist der Fall, wenn der Faktor aus Gleichung 15 kleiner als ist, dann erfolgt eine Mittelung über mehrere Zeitschritte. Ebenso erfahren die Wahrscheinlichkeiten aus Gleichung 14 durch den Faktor eine Mittelung. Das führt dazu, daß die Wahrscheinlichkeiten erst nach einigen Schritten ihr Maximum erreichen können. Der Update und damit die Verringerung des Fehlers und Erhöhung der Fitness erfolgen aber nur optimal, wenn die Wahrscheinlichkeit über mehrere Schritte einen Wert in der Umgebung von aufweist. Nach Gleichung 14 ist die Summe aller Wahrscheinlichkeiten gleich , d.h. wenn eine Gleichung eine Wahrscheinlichkeit von 95% hat, müssen sich alle anderen die restlichen 5% teilen. Die Wahrscheinlichkeit für eine unpassende Gleichung ist also sehr klein. Schwenkt der Roboter auf seiner Fahrt jetzt auf eine Bahn, deren zugehörige Gleichung noch eine niedrige Wahrscheinlichkeit hat, kann es sehr lange dauern, bis die neue, eigentlich passende Differentialgleichung ein Update erfährt. Bei sehr kurzen Wegstücken kann es sogar dazu kommen, daß überhaupt kein Update durchgeführt wird, weil dieses Wegstück bereits wieder verlassen wurde, bevor die Fisher-Eigen-Dynamik umschlagen konnte.

4.1.2 Schranke für

Um diese Verzögerung klein zu halten, wird eine untere Schranke für die Wahrscheinlichkeiten definiert, die von keinem unterschritten werden soll. Ist das doch der Fall, wird das entsprechende gleich dem Wert dieser Schranke gesetzt. Da die Summe aller Wahrscheinlichkeiten gleich sein soll ergibt sich eine obere Schranke, die die nicht überschreiten können.

$$p_{o}=1,0-\left( N-1\right) *p_{u}\, \, \, \, \, \, \, \, \, \, \, p_{u}\approx 0,02$$ (18)

Diese Schranken müssen beim Update der Wahrscheinlichkeiten nach Gleichung 14 berücksichtigt werden. Falls eine Korrektur vorgenommen wurde, erhält das größte Wert .

4.1.3 Verzögerter Update

Die Änderungen der Wahrscheinlichkeiten folgen im Falle eines Umschwenkens immer den Fitnesswerten nach. In ungünstigen Situationen kann es passieren, daß die falschen Koeffizienten aufgrund ihrer noch hohen Wahrscheinlichkeitswerte einen Update mit völlig unpassenden Werten erfahren. Um das zu verhindern, können

1. die Lernparameter etwas vergrößert werden , damit schneller gelernt wird, oder
2. der Update kann mit verzögerten Werten von und vorgenommen werden, während die Fitness aus aktuellen Werten errechnet wird. Das Lernen der Koeffizienten findet damit ebenfalls verzögert statt.

Der erste Ansatz löst das Problem nicht prinzipiell, weil die Lernrate indirekt die Länge des Wegstückes bestimmt, das mit einer bestimmten Kurve (Differentialgleichung) verglichen werden soll. Je höher die Lernrate gewählt wird, umso kürzer ist das ``passende'' Wegstück.

Der zweite Ansatz funktioniert nur unter der Annahme, daß der Roboter sich größtenteils auf geradlinigen Bahnen bewegt und ein ``Einschwenken'' auf eine andere Richtung relativ schnell erfolgt. Weiterhin muß nun doch ein Teilstück des zurückgelegten Weges mit Hilfe von Punktkoordinaten abgespeichert werden. Die gewählte Verzögerung muß der Weglänge entsprechen, die während der Richtungsänderung zurückgelegt wird. Der Betrag der Verzögerung kann durch Auswerten der Information nach Shannon über den Fitnesswerten und den Wahrscheinlichkeiten relativ gut geschätzt werden.

4.2 Spezielle Fehlerfunktion für Geraden

Für die Fehlerfunktion wird ein Maß für den Abstand zweier Differentialgleichungen¹ benötigt. Die aus dem gerade zurückgelegten Wegstück angenommene Gleichung soll mit jeder anderen Differentialgleichung verglichen werden. Der größte erreichbare Abstand soll per Definition den Wert erhalten. Da in diesem Spezialfall den Anstieg der Geraden in zwei Variablen ( ) ausgedrückt wird, kann aus deren Vorzeichen auch noch eine Richtung (Vektor) bestimmt werden. Der Abstand soll den Wert haben, wenn die zwei Geraden den größten Abstand voneinander aufweisen, d.h. die Vektoren genau in die entgegengesetzte Richtung zeigen bzw. einen Winkel von 180 einschließen. Bei Identität soll der Abstand betragen.

Die Argumente für die Abstandsfunktion sind die Wegstrecken-Informationen (oder der Winkel und die Weglänge ) aus einem Zeitschritt und die zu lernenden Werte , die den Winkel (Ausrichtung) der Gerade (Kante) im internen Koordinatensystem repräsentieren. Im ideal gelernten Zustand im Zeitschritt sind die folgenden Ausdrücke äquivalent.

$$\tan \left( \alpha _{t}\right) =\frac{\Delta y_{t}}{\Delta x... ...\, \, \, \sqrt{\Delta x^{2}_{t}+\Delta y^{2}_{t}}=\Delta s_{t}$$ (19)

und

$$\tan \left( \beta _{i}\right) =\frac{a_{y,i}}{a_{x,i}},\, \, \, \, \sqrt{a^{2}_{x,i}+a^{2}_{y,i}}=1$$ (20)

Es wurden mehrere Abstandsfunktionen getestet.

1. Die erste betrachtete Abstandsfunktion ist die Fehlerfunktion nach Gleichung 11
2. In der zweiten Version wurde das Quadrat aus Gleichung 11 durch den Betrag ersetzt.
   

   $$E=j(\alpha _{t},\beta _{i})=\frac{\left\vert \frac{\Delta x_... ...ac{\Delta y_{t}}{\Delta s_{t}}-a_{y,i}\right\vert }{2\sqrt{2}}$$ (21)

   
   

3. Die dritte Version der Abstandsfunktion widerspiegelt den Betrag des Winkelabstandes.
   

   $$E=g\left( \alpha _{t},\beta _{i}\right) =\arccos \left( \fra... ...*a_{x,i}+\Delta y_{t}*a_{y,i}}{\Delta s_{t}}\right) *\pi ^{-1}$$ (22)

   
   

Abbildung: Abstandsfunktionen für Geradengleichungen

In Abbildung 6 auf Seite ist der Verlauf der einzelnen Funktionen an der Stelle dargestellt, der Wert für läuft zwischen und . Alle Abstandsfunktionen haben den Maximalwert , wenn die zu vergleichenden Vektoren in die entgegengesetzte Richtung zeigen. Das sehr langsame Ansteigen des Abstandes nach Gleichung 11 bei kleinen Winkeldifferenzen hat zur Folge, daß die Wahrscheinlichkeitswerte der einzelnen Differentialgleichungen nicht entsprechend eingestellt werden und die Information geringer ist (d.h. der Wert der Information nach Gleichung 17 steigt an). Für den Fall, daß mehrere Geraden nahe beieinander liegen, können Effekte wie das Heranziehen eigentlich unpassender Geraden auftreten. Bei der Funktion nach Gleichung 21 treten diese Effekte nicht mehr auf. Sie weist die größte Trennschärfe im Nahbereich auf, d.h. der Unterschied zwischen zwei ähnlich gut passenden Geradengleichungen ist größer, wodurch sich die Wahrscheinlichkeitswerte schneller neu einstellen können. Der gegenüber den Gleichungen 22 und 11 sehr ungewöhnliche Funktionsverlauf kann in Kauf genommen werden, da die Unregelmäßigkeiten nur in dem Bereich bemerkbar werden, in dem der Abstand zweier Geraden größer als 90 ist. Unter der Annahme, daß mindestens vier verschiedene Geradengleichungen der Menge der betrachteten Gleichungen angehören und der Raum, in dem sich der Roboter bewegt, vier rechtwinklig zueinander stehende Wände hat, so ist dieser Abstand gleichzeitig der größte erreichbare Abstand überhaupt.

Die Abstandsfunktion nach Gleichung 22 gibt mit der direkten Differenz zwischen zwei Winkeln zwar ein begrifflich sehr gut faßbares Abstandsmaß, benötigt aber den meisten Rechenaufwand. Es lassen sich außerdem Funktionen finden, die steilere Anstiege aufweisen. Im allgemeinen eignen sich Funktionen mit steilen Anstiegen in der näheren Umgebung des Referenzpunktes besser als Abstandsfunktion.

g0r Abstandsfunktion mit steilerem Anstieg Die Fehlerfunktion nach Gleichung 11 ist im Prinzip eine zwischen und normierte Kosinusfunktion, die als Argument den Differenzwinkel der beiden Geraden (Vektoren) hat. Bei der Suche nach Funktionen mit steileren Anstiegen im Nahbereich fiel die Funktion auf. Ein weiterer Vorteil dieser Funktion ist das Plateau bei , das bewirkt, daß alle in der näheren Umgebung liegenden Vektoren annähernd gleich stark berücksichtigt werden und die Entscheidung über den Updatesieger stärker durch die Wahrscheinlichkeiten erfolgt.

$$E=\frac{1}{2}*\left( \cos \left( \left( \arctan \left( a_{y,... ... y_{t},\Delta x_{t}\right) \right) -\pi \right) ^{3}+1\right)$$ (23)

Diese Abstandsfunktion lieferte bei unseren Experimenten die besten Ergebnisse. Bei Richtungsänderungen des Roboters schlugen die Wahrscheinlichkeiten schnell um, und die Anzahl der Fälle, in denen zwei Differentialgleichungsobjekte über einen längeren Zeitraum gleiche Wahrscheinlichkeiten aufwiesen, wurde minimiert.

5. Erweiterungen

5.1 Kreisbahnsegmente

Nachdem gezeigt wurde, daß das Prinzip der lernenden Differentialgleichungen für einfache Kurvenformen anwendbar ist, kann zu komplizierteren Kurvenformen übergegangen werden. Die einfache Gleichung für den Kreisumfang kann nach umgestellt werden. Der Radius ergibt sich aus dem zurückgelegten Weg auf der Kreisbahn geteilt durch die Winkeldifferenz in der Ausrichtung.

$$R=\frac{U}{2\pi }\approx \frac{\Delta s}{\Delta \alpha }=a_{i}$$ (24)

Der Radius einer Kreisbahn ist also der Parameter , der mit dieser Differentialgleichung gelernt werden kann. Durch negative Winkel kann der Parameter auch ein negatives Vorzeichen bekommen. Kreisradien sind aber immer positiv, das Vorzeichen bezeichnet hier die Richtung, auf der sich der Roboter auf der Kreisbahn bewegt (positiv = entgegen dem Uhrzeigersinn). Die Werte von und können sehr stark fluktuieren. Das hat zur Folge, daß der Parameter , der ja der Quotient aus und ist, noch stärkeren Schwankungen unterliegen würde. Um Fehlern bei der Berechnung im Computer entgegenzuwirken, werden und als getrennte Variablen im Speicher gehalten. Der Update der Kreisgleichungsparameter erfolgt (analog zu Gleichung 15) mit dieser Gleichung:

$$\Delta a_{i}=\varepsilon *p_{i}*\left( a_{i}*\Delta \alpha -\Delta s\right)$$ (25)

5.2 Abstandsfunktion für Kreisradien

Die Fehlerfunktion soll den Abstand von zwei Kreisradien auf den Wertebereich abbilden.

$$E_{i}=1-\frac{\left( \frac{k}{2}\right) ^{2}}{\left( a_{i}*\... ...{2}\right) ^{2}}\, \, \, \, \, \, \, k\epsilon [1\, ..\, 1000]$$ (26)

Abbildung: Abstandsfunktion für Kreisradien

Mit dem Parameter läßt sich die Steilheit bzw. mittlere Breite der Funktion einstellen und damit die Trennschärfe je nach Anwendungsgebiet beinflussen oder geeignet auswählen. Im Unendlichen steigt der Wert der Funktion jeweils auf .

5.3 Kreisgleichungen gegen Geradengleichungen

Werden Versuche mit verschiedenen Arten von Differentialgleichungsobjekten in einem Pool (siehe 2.2) durchgeführt, ist festzustellen, daß eine Art nur in besonders wenigen Fällen Updates gewinnt.

So können sich zum Beispiel Differentialgleichungsobjekte für Kreisbahnen nur dann gegen die für Geraden durchsetzen, wenn wenige andere Differentialgleichungsobjekte vorhanden sind. Anderenfalls ist der Konkurrenzdruck zu hoch und die Wahrscheinlichkeiten können sich nicht auf einem Wert stabilisieren, bei dem Updates möglich werden. Durch die Wahl eines größeren Wertes für in Gleichung 26 kann zwar der Einzugsbereich für bestimmte Instanzen von Differentialgleichungsobjekten vergrößert werden, beschränkt aber gleichzeitig die Anzahl der sinnvoll nutzbaren Objekte. Ein zu großer Wert für führt allerdings dazu, daß diese eine Gleichung immer wieder einen sehr hohen Fitnesswert aufweist und damit kein Umschlagen der Wahrscheinlichkeiten erfolgen kann.

Allgemein kann gesagt werden, daß kompliziertere Kurvenformen seltener einen Update gewinnen, weil die einfacheren Kurvenformen (z.B. Geraden) in ihnen schon enthalten sind. Damit weist neben der betrachteten komplizierten Kurvenform auch immer eine einfache Kurvenform eine relativ hohe Fitness auf, und die Information nach Gleichung 17 bleibt unter dem Schwellwert für zulässige Updates. Da sich die Konstruktion von wirklich gleichwertigen Abstandsfunktionen für verschiedene Klassen von Differentialgleichungsobjekten schwierig gestaltet, werden immer nur gleichartige Objekte in einer Menge zusammengefaßt.

6. Virtuelle Rotation und Driftkorrektur

6.1 Typische Fehlerbilder

Abbildung 9: Trajektorie des Roboters nach 1, 3 und 21 Umrundungen, Rechteck-Welt

a)

b)

c)

In Abbildung 9a ist der zurückgelegte Weg des Roboters bei einer Versuchsfahrt dargestellt. Ein Skalenteil entspricht dabei einem Millimeter in der wirklichen Welt. Der Roboter wurde auf Wandverfolgung programmiert und hat die aufgebaute Welt (ein Rechteck mit abgerundeten Ecken) 21 mal in einer Richtung umrundet. Dabei wurde nur aus den Odometriedaten der Räder die aktuelle Position des Roboters ca. aller mm zurückgelegten Weges neu berechnet. Deutlich ist ein systematischer Fehler bei der Berechnung der aktuellen Position zu erkennen, der von verschiedenen Reibwerten der Räder oder Differenzen der Raddurchmesser herrühren kann. Durch diesen Fehler wird die momentane Ausrichtung des Roboters falsch berechnet und erzeugt eine virtuelle Drehung des Weltkoordinatensystems. Die Winkelgeschwindigkeit² dieser Drehung wird nur durch Eigenschaften des Roboters (Raddurchmesser, Radstand, Spurweite, Bereifung) und Eigenschaften des Untergrundes bestimmt. Die Abhängigkeit dieses Fehlers von der Länge oder Art des zurückgelegten Weges oder der Gesamtdrehung des Roboters bezüglich seiner ursprünglichen Ausrichtung ist nicht durch eine vorher bekannte Funktion darstellbar. Die in Abbildung 10 dargestellte Trajektorie

Abbildung 10: Trajektorie des Roboters nach 1, 3 und 24 Umrundungen, L-Welt

a) b) c)

macht das deutlich. Sie wurde unter den gleichen Bedingungen wie die erste Trajektorie aufgenommen. Im Gegensatz zu der in Bild 9 gezeigten Trajektorie beträgt die Gesamtdrehung des Roboters in diesem Fall nach jeder durchlaufenen Runde wieder 0 . Die Bahn ist im Prinzip eine geknickte, liegende Acht. Der Roboter mußte auf seinem Weg im selben Maß Links- und Rechtsdrehungen ausführen. Die Winkelabweichung war in diesem Fall kleiner, bleibt aber trotzdem ein systematischer Störfaktor. Auf das Phänomen der virtuellen Rotation der Weltkoordinaten durch fehlerbehaftete Positionsbestimmung wird auch in [2] hingewiesen.

6.2 Driftkorrektur

Durch eine Erweiterung des oben beschriebenen Algorithmus kann zusätzlich zu den gelernten Bahnparametern ein Driftparameter gelernt werden, der die Winkelgeschwindigkeit der virtuellen Rotation des Weltkoordinatensystems widerspiegelt. Durch Integration von kann zu jedem Zeitpunkt die aktuelle Verdrehung des Koordinatensystems bestimmt und damit der systematische Fehler korrigiert werden. Die Parameter und werden in jedem Zeitschritt neu berechnet.

$$\varphi _{neu}=\varphi _{alt}+\gamma$$ (27)

und

$$\gamma _{neu}=\gamma _{alt}+\Delta \gamma$$ (28)

Um die Änderung der Winkelgeschwindigkeit erfassen zu können, werden gut angepaßte Geradengleichungen benötigt. Damit diese Anpassung durch die permanente virtuelle Drehung der Weltkoordinaten nicht verlorengeht, wird der Update der Geradengleichungen nach Gleichung 15 schon mit den rückgedrehten Werten und anstelle von und durchgeführt.

$$\overrightarrow{r}=\left( \begin{array}{c} \Delta x\\ \Delt... ...phi \right) & \cos \left( -\varphi \right) \end{array}\right)$$

$$\left( \begin{array}{c} \Delta x_{t}\\ \Delta y_{t} \end{array}\right) =\overrightarrow{r_{t}}=T\overrightarrow{r}$$ (29)

$$\Delta \gamma =\sum ^{n}_{i=1}\frac{\varepsilon \sigma (p_{i... ...eft( \delta y_{s}-a_{y,i}\right) *\delta x_{s}\right) \right)$$ (30)

$$\delta x_{s}=\frac{\Delta x_{t}}{\Delta s}\, ,\, \, \, \, \d... ...a y_{t}}{\Delta s},\, \, \, \, \, K\epsilon [5000\, ..\, 50000]$$

Mit dem Faktor wird das Verhältnis der Lerngeschwindigkeit der einzelnen Koeffizienten zur Winkelgeschwindigkeit eingestellt. Für wird der gleiche Wert wie in Gleichung 15 angesetzt. In den Abbildungen 11 und 12 sind die in Echtzeit korrigierten Trajektorien der oben gezeigten Testläufe zu sehen. Die restliche Parallelverschiebung resultiert aus der Differenz von angenommenem und eigentlichem Mittelpunkt des Roboterkoordinatensystems während der Rückdrehung der Punkte einer Trajektorie.

online korrigierte Version der Trajektorie aus Abbildung 9

online korrigierte Version der Trajektorie aus Abbildung 10

Da die Parameter für den Verdrehungsfehler online gelernt werden, können auch Änderungen des Untergrundes, die eine Änderung des systematischen Fehlers hervorrufen, automatisch korrigiert werden.

7. Ausblick

Der vorgestellte Algorithmus hat gezeigt, daß er zur Landmarkenerkennung, speziell zur Erkennung von bestimmten Pfadprofilen, genutzt werden kann. Er ist dabei nicht an das Verfahren der Odometrie gebunden. Die Strukturen der Umgebung (Wände) müssen nicht durch Wandverfolgung ``erlaufen'' werden, sondern können auch das Ergebnis eines Laserscans sein. Werden die Punkte eines Laserscans nach dem Winkel, unter dem sie aufgenommen wurden, sortiert³, ergibt sich annähernd dieselbe Trajektorie wie bei Wandverfolgung⁴. Mit mehreren aufeinanderfolgenden Scans (auch aus der Bewegung heraus) kann die Orientierung im Raum direkt und kontinuierlich bestimmt werden und man erhält eine Art Kompaß, der sich an den Gegebenheiten des Raumes (z.B. Wände) orientiert.

In [2], Abschnitt 5.3 beschreibt J.S.GUTMANN einen Algorithmus zur Berechnung der Verdrehung eines Laserscans unter Benutzung eines Winkelhistogramms. Der oben beschriebene Algorithmus erzielt in ähnlicher Weise die gleichen Ergebnisse, nur mit dem Unterschied, daß die Winkel direkt aus den Koeffizienten der Differentialgleichungsobjekte abgelesen werden können, ohne daß eine Kreuzkorrelation benötigt wird. Weiterhin sind erste (wenn auch nur partiell korrekte) Ergebnisse schon nach einigen wenigen Updateschritten verfügbar, und eine Erhöhung der Anzahl der Scanpunkte verbessert auch die Genauigkeit, ohne daß signifikant mehr Rechenleistung benötigt wird. Da in jedem Schritt immer dieselben einfachen Operationen durchgeführt werden, kann dieser Algorithmus auch direkt in Hardware realisiert werden.

Literatur

1

Werner Ebeling, Andreas Engel, and Rainer Feistel.
Physik der Evolutionsprozesse.
Akademie Verlag, Berlin, 1990.

2

Jens Steffen Gutmann.
Vergleich von Algorithmen zur Selbstlokalisierung eines mobilen Roboters.
Master's thesis, Universität Ulm, 1996.

3

Jens Steffen Gutmann, Wolfgang Hatzack, Immanuel Herrmann, Bernhard Nebel, Frank Rittinger, Augustinus Topor, Thilo Weigel, and Bruno Welsch.
Reliable self-localization, multirobot sensor integration and basic soccer skills.
1998.

4

Sven König and Reid G. Simmons.
Self-localization by hidden representations.
1997.

5

Claude E. Shannon and Warren Weaver.
Mathematische Grundlagen der Informationstheorie.
R. Oldenbourg, München, 1976.

Über dieses Dokument ...

Echtzeit-Lernverfahren zur Fehlerbegrenzung und Driftkorrektur für Odometrie-basierte Lokalisationsverfahren

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -html_version 3.2,table -show_section_numbers -split 2 -local_icons -scalable_fonts -numbered_footnotes Diffeq.tex

The translation was initiated by Thomas Pantzer on 2000-09-12