Lower bounds for the polygon exploration problem

Lower Bounds for the Polygon Exploration Problem Extended Abstract Roland Hagius aChristian Icking aElmar Langetepe b aFernUniversit¨at Hagen, Praktische Informatik VI, 58084 Hagen, Germany bUniversit¨at Bonn, Institut f¨ur Informatik I, 53117 Bonn, Germany Abstract We improve the best known lower bound for the polygon exploration problem from 1.2071 to 1.2825. 1. Introduction Exploring an unknown environment is a basic problem for autonomous mobile systems. Here, we suppose that a simple polygon in the plane represents the unknown environment and a pointshaped robot with a vision system, starting at some boundary point s, has the task of going around inside the polygon until the whole environment has been visible at least once before returning to s. Seeing all points inside the polygon is clearly equivalent to seeing its whole boundary, as long as the polygon is simple (does not contain holes, as we assume). The shortest watchman tour starting and ending in sis the shortest tour that can see the whole polygon, see figure watchman. This is the perfect solution in a known environment, and it can be computed using the algorithms of Chin and Ntafos or Tan and Hirata [1,3,7,8]. But in an unknown environment the shortest watchman tour is also not known, so any tour that explores the polygon online is inevitably longer than the shortest watchman tour; there are exceptions for special cases [2]. So it is an interesting question to ask for a strategy that produces exploration tours that are not so much longer than the perfect solution in a known polygon, and Hoffmann et al. [4] have given such a competitive exploration strategy. This strategy guarantees a tour that is at most 26.5 times as long as the shortest watchman tour. Although this upper bound is most probably not tight, it is not really obvious how to prove a shorter s Fig. 1. A shortest watchman tour. factor by enhancing this rather complicated proof or by giving a better strategy. And the worst case that is known for this strategy has a factor of just 5. 2. First ideas for lower bounds In this paper we propose to look at this problem “from the other side”: what is a lower bound for this problem, i. e., can we show that no strategy can guarantee a competitive factor less than this lower bound? A proof for such a bound can be given by a concrete polygon for which we have to show that an arbitrary strategy will necessarily make a certain detour as compared to the shortest tour. A trivial lower bound is (√2 + 1)/2≈1.2071, see the left picture in Fig. 2: we use an isosceles, rectangular triangle, the start point sis at the right angle and at the other two corners there are two very small 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry ss Fig. 2. Deriving the lower bounds 1.2071 (left) and 1.2145 (right). pockets. One of the pockets is formed such that the corner must be visited while the other is not. The line segment connecting the two corners is called a threshold. To trick any strategy to make a detour we can wait until this threshold is reached: if this occurs left of the midpoint then the right corner must be visited, and vice versa. Thus, only when the robot eventually visits the threshold, it can see which corner is still to visit. Now it is easy to see that we have a lower bound of (√2 + 1)/2 here. In fact we can act as the malicious adversary of a strategy: depending on the decisions of the strategy we decide how the polygon looks like at those parts that have not been seen yet. For example, the previous idea can be refined by introducing a second threshold, see the right picture in Fig. 2. First, we let the strategy reach the line between the two corners as before. Here, we reveal one of the corners, but in contrast to the first example for the second corner two possibilities remain: either we have to visit the corner itself or it suffices to reach the second threshold which is a diagonal line through the corner. After carefully choosing the lengths and the angles (the triangle is still isoceles, but the angle at sis 96.99◦) we obtain a bound of 1.2145, which constitutes a small progress. 3. Using more thresholds But this idea of several thresholds can be driven further. In the following, we sketch our approach with three thresholds. The basic figure is a triangle, but from one of its corners there are edges to an inner point, this will be the starting point s, see Fig. 3. So besides vertex sthere are four corners in the scene with a hidden pocket. The pockets may be formed such that the corner must be visited or not, this is the information which is unknown at the start. Any tour, also the shortest watchman tour, has to visit at least all three thresholds. It is also clear that a reasonable strategy will visit the thresholds in the same order as they appear along the triangle, otherwise an even bigger detour will be generated. Now on each threshold we place a critical point: if the robot visits the threshold to the right of the critical point (as seen from s) then we as the malicious adversary decide that the left corner of the threshold must also be visited. If the visit occurs to the left of the critical point then the threshold is done except for the last one where we decide that in this case the right corner has to be visited. We as the adversary are free to decide about the exact shape of the triangle, the placement of s, and also the placement of the critical points. This is a challenging optimization exercise with many degrees of freedom and several interwoven levels of optimization, which probably can only be solved numerically. Due to the lack of space we can only briefly summarize our result obtained with the help of Cabri Geometry [5,6], see Fig. 4. We use an equilateral triangle (but it is not clear if this is the best) and a starting point sas shown in the figure. For each threshold there is one uncertainty, so we have eight cases altogether. For each case we take the length of the shortest watchman tour and compare it to the tour passing through the critical points and the corners that have to be visited in that case. The minimum of these eight ratios which we have determined to be at least 1.2825 is a lower bound for the exploration problem. March 25-26, 2004 Seville (Spain) two more hidden pockets here s Fig. 3. A triangle-like polygon with three thresholds and four hidden pockets. 4. Conclusions The new lower bound of 1.2825 for the polygon exploration problem represents a certain progress, but we think that with our technique one can go some further steps in that direction. Since the optimization problem presented here has so many degrees of freedom and consists of several levels that mutually depend on each other, we can not be sure, yet, to have found the global optimum for the three thresholds. Furthermore, it looks promising, but tedious, to introduce four or even more thresholds, but since the number of cases will be about two to the power of the number of thresholds, there is some considerable work to be done. Finally, it is interesting to note that there is still a great gap between the lower bound obtained in this way and the best known upper bound of 26.5. References [1] W.-P. Chin and S. Ntafos. Shortest watchman routes in simple polygons. Discrete Comput. Geom., 6(1):9–31, 1991. [2] X. Deng, T. Kameda, and C. Papadimitriou. How to learn an unknown environment I: The rectilinear case. J. ACM, 45(2):215–245, 1998. [3] M. Hammar and B. J. Nilsson. Concerning the time bounds of existing shortest watchman route algorithms. In Proc. 11th International Symposium on Fundamentals of Computation Theory, volume 1279 of Lecture Notes Comput. Sci., pages 210–221. Springer- Verlag, 1997. [4] F. Hoffmann, C. Icking, R. Klein, and K. Kriegel. The polygon exploration problem. SIAM J. Comput., 31:577–600, 2001. [5] J.-M. Laborde. Some issues raised by the development of implemented dynamic geometry as with Cabrig´eom`etre. In Abstracts 15th European Workshop Comput. Geom., pages 7–19. INRIA Sophia-Antipolis, 1999. [6] J.-M. Laborde and F. Bellemain. Cabri Geometry II. Texas Instruments, Dallas, 1993. [7] X. Tan and T. Hirata. Constructing shortest watchman routes by divide-and-conquer. In Proc. 4th Annu. Internat. Sympos. Algorithms Comput., volume 762 of Lecture Notes Comput. Sci., pages 68–77. Springer- Verlag, 1993. [8] X. Tan, T. Hirata, and Y. Inagaki. Corrigendum to “an incremental algorithm for constructing shortest watchman routes”. Internat. J. Comput. Geom. Appl., 9(3):319–323, 1999. 20th European Workshop on Computational Geometry SWT 24,24 cm SWT 23,39 cm SWT 17,04 cm SWT 20,45 cm SWT 18,24 cm SWT 17,39 cm SWT 13,77 cm SWT 15,97 cm Tour 31,09 cm Tour 30,00 cm Tour 21,87 cm Tour 26,25 cm Tour 23,46 cm Tour 22,35 cm Tour 17,70 cm Tour 20,55 cm C 1,282535654 C 1,2827339161 C 1,283498585 C 1,28371123 C 1,285728851 C 1,28511096 C 1,28541435 C 1,28663922 Fig. 4. Eight cases for three thresholds.