Tabatabaei, Azadeh; Soheil, Farehe; Aletaha, Mohammad; Ghodsi, Mohammad Integer Cow-path Problem and Simple Robot Street SearchCanadian Conference on Computational Geometry (CCCG) 2021: 388–398
In this paper, we revisit the well-known cow-path problem and introduce a new variation called Integer Cow- path Problem (ICP). In the general cow-path problem, w rays with one common end-point and a robot standing on the end-point are given. A target point is put along one of the rays and can be detected only then it is reached by the robot. The robot has to find the target by traversing the rays starting from the end-point. In the ICP, the robot is restricted to take an integer number of steps. The goal is to design a strategy for the robot to find the target such that the length of the traveled path is as small as possible. We present a randomized strategy that gives an upper bound on the competitive ratio for the ICP. Furthermore, as an application of this variation, we study the Simple Robot Street Search problem and give a randomized strategy that is inspired from the strategy for the ICP.