[English] [Sitemap] [Über geometrylab.de]
	Startseite > Roboter-Bewegungsplanung > Roboterstrategien in Polygonen > Search Ratio von Suchpfaden in einfach Polygonen

Anleitung

Dieses Applet dient zur Bewertung eines Suchpfades in einem einfachen Polygon mittels der search ratio sowie zur Bewertung verschiedener Suchalgorithmen, bzw. Algorithmen zur generierung des optimalen Suchpfads.

Dazu wird zuerst in der Zeichenfläche ein Polygon gezeichnet. Sobald das Polygon vollständig ist, werden die visibility cuts als grüne Lininen eingezeichnet. Anschließend kann entweder ein Suchpfad per Hand eingezeichnet werden oder in der linken unteren Ecke ein Algorithmus zur Suchpfadgenerierung gewählt werden. Der Startpunkt des Suchpfad ist dabei immer der erste Punkt des Polygons, kann jedoch mit Rechtsklick auf einer andere Polygonecke und der Auswahl von "Path start" auf diese Ecke verschoben werden.

Sobald Suchpfad und Polygon vorhanden sind, wird die search ratio berechnet und eingezeichnet. Dabei stellen die schwarzen Linien den Suchpfad, die roten Linien den kürzesten Pfad zum Punkt mit der größten search ratio und die blauen Linien (die die schwarzen teilweise überdecken) den Weg über den Suchpfad zu der Ecke mit der höchsten search ratio. Dabei wird noch für jede reflex Ecke ihre search ratio daneben geschrieben.
Zusätzlich wird noch ein zweiter Suchpfad berechnet und in pink eingezeichnet. Dieser verbesserte Suchpfad schneidet die cuts in der gleichen Reihenfolge und an den gleichen Stellen wie der originale Suchpfad, die Schnittpunkte sind jedoch mit den kürzest möglichen Pfaden verbunden, sämtliche unnötigen Umwege, die der originale Suchpfad nimm, sind dadurch entfernt.
Die search ratio des orginalen Suchpfads wird bei "SR" angezeitg, die search ratio des verbesserten Suchpfads bei "Imp. SR".

Die automatische Berechnung der search ratio lässt sich mit dem Häkchen bei "auto compute" abschalten, die search ratio wird dann erst berechnet, wenn der "Compute"-Button betätigt wird.
Mittels der "Convert"-Schaltfläche lässt sich der automatisch berechnete Pfad in einen editierbaren umwandeln.

Die Search Ratio

Die search ratio ist ein Maß, um die Güte eines Suchpfades für einzelne oder mehrere Ziele in einem bestimmten Polygon zu bewerten. Die search ratio eines einzelnen Punktes p wird festgelegt als das Verhältnis aus dem Weg, den man über den Suchpfad nehmen muss, um den Punkt zu erreichen, und dem kürzestmöglichen Weg zu diesem Punkt:

Für mehrere Ziele wird für jedes einzelne Ziel die search ratio berechnet, die höchste dieser search ratios ist dann die search ratio des Suchpfads. Für ein ganzes Polygon müsste also alle Punkte des Polygons bewertet werden, es lässt sich aber zeigen, daß die Betrachtung der reflexen Ecken, die die visibility cuts im Polygon bilden, ausreicht:

Implementierte Algorithmen/Pfadgeneratoren

1. draw by hand: Der Suchpfad wird vom Benutzer per Hand gezeichnet
2. PolyExplore: Das Polygon wird wiederholt mittels des Onlinealgorihtmus PolyExplore erkundet. Dabei wird mit einer niedrigen Suchtiefe anfangen und diese in jeder Iteration verdoppelt, bis sämtliche visibility cuts überschritten wurden.
3. Brute Force: Die Cuts werden gleichmäßig in Schnittpunkte unterteilt und dann sämtlich möglichen Pfade berechnet und der Pfad mit der geringsten search ratio ausgegeben. Findet nicht den absolut optimalen Suchpfad, die Genauigkeit der Annäherung kann aber im Sourcecode für praktisch jede Anwendung hoch genug eingestellt werden.
   Die Variante ohne Multithreading wurde entfernt, der Algorithmus verwendet derzeit zwei Threads um die Berechnung auf einem Dualcore-Prozessor zu beschleunigen.
4. Local Opt. Backwards: Für jeden cut wird genau einmal der Schnittpunkt mit der zu dem jeweiligen Zeitpunkt geringsten search ratio berechnet (d.h. die Schnittpunkte werden nacheinander lokal optimiert). Dabei wird in in der umgekehrten Reihenfolge optimiert, in der die cuts besucht werden. Da die optimale Reihenfolge der cuts nicht bekannt ist, werden alle möglichen Reihenfolgen durchprobiert.
5. Local Forward: Wie Local Opt. Backwards, nur werden die cuts in der Reihenfolge, in der sie besucht werden, optimiert.
6. Local Opt. Lowest: Wie die beiden vorherigen, nur wird hier immer der cut mit der niedrigsten search ratio optimiert.
7. Local Opt. Random: Wie die vorherigen Local-Algorithmen, nur ist die Reihenfolge, in der die cuts optimiert werden, zufällig.
8. Local Opt. SWT: Optimiert die cuts in der gleiche Reihenfolge wie Local Opt. Backwards. Allerdings werden hier nicht mehr alle cut-Reihenfolgen durchprobiert, sondern als cut-Reihenfolge die Reihenfolge gewählt, in der die Shortest Watchman Tour die cuts schneidet.
9. Local Opt. SP: Optimiert die cutsi in der gleichen Reihenfolge wie Local Opt. Backwards. Allerdings werden hier nicht mehr alle cut-Reihenfolgen durchprobiert, sondern die cuts nach der Länge der kürzesten Pfade der zugehörigen reflexen Ecken sortiert.
10. Shortest Watchman Tour: Für das Polygon wird wiederholt die Shortest Watchman Tour bis zu einer bestimmten Suchtiefe berechnet, wobei die Suchtiefe in jeder Iteration verdoppelt wird.

Autor: Jörg Wegener

Adaptiert aus: Fleischer, R; Kamphans, T.; Klein,R.; Langetepe, E.; Trippen, G.: Competitive online approximation of the optimal search ratio, Siam J. Comput. (2008), 881–898.

© Universität Bonn, Informatik Abt. I - - Letzte Änderung 21-07-2009 18:33