Publication Details
Title: Navigation Without Perception of Coordinates and Distances
Author: A. Hemmerling
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-018.pdf
Overview:
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. Keywords: motion planning, on-line algorithms, labyrinth problems, exhaustive search, rotation counting, trap constructions, power of compass
Bibliographic Information:
ICSI Technical Report TR-93-018
Bibliographic Reference:
A. Hemmerling. Navigation Without Perception of Coordinates and Distances. ICSI Technical Report TR-93-018, March 1993
Author: A. Hemmerling
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-018.pdf
Overview:
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. Keywords: motion planning, on-line algorithms, labyrinth problems, exhaustive search, rotation counting, trap constructions, power of compass
Bibliographic Information:
ICSI Technical Report TR-93-018
Bibliographic Reference:
A. Hemmerling. Navigation Without Perception of Coordinates and Distances. ICSI Technical Report TR-93-018, March 1993