Kognitive Robotik: Unterschied zwischen den Versionen

Aus II-Wiki
Zur Navigation springen Zur Suche springen
 
(12 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 110: Zeile 110:
  
 
= Sensorik =
 
= Sensorik =
* interne
+
 
 +
'''Notwendig um:'''
 +
* sich selbst wahrzunehmen
 +
* Informationen über Umgebung zu erfassen
 +
* auf Umwelt reagieren zu können
 +
 
 +
==Interne & Externe Sensoren==
 +
'''interne Sensoren:'''
 +
* Erfassung interner Zustände des Roboters
 +
* Erfassung der Eigenbewegung
 +
* ohne Bezug zur Umgebung
 +
* besonders relevant: Odometriesensoren
 +
* Beispiele:
 
** Kreisel
 
** Kreisel
 
** Inkrementalgeber
 
** Inkrementalgeber
 
** Gyroskop
 
** Gyroskop
* externe
+
** Kompass
 +
 
 +
'''externe Sensoren:'''
 +
* Erfassung der Umwelt
 +
* Aufbau von Umgebungsmodellen
 +
* Interaktion mit Umgebung
 +
* besonders relevant: entfernungsmessende Sensoren, passive visuelle/akustische/taktile Sensoren
 +
* Klassifizierung:
 
** berührungslose
 
** berührungslose
 
*** akustische
 
*** akustische
Zeile 129: Zeile 148:
 
*** Kontaktleisten
 
*** Kontaktleisten
  
* Sensorelemente
+
== Sensorelemente ==
** emittierendes Element
+
* emittierendes Element
*** Umwandlung eines Elektrischen Signals in ein zur Erfassung der Messgröße benötigtes nicht elektrisches Signal
+
** Umwandlung eines elektrischen Signals in ein zur Erfassung der Messgröße geeignetes nicht-elektrisches Signal
** sensitives Element
+
* sensitives Element
*** Umwandlung von einem nicht elektrischen Messsignal in ein elektrisches Signal
+
** Umwandlung von einem nicht-elektrischen Messsignal in ein elektrisches Signal
** Duplexelement
+
* Duplexelement
*** Ein Element welches als emittierendes oder sensitives Element arbeitet
+
** Ein Element welches abwechselnd als emittierendes oder sensitives Element arbeitet
* Sensor
+
 
** aktiv
+
== Aktive & Passive Sensoren ==
*** besteht aus mindestens einem sensitiven und einem emittierenden Element oder einem Duplexelement sowie einer Einrichtung zur Signalanpassung
+
* aktiv
** passiv
+
** besteht aus mindestens einem sensitiven und einem emittierenden Element oder einem Duplexelement sowie einer Einrichtung zur Signalanpassung
*** besteht aus mindesten einem sensitiven Element und einer Signalanpassungeinrichtung
+
* passiv
 +
** besteht aus mindesten einem sensitiven Element und einer Signalanpassungeinrichtung
  
 
== Ultraschallsensoren ==
 
== Ultraschallsensoren ==
 +
 
* aktiver Sensor
 
* aktiver Sensor
* Messen der Laufzeit von Schallwellen zur Bestimmung von Entfernungen (TOF - Sensor (Time of Flight Sensor))
+
* messen der Laufzeit von Schallwellen zur Bestimmung von Entfernungen (TOF - Sensor (Time of Flight Sensor))
* sehr Preiswert
+
* sehr preiswert
* Messbare Entfernung 100mm - 5 m
+
* messbare Entfernung 100mm - 5 m
 
* Auflösung 3 cm
 
* Auflösung 3 cm
* Grundprinzip:
+
 
 +
'''Grundprinzip:'''
 
<pre>
 
<pre>
 
 
Empfänger        \          ___
 
Empfänger        \          ___
 
  /|      \        \      /    \
 
  /|      \        \      /    \
Zeile 160: Zeile 181:
 
       gemessene Entfernung
 
       gemessene Entfernung
 
</pre>
 
</pre>
 +
 +
<math>d = c \cdot \frac{t}{2}</math>
 +
* d...Entfernung
 +
* c...Schallgeschwindigkeit
 +
* t...Laufzeit
 +
 +
'''Eigenschaften:'''
 
* Schalldruck nimmt mit dem Quadrat der Entfernung ab
 
* Schalldruck nimmt mit dem Quadrat der Entfernung ab
* abhängig von Matrialeigenschaften  
+
* Ausbreitung an Übertragungsmedium gebunden
** keine Absorption → Totalreflexion (metallische Oberflächen)
+
* Messwert abhängig von Matrialeigenschaften , Entfernung, Oberflächenbeschaffenheit, geometrischen Eigenschaften
** totale Absorption → keine Reflexion (Stoffe, Dämmwolle)
+
* keine Absorption → Totalreflexion (metallische Oberflächen)
** Oberflächenkrümmung bestimmt Richtung der Reflexion → Scheinobjekte durch Spiegelung
+
* totale Absorption → keine Reflexion (Stoffe, Dämmwolle)
 +
* Oberflächenkrümmung bestimmt Richtung der Reflexion → Scheinobjekte durch Spiegelung
  
== Lasersensor ==
+
== Lasersensoren ==
* Misst Laufzeit von Lichtwellen => TOF- Sensor
+
* misst Laufzeit von Lichtwellen => TOF- Sensor
* Lasersensoren verhältnismäßig teuer
+
* Parameter des Übertragungsmediums unbedeutend
 +
* verhältnismäßig teuer
 
* Messbare Entfernung 100mm - 100 m
 
* Messbare Entfernung 100mm - 100 m
 
* Auflösung: 1 cm
 
* Auflösung: 1 cm
 
* 2D als auch 3D (noch teuerer als 2D und noch nicht sehr verbreitet) Erfassung der Umwelt möglich  
 
* 2D als auch 3D (noch teuerer als 2D und noch nicht sehr verbreitet) Erfassung der Umwelt möglich  
* Nur Spiegle und Glasscheiben sind Problematische Materialien
+
* nur Spiegel und Glasscheiben sind problematische Materialien
  
== Kammerasysteme ==
+
== Kamerasysteme ==
* monokulare System
+
* passiver Sensor -> abhängig von Beleuchtung
* Stereokammerasysteme
+
* typische Konfigurationen:
* monokulare omnidirektionale Systeme
+
** monokulare System
* liefern mit Abstand reichhaltigste informationen
+
** Stereokammerasysteme
 +
** monokulare omnidirektionale Systeme
 +
* liefern mit Abstand reichhaltigste Informationen
 
* erfordern sehr hohen Berechnungsaufwand
 
* erfordern sehr hohen Berechnungsaufwand
* Stereokameras vor allem für Entfernungsinformationen
+
* Stereokameras vor allem für Extraktion von Entfernungsinformationen eingesetzt
 
** geht auch monokular bei Bewegung des Roboters
 
** geht auch monokular bei Bewegung des Roboters
 
* Omnidirektionale Systeme zur Erfassung der gesamten Umgebung
 
* Omnidirektionale Systeme zur Erfassung der gesamten Umgebung
Zeile 187: Zeile 219:
  
 
= Navigation =
 
= Navigation =
* Problemstellung
+
'''Problemstellung:'''
** Wo befindet sich der Roboter
+
* Wo befindet sich der Roboter
** Wo befinden sich andere Objekte oder Orte in Relation zum Roboter
+
* Wo befinden sich andere Objekte oder Orte in Relation zum Roboter
** Wie kommt der Roboter von der aktuellen Position zu anderen Orten
+
* Wie kommt der Roboter von der aktuellen Position zu anderen Orten
** Vermeidung von Kollisionen mit Hindernissen
+
* Vermeidung von Kollisionen mit Hindernissen
  
== Lokale & Globale Navigation ==
 
 
'''Lokale Navigation:'''
 
'''Lokale Navigation:'''
 
* mit und ohne Umgebungsmodell möglich
 
* mit und ohne Umgebungsmodell möglich
Zeile 199: Zeile 230:
 
* auf Basis entfernungsmessender Sensoren
 
* auf Basis entfernungsmessender Sensoren
 
* Art und Anordnung der Sensoren bestimmt Leistungsfähigkeit
 
* Art und Anordnung der Sensoren bestimmt Leistungsfähigkeit
 +
* betrachten nur aktuellen sensorischen Kontext
 
* reaktive Verfahren
 
* reaktive Verfahren
  
Zeile 204: Zeile 236:
 
* basierend auf Umgebungsmodell
 
* basierend auf Umgebungsmodell
 
* Selbstlokalisation
 
* Selbstlokalisation
* wo ist mein Ziel?
+
* Erreichen eines Ziels
 
* Pfadplanung
 
* Pfadplanung
 
* Art des Umgangs mit Unsicherheiten bestimmt Leistungsfähigkeit
 
* Art des Umgangs mit Unsicherheiten bestimmt Leistungsfähigkeit
 
* planende Verfahren
 
* planende Verfahren
  
== Umgebungsmodelle ==
+
== Lokale Navigation ==
 +
 
 +
=== Direkte Sensor-Aktor-Kopplung ===
 +
 
 +
'''Realisierungen:'''
 +
# überwachtes Training eines NN
 +
#* einfach zu realisieren
 +
#* System kann nie besser als Supervisor werden
 +
#* z.B. ALVINN
 +
# Training eines NN mit RL
 +
#* zeitaufwändig
 +
#* Roboter muss Erfolg/Misserfolg erfahren
 +
#* für viele Realweltanwendungen nicht einsetzbar
 +
 
 +
=== Klassifikation Freiraum-Hindernis (explizite Repräsentation der lokalen Umgebung) ===
 +
 
 +
'''Am Beispiel Belegtheitskarte:'''
 +
* akurate Positionsbestimmung
 +
* keine Annahmen bzgl. Umgebungsgeometrie
 +
* Sensordaten ermöglichen Modellierung der Umgebung
 +
* Daten für Traning des NN in Simulator gewonnen
 +
** je besser Trainigsdaten & Sensormodell desto besser Ergebnis
 +
** Gewinnung der Trainigsdaten in Realwelt zu aufwendig
 +
 
 +
=== Visuelle Hinderniswahrnehmung ===
 +
 
 +
==== invers-perspektivische Kartierung ====
 +
* erzeugt Draufsicht auf betrachteten Sichtbereich
 +
** bewegt sich Roboter, wird invers-perspektivisch-transformiertes Bild um Betrag der Bewegung verschoben und mit vorherigem Bild verglichen
 +
** sind keine Differenzen erkennbar -> kein Hindernis vorhanden
 +
** Differenzen über pixelweise Differenzbildung, Verschiebungsvektoren oder Farbinformationen berechenbar
 +
* für Transformation nur folgende Parameter benötigt:
 +
** Kameraneigungswinkel
 +
** Entfernung Bildebene-Bezugsebene
 +
** tonnenförmige Bildverzerrung
 +
* um Flussschätzung effizient zu machen -> vorher Interest Operator anwenden
 +
** verstärkt Ecken, die zur Flussschätzung besonders geeignet sind
 +
** zusätzlich noch Strukturanalyse
 +
** daraus können dann noch Farbmerkmale gelernt werden, welche ebenfalls Freiraum darstellen
 +
* Vorteile:
 +
** Erfassung des gesamten zu befahrenden Bereiches
 +
** keine Annahmen über Geometrie der Hindernisse
 +
* Probleme:
 +
** Mindesthöhe der Hindernisse nötig
 +
** Reflexionen und Schatten als Hindernisse detektiert
 +
** hoher Berechnungsaufwand
 +
** exakte Synchronisation zwischen Bewegungs- und Bildinformationen erforderlich
 +
 
 +
==== Gradientensuche ====
 +
* Gradientensuche (Farb- oder Grauwert) entlang der Bildspalten
 +
* hoher Gradient lässt auf Hindernis schließen
 +
* Vorteil: einfach umsetzbar
 +
* Nachteile:
 +
** homogen gefärbter Untergrund nötig
 +
** Hindernis muss immer bis zum Boden reichen
 +
 
 +
==== Symmetrierung des optischen Flusses ====
 +
* Ausbalancierung der Flussfelder der rechten udn linken Bildhälfte
 +
* ergibt mittige Fahrt zwischen Hindernissen
 +
* strukturierte Umgebung nötig
 +
 
 +
==== Zustandsschätzung für markante Szenenpunkte ====
 +
* Zustand eines Szenenpunktes sei durch seine 3D-Koordinaten charakterisiert
 +
* eingesetzt wird Kombination aus
 +
** Interest-Operator zum Auffinden von Features im Bild
 +
** Feature-Tracker
 +
** Kalman-Filter zur Schätzung der 3D-Koordinaten
 +
* Farben kodieren Höhe der Objekte
 +
 
 +
==== Segemntierung mittels Untergrunddeskriptoren ====
 +
* Bereich vor Roboter als freier Untergrund angenommen
 +
* für diesen Bereich Beschreibung (z.B. Farbhistogramm) erstellt
 +
* Rest der Szene nach Ähnlichkeit zu dieser Beschreibung segmentiert
 +
 
 +
== Globale Navigation ==
 +
 
 +
4 grundlegende Fragestellungen:
 +
* Wo soll ich hin?
 +
* Was ist der beste Weg dorthin?
 +
* Wo war ich schon?
 +
* Wo bin ich gerade?
 +
 
 +
=== Umgebungsmodelle ===
 
* zwei Typen von Umgebungsmodellen
 
* zwei Typen von Umgebungsmodellen
 
<graphviz>
 
<graphviz>
 
digraph G {
 
digraph G {
  Umgebungsmodell -> "metrische Umgebungsmodelle";
+
  Umgebungsmodell -> "metrische (quantitative) \n Umgebungsmodelle";
  Umgebungsmodell -> "topologische Umgebungsmodelle";
+
  Umgebungsmodell -> "topologische (qualitative) \n Umgebungsmodelle";
 
}</graphviz>
 
}</graphviz>
 +
 
* Kategorisierung nach Abstraktionsgrad
 
* Kategorisierung nach Abstraktionsgrad
 
<graphviz>
 
<graphviz>
Zeile 221: Zeile 336:
 
  Umgebungsmodell -> "gitterbasierte,  \n metrische Umgebungsmodelle";
 
  Umgebungsmodell -> "gitterbasierte,  \n metrische Umgebungsmodelle";
 
  Umgebungsmodell -> "Umgebungsmodelle mit \n geometrischen Primitiven";
 
  Umgebungsmodell -> "Umgebungsmodelle mit \n geometrischen Primitiven";
  Umgebungsmodell -> "topologische \n Umgebungsmodelle";
+
  Umgebungsmodell -> "topologische \n Umgebungsmodelle";
  Umgebungsmodell -> "semantische \n Umgebungsmodelle";
+
  Umgebungsmodell -> "semantische \n Umgebungsmodelle";
 
}</graphviz>
 
}</graphviz>
  
* Die Erstellung der Umgebungsmodelle kann auf drei Arten passieren
+
==== Gitterbasierte, metrische Umgebungsmodelle ====
** Vorheriges Vermessen der Umgebung und Programmieren der Karte
 
*** Aufwendig und Sensoreindrücke/ Ungenauigkeiten nicht berücksichtigt
 
*** Nicht für Dynamische Umgebungen
 
** Umgebung mit Hilfe der Robotersensoren erfassen und bei bekannter Roboterpose Kartieren
 
*** Güte des Modells von Positionsbestimmung abhängig
 
** zeitgleiches Kartieren und Lokalisieren
 
*** SLAM (Self localisation and mapping)
 
 
 
=== Gitterbasierte metrische Umgebungsmodelle ===
 
 
* kontinuierliche Belegtheitswerte für Gitterzellen
 
* kontinuierliche Belegtheitswerte für Gitterzellen
 
* maßstabsgetreues Umgebungsabbild
 
* maßstabsgetreues Umgebungsabbild
Zeile 241: Zeile 347:
 
* geringer Abstraktionsgrad
 
* geringer Abstraktionsgrad
  
=== Umgebungsmodell mit geometrischen Primitiven ===
+
==== Umgebungsmodell mit geometrischen Primitiven ====
 
* besser an tatsächliche Umgebungsstruktur angepasst
 
* besser an tatsächliche Umgebungsstruktur angepasst
 
* Umwelt muss weitgehend gradlinige Strukturen aufweisen
 
* Umwelt muss weitgehend gradlinige Strukturen aufweisen
* Genauere Abbildung der Umgebung als mit Gitterstruktur möglich
+
* genauere Abbildung der Umgebung als mit Gitterstruktur möglich
 
* Extraktion der geometrischen Primitiven direkt aus den Sensordaten ist sehr aufwendig
 
* Extraktion der geometrischen Primitiven direkt aus den Sensordaten ist sehr aufwendig
  
=== Topologisches Umgebungsmodell ===
+
==== Topologisches Umgebungsmodell ====
 
* quantitatives Modell
 
* quantitatives Modell
 
* Darstellung meist in Form eines Graphen (Knoten sind markante Plätze und Kanten kodieren die Erreichbarkeit)
 
* Darstellung meist in Form eines Graphen (Knoten sind markante Plätze und Kanten kodieren die Erreichbarkeit)
Zeile 254: Zeile 360:
 
* gut geeignet für effiziente Pfadplanung
 
* gut geeignet für effiziente Pfadplanung
  
=== Sematisches Umgebungsmodell ===
+
==== Semantisches Umgebungsmodell ====
 
* höchste Abstraktionsstufe
 
* höchste Abstraktionsstufe
 
* erleichtert die Formulierung von Aufträgen an den Roboter ("Fahre in Küche" und nicht "Fahre zur Position 123,456")
 
* erleichtert die Formulierung von Aufträgen an den Roboter ("Fahre in Küche" und nicht "Fahre zur Position 123,456")
Zeile 260: Zeile 366:
 
* geringer Speicherverbrauch und effiziente Pfadplanung möglich
 
* geringer Speicherverbrauch und effiziente Pfadplanung möglich
 
* Dynamik der Umwelt kann mit berücksichtigt werden (Türen, Fahrstühle)
 
* Dynamik der Umwelt kann mit berücksichtigt werden (Türen, Fahrstühle)
 +
 +
==== Aufbau von Umgebungsmodellen ====
 +
* Die Erstellung der Umgebungsmodelle kann auf drei Arten passieren
 +
** Vorheriges Vermessen der Umgebung und Programmieren der Karte
 +
*** Aufwendig und Sensoreindrücke/ Ungenauigkeiten nicht berücksichtigt
 +
*** Nicht für Dynamische Umgebungen
 +
** Umgebung mit Hilfe der Robotersensoren erfassen und bei bekannter Roboterpose Kartieren
 +
*** Güte des Modells von Positionsbestimmung abhängig
 +
** zeitgleiches Kartieren und Lokalisieren
 +
*** SLAM (Self localisation and mapping)
  
 
== Selbstlokalisation ==
 
== Selbstlokalisation ==
Zeile 265: Zeile 381:
 
*# globale (absolute) Selbstlokalisation
 
*# globale (absolute) Selbstlokalisation
 
*#* Roboter wird an beliebigen Ort gestellt
 
*#* Roboter wird an beliebigen Ort gestellt
*#* Nimmt seine Umwelt nur mit seinen eigenen Sensoren wahr und kann sich in der Umgebung bewegen
+
*#* nimmt seine Umwelt nur mit seinen eigenen Sensoren wahr und kann sich in der Umgebung bewegen
*#* Muss anhand seiner Eindrücke seine aktuelle Pose schätzen
+
*#* muss anhand seiner Eindrücke seine aktuelle Pose schätzen
 
*#* großer Suchraum ==> viel Rechenaufwand
 
*#* großer Suchraum ==> viel Rechenaufwand
 
*# relative Selbstlokalisation (pose tracking)
 
*# relative Selbstlokalisation (pose tracking)
 
*#* initiale Pose ungefähr bekannt
 
*#* initiale Pose ungefähr bekannt
*#* Pose soll kontinuierliche korrigiert werden
+
*#* Pose soll kontinuierlich korrigiert werden
 
*#* deutliche geringerer Suchraum ==> geringerer Rechenaufwand
 
*#* deutliche geringerer Suchraum ==> geringerer Rechenaufwand
 
* beide Fälle werden durch die selben Algorithmen abgedeckt
 
* beide Fälle werden durch die selben Algorithmen abgedeckt
Zeile 284: Zeile 400:
 
* Fehler ist nicht beschränkt
 
* Fehler ist nicht beschränkt
  
=== Odomentrie und lokale externe Sensoren ===
+
=== Odometrie und lokale externe Sensorinformationen ===
* Für die Zustandschätzung stehen externe und interne Sensoren zur Verfügung
+
* für die Zustandschätzung stehen externe und interne Sensoren zur Verfügung
 
* zentrales Ziel ist die Verringerung des Odometriefehlers
 
* zentrales Ziel ist die Verringerung des Odometriefehlers
 
* Korrektur der internen Odometrie mit Hilfe von externen Sensoreindrücken
 
* Korrektur der internen Odometrie mit Hilfe von externen Sensoreindrücken
 
** Ein Stück fahren
 
** Ein Stück fahren
** Sensorwerte mit Startwerten vergleichen
+
** externe Sensorwerte mit Startwerten vergleichen
** mit Odometrie vergleichen
+
** mit Odometrie ausgleichen
 +
** Korrespondenzen bestimmen
 
** Odometrie korrigieren
 
** Odometrie korrigieren
 
* nur relative Zustandsschätzung möglich
 
* nur relative Zustandsschätzung möglich
 +
* nur für kurze Wegstrecken einsetzbar
 
* Fehler ist unbeschränkt
 
* Fehler ist unbeschränkt
  
 
=== Odometrie und lokale sowie globale Sensorinformationen ===
 
=== Odometrie und lokale sowie globale Sensorinformationen ===
 
* Zustandschätzung anhand interner und externer Sensorinformationen
 
* Zustandschätzung anhand interner und externer Sensorinformationen
* Ziel ist die Schätzung der globalen Position des Roboters
+
* Ziel ist die Schätzung der globalen Pose des Roboters
 
* globale Informationsquellen (Landmarken, Umgebungskarten)
 
* globale Informationsquellen (Landmarken, Umgebungskarten)
 
* Landmarken oft im Zusammenhang mit SLAM-Verfahren
 
* Landmarken oft im Zusammenhang mit SLAM-Verfahren
Zeile 303: 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 313: 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 338: 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 373: 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 381: 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
  
== lokale Navigation ==
+
== Metrische Pfadplanung ==
=== Potentialfeld-Verfahren ===
+
* Berechnung von Wegen, die bestimmten Optimalitätskriterien genügen
* Jedes Hindernis wirkt mit einer Abstoßenden Kraft auf den Roboter
+
* Zerlegung des Pfades in Wegpunkte, die Subziele darstellen (müssen aber keine Landmarken sein)
* Wird das Hindernis mit mehreren Sensoren erfast 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 Hindernis verloren
+
'''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 =
 +
 
 +
* für die letzendliche Generierung eines Fahrkommandos zuständig
 +
* berücksichtigt globale Planungsebene und lokale Hindernissituation
 +
* Anforderungen ergeben sich aus Umgebung
 +
* Idealfall:
 +
** 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 393: 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 408: 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

Aktuelle Version vom 1. August 2009, 18:27 Uhr

<hiddenlogin linktext="Passwort für Vorlesungsunterlagen">User: nistudss08 Pwd: n!-SS08</hiddenlogin>

Einführung

Paradigmen:

  • In der Robotik gibt es zur Zeit drei wesentliche Paradigmen
    • hierarchisches Paradigma (Sens → Plan → Act)
    • reaktives Paradigma (Sens → Act )
    • hybrid deliberativ/reaktiv
         Plan
           ↑
           ↓
   Sens ←----→ Act

Serviceroboter:

  • Ein Serviceroboter ist ein System,
    • das sich mobil in seiner Einsatzumgebung bewegen kann
    • das über eine gewisse Autonomie verfügt
    • dessen Serviceleistung mit menschlicher Interaktion verbunden ist
  • werden z.B. eingesetzt im Bergbau, Büro, Entertainment, Feuerbekämpfung, Landwirtschaft, Medizin, Minenräumung, Reinigung, Raumfahrt, Tanken, Sortierung, Überwachung, Unterwasser

Basiskomponenten:

KogRob-Basiskomponenten.jpg

Aktuatorik

Notwendig um:

  • sich in der Arbeitsumgebung zu bewegen
  • autonomen Robotern Mobilität zu ermöglichen
  • Gegenstände zu manipulieren

Roboteraktuatoren:

  • Antrieb
    • Laufmaschinen
    • Radantriebe
      • Differential Dirve
      • Synchron Drive
      • Tricycle Drive
  • Manipulatoren
    • Greifer
    • Mehrgelenkarme
  • Artikulation
    • Display
    • Gesicht & Sprache
    • Körpersprache

Radbasierte Antriebe:

  • am weitesten verbreitet
  • konstruktiv einfach zu realisieren
  • preiswert
  • einfache Ansteuerung
  • einfache Handhabung der Odometrie
  • aber:
    • Voraussetzung: ebener Untergrund
    • nur geringe Unebenheiten können überwunden werden

Differential Drive

  o   O   o
      |
      |
  o   O   o ← Castorräder
      ↑
    Antriebsränder
  • einfache mechanische Konstruktion
  • keine Trennung zwischen Antrieb und Lenkung
  • Odometrie einfach zu berechnen aber recht ungenau
  • empfindlich gegenüber Unebenheiten im Boden
  • Drehung auf der Stelle möglich

Tricycle Drive

      O ← angetriebenes lenkbares Rad
      |
  O ----- O ← Passivräder
  • einfache mechanische Konstruktion
  • im einfachsten Fall wird nur ein Rad angetrieben und gelenkt
  • keine Drehung auf der Stelle möglich (Schleppkurve muss berücksichtigt werden)
  • immer stabiler Bodenkontakt

Synchro Drive

   O ---- O ← drehbare Antriebsränder
   |      |
   |      |
   O ---- O
  • mechanische Konstruktion aufwändiger
  • mindestens drei synchron angetriebene/gelenkte Räder notwendig
  • Drehung auf der Stelle sowie Bewegung in beliebige Richtung ohne Drehung der Antriebsplatform möglich
  • stabiler Bodenkontakt weitestgehend gegeben
  • gute odometrische Eigenschaften, da alle Räder stets die gleiche Rotationsrichtung aufweisen (minimiert Schlupf)

Artikulation

  • führen von Dialogen mit Personen
  • übermitteln von Statusinformationen
  • kritische oder mehrdeutige Situtationen auflösen
  • Siehe MMK

Sensorik

Notwendig um:

  • sich selbst wahrzunehmen
  • Informationen über Umgebung zu erfassen
  • auf Umwelt reagieren zu können

Interne & Externe Sensoren

interne Sensoren:

  • Erfassung interner Zustände des Roboters
  • Erfassung der Eigenbewegung
  • ohne Bezug zur Umgebung
  • besonders relevant: Odometriesensoren
  • Beispiele:
    • Kreisel
    • Inkrementalgeber
    • Gyroskop
    • Kompass

externe Sensoren:

  • Erfassung der Umwelt
  • Aufbau von Umgebungsmodellen
  • Interaktion mit Umgebung
  • besonders relevant: entfernungsmessende Sensoren, passive visuelle/akustische/taktile Sensoren
  • Klassifizierung:
    • berührungslose
      • akustische
        • Ultraschall
        • Mikrofone
      • optische
        • Laserscanner
        • Kameras
      • sonstige
        • GPS
        • Radar
    • taktile
      • Bumper
      • Kontaktleisten

Sensorelemente

  • emittierendes Element
    • Umwandlung eines elektrischen Signals in ein zur Erfassung der Messgröße geeignetes nicht-elektrisches Signal
  • sensitives Element
    • Umwandlung von einem nicht-elektrischen Messsignal in ein elektrisches Signal
  • Duplexelement
    • Ein Element welches abwechselnd als emittierendes oder sensitives Element arbeitet

Aktive & Passive Sensoren

  • aktiv
    • besteht aus mindestens einem sensitiven und einem emittierenden Element oder einem Duplexelement sowie einer Einrichtung zur Signalanpassung
  • passiv
    • besteht aus mindesten einem sensitiven Element und einer Signalanpassungeinrichtung

Ultraschallsensoren

  • aktiver Sensor
  • messen der Laufzeit von Schallwellen zur Bestimmung von Entfernungen (TOF - Sensor (Time of Flight Sensor))
  • sehr preiswert
  • messbare Entfernung 100mm - 5 m
  • Auflösung 3 cm

Grundprinzip:

Empfänger         \          ___
 /|       \        \       /     \
| |   )    |        |     |       | Hindernis
 \|       /         |      \ ___ /
Sender             /
   |              /       |
   |←--------------------→|
      gemessene Entfernung

  • d...Entfernung
  • c...Schallgeschwindigkeit
  • t...Laufzeit

Eigenschaften:

  • Schalldruck nimmt mit dem Quadrat der Entfernung ab
  • Ausbreitung an Übertragungsmedium gebunden
  • Messwert abhängig von Matrialeigenschaften , Entfernung, Oberflächenbeschaffenheit, geometrischen Eigenschaften
  • keine Absorption → Totalreflexion (metallische Oberflächen)
  • totale Absorption → keine Reflexion (Stoffe, Dämmwolle)
  • Oberflächenkrümmung bestimmt Richtung der Reflexion → Scheinobjekte durch Spiegelung

Lasersensoren

  • misst Laufzeit von Lichtwellen => TOF- Sensor
  • Parameter des Übertragungsmediums unbedeutend
  • verhältnismäßig teuer
  • Messbare Entfernung 100mm - 100 m
  • Auflösung: 1 cm
  • 2D als auch 3D (noch teuerer als 2D und noch nicht sehr verbreitet) Erfassung der Umwelt möglich
  • nur Spiegel und Glasscheiben sind problematische Materialien

Kamerasysteme

  • passiver Sensor -> abhängig von Beleuchtung
  • typische Konfigurationen:
    • monokulare System
    • Stereokammerasysteme
    • monokulare omnidirektionale Systeme
  • liefern mit Abstand reichhaltigste Informationen
  • erfordern sehr hohen Berechnungsaufwand
  • Stereokameras vor allem für Extraktion von Entfernungsinformationen eingesetzt
    • geht auch monokular bei Bewegung des Roboters
  • Omnidirektionale Systeme zur Erfassung der gesamten Umgebung
    • Momentan noch recht geringe Auflösung
  • Siehe Robotvision

Navigation

Problemstellung:

  • Wo befindet sich der Roboter
  • Wo befinden sich andere Objekte oder Orte in Relation zum Roboter
  • Wie kommt der Roboter von der aktuellen Position zu anderen Orten
  • Vermeidung von Kollisionen mit Hindernissen

Lokale Navigation:

  • mit und ohne Umgebungsmodell möglich
  • Hinderniswahrnehmung und -vermeidung
  • auf Basis entfernungsmessender Sensoren
  • Art und Anordnung der Sensoren bestimmt Leistungsfähigkeit
  • betrachten nur aktuellen sensorischen Kontext
  • reaktive Verfahren

Globale Navigation:

  • basierend auf Umgebungsmodell
  • Selbstlokalisation
  • Erreichen eines Ziels
  • Pfadplanung
  • Art des Umgangs mit Unsicherheiten bestimmt Leistungsfähigkeit
  • planende Verfahren

Lokale Navigation

Direkte Sensor-Aktor-Kopplung

Realisierungen:

  1. überwachtes Training eines NN
    • einfach zu realisieren
    • System kann nie besser als Supervisor werden
    • z.B. ALVINN
  2. Training eines NN mit RL
    • zeitaufwändig
    • Roboter muss Erfolg/Misserfolg erfahren
    • für viele Realweltanwendungen nicht einsetzbar

Klassifikation Freiraum-Hindernis (explizite Repräsentation der lokalen Umgebung)

Am Beispiel Belegtheitskarte:

  • akurate Positionsbestimmung
  • keine Annahmen bzgl. Umgebungsgeometrie
  • Sensordaten ermöglichen Modellierung der Umgebung
  • Daten für Traning des NN in Simulator gewonnen
    • je besser Trainigsdaten & Sensormodell desto besser Ergebnis
    • Gewinnung der Trainigsdaten in Realwelt zu aufwendig

Visuelle Hinderniswahrnehmung

invers-perspektivische Kartierung

  • erzeugt Draufsicht auf betrachteten Sichtbereich
    • bewegt sich Roboter, wird invers-perspektivisch-transformiertes Bild um Betrag der Bewegung verschoben und mit vorherigem Bild verglichen
    • sind keine Differenzen erkennbar -> kein Hindernis vorhanden
    • Differenzen über pixelweise Differenzbildung, Verschiebungsvektoren oder Farbinformationen berechenbar
  • für Transformation nur folgende Parameter benötigt:
    • Kameraneigungswinkel
    • Entfernung Bildebene-Bezugsebene
    • tonnenförmige Bildverzerrung
  • um Flussschätzung effizient zu machen -> vorher Interest Operator anwenden
    • verstärkt Ecken, die zur Flussschätzung besonders geeignet sind
    • zusätzlich noch Strukturanalyse
    • daraus können dann noch Farbmerkmale gelernt werden, welche ebenfalls Freiraum darstellen
  • Vorteile:
    • Erfassung des gesamten zu befahrenden Bereiches
    • keine Annahmen über Geometrie der Hindernisse
  • Probleme:
    • Mindesthöhe der Hindernisse nötig
    • Reflexionen und Schatten als Hindernisse detektiert
    • hoher Berechnungsaufwand
    • exakte Synchronisation zwischen Bewegungs- und Bildinformationen erforderlich

Gradientensuche

  • Gradientensuche (Farb- oder Grauwert) entlang der Bildspalten
  • hoher Gradient lässt auf Hindernis schließen
  • Vorteil: einfach umsetzbar
  • Nachteile:
    • homogen gefärbter Untergrund nötig
    • Hindernis muss immer bis zum Boden reichen

Symmetrierung des optischen Flusses

  • Ausbalancierung der Flussfelder der rechten udn linken Bildhälfte
  • ergibt mittige Fahrt zwischen Hindernissen
  • strukturierte Umgebung nötig

Zustandsschätzung für markante Szenenpunkte

  • Zustand eines Szenenpunktes sei durch seine 3D-Koordinaten charakterisiert
  • eingesetzt wird Kombination aus
    • Interest-Operator zum Auffinden von Features im Bild
    • Feature-Tracker
    • Kalman-Filter zur Schätzung der 3D-Koordinaten
  • Farben kodieren Höhe der Objekte

Segemntierung mittels Untergrunddeskriptoren

  • Bereich vor Roboter als freier Untergrund angenommen
  • für diesen Bereich Beschreibung (z.B. Farbhistogramm) erstellt
  • Rest der Szene nach Ähnlichkeit zu dieser Beschreibung segmentiert

Globale Navigation

4 grundlegende Fragestellungen:

  • Wo soll ich hin?
  • Was ist der beste Weg dorthin?
  • Wo war ich schon?
  • Wo bin ich gerade?

Umgebungsmodelle

  • zwei Typen von Umgebungsmodellen

<graphviz> digraph G {

Umgebungsmodell -> "metrische (quantitative) \n Umgebungsmodelle";
Umgebungsmodell -> "topologische (qualitative) \n Umgebungsmodelle";

}</graphviz>

  • Kategorisierung nach Abstraktionsgrad

<graphviz> digraph G {

Umgebungsmodell -> "gitterbasierte,  \n metrische Umgebungsmodelle";
Umgebungsmodell -> "Umgebungsmodelle mit \n geometrischen Primitiven";
Umgebungsmodell -> "topologische \n Umgebungsmodelle";
Umgebungsmodell -> "semantische \n Umgebungsmodelle";

}</graphviz>

Gitterbasierte, metrische Umgebungsmodelle

  • kontinuierliche Belegtheitswerte für Gitterzellen
  • maßstabsgetreues Umgebungsabbild
  • einfache Handhabung
  • hoher Speicherverbrauch
  • geringer Abstraktionsgrad

Umgebungsmodell mit geometrischen Primitiven

  • besser an tatsächliche Umgebungsstruktur angepasst
  • Umwelt muss weitgehend gradlinige Strukturen aufweisen
  • genauere Abbildung der Umgebung als mit Gitterstruktur möglich
  • Extraktion der geometrischen Primitiven direkt aus den Sensordaten ist sehr aufwendig

Topologisches Umgebungsmodell

  • quantitatives Modell
  • Darstellung meist in Form eines Graphen (Knoten sind markante Plätze und Kanten kodieren die Erreichbarkeit)
  • Erstellung meist interaktiv mit einem Supervisor, automatischer Aufbau schwer möglich
  • geringer Speicherverbrauch
  • gut geeignet für effiziente Pfadplanung

Semantisches Umgebungsmodell

  • höchste Abstraktionsstufe
  • erleichtert die Formulierung von Aufträgen an den Roboter ("Fahre in Küche" und nicht "Fahre zur Position 123,456")
  • Erstellung mit Hilfe eines Supervisors
  • geringer Speicherverbrauch und effiziente Pfadplanung möglich
  • Dynamik der Umwelt kann mit berücksichtigt werden (Türen, Fahrstühle)

Aufbau von Umgebungsmodellen

  • Die Erstellung der Umgebungsmodelle kann auf drei Arten passieren
    • Vorheriges Vermessen der Umgebung und Programmieren der Karte
      • Aufwendig und Sensoreindrücke/ Ungenauigkeiten nicht berücksichtigt
      • Nicht für Dynamische Umgebungen
    • Umgebung mit Hilfe der Robotersensoren erfassen und bei bekannter Roboterpose Kartieren
      • Güte des Modells von Positionsbestimmung abhängig
    • zeitgleiches Kartieren und Lokalisieren
      • SLAM (Self localisation and mapping)

Selbstlokalisation

  • Grundlegende Fragestellung
    1. globale (absolute) Selbstlokalisation
      • Roboter wird an beliebigen Ort gestellt
      • nimmt seine Umwelt nur mit seinen eigenen Sensoren wahr und kann sich in der Umgebung bewegen
      • muss anhand seiner Eindrücke seine aktuelle Pose schätzen
      • großer Suchraum ==> viel Rechenaufwand
    2. relative Selbstlokalisation (pose tracking)
      • initiale Pose ungefähr bekannt
      • Pose soll kontinuierlich korrigiert werden
      • deutliche geringerer Suchraum ==> geringerer Rechenaufwand
  • beide Fälle werden durch die selben Algorithmen abgedeckt

Rein odometriebasierte Verfahren

  • nur interne Sensorinformationen
  • Güte der Schätzung ist abhängig von
    • Güte der Sensoren
    • Antriebsart
    • Bodenbeschaffenheit
  • nur relative Zustandsschätzung
  • nur für kurze Wegstrecken einsetzbar
  • Fehler ist nicht beschränkt

Odometrie und lokale externe Sensorinformationen

  • für die Zustandschätzung stehen externe und interne Sensoren zur Verfügung
  • zentrales Ziel ist die Verringerung des Odometriefehlers
  • Korrektur der internen Odometrie mit Hilfe von externen Sensoreindrücken
    • Ein Stück fahren
    • externe Sensorwerte mit Startwerten vergleichen
    • mit Odometrie ausgleichen
    • Korrespondenzen bestimmen
    • Odometrie korrigieren
  • nur relative Zustandsschätzung möglich
  • nur für kurze Wegstrecken einsetzbar
  • Fehler ist unbeschränkt

Odometrie und lokale sowie globale Sensorinformationen

  • Zustandschätzung anhand interner und externer Sensorinformationen
  • Ziel ist die Schätzung der globalen Pose des Roboters
  • globale Informationsquellen (Landmarken, Umgebungskarten)
  • Landmarken oft im Zusammenhang mit SLAM-Verfahren
  • Problem ist die robuste Detektion der Landmarke

Probabilistische Lokalisation

  • Roboterlokalisation wird als Bayes'sches Zustandsschätzproblem formuliert
  • Belief (Bel) bezeichnet den Roboterzustand
  • Schätzen des Bel anhand von verrauschten Messwerten
  • Dazu notwendig ist eine iterative Vorschrift wie der Bel berechnet werden kann so das neue Messwerte schnell eingerechnet werden können
    • X .... Menge aller Zustände
    • D .... Menge aller Messwerte
    • Berechnung der Wahrscheinlichkeit das sich der Roboter in einem bestimmten Zustand k befindet wenn vorher die Beobachtungen 0..k gemacht wurden
  • Der Roboter befindet sich in dem Zustand mit dem höchsten Bel
  • zwei Arten von Messwerten
    • relative Messwerte (Odometrie) -> Fehler ist Abhängig von den vorangegangenen Zeitschritten
    • absolute Messwerte (GPS, Landmarken) -> Fehler ist unabhängig von den vorangegangenen Zeitschritten
  • 2 Arten des Beliefs möglich:
    • a priori Belief
      • Aktionen und Beobachtungen bis zum vorangegangenen Zeitschritt (k-1)
    • a posteriori Belief
      • Zusätzlich zum a priori Belief werden noch die aktuellen absoluten Informationen mit berücksichtigt

iterative Berechnungsvorschrift für den Belief:

  • ... Sensormodell
  • ... Bewegungsmodell
  • ... Belief des vorhergehenden Zustandes

Umsetzungen:

  • Kalman-Filter (kontinuierlich)
  • Particle Filter (diskret)

Probabilistisches Aktionsmodell

  • auch als Bewegungsmodell bezeichnet
  • gibt an, mit welcher Wahrscheinlichkeit der Roboter einen Zustand erreicht wenn der vorher im Zustand war und Aktion ausgeführt hat
  • muss experimentell ermittelt werden

Probabilistisches Wahrnehmungsmodell

  • wird auch als Beobachtungs- bzw. Sensormodell bezeichnet
  • gibt an, mit welcher Wahrscheinlichkeit ein Roboter im Zustand die Beobachtung macht
  • Berücksichtigung der Eingenschaften des Sensors (Ungenauigkeiten !!)
  • benötigt ein Umgebungsmodell wie eine Karte oder Landmarkenanordnung

Zustandschätzung

Kalman-Filter

  • rekursiver Datenverarbeitungsalgorithmus zur Zustandschätzung eines linearen verrrauschten dynamischen Systems
  • für alle Verteilungen wird angenommen das sie sich durch Gaußfunktionen approximieren lassen
  • arbeitet alternierend in zwei Phasen
    • Prädiktionsschritt
      • bestimmen des möglichen neuen Zustandes () unter Berücksichtung der Rauschprozesse (Bewegungsmodell)
      • für die Unsicherheit gilt:
    • Korrekturschritt
      • Die Korrekturvorschrift berücksichtigt jetzt das Sensormodell und die Beobachtungen -> dadurch wird die Unsicherheit eingeschränkt
      • Unsicherheit nach Prädiktion und Korrektur
      • mit
        • Wichtung für Berücksichtigung der Beobachtung in Zustandsschätzung
        • der Beobachtung klein:
        • der Beobachtung groß:
    • Unsicherheit der Gesamtschätzung kleiner als einzelne Unsicherheiten
    • optimal wenn System linear und Unsicherheiten gaußverteilt

Particle Filter

  • Satz gewichteter Samples repräsentiert den aktuellen Belief
  • jedes Sample ist eine mögliche Pose des Roboters
  • Summe der nicht-negativen Gewichte aller Samples ist eins
  • 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
  • gestattet sehr genaue Zustandsschätzung
  • Grundlage für alle MCL (Monte-Carlo-Lokalisations-)verfahren

Monte Carlo Localization

  • partikelbasiertes, probabilistisches Verfahren
  • für Sonarsensoren entwickelt
  • verwendet unterschiedliche Informationen
    • ausgeführte Kommandos + Bewegungsmodell
    • sensorische Wahrnehmung + Sensormodell
  • die Partikel sind an kein Raster gebunden
  • ermöglicht das Verfolgen mehrerer Positionshypothesen
  • Partikel können dort platziert werden wo sie nötig sind

Prinzipieller Ablauf:

  • Initialzustand
    • alle Partikel sind gleichmäßig verteilt
    • alle besitzen das gleiche Gewicht
  • Umweltbeobachtung
    • für jedes Partikel wird die zu erwartende Beobachtung bestimmt und mit der realen Beobachtung verglichen
    • Sensormodel wird hier mit berücksichtigt
    • Bei Übereinstimmung bekommt das Paritkel ein neues hohes Gewicht, sonst ein kleineres
  • Resampling
    • Die Verteilungsdichte der Partikel wird entsprechend der Gewichte neu angeordnet
    • Samples mit kleinen Gewichten werden umgeordnet
  • Bewegungsprädiktion
    • Roboter bewegt sich
    • Unter Berücksichtigung des Bewegungsmodels werden die Partikel bewegt
  • 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
    1   1
  O---O---O
1 |   |   |   (Diagonale hat Gewicht von 1,4)
  O---O---O
1 |   |   |
  O---O---O
  • mit Dijkstra-Algo kürzesten Weg zum Ziel berechnen

Dijkstra-Algorithmus:

Initialisierung:

  • d(Ziel) = 0
  • d(sonst) =

Danach:

  • Schritt für Schritt für alle Knoten Entfernung vom Ziel berechnen, durch Addition der Kantengewichte
  • Minimum ergibt kürzesten Weg
        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)

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

  • für die letzendliche Generierung eines Fahrkommandos zuständig
  • berücksichtigt globale Planungsebene und lokale Hindernissituation
  • Anforderungen ergeben sich aus Umgebung
  • Idealfall:
    • 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
------------------------------------------------
__             __                __
   \_      _ /    \ _        _ /    \ _        _  resultierender Kurs eines Roboters 
      \__ /           \ __ /            \ __ /    der einen Gang entlang fährt

------------------------------------------------
  • Aufgrund der unsicheren Sensorik führt das Potentialfeld-Verfahren zu pendelnden Fahrbewegungen in Korridoren

Vektorfeldhistogramm

  • soll Probleme des Potentialfeld-Verfahrens lösen
  • dreistufige Repräsentation
    1. Gittermodell
    2. Polarhistogramm
      • Roboterumgebung wird in Kreissegmente eingeteilt
      • Jede belegte Zelle wirkt als Kraft auf den Roboter unter Berücksichtigung des Abstandes und dem Quadrat des Belegtheitswertes
      • Die Kräfte werden pro Kreissegment in einem Histogramm zusammengefasst
    3. Ableitung der Steuerparameter
      • 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
      • 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
    • Größe des Roboters wird vernachlässigt
    • Trägheit des Roboters wird nicht berücksichtigt
    • schmale Täler im Histogramm verursachen eine häufige Richtungsänderung des Roboters

Vektorfeldhistogramm+

  • Grundfunktion wie VHF
  • Größe des Roboters wird berücksichtigt in dem die Hindernisszellen angepasst werden
  • Bewegungsänderungen werden durch Kreisbahnen approximiert um die Trägheit des Roboters zu berücksichtigen
  • Hysterese erzeugt sanftere Bewegungen
  • Kostenfunktionen bei der Auswahl der Kandidaten ermöglichen Realisierung von unterschiedlichem Verhalten