Zeile 421: |
Zeile 421: |
| | | |
| == Probabilistische Lokalisation == | | == Probabilistische Lokalisation == |
− | * Roboterlokalisation wird als Bays'sches Zustandsproblem formuliert | + | * Roboterlokalisation wird als Bayes'sches Zustandsschätzproblem formuliert |
| * Belief (Bel) bezeichnet den Roboterzustand | | * Belief (Bel) bezeichnet den Roboterzustand |
| * Schätzen des Bel anhand von verrauschten Messwerten | | * Schätzen des Bel anhand von verrauschten Messwerten |
− | * Dazu notwendig eine iterative vorschrift wie der Bel berechnet werden kann so das neue Messwerte schnell eingerechnet werden können | + | * Dazu notwendig ist eine iterative Vorschrift wie der Bel berechnet werden kann so das neue Messwerte schnell eingerechnet werden können |
| * <math> Bel(x_k) = P(x_k | d_{0..k})</math> | | * <math> Bel(x_k) = P(x_k | d_{0..k})</math> |
| ** X .... Menge aller Zustände | | ** X .... Menge aller Zustände |
Zeile 431: |
Zeile 431: |
| * Der Roboter befindet sich in dem Zustand mit dem höchsten Bel | | * Der Roboter befindet sich in dem Zustand mit dem höchsten Bel |
| * zwei Arten von Messwerten | | * zwei Arten von Messwerten |
− | ** relative Messwerte (Odometrie) ==> Fehler ist Abhängig von den vorangegangenen Zeitschritten | + | ** relative Messwerte (Odometrie) -> Fehler ist Abhängig von den vorangegangenen Zeitschritten |
− | ** absolute Messwerte (GPS, Landmarken) ==> Fehler ist unabhängig von den vorangegangenen Zeitschritten | + | ** absolute Messwerte (GPS, Landmarken) -> Fehler ist unabhängig von den vorangegangenen Zeitschritten |
− | * a priori Belief <math> Bel^{-}(x_k)</math> | + | * 2 Arten des Beliefs möglich: |
− | ** Aktionen und Beobachtungen bis zum vorangegangenen Zeitschritt (k-1) | + | ** a priori Belief <math> Bel^{-}(x_k)</math> |
− | * a posteriori Belief <math> Bel^{+}(x_k)</math> | + | *** Aktionen und Beobachtungen bis zum vorangegangenen Zeitschritt (k-1) |
− | ** Zusätzlich zum a priori Belief werden noch die aktuellen absoluten Informationen mit berücksichtigt | + | ** a posteriori Belief <math> Bel^{+}(x_k)</math> |
| + | *** Zusätzlich zum a priori Belief werden noch die aktuellen absoluten Informationen mit berücksichtigt |
| | | |
− | * iterative Berechnungsvorschrift für den Belief <br> <math> Bel(x_k) = \eta_k P(z_k | x_k) \int_{x \in X} P(x_k | x_{k-1},a_{k-1})Bel(x_{k-1})dx_{k-1}</math>
| + | '''iterative Berechnungsvorschrift für den Belief:''' |
− | ** <math> P(z_k | x_k)</math> ... Sensormodell
| + | <br> <math> Bel(x_k) = \eta_k P(z_k | x_k) \int_{x \in X} P(x_k | x_{k-1},a_{k-1})Bel(x_{k-1})dx_{k-1}</math> |
− | ** <math> P(x_k | x_{k-1},a_{k-1})</math> ... Bewegungsmodell
| + | * <math> P(z_k | x_k)</math> ... Sensormodell |
− | ** <math> Bel(x_{k-1}) </math> ... Belief des vorhergehenden Zustandes
| + | * <math> P(x_k | x_{k-1},a_{k-1})</math> ... Bewegungsmodell |
− | * Verschiedene Umsetzungen
| + | * <math> Bel(x_{k-1}) </math> ... Belief des vorhergehenden Zustandes |
− | ** Kalman-Filter
| + | |
− | ** Particle Filter
| + | '''Umsetzungen:''' |
| + | * Kalman-Filter (kontinuierlich) |
| + | * Particle Filter (diskret) |
| | | |
| === Probabilistisches Aktionsmodell === | | === Probabilistisches Aktionsmodell === |
| * auch als Bewegungsmodell bezeichnet | | * auch als Bewegungsmodell bezeichnet |
− | * gibt an, mit welcher Wahrscheinlichkeit der Roboter einen Zustand <math> x_k </math> erreicht wenn der vorher im Zustand <math> x_{k-1} </math> war | + | * gibt an, mit welcher Wahrscheinlichkeit der Roboter einen Zustand <math> x_k </math> erreicht wenn der vorher im Zustand <math> x_{k-1} </math> war und Aktion <math>a_{k-1}</math> ausgeführt hat |
− | * kann meist nur experimentell ermittelt werden | + | * muss experimentell ermittelt werden |
| | | |
| === Probabilistisches Wahrnehmungsmodell === | | === Probabilistisches Wahrnehmungsmodell === |
Zeile 456: |
Zeile 459: |
| * Berücksichtigung der Eingenschaften des Sensors (Ungenauigkeiten !!) | | * Berücksichtigung der Eingenschaften des Sensors (Ungenauigkeiten !!) |
| * benötigt ein Umgebungsmodell wie eine Karte oder Landmarkenanordnung | | * benötigt ein Umgebungsmodell wie eine Karte oder Landmarkenanordnung |
| + | |
| + | = Zustandschätzung = |
| | | |
| == Kalman-Filter == | | == Kalman-Filter == |
− | * rekursiver Datenverarbeitungsalgorithmus zur Zustandschätzung eines linearen Systems | + | * rekursiver Datenverarbeitungsalgorithmus zur Zustandschätzung eines linearen verrrauschten dynamischen Systems |
| * für alle Verteilungen wird angenommen das sie sich durch Gaußfunktionen approximieren lassen | | * für alle Verteilungen wird angenommen das sie sich durch Gaußfunktionen approximieren lassen |
− | * Arbeitet in zwei Phasen | + | * arbeitet alternierend in zwei Phasen |
| ** Prädiktionsschritt | | ** Prädiktionsschritt |
− | *** Bestimmen des möglichen neuen Zustandes unter Berücksichtung der Rauschprozesse (Bewegungsmodell) <br> Für die Unsicheheit gilt: <math> \sigma_1^2 = \sigma_0^2 + \sigma_w^2</math> | + | *** bestimmen des möglichen neuen Zustandes (<math>x_k = x_{k-1} + s+ w_k </math>) unter Berücksichtung der Rauschprozesse (Bewegungsmodell) |
| + | *** für die Unsicherheit gilt: <math> {\sigma_1}^2 = {\sigma_0}^2 + {\sigma_w}^2</math> |
| ** Korrekturschritt | | ** Korrekturschritt |
− | *** Die korrekturvorschrift Berücksichtigt jetzt das Sensormodell und die Beobachtungen. Dadurch wird die Unsicherheit eingeschränkt | + | *** Die Korrekturvorschrift berücksichtigt jetzt das Sensormodell und die Beobachtungen -> dadurch wird die Unsicherheit eingeschränkt |
− | *** Usicherheit nach KPrädiktion und Korrektur<math> \sigma_1^{2,+} = (1-K)\sigma_1^2 </math> | + | *** Unsicherheit nach Prädiktion und Korrektur <math> {\sigma_1}^{2,+} = (1-K) \cdot {\sigma_1}^2 </math> |
| *** mit <math> K = \frac{\sigma_1^2}{\sigma_1^2 + \sigma_\nu^2} </math> | | *** mit <math> K = \frac{\sigma_1^2}{\sigma_1^2 + \sigma_\nu^2} </math> |
| + | **** Wichtung für Berücksichtigung der Beobachtung in Zustandsschätzung |
| + | **** <math>\sigma</math> der Beobachtung klein: <math>K \rightarrow 1</math> |
| + | **** <math>\sigma</math> der Beobachtung groß: <math>K \rightarrow 0</math> |
| + | ** Unsicherheit der Gesamtschätzung kleiner als einzelne Unsicherheiten |
| + | ** optimal wenn System linear und Unsicherheiten gaußverteilt |
| | | |
| == Particle Filter == | | == Particle Filter == |
| * Satz gewichteter Samples repräsentiert den aktuellen Belief | | * Satz gewichteter Samples repräsentiert den aktuellen Belief |
− | * Jedes Sample ist eine mögliche Pose des Roboters | + | * jedes Sample ist eine mögliche Pose des Roboters |
− | * Summe der gewichte aller Samples ist eins | + | * Summe der nicht-negativen Gewichte aller Samples ist eins |
− | * Konvergiert auch in nicht linearen und und Gaußähnlich verhaltenden systemen | + | * konvergiert auch in nicht-linearen und gaußähnlich verhaltenden Systemen |
− | * Alle Samples gruppieren sich im laufe der Anwendung des Filters um die Zustände mit dem höchsten Belief | + | * Alle Samples gruppieren sich im Laufe der Anwendung des Filters um die Zustände mit dem höchsten Belief |
| * gestattet sehr genaue Zustandsschätzung | | * gestattet sehr genaue Zustandsschätzung |
| * Grundlage für alle MCL (Monte-Carlo-Lokalisations-)verfahren | | * Grundlage für alle MCL (Monte-Carlo-Lokalisations-)verfahren |
| | | |
− | === Monte Carlo Localisation === | + | === Monte Carlo Localization === |
| * partikelbasiertes, probabilistisches Verfahren | | * partikelbasiertes, probabilistisches Verfahren |
− | * für Sonar Sensoren entwickelt | + | * für Sonarsensoren entwickelt |
− | * Verwendet unterschiedliche Informationen | + | * verwendet unterschiedliche Informationen |
| ** ausgeführte Kommandos + Bewegungsmodell | | ** ausgeführte Kommandos + Bewegungsmodell |
− | ** senorische Wahrnehmung + Sensormodell | + | ** sensorische Wahrnehmung + Sensormodell |
− | * Die Partikel sind an kein Raster gebunden | + | * die Partikel sind an kein Raster gebunden |
− | * ermöglicht das Verfolgen mehrere Positionshypothesen | + | * ermöglicht das Verfolgen mehrerer Positionshypothesen |
| * Partikel können dort platziert werden wo sie nötig sind | | * Partikel können dort platziert werden wo sie nötig sind |
| + | |
| + | '''Prinzipieller Ablauf:''' |
| * Initialzustand | | * Initialzustand |
| ** alle Partikel sind gleichmäßig verteilt | | ** alle Partikel sind gleichmäßig verteilt |
Zeile 491: |
Zeile 504: |
| * Umweltbeobachtung | | * Umweltbeobachtung |
| ** für jedes Partikel wird die zu erwartende Beobachtung bestimmt und mit der realen Beobachtung verglichen | | ** für jedes Partikel wird die zu erwartende Beobachtung bestimmt und mit der realen Beobachtung verglichen |
− | ** Sensormodel wird hier mit Berücksichtigt | + | ** Sensormodel wird hier mit berücksichtigt |
− | ** Bei Übereinstimmung bekommt das Paritkel ein neues hohes Gewicht sonst ein kleineres | + | ** Bei Übereinstimmung bekommt das Paritkel ein neues hohes Gewicht, sonst ein kleineres |
| * Resampling | | * Resampling |
| ** Die Verteilungsdichte der Partikel wird entsprechend der Gewichte neu angeordnet | | ** Die Verteilungsdichte der Partikel wird entsprechend der Gewichte neu angeordnet |
Zeile 499: |
Zeile 512: |
| ** Roboter bewegt sich | | ** Roboter bewegt sich |
| ** Unter Berücksichtigung des Bewegungsmodels werden die Partikel bewegt | | ** Unter Berücksichtigung des Bewegungsmodels werden die Partikel bewegt |
− | * Erneute Umweltbeobachtung | + | * erneute Umweltbeobachtung |
| + | |
| + | = Pfadplanung = |
| + | '''Ziel:''' |
| + | * finden eines zusammenhängenden Weges zum Ziel, unter bestimmten Optimalitätskriterien: |
| + | ** Kollisionsfreie Fahrt |
| + | ** größtmöglicher Abstand zu Hindernissen |
| + | ** kürzester/schnellster Weg |
| + | * sowohl qualitativ (topologisch) als auch quantitativ (metrisch) möglich |
| + | * in beiden Fällen ähnliche Algorithmen verwendet |
| + | ** Dijkstra |
| + | ** A* |
| + | |
| + | '''Voraussetzungen:''' |
| + | * globales Umgebungsmodell |
| + | * Kenntnis der eigenen Pose und Ausdehnung |
| + | |
| + | == Topologische Pfadplanung == |
| + | * am Verhalten biologischer Systeme angelehnt |
| + | * benutzt Landmarken zur Beschreibung (Türen, Kreuzungen, Schilder etc.) |
| + | ** müssen gut sichtbar und eindeutig sein |
| + | ** sollten nicht dynamisch sein |
| + | * schwierig umzusetzen |
| + | |
| + | '''Prinzip:''' |
| + | * Umgebung als Graph aus Knoten und Kanten dargestellt |
| + | ** Knoten = Landmarken |
| + | ** Kanten = Pfade zwischen Knoten |
| + | * zusätzliche Kanteninformationen möglich (Himmelsrichtung, Entfernung, Terraintyp, Verhalten das angewendet werden soll) |
| + | * Dijkstra-Algo um optimalen Pfad zu berechnen |
| + | * Vorteil: Navigationsfehler können an Landmarken vollständig getilgt werden |
| + | * Nachteil: Wahrnehmung der entsprechenden Merkmale muss robust funktionieren |
| + | |
| + | == Metrische Pfadplanung == |
| + | * Berechnung von Wegen, die bestimmten Optimalitätskriterien genügen |
| + | * Zerlegung des Pfades in Wegpunkte, die Subziele darstellen (müssen aber keine Landmarken sein) |
| + | |
| + | '''Vorraussetzungen:''' |
| + | * Repräsentation des Umgebungsmodells |
| + | * Algo der auf der Repräsentation arbeitet und Planung durchführt |
| + | * Arbeitsraum: physikalischer Raum, in der sich Roboter bewegt (z.B. 3D-Welt -> 6 Freiheitsgrade) |
| + | * Konfigurationsraum: Datenstruktur auf der gearbeitet werden kann (z.B. 2D-Gridwelt -> 2 Freiheitsgrade) |
| + | * um Freiheitsgrade zu minimieren müssen Annahmen getroffen werden: |
| + | ** Roboter bewegt sich in x-y-Ebene |
| + | ** Hindernisse reichen bis zum Boden |
| + | ** runder, holonomer Roboter |
| + | |
| + | '''Prinzip:''' |
| + | * aus globaler Umgebung, gitterbasierte Belegtheitskarte erstellen |
| + | ** Darstellung in Grauwerten |
| + | * Binarisierung der Gitterzellen durch Schwellwertbildung -> entscheidet ob Zelle befahrbar ist oder nicht |
| + | * Dilatation zum Schließen von Lücken (zusätzlicher Effekt: Vergößerung des Hindernisses) |
| + | * Belegtheitskarte in Graph mit Knoten und Kanten umwandeln |
| + | * Kanten haben Gewichte von 1 |
| + | |
| + | <pre> |
| + | 1 1 |
| + | O---O---O |
| + | 1 | | | (Diagonale hat Gewicht von 1,4) |
| + | O---O---O |
| + | 1 | | | |
| + | O---O---O |
| + | </pre> |
| + | |
| + | * mit Dijkstra-Algo kürzesten Weg zum Ziel berechnen |
| + | |
| + | '''Dijkstra-Algorithmus:''' |
| + | |
| + | Initialisierung: |
| + | * d(Ziel) = 0 |
| + | * d(sonst) = <math>\infty</math> |
| + | Danach: |
| + | * Schritt für Schritt für alle Knoten Entfernung vom Ziel berechnen, durch Addition der Kantengewichte |
| + | * Minimum ergibt kürzesten Weg |
| + | |
| + | <pre> |
| + | 1 1 1 1 |
| + | (3,4)---(2,4)---(1,4)---(1,0)---(1,4) es wird immer kleinstes Gewicht genommen: |
| + | 1 | | | | | 1,4 + 1,4 = 2,8 |
| + | (3,0)---(2,0)---(1,0)---(0,0)---(1,0) 2,4 + 1,0 = 3,4 |
| + | 1 | | | | | 2,8 < 3,4 -> also Gewicht 2,8 nehmen |
| + | (3,4)---(2,4)---(1,4)---(1,0)---(1,4) |
| + | 1 | | | | | |
| + | (3,8)---(2,8)---(2,4)---(2,0)---(2,4) |
| + | </pre> |
| + | |
| + | '''Eigenschaften:''' |
| + | * sehr aufwendig, da Entfernung für jeden Knoten berechnet wird -> Fibonacci-Heap verwenden um Komplexität zu verringern |
| + | * kürzeste Wege führen sehr nah an Hindernissen vorbei -> eher unerwünscht |
| + | ** Lösung: Entfernung zur Kante mit an Knoten schreiben |
| + | ** Entfernung klein = hoher Kostenaufschlag |
| + | ** Entfernung groß = kein Kostenaufschlag |
| + | ** Ergebnis: Roboter fährt in Gangmitte |
| + | |
| + | '''Optimierung:''' |
| + | * Einbeziehung weiterer Kriterien in Pfadplanung |
| + | * kürzester Weg allein reicht nicht |
| + | * natürliches und glatteres Fahrverhalten angestrebt |
| + | |
| + | = Bewegungssteuerung = |
| | | |
− | == lokale Navigation ==
| + | * für die letzendliche Generierung eines Fahrkommandos zuständig |
− | === Potentialfeld-Verfahren ===
| + | * berücksichtigt globale Planungsebene und lokale Hindernissituation |
− | * Jedes Hindernis wirkt mit einer Abstoßenden Kraft auf den Roboter | + | * Anforderungen ergeben sich aus Umgebung |
− | * Wird das Hindernis mit mehreren Sensoren erfast so ist die Kraft größer als von einem Hindernis welches nur von einem Sensor erfast wird. | + | * Idealfall: |
− | * Durchfahren von Türen sehr schwer, weil alle Kräfte zu einer resultierenden Kraft aufsummiert werden, dadurch geht aber die Information über die Lage des Hindernis verloren | + | ** Umgebung stationär |
| + | ** exaktes Umgebungsmodell |
| + | ** Pose immer bekannt |
| + | ** Planungsverfahren würde ausreichen |
| + | * Realität: |
| + | ** Umgebung nicht stationär (dynamische Hindernisse) |
| + | ** Pose mit Unsicherheiten behaftet |
| + | |
| + | == Potentialfeld-Verfahren == |
| + | * jedes Hindernis wirkt mit einer abstoßenden Kraft auf den Roboter |
| + | * wird das Hindernis mit mehreren Sensoren erfasst, so ist die Kraft größer als von einem Hindernis welches nur von einem Sensor erfast wird |
| + | * Durchfahren von Türen sehr schwer, weil alle Kräfte zu einer resultierenden Kraft aufsummiert werden, dadurch geht aber die Information über die Lage des Hindernises verloren |
| <pre> | | <pre> |
| ------------------------------------------------ | | ------------------------------------------------ |
Zeile 511: |
Zeile 634: |
| \_ _ / \ _ _ / \ _ _ resultierender Kurs eines Roboters | | \_ _ / \ _ _ / \ _ _ resultierender Kurs eines Roboters |
| \__ / \ __ / \ __ / der einen Gang entlang fährt | | \__ / \ __ / \ __ / der einen Gang entlang fährt |
| + | |
| ------------------------------------------------ | | ------------------------------------------------ |
| </pre> | | </pre> |
− | * Aufgrund der unsicheren Sensorik führt das Potentialfeld Verfahren zu pendelnden Fahrbewegungen in Korridoren | + | * Aufgrund der unsicheren Sensorik führt das Potentialfeld-Verfahren zu pendelnden Fahrbewegungen in Korridoren |
| | | |
− | === Vektorfeldhistogramm ===
| + | == Vektorfeldhistogramm == |
− | * Soll Probleme des Potentialfeldverfahrens lösen | + | * soll Probleme des Potentialfeld-Verfahrens lösen |
| * dreistufige Repräsentation | | * dreistufige Repräsentation |
| *# Gittermodell | | *# Gittermodell |
Zeile 526: |
Zeile 650: |
| *#* In dem Polarhistogramm werden, mit Hilfe einer Schwelle, mögliche Kandidaten für Freiraum gesucht | | *#* In dem Polarhistogramm werden, mit Hilfe einer Schwelle, mögliche Kandidaten für Freiraum gesucht |
| *#* Der globale Plan des Roboters bestimmt dann welcher Freiraum gewählt wird und damit in welche grobe Richtung gefahren wird | | *#* Der globale Plan des Roboters bestimmt dann welcher Freiraum gewählt wird und damit in welche grobe Richtung gefahren wird |
− | *#* Die genaue Richtung wird bestimmt in dem man den Mittelwert aus dem nächsten freien Sektor und dem am weitesten entfernten freien Sektor von der Zielrichtung auswählt | + | *#* Die genaue Richtung wird bestimmt indem man den Mittelwert aus dem nächsten freien Sektor und dem am weitesten entfernten freien Sektor von der Zielrichtung auswählt |
| * Nachteile | | * Nachteile |
| ** Größe des Roboters wird vernachlässigt | | ** Größe des Roboters wird vernachlässigt |
| ** Trägheit des Roboters wird nicht berücksichtigt | | ** Trägheit des Roboters wird nicht berücksichtigt |
− | ** Schmale Täler im Histogramm verursachen eine häufige Richtungsänderung des Roboters | + | ** schmale Täler im Histogramm verursachen eine häufige Richtungsänderung des Roboters |
| | | |
− | === Vektorfeldhistogramm+ ===
| + | == Vektorfeldhistogramm+ == |
| * Grundfunktion wie VHF | | * Grundfunktion wie VHF |
| * Größe des Roboters wird berücksichtigt in dem die Hindernisszellen angepasst werden | | * Größe des Roboters wird berücksichtigt in dem die Hindernisszellen angepasst werden |