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 |
| + | ** hierarchisches Paradigma (Sens → Plan → Act) |
| + | ** reaktives Paradigma (Sens → Act ) |
| + | ** hybrid deliberativ/reaktiv |
| + | <pre> |
| + | Plan |
| + | ↑ |
| + | ↓ |
| + | Sens ←----→ Act |
| + | </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 |
| + | ** 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 == |
| + | |
| + | <pre> |
| + | o O o |
| + | | |
| + | | |
| + | o O o ← Castorräder |
| + | ↑ |
| + | Antriebsränder |
| + | </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> |
| + | O ← angetriebenes lenkbares Rad |
| + | | |
| + | O ----- O ← Passivräder |
| + | </pre> |
| + | |
| + | * 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 == |
| + | |
| + | <pre> |
| + | O ---- O ← drehbare Antriebsränder |
| + | | | |
| + | | | |
| + | 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 |
| + | * übermitteln von Statusinformationen |
| + | * kritische oder mehrdeutige Situtationen auflösen |
| + | * 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 |
| + | ** 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:''' |
| + | <pre> |
| + | Empfänger \ ___ |
| + | /| \ \ / \ |
| + | | | ) | | | | Hindernis |
| + | \| / | \ ___ / |
| + | Sender / |
| + | | / | |
| + | |←--------------------→| |
| + | gemessene Entfernung |
| + | </pre> |
| + | |
| + | <math>d = c \cdot \frac{t}{2}</math> |
| + | * 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:''' |
| + | # ü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 |
| + | <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 |
| + | *# 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 |
| + | * 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 |
| + | * <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]] |