Planungsverfahren

• Exakte Verfahren: basiert auf exaktem (in algebraischer Form beschriebenen) Umweltmodell. Beispiel: Retraktion, Voronoi.
• Approcimierte Verfahren: Umwelt durch Näherung beschrieben (Kuben, Zylinder, Polyeder,...). Beispiel: Sichtgraph.
• Straßenkarten:
  • Gegeben: 2-dim. Weltmodell, Start und Ziel
  • Aufgabe: Suche günstigsten Weg von Start zu Ziel
  • Lösung:
    1. konstruiere Netz von Wegen $\mathrm{\Bbb{W}}$ in $\mathrm{I \hspace{-0.17em} K }_$Frei
    2. bilde $K_$Start auf $K_$Ziel ab: $(\mathrm{\Bbb{W}}(K_$Start$), \mathrm{\Bbb{W}}(K_$Ziel$))$
  • Wegkonstruktion mit: Retraktionsverfahren (z.B. Voronoidiagramm)
  • Suche im Netz mit z.B.: Baumsuche, wuklidischer Abstand, Potentialfeld
  • Retraktion: Sei $X$ eine Menge und $Y \subset X$. Eine surjektive Abbildung $p: X \longmapsto Y$ heisst Retraktion gdw. $p$ stetig und $p(y) = y; \forall y \in Y$. D.h. Abbildung der Menge $X$ auf ihre Teilmenge $Y$, wobei die Menge $Y$ auf sich selbst abgebildet wird.
  • Für die Bahnplanung gilt: Y ist ein Netz von eindimensionalen Kurven (Wegenetz); Retraktionsmethoden unterscheiden sich in der Wahl von p.
  • Voronoi-Diagramm ist ein Beispiel für p: mittlerer Abstand (Folie 30)
  • Sichtgraphen: Konstruktion:
    • Verbinde jedes Paar von Eckpunkten auf dem Rand von $\mathrm{I \hspace{-0.17em} K }_$Frei durch ein gerades Liniensegment, wenn das Segment kein Hindernis schneidet.
    • Verbinde $q_$Start mit $q$Ziel analog dazu. Beispiele (Folie 32)
  • Anmerkungen zur Sichtgraphmethode:
    1. Wege sind ``halbfrei'' (nicht kollisionsfrei), da Hinderniskanten auch Wegsegmente darstellen können. Abhilfe durch Erweiterung der Hindernisse (durch Kreis (um Roboter und Kreisradius um Hindernisse) oder durch Rechteck).
    2. Wenn ein Weg gefunden ist, ist es auch der kürzeste Weg (!!)
    3. Methode ist exakt, wenn der Roboter nur 2 translatorische Freiheitsgrade hat und alles durch polygone darstellbar ist.
    4. auch im $\MR ^3$ anwendbar. (Dann allerdings sind gefundene Wege nicht mehr unbedingt die kürzesten Wege).
• Zellenzerlegungsmethoden:
  • Lösung:
    1. Zerlege $\mathrm{I \hspace{-0.17em} K }_$Frei in solche Zellen, dass ein Weg zwischen 2 Konfigurationen innerhalb einer Zelle leicht zu finden ist
    2. Stelle Adjazenz (Nachbarschaft) Relation in einem Graphen dar
    3. Suche optimalen Weg von q(Start) nach q(Ziel) in dem Graphen
  • Exakte Zellenzerlegung:
    • Lösung: Zerlege Freiraum so, dass Zellen disjunkt und Zerlegung vollständig.
    • Exakte Zellenzerlegung mit ``line-sweep''-Operator (Senkrechte Linie von jeder Ecke aus bis zum nächsten Hindernis oder zur ``Wand'') Zellen nummerieren.
    • Verbindungsgraph der freien Unterräume: Zellen = Knoten, Kanten = freie Übergnage zwischen benachbarten Zellen.
  • Approximative Zellenzerlegung:
    • Lösung:
      1. Zerlege Freiraum in Zellen vordefinierter Form (z.B. Rechtecke,Quadrate)
      2. Wenn Zelle nicht vollständig im Freiraum liegt, verringere Größe und zerlege Zelle weiter (z.B. Quadtree).
      3. Diese Schritte nur bis zu einer Minimalgröße der Zelle anwenden.
    • Vorteil: einfache Zerlegung $\rightarrow$ einfache Wegsuche
    • Nachteil: Freiraum kann i.A. nur annähernd beschrieben werden.
    • Approximative Zellenzerlegung: Graphengenerierung: Quadtree: Zerlege Quadrat in vier gleich grosse Teiquadrate. Baumstruktur mit Nummern 0-3 (Nummerierung im Gegenuhrzeigersinn, Anfang unten links im Quadrat; Bei Unterteilung eines Quadrates $\rightarrow$ akt. Knoten wird Vaterknoten von neuer Vierergruppe). (Siehe Folie 41-44)
• Potentialfelder:
  • Roboter bewegt sich unter dem Einfluss von Kräften, welche ein potentialfeld auf ihn ausübt. (Abbildung U von $\mathrm{I \hspace{-0.17em} K }_$Frei nach $\MR$).
  • Ziel hat Anziehungspotential
  • Hindernisse haben Abstossungspotential
  • Die Summe der einwirkenden Kräfte bestimmen die Bewegung.
  • Eigenschaften Abstossungspotential:
    • In geringem Abstand zu Hindernissen sollen keine Potentialbarrieren (lokale Minima) entstehen, welche der Roboter nicht durchqueren kann.
    • In großem Abstand zu Hindernissen soll der Roboter nicht beeinflusst werden.
  • Eigenschaften Anziehungspotential:
    • Es soll nur ein Minimum in q(Ziel) geben
  • Lokale Minima:
    • Problem: Durch Summation kann U lokale Minima besitzen, in denen der Roboter steckenbleiben kann.
    • Lösung: An-/Abstossungspotentiale so wählen, dass kein lokales Minimum (ausser q(Ziel)) existiert; Im Suchalgorithmus Techniken zur Flucht aus lokalen Minima anwenden.
  • Andere Bahnplanungsverfahren: Sensorgestützte Bahnplanung (Klassen B,D); Algebraische Methoden (bei einfachen Umweltmodellen); Konnektionistische Methode (Wissen über Umwelt wird implizit in neuronalen Netzen repräsentiert).