Finding a door along a wall with an error afflicted robot

Finding a door along a wall with an error afflicted robot Tom Kamphans aand Elmar Langetepe a aUniversity of Bonn Institute of Computer Science I R¨omerstraße 164 53117 Bonn Germany http://web.informatik.uni-bonn.de/I/agklein.html Abstract We consider the problem of finding a door in a wall with a blind robot, that does not know the distance to the door or whether the door is located left hand or right hand to its start point. This problem can be solved with the well-known doubling strategy yielding an optimal competitive factor of 9 with the assumption, that the robot does not make any errors during its movements. We study the case, that the robots movement is errorneous. We give upper bounds for the movement error, such that reaching the door is guaranteed. More precisely the error range δhas to be smaller than 1 3. Additionally, the corresponding competitive factor is given by 1 + 8 1+δ 1−3δ. Keywords: Online algorithm, Online motion planning, searching, competitive ratio, errors. 1. Introduction Online motion planning in unknown environments is theoretically well-understood and practically solved in many settings. During the last decade many different objectives where discussed under several robot models. For a general overview of theoretical online motion planning problems and its analysis see the surveys [3,9,10,7]. Theoretical correctness results and performance guarantees often suffer from idealistic assumptions, therefore in the worst case a correct implementation is impossible. On the other hand practioners analyze correctness results and performance guarantees mainly statistically. Therefore it is useful to investigate, how online algorithms with idealistic assumptions behave, if those assumptions cannot be fulfilled. More precisely, can we incorporate assumptions of errors in sensors and motion directly into the theoretical analysis? We already successfully considered the behaviour of the well-known pledge algorithm, see Abelson Email addresses: [email protected] (Tom Kamphans), [email protected] (Elmar Langetepe). and diSessa [1] and Hemmerling [6], in the presence of errors [8]. The task of finding a point on a line without knowing the direction or the distance to the start point was considered by Baeza-Yates et. al. [2] and independently by Gal [5] and lead to the so called doubling strategy, which gives a basic paradigma for other searching algorithms, i.e., searching for a point on mrays or approximating the optimal search path, see [4]. Under the competitive framework doubling with a factor of two is the optimal strategy for searching a point on the line. The competitive analysis compares the cost of the strategy with the cost of a solution which is computed under full information, see [2]. In this paper we investigate how the doubling strategy behaves in the presence of errors and how the error influences the correctness and the corresponding competitive factor of the strategy. We assume that an error range for a single step is known in advance but the agent gets no further information about the cummulated error. Therefore for the agent it makes no sense not to use the doubling heuristic. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry 2. The lost cow problem The task is to find a door in a wall, respectively a point, t, on a line. The robot does not know whether tis located left hand or right hand to its start position, s, nor does it know the distance from sto t. Baeza-Yates et. al. [2] describe the strategy to solve this problem using a function f.f(i) is the distance the robot walks in the ith step. If iis odd, the robot moves f(i) steps from the start to the right and f(i) steps back; if iis even, the robot moves to the left. It is assumed, that the movement is correct, so after moving f(i) steps from the start point to the right and moving f(i) steps to the left, the robot has reached its start point. Baeza-Yates et. al. showed, that a strategy with f(i) = 2iis 9competitive and this is optimal. An online strategy that produces a path of length |πonl|is called C-competitive if for all scenes |πonl| ≤ C· |πopt|+A holds, where |πopt|denotes the path length of the optimal strategy which makes use of full information. 3. Modelling the error The robot moves straight line segments of a certain length from the start point alternately to the left and to the right. Every movement can be afflicted with an error, that causes the robot to move more or less far than expected. However, we require the robots error in every step is within a certain error bound, δ. More precisely if the strategy moves the robot a distance ℓwe require that the covered distance is in the range [ℓ·(1 −δ), ℓ ·(1 + δ)] with δ∈[0,1[. 4. Reaching the door How large can the error bound δbecome under the restiction, that the robot should be able to reach the door? W. l. o. g. we consider the case, that the door is located on the same side as the first step of the agent. We assume that the door is located at d= 22j−ε, so an error-free robot hits the door during the iteration with step width f(j) = 22j. s′ s ∆2j+2k−1d 22j+2k 4−δ 2−δ 2 + δ 1 + δ 1−δ Fig. 1. In the worst case, the start point of every iteration drifts away from the door. The vertical path segments are to highlight the single iterations, the robot moves on horizontal segments only. In the worst case, every step to the right of the error afflicted robot is too short and every step to the left is too long, so start point of the iterations drifts to the left, see Fig. 1. Let ∆kdenote the drift after kiterations. ∆k= k X i=0 2i·(1 + δ) | {z } Steps, that are too long −2i·(1 −δ) | {z } Steps, that are too short  = 2δ· k X i=0 2i= 2δ(2k+1 −1). Let the error afflicted robot miss the door during the iteration with step width f(j) = 22jdue to the drift to the left. Now we are interested in the number of additional steps, and whether the robot is able to reach the door at all. Obviously the reachability and the number of additional steps depends on the error δ. If the robot hits the door, it will hit in the iteration with a step with of 22j+2k, k∈N>0, because the door is located right hand to the start point. To ensure, that the robot hits the door, the length of the last straight path must be at least as large as the distance to door plus the overall drift to the left. The last straight path may be error afflicted again, but its length is a least the lower bound of the error range in the iteration 22j+2k. This yields March 25-26, 2004 Seville (Spain) ∆2j+2k−1+d≤22j+2k·(1 −δ) ⇔2δ·22j+2k−2δ+ 22j−ε≤22j+2k−22j+2kδ ⇒22j2δ22k+ 1 −22k+δ22k−2δ <22j3δ22k+ 1 −22k≤ε ⇔δ≤1 3 22k−1 22k+ε 3·22j+2k ⇒δ≤1 3 22k−1 22k The last term converges for k→ ∞ to 1 3. Thus Corollary 1 If the error δis not greater than 1 3 the robot will hit the door. With the given analysis it is also possible to present relations between the error range and the number of additional iterations. For example: Corollary 2 If the error δis not greater than 1 4 the robot will hit the door with only one iteration step more than the error-free robot. 5. Analyzing the performance W. l. o. g. for the competitive setting it would be the worst, if the door is hit during the iteration with step width 22j+2, but located just a litte bit further away than the rightmost point that was reached during the iteration with step width 22j, i. e. d= 22j(1 −δ)−∆2j−1+ε= 22j(1 −3δ) + 2δ+ε. This yields a factor of |πonl| d=1 d 2 2j+1 X i=1 2i+ ∆2j+1 +d! =1 d2·(22j+2 −1) + 2δ(22j+2 −1) + d =22j8(1 + δ)−1+δ+ε 22j 22j1−3δ+2δ+ε 22j+ 1 <81 + δ 1−3δ+ 1 To show that this is the worst case, we show that the robots errors in the left and in the right direction are different. Furthermore the error in each step may be a different one. Let δ+ ibe length of the movement to the right in the i-th step and δ− ibe the length of the movement to the left. Now 2j−1 X i=1 (δ− i−δ+ i) denotes the deviation from the start point before the 2j-th step and 2j−1 X i=1 (δ− i+δ+ i) is the path length up to this point. As above the door is hit during the step 2j+ 2, therefore its distance is d=δ+ 2j−∆2j−1+ε =δ+ 2j− 2j−1 X i=1 (δ− i−δ+ i) + ε For the corresponding path length we have |πonl|= 2j+1 X i=1 (δ− i+δ+ i) + 2j+1 X i=1 (δ− i−δ+ i) + d due to the fact that we will finally stop at distance d, we add the deviation to d. With this we get |πonl| d= 1 + P2j+1 i=1 (2δ− i) δ+ 2j−P2j−1 i=1 (δ− i−δ+ i) + ε We can conclude that the ratio achieves its maximum if we exceed every δ− ito the greatest extend, which is 2i(1 + δ). Now we only have to fix δ+ iin order to maximize the ratio. Obviously the nominator gets its smallest value if every δ+ iis very small, therefore we use δ+ i= 2i(1 −δ). Theorem 3 If the error δis not greater than 1 3the robot will hit the door with the doubling strategy. The generated path is not longer than 81+δ 1−3δ+ 1 times the shortest path to the door. 6. Summary We have analyzed a simple doubling strategy to find a door in a wall respectively a point on a line in the presence of errors in movements. We showed that the robot is still able to reach the door if the error is less than 1 3. Moreover, if the error is less than 1 4the robot will need at most two iteration steps more than the error-free robot. If the error in 20th European Workshop on Computational Geometry the movement is bound by δ < 1 3, the competitive ratio is 81 + δ 1−3δ+ 1. Both error bounds are rather big, so it can be expected, that real robots will meet this error bounds. The problem for mrays is a little bit different because the robot may detect the starting point if it changes from one corridor to another. Here, one may be interested in the probability of entering correctly the next corridor. References [1] H. Abelson and A. A. diSessa. Turtle Geometry. MIT Press, Cambridge, 1980. [2] R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Inform. Comput., 106:234–252, 1993. [3] P. Berman. On-line searching and navigation. In A. Fiat and G. Woeginger, editors, Competitive Analysis of Algorithms. Springer-Verlag, 1998. [4] R. Fleischer, T. Kamphans, R. Klein, E. Langetepe, and G. Trippen. Competitive online approximation of the optimal search ratio. 2004. to appear. [5] S. Gal. Continous search games. In Search theory: some recent developments., volume 112 of Lecture Notes in pure and applied mathematics, pages 33–53. Dekker, New York, NY, 1989. [6] A. Hemmerling. Labyrinth Problems: LabyrinthSearching Abilities of Automata. B. G. Teubner, Leipzig, 1989. [7] C. Icking, T. Kamphans, R. Klein, and E. Langetepe. On the competitive complexity of navigation tasks. In H. B. Hendrik I. Christensen, Gregory D. Hager and R. Klein, editors, Sensor Based Intelligent Robots, volume 2238 of LNCS, pages 245–258, Berlin, 2002. Springer. [8] T. Kamphans and E. Langetepe. The pledge algorithm reconsidered under errors in sensors and motion. In Proc. of the 1th Workshop on Approximation and Online Algorithms, Lecture Notes Comput. Sci., Berlin, 2003. Springer. to appear. [9] J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633–701. Elsevier Science Publishers B.V. NorthHolland, Amsterdam, 2000. [10] N. S. V. Rao, S. Kareti, W. Shi, and S. S. Iyengar. Robot navigation in unknown terrains: introductory survey of non-heuristic algorithms. Technical Report ORNL/TM-12410, Oak Ridge National Laboratory, 1993.