Navigation Without Perception of Coordinates and Distances

TitleNavigation Without Perception of Coordinates and Distances
Publication TypeTechnical Report
Year of Publication1993
AuthorsHemmerling A
Other Numbers806
Keywordsexhaustive search, labyrinth problems, motion planning, On-line Algorithms, power of compass, rotation counting, trap constructions

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 (polygonal) scene.It is shown how the target point can be reached by exhaustive search without using a compass, with the complexity exp(O(n^2)). Using a compass, there is a target–reaching algorithm, based on rotation counting, with the complexity O(n^2).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.

Bibliographic Notes

ICSI Technical Report TR-93-018

Abbreviated Authors

A. Hemmerling

ICSI Publication Type

Technical Report