Search-and-Fetch with One Robot on a Disk

A robot is located at a point in the plane. A treasure and an exit, both stationary, are located at unknown (to the robot) positions both at distance one from the robot. Starting from its initial position, the robot aims to fetch the treasure to the exit. At any time the robot can move anywhere on the disk with constant speed. The robot detects an interesting point (treasure or exit) only if it passes over the exact location of that point. Given that an adversary controls the locations of both the treasure and the exit on the perimeter, we are interested in designing algorithms that minimize the treasure-evacuation time, i.e. the time it takes for the treasure to be discovered and brought to the exit by the robot.In this paper we differentiate how the robot’s knowledge of the distance between the two interesting points affects the overall evacuation time. We demonstrate sthe difference between knowing the exact value of that distance versus knowing only a lower bound and provide search algorithms for both cases. In the former case we give an algorithm which is off from the optimal algorithm (that does not know the locations of the treasure and the exit) by no more than 42+3π+262+2π+2≤1.019$$\frac{4 \sqrt{2}+3 \pi +2}{6 \sqrt{2}+2 \pi +2}\le 1.019$$ multiplicatively, or π2-2≤0.157$$\frac{\pi }{2}-\sqrt{2}\le 0.157$$ additively. In the latter case we provide an algorithm which is shown to be optimal.