Finding a door along a wall with an error afflicted robot

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δ.