Abstract

We consider the target-reaching problem in plane scenes for a point robot which has a tactile sensor and can locate the target ray. It might have a compass, too, but it is not able to perceive the coordinates of its position nor to measure distances. The complexity of an algorithm is measured by the number of straight moves until reaching the target, as a function of the number of vertices of the scene. It is shown how the target point can be reached by exhaustive search without using a compass, with the complexity exp). Using a compass, there is a target-reaching algorithm, based on rotation counting, with the complexity O. The decision problem, to recognize if the target cannot be reached because it belongs to an obstacle, cannot be solved by our type of robot. If the behaviour of a robot without compass is periodic in a homogeneous environment, it cannot solve the target-reaching problem.