• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Lokalisierung Mobiler Agenten

Contents

  • Behandelter Stoff
    • Übersicht
    • Statische Lokalisierung
  • Dynamische Lokalisierung
  • SLAM
  • Material und Links
  • Vorlesungsempfehlungen
  • Termine und Klausurablauf
Dieser Artikel beschäftigt sich mit der Vorlesung „Lokalisierung Mobiler Agenten“ am KIT. Er dient als Prüfungsvorbereitung. Ich habe die Vorlesungen bei Herrn Dr.-Ing. Gerhard Kurz im Sommersemester 2016 gehört.

Behandelter Stoff

Übersicht

Datum Kapitel Inhalt
17.05.2016 5. Vorlesung Hessische Normalform, Least Squares
24.05.2016 6. Vorlesung Least Squares
21.06.2016 10. Vorlesung Optimalitätsbeweise (Erwartungstreue); Stochastische Kombination
28.06.2016 11. Vorlesung Dynamische Lokalisierung (Kalman Filter: Prädiktions und Filterschritt)
05.07.2016 12. Vorlesung Kalman Filter: Filterschritt; SLAM
12.07.2016 13. Vorlesung Particle Filter, SLAM

Statische Lokalisierung

Slides: 20160517-lma-1

Hessische Normalform (Hesse normal form)
An equation describing a plane: $$x \cdot n - d = 0$$ where $x$ is a point, $n$ is the normal of the plane and $d$ is the distance of the plane to $0$.
Methode der kleinsten Quadrate (Least Squares Methode)
Bei der Lokalisierung mobiler Agenten in einem Raum mit 4 Wänden genügen zwei nicht-parallele Abstandsmessungen. Hat man mehr Messungen, so kann man mit der Methode kleinster Quadrate die beste Position bestimmen.

Der Fehler ist dann $e = y - H x$.

Damit definiert man das Gütemaß $$G(x) = (y- Hx)^T W^{-1} (y-Hx)$$ wobei $W^{-1}$ eine symmetrisch positiv definite Gewichtungsmatrix ist.
Rekursive Methode kleinster Quadrate
Wenn bereits einmal die beste Ebene bestimmt wurde will man nicht wieder alles neu berechnen, wenn ein neues Sensorergebnis hinzukommt. Bei uns mit Vektorwertigen Sensoren, nicht wie im wie im Skript mit Skalaren.

Slides: 6. Vorlesung

Sherman-Morrison-Woodbury Formel
Für zwei $n\times k$-Matrizen $U, V$ gilt:
Die $k\times k$-Matrix $E-V^T A^{-1}U$ sei regulär, dann gilt $$(A-UV^T)^{-1} = A^{-1}+A^{-1}U(E-V^TA^{-1}U)^{-1}V^T A^{-1}$$

Dynamische Lokalisierung

Kalman-Filter
Siehe Kalman-filter Artikel.

SLAM

SLAM (Simultaneous Location and Mapping)
SLAM ist ein Algorithmus, welcher zugleich eine Karte erstellt und einen mobilen Agenten auf der Karte lokalisiert. Eine Karte sind positionen von Landmarken.

Ansätze:
  • Filterung (rekursiv): z.B. Kalman-Filter; EKF, UKF (sigma-Punkte / samples; einfach zu implementieren und liefert häufig bessere Ergebnisse als EKF), Partikelfilter (Wahrscheinlichkeitsdichten werden durch Partikel / samples repräsentiert)
    $\Rightarrow$ Schätzen für Zeitschritt
  • Smoothing / Glättung (batch): Nachteile (Rechenaufwendig, erst nach batch ist Ergebnis da, man muss Daten speichern) und Vorteile (komplette Trajektorie, optimale Schätzung selbiger); z.B. Graph-based SLAM
Loop Closure: Wenn der Agent wieder an einen Punkt kommt, an dem er bereits war, kann ein Kreis geschlossen werden. Daher können die vorherigen Landmarken im Kreis neu geschätzt werden. Allerdings kann ein falsches Loop Closure zur Divergenz des Filters führen.

Herausforderungen:
  • Datenassoziation: Erkennen ob Landmarken die gleichen sind.
  • Komplexität (große Karte)
  • Veränderung der Umgebung: z.B. Auto als Landmarke erkannt; neue Brücke kommt hinzu oder wurde abgerissen
  • Nichtlinearitäten des Prolems
Landmarke
Ein gut sichtbares / wiedererkennbares Objekt, welches zur Abstandsmessung benutzt werden kann.
EKF SLAM
EKF SLAM basiert auf dem Extended Kalman Filter. Vereinfachungen:
  • Problem in 2D
  • Feste Zahl von punktförmigen Landmarken
  • Assoziationen bekannt: Landmarken werden zuverlässig erkannt und nicht verwechselt.
Zustand $\mathbf{x}_k = [\underbrace{x_k, y_k, \theta_k}_{\text{Pose des Roboters}}, \underbrace{m_{1, x}, m_{1, y}}_{\text{LM 1}}, \dots, \underbrace{m_{M, x}, m_{M, y}}_{\text{LM } M}]$
Dimension von $\mathbf{x}_k$: $3 + 2 M$.
Kovarianz hat $(3+2M)^2$ Elemente, d.h. der Speicheraufwand ist quadratisch in der Zahl der Landmarken.

Systemgleichung: $x_{k+1} = a_k (x_k, M_k) + w_k$
$x_{k+1} \approx A_k x_k + w_k,$ wobei $A_k$ Jaccobi-Matrix von $a_k(x_k, u_k)$ für festes $u_k$ an der Stelle $\hat{x}_k^e$.

Messgleichung: $y_k = h(x_k) + v_k$
In der Regel sind nicht alle Landmarken zugleich sichtbar. In diesem Fall werden Zeilen in der Messabbildung weggelassen. $$y_k = H_k(x_k) + v_k,$$ wobei $H_k$ die Jaccobi-Matrix von $h(x_k)$ an der Stelle $\hat{x}_k^P$ ist.
Particle Filter (Partikelfilter, Sequential Monte Carlo, SMC)
Idee: Schätze Zustand über Partikel. Ansatz: Sample aus Tranistionsdichte $$f(x_{k+1} | x_k = p_k^1, u_k$$ Implementierung:
  • Rauschen $w_k$ samples $\rightarrow v_k^1, \dots, v_k^N$
  • Propagiere durch $x_{k+1} = a_N(x_N, u_N) + w_N$, d.h. $p^1_{k+1} = a_k (p_k^1, u_k) + v_k^1$
  • Gewichte bleiben gleich
Problem: Viele Partikel $p_k^i$ haben geringes Gewicht $w_k^i$
Lösung: Resampling mit sequential importance resampling (SIR: ziehe $N$ neue Partikel mit Gewichten $\frac{1}{n}$ aus Menge der alten Partikel, wobei die Wahrscheinlichkeit das Partikel $p_k^i$ zu ziehen gerade $w_k^i$ ist.)

Material und Links

Die Vorlesung wurde gestreamt und ist unter mml-streamdb01.ira.uka.de verfügbar.

  • Vorlesungswebsite

Literatur und Links:

  • SLAM-Vorlesung der Uni Freiburg (Material)

Vorlesungsempfehlungen

Folgende Vorlesungen sind ähnlich:

  • Analysetechniken großer Datenbestände
  • Informationsfusion
  • Machine Learning 1
  • Machine Learning 2
  • Mustererkennung
  • Neuronale Netze
  • Lokalisierung Mobiler Agenten
  • Probabilistische Planung

Termine und Klausurablauf

Es ist eine mündliche Prüfung.

Published

Mai 18, 2016
by Martin Thoma

Category

German posts

Tags

  • Klausur 34
  • Machine Learning 81
  • Sensors 1

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor