Navigation

• Wo bin ich ? (Self Localization)

  • realtive Positionierung mit internen Sensoren

  • absolute Positionierung anhand von Marken

  • probabilistische Positionierung

  • Lokalisierung und Bewegungsunschärfe

• Wohin soll ich gehen? (Task Planning)

• Wie komme ich dahin? (Path Planning)

  • Karten

  • Pfadplanung

  • Visibility Graph und Value Iteration

Unsicherheiten

• stochastische Roboterbewegung

• stochastische Umgebung

• Sensoren rauschen, nehmen nicht allles wahr

• Algorithmen sind nur Nährungslösungen

Interne Repräsentation der Welt sind nur Schätzungen

• Positionsglaube in externen Referenzsystem

• 
  

• Positionsschätzung mittels Beobachtung der eigenen Bewegung, der Bewegungsorgane oder des Bewegungsbefehls

• Alte Position + Beobachtung der Eigenbewegung => Position

  • Odometrie

  • Trägheitsnavigation

Relative Positionierung mittels Beobachtung der Antriebsräder

• antriebsabhängig - differentieller Antrieb

• Systematische Fehler

  • Mittelwert Fehler ungleich 0 - kalibrierbar

• Unsystematische Fehler durch stochastische Welt

  • 
    

Modellierung der Fehler für Simulation eines Roboters, für probabilistische Lokalisierungsverfahren - Prognoseschritte

Fehlerarten:

• Entfernungsfehler

• Drehfehler

• Driftfehler

unscharfes Bewegungsmodell

• geeignete Odometrieräder

• Kalibrierung

  • reduziert systematischen Fehler

• Verwendung von Richtungssensoren

  • relative Messung: Gyroskope, Winkelgeschwindigkeit

  • absolute Messung mit Kombass (besser)

• Abgleich mit Wahrnehmung

  • Ständiger Abgleich der geschätzten Position mit aktueller Wahrnehmung der Umgebung

• Beobachtung der Umwelt => Position

Grundidee: Positionsbestimmung anhand natürlicher oder künstlicher Landmarken mit bekannter Position

Objekt/ Merkmal mit Eigenschaften

• Wahrnehmbar (Sensorik, Blickwinkelabhängig)

• Informationsgehalt (eindeutigkeit)

• bekannte Position im Weltmodell (in Karte)

• relative Position zum Roboter bestimmbar (bspw. Entfernung und Richtung zur Landmarke)

• Positionsbestimmung durch Entfernungsmessung zu bekannten Landmarken

• Positionsbestimmung durch Winkelmessung zu bekannten Landmarken

Relative Positionierung: auf kurze Distanz genau, aber zunehmende Ungenauigkeit

Absolute Positionierung: prima, aber Landmarken nicht immer sichtbar oder mehrdeutig (langer Korridor)

Offene Fragen:

• Wie können sich relative und absolute Positionierung ergänzen?

• Wie kann die Unsicherheit in der Position repräsentiert werden?

• Natürliche Landmarken

  • Berge, Bäume, Wände, Sterne, Sonne, Magnetfeld

  • Sensoren: passiv: Kamera, aktiv: Laserscanner

• Künstliche Lamndmarken

  • Passive ohne explizite Navigationsfunktion

  • Aktive (Baken/ Beacons) für Navigationszwecke installiert

    • Leuchtturm

    • GPS

    • Thermale Markierungen

• Probabilistische Lokalisierung Synthese

  • (Monte Carlo Localization in ARIA, in ROS)

Navigation innerhalb der Sensorreichweite

• real-time obstacle

• avoidance algorithms

sichtbarer Zielpunkt, Türdurchfahrt, Kollisionsvermeidung, Linienfolgen

starke Sensorkopplung, reaktive Ansätze

Navigation außerhalb der Sensorreichweite

Navigation im Großen, Grobplannung

• planning algorithms (Suchalgorithmen)

Planung optimaler Wege, Vermeidung Umwege & Sackgassen

Lose Sensorkopplung, Karte zwingend

• Kollisionsfreiheit

• Länge

• Fahrzeit

• Gesamtrotation

• Rechenzeit

• Sicherheit

• Coverage

• Küstennähe

Mehrzielotimierung

Wichtig für logale Navigation:

• Umweltdynamik

• Zeitbeschränkung

Wichtig für globale Navigation:

• Aufgabenänderung

• Vorausplanung

Kombination ergibt Steuerungsarchitektur mit Navigator, Pilot .. allerdings nicht unproblematisch

• in topologischen Karten

  • Graphensuche

• in geometrischen Karten

  • Roadmap

    • Visibility Graph

    • Vonoroi Diagramme

  • cell decomposition

    • regionsorientiert: Exakt/ Approximiert

  • Potenzialfeld

  • Value Iteration

Konstruktion eines Graphen aus befahrbaren Wegen im

freien Raum => ergibt Roadmap (ungerichteter Graph)

damit

• Einschränkung der Komplexität

• Anwendung von Suchalgorithmen möglich, z.B. A*

Idee:

• Paarweises Verbinden der Hindernisecken, des Startpunktes und Zielpunktes im freien Raum,

• zusätzlich die Objektkanten

Anschließend Pfadsuche im Graph

• Pros: Vollständig, optimal

• Cons: semifreie Pfade, Kantenanzahl wächst exponentiell

• Wie finden wir den Weg in dem Graphen?

  • A*

Komplexitätsreduktion – Reduzierter Visibility Graph

• Löschen ungünstiger Kanten

• Konkave Ecken weglassen

Qualität des Weges, Stochastische Umwelt

• Aufblähen der Hindernisse (obstacle growing)

Komplexität und Qualität

• Moravec, kreisförmiges Aufblähen der Hindernisse um Ungewissheit

• dadurch unvollständig, eventuell Verlust des optimalen Weges

Pfadplannung in geometrischen Karten

Ausgangspunkt: geometrische Karte mit Hindernissen und Zielpunkt

• Ziel - hohes anziehendes Potential

• Hindernisse - hohes abstoßendes Potential

Vorgehen

• erstllen Potentialfeld

• berechnung des Vektorfeldes

• Fahrt in Richtung der Vektoren

• mächtige Methode zur Planung bei Unsicherheit

• einfach, intuitiv, wiederverwendbar

• grundidee vieler Verfahren in der lokalen Navigation

• Erstellung aufwändig bei Value Iteration

• einfache Potentialfelder können lokale Minima enthalten

• bewegliche Hindernisse und Objekte

• Kinematik des Roboters

• Unsicherheit der Karte, der Beobachtung, der Bewegung

• Pfadplannung in der Karte (globale Navigation) und Durchführung der Fahrt (lokale Navigation)

• Unsicherheiten der Sensordaten und der Bewegung können zu Abweichungen der angenommenen Position von der realen Position führen

• Lösung: probabilistiscche Lokalisierung oder ausreichende Genauigkeit der absoluten Positionierung

Eine Karte ist ein Modell der Umwelt, welches die für die Navigation relevanten Aspekte der Umwelt abbildet.

=> ein Weltmodell, eine Wissensrepräsentation

Was ist eigentlich ein Modell?

• Abbildung

• Verkürzung

• Pragmatische Funktion

• Positionierung (Lokalisierung)

• Exploration (Mapping)

• Pfadplannung

• Hindernisse und Freiräume

• Entfernungen

• Unsicherheit

• Gefährlichkeit

• Dynamik

• Ziele, Windverhältnisse, Ladestationen …

• Gittermodell mit Koordinaten

Belegungsgitter (engl. occupancy grid)

• Kachelwert zeigt Hindernis {Belegt, Frei, Unbekannt}

• Unwissen wird repräsentiert

Probleme

• Auflösung

  • kleine KAcheln - Speicherplatz und Rechenzeit

  • großen Kacheln - keine kleine Objekte, Freiräume dargestellt

  • Lösung quadtree

• aufwändiges Update von Objektpositionen

Vorteile

• zeigt freien Raum - für Pfadplannung benötigt

Topologische Karten sind Graphen

• Knoten: Orte mit Bedeutung (Aktionsmöglichkeiten, Entscheidungspunkte)

• Kanten: Wege, Aktionen zwischen diesen Orten, Beziehungen

• menschlichen Vorgehensweise ähnlicher

• Höherer Abstraktionsgrad, Segmentierung

• Speicherplatzsparend

• Anwendung in der globalen Navigation

topologische Karte + A* -> Wegeplanung