<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
- 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=c\cdot {\frac {t}{2}}$

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
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
$Bel(x_{k})=P(x_{k}|d_{0..k})$ $Bel(x_{k})=P(x_{k}|d_{0..k})$
- 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 $Bel^{-}(x_{k})$ $Bel^{-}(x_{k})$
  - Aktionen und Beobachtungen bis zum vorangegangenen Zeitschritt (k-1)
- a posteriori Belief $Bel^{+}(x_{k})$ $Bel^{+}(x_{k})$
  - Zusätzlich zum a priori Belief werden noch die aktuellen absoluten Informationen mit berücksichtigt

iterative Berechnungsvorschrift für den Belief:
$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}$

$P(z_{k}|x_{k})$ ... Sensormodell
$P(x_{k}|x_{k-1},a_{k-1})$ ... Bewegungsmodell
$Bel(x_{k-1})$ ... 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 $x_{k}$ erreicht wenn der vorher im Zustand $x_{k-1}$ war und Aktion $a_{k-1}$ 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 $x_{k}$ die Beobachtung $z_{k}$ 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 ( $x_{k}=x_{k-1}+s+w_{k}$ ) unter Berücksichtung der Rauschprozesse (Bewegungsmodell)
  - für die Unsicherheit gilt: ${\sigma _{1}}^{2}={\sigma _{0}}^{2}+{\sigma _{w}}^{2}$
- Korrekturschritt
  - Die Korrekturvorschrift berücksichtigt jetzt das Sensormodell und die Beobachtungen -> dadurch wird die Unsicherheit eingeschränkt
  - Unsicherheit nach Prädiktion und Korrektur ${\sigma _{1}}^{2,+}=(1-K)\cdot {\sigma _{1}}^{2}$
  - mit $K={\frac {\sigma _{1}^{2}}{\sigma _{1}^{2}+\sigma _{\nu }^{2}}}$ $K={\frac {\sigma _{1}^{2}}{\sigma _{1}^{2}+\sigma _{\nu }^{2}}}$
    - Wichtung für Berücksichtigung der Beobachtung in Zustandsschätzung
    - $\sigma$ der Beobachtung klein: $K\rightarrow 1$
    - $\sigma$ der Beobachtung groß: $K\rightarrow 0$
- 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