[German] [Sitemap] [About geometrylab.de]
	Home > Robot Motion Planning > Robot motion planning in polygons > Search Ratio Of Search Paths In Simple Polygons

Manual

This applet evaluates a search path in a certain simple polygon via the search ratio as well as a number of search algorithms and algorithms for computing the optimal search path.

For this first a polygon has to be drawn in the drawing area. As soon as the polygon is complete the visibility cuts will be shown as green lines. Then you can either draw a search path by hand or choose a search path generating algorithm. The start point is always the first point of the polygon, but it can be changed via rightclicking a different point and choosing "Path start" in the popup context menu.

As soon as a polygon and a search path have been drawn the search ratio is computed and drawn in. Black lines mark the search path, blue lines the path to the polygon point with the highest search ratio taking the route along the search path and red lines the shortest path to that point. The search ratio of each reflex vertex is drawn next to it.
Additionally a second search path is calculated and drawn in pink. This improved search path cuts the visibility cuts in the same order and points as the original search path, but it connects these points with the shortest paths respectively. All detours the original search path might contain are eliminated by this.
The search ratio of the original search path is shown at "SR", the search ratio of the improved search path is shown at "Imp. SR".

The automatic computing of the search ratio can be turned off by unchecking "auto compute", the search ratio is then only calculated by clicking the "Compute" button. The "Convert" button converts a generated path into an editable one.

The Search Ratio

The search ratio is used to evaluate the quality of a certain search path in a certain polygon. The search ratio of a single point p is set as the ratio of the route a long the search path to p and the shortest path to p possible.

For multiple targets the search ratio for each target has to be computed, the highest of these search ratio denotes then the search ratio of the entire search path. For a whole polygon all points would have to be evaluated. Fortunately it can be proven that only the reflex vertices which make up the visibility cuts have to be evaluated:

Implemented Algorithms/Path Generators

1. draw by hand: The search path is to be drawn by the user by hand
2. PolyExplore: The Polygon is search repeatedly using the PolyExplore algorithm, the search depth starts relatively small and is doubled in each iteration until the whole Polygon is explored.
3. Brute Force: The cuts are divided evenly into intersection points. Then all possible paths using these points are calculated, the final path is the one with the lowest search ratio. This does not compute the optimal search path (an algorithm for that is still unknown), but the approximation can be set to be as accurate as needed (not in the applet itself but in its source code).
   The version without multithreading has been removed. The algorithm uses two threads to increase calculation speed on dual core processors.
4. Local Opt. Backwards: For each cut the intersection point with the lowest search ratio for the polygon at that moment is computed once (each intersection point is optimized locally once one after the other). They are optimized in backward order, meaning the last visited cut is optimized first. Since the optimal order of the visibility cuts is not known, all possible orders are computed.
5. Local Forward: Same as Local Opt. Backwards, but the cuts are optimized in the same order as they are visited.
6. Local Opt. Lowest: Same as above, but the cut with lowest search ratio that has not been optimized yet is optimized.
7. Local Opt. Random: Same as above, but the cuts get optimized in a random order.
8. Local Opt. SWT: The cuts are optimized in the same order as in Local Opt. Backwards. Instead of comparing every possible cut order the order in which the Shortest Watchman Tour crosses the cuts is taken as cut order.
9. Local Opt. SP: The cuts are optimized in the same order as in Local Opt. Backwards. Instead of comparing every possible cut order the are sorted regarding the length of the shortest paths to their reflex vertices.
10. Shortest Watchman Tour: The Shortest Watchman Tour is computed repeatedly with a restricted search depth which is doubled each iteration.

Author: Jörg Wegener

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

© University of Bonn, Computer Science I - - Last modified 21-07-2009 18:33