Kognitive Robotik: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Sonne (Diskussion | Beiträge) K (→Kalman-Filter) |
|||
(26 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
<hiddenlogin linktext="Passwort für Vorlesungsunterlagen">User: nistudss08 Pwd: n!-SS08</hiddenlogin> | <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 | * In der Robotik gibt es zur Zeit drei wesentliche Paradigmen | ||
− | ** hierarchisches Paradigma (Sens | + | ** hierarchisches Paradigma (Sens → Plan → Act) |
− | ** reaktives Paradigma (Sens | + | ** reaktives Paradigma (Sens → Act ) |
− | ** hybrid deliberativ /reaktiv | + | ** hybrid deliberativ/reaktiv |
<pre> | <pre> | ||
Plan | Plan | ||
Zeile 13: | Zeile 14: | ||
</pre> | </pre> | ||
− | + | '''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:''' | ||
+ | |||
+ | [[Datei:KogRob-Basiskomponenten.jpg|500px]] | ||
+ | |||
+ | = Aktuatorik = | ||
+ | |||
+ | '''Notwendig um:''' | ||
+ | * sich in der Arbeitsumgebung zu bewegen | ||
+ | * autonomen Robotern Mobilität zu ermöglichen | ||
+ | * Gegenstände zu manipulieren | ||
+ | |||
+ | '''Roboteraktuatoren:''' | ||
* Antrieb | * Antrieb | ||
− | ** Differential Dirve | + | ** Laufmaschinen |
− | ** Synchron Drive | + | ** Radantriebe |
− | ** Tricycle Drive | + | *** Differential Dirve |
+ | *** Synchron Drive | ||
+ | *** Tricycle Drive | ||
* Manipulatoren | * Manipulatoren | ||
** Greifer | ** Greifer | ||
Zeile 23: | Zeile 44: | ||
* Artikulation | * Artikulation | ||
** Display | ** Display | ||
− | ** Gesicht &Sprache | + | ** Gesicht & Sprache |
+ | ** Körpersprache | ||
− | + | '''Radbasierte Antriebe:''' | |
− | * einfache | + | * 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 == | ||
<pre> | <pre> | ||
Zeile 36: | Zeile 63: | ||
| | | | ||
| | | | ||
− | o O o ← | + | o O o ← Castorräder |
↑ | ↑ | ||
Antriebsränder | Antriebsränder | ||
</pre> | </pre> | ||
+ | * 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 == | ||
− | |||
− | |||
− | |||
− | |||
− | |||
<pre> | <pre> | ||
− | |||
O ← angetriebenes lenkbares Rad | O ← angetriebenes lenkbares Rad | ||
| | | | ||
Zeile 54: | Zeile 82: | ||
</pre> | </pre> | ||
− | + | * einfache mechanische Konstruktion | |
− | * mechanische Konstruktion | + | * im einfachsten Fall wird nur ein Rad angetrieben und gelenkt |
− | * Drehung auf der Stelle | + | * keine Drehung auf der Stelle möglich (Schleppkurve muss berücksichtigt werden) |
− | * stabiler Bodenkontakt | + | * immer stabiler Bodenkontakt |
− | + | ||
+ | == Synchro Drive == | ||
<pre> | <pre> | ||
− | |||
O ---- O ← drehbare Antriebsränder | O ---- O ← drehbare Antriebsränder | ||
| | | | | | ||
| | | | | | ||
O ---- O | O ---- O | ||
+ | </pre> | ||
+ | * 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 | * führen von Dialogen mit Personen | ||
* übermitteln von Statusinformationen | * übermitteln von Statusinformationen | ||
Zeile 76: | Zeile 109: | ||
* Siehe [[Multimodale_Mensch-Maschine-Kommunikation| MMK]] | * Siehe [[Multimodale_Mensch-Maschine-Kommunikation| 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 | ** 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 88: | Zeile 140: | ||
*** optische | *** optische | ||
**** Laserscanner | **** Laserscanner | ||
− | **** | + | **** Kameras |
*** sonstige | *** sonstige | ||
− | **** | + | **** GPS |
**** Radar | **** Radar | ||
** taktile | ** taktile | ||
Zeile 96: | Zeile 148: | ||
*** Kontaktleisten | *** 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 | * aktiver Sensor | ||
− | * | + | * messen der Laufzeit von Schallwellen zur Bestimmung von Entfernungen (TOF - Sensor (Time of Flight Sensor)) |
− | * sehr | + | * sehr preiswert |
− | * | + | * messbare Entfernung 100mm - 5 m |
* Auflösung 3 cm | * Auflösung 3 cm | ||
− | + | ||
+ | '''Grundprinzip:''' | ||
<pre> | <pre> | ||
− | |||
Empfänger \ ___ | Empfänger \ ___ | ||
/| \ \ / \ | /| \ \ / \ | ||
Zeile 127: | 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 |
− | + | * 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 | * 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 Spiegel und Glasscheiben sind problematische Materialien |
− | == | + | == Kamerasysteme == |
− | * monokulare System | + | * passiver Sensor -> abhängig von Beleuchtung |
− | * Stereokammerasysteme | + | * typische Konfigurationen: |
− | * monokulare omnidirektionale Systeme | + | ** monokulare System |
− | * liefern mit Abstand reichhaltigste | + | ** 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 153: | Zeile 218: | ||
* Siehe [[Robotvision]] | * 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:''' | ||
+ | # ü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 === | === Umgebungsmodelle === | ||
Zeile 164: | Zeile 327: | ||
<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 172: | 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 | + | Umgebungsmodell -> "topologische \n Umgebungsmodelle"; |
− | Umgebungsmodell -> "semantische | + | Umgebungsmodell -> "semantische \n Umgebungsmodelle"; |
}</graphviz> | }</graphviz> | ||
− | + | ==== Gitterbasierte, metrische Umgebungsmodelle ==== | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | ==== Gitterbasierte metrische Umgebungsmodelle ==== | ||
* kontinuierliche Belegtheitswerte für Gitterzellen | * kontinuierliche Belegtheitswerte für Gitterzellen | ||
* maßstabsgetreues Umgebungsabbild | * maßstabsgetreues Umgebungsabbild | ||
Zeile 194: | Zeile 350: | ||
* 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 |
* Extraktion der geometrischen Primitiven direkt aus den Sensordaten ist sehr aufwendig | * Extraktion der geometrischen Primitiven direkt aus den Sensordaten ist sehr aufwendig | ||
Zeile 204: | Zeile 360: | ||
* gut geeignet für effiziente Pfadplanung | * gut geeignet für effiziente Pfadplanung | ||
− | ==== | + | ==== 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 211: | Zeile 367: | ||
* Dynamik der Umwelt kann mit berücksichtigt werden (Türen, Fahrstühle) | * Dynamik der Umwelt kann mit berücksichtigt werden (Türen, Fahrstühle) | ||
− | === Selbstlokalisation | + | ==== 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 | * Grundlegende Fragestellung | ||
*# 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 |
− | *#* | + | *#* 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 | + | *#* 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 | ||
− | + | === Rein odometriebasierte Verfahren === | |
* nur interne Sensorinformationen | * nur interne Sensorinformationen | ||
* Güte der Schätzung ist abhängig von | * Güte der Schätzung ist abhängig von | ||
Zeile 234: | Zeile 400: | ||
* Fehler ist nicht beschränkt | * 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 | * 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 | + | ** 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 === | |
− | |||
* Zustandschätzung anhand interner und externer Sensorinformationen | * Zustandschätzung anhand interner und externer Sensorinformationen | ||
− | * Ziel ist die | + | * 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 | ||
* Problem ist die robuste Detektion der Landmarke | * 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 | ||
+ | * <math> Bel(x_k) = P(x_k | d_{0..k})</math> | ||
+ | ** 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 <math> Bel^{-}(x_k)</math> | ||
+ | *** Aktionen und Beobachtungen bis zum vorangegangenen Zeitschritt (k-1) | ||
+ | ** 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> | ||
+ | * <math> P(z_k | x_k)</math> ... Sensormodell | ||
+ | * <math> P(x_k | x_{k-1},a_{k-1})</math> ... Bewegungsmodell | ||
+ | * <math> Bel(x_{k-1}) </math> ... 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 <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 | ||
+ | * muss experimentell ermittelt werden | ||
+ | |||
+ | === Probabilistisches Wahrnehmungsmodell === | ||
+ | * wird auch als Beobachtungs- bzw. Sensormodell bezeichnet | ||
+ | * gibt an, mit welcher Wahrscheinlichkeit ein Roboter im Zustand <math> x_k </math> die Beobachtung <math> z_k </math> 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 (<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 | ||
+ | *** Die Korrekturvorschrift berücksichtigt jetzt das Sensormodell und die Beobachtungen -> dadurch wird die Unsicherheit eingeschränkt | ||
+ | *** 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> | ||
+ | **** 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 == | ||
+ | * 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 | ||
+ | |||
+ | <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> | ||
+ | ------------------------------------------------ | ||
+ | __ __ __ | ||
+ | \_ _ / \ _ _ / \ _ _ resultierender Kurs eines Roboters | ||
+ | \__ / \ __ / \ __ / der einen Gang entlang fährt | ||
+ | |||
+ | ------------------------------------------------ | ||
+ | </pre> | ||
+ | * 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 | ||
+ | *# Gittermodell | ||
+ | *# 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 | ||
+ | *# 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 | ||
+ | |||
+ | [[Kategorie:Studium]] |
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:
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
- akustische
- taktile
- Bumper
- Kontaktleisten
- berührungslose
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
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
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
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)
- Vorheriges Vermessen der Umgebung und Programmieren der Karte
Selbstlokalisation
- Grundlegende Fragestellung
- 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
- relative Selbstlokalisation (pose tracking)
- initiale Pose ungefähr bekannt
- Pose soll kontinuierlich korrigiert werden
- deutliche geringerer Suchraum ==> geringerer Rechenaufwand
- globale (absolute) Selbstlokalisation
- 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
- a priori Belief
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
- Prädiktionsschritt
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
- Gittermodell
- 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
- 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