We consider the problems related to
localizing a mobile robot in an environment
for which the robot has a map.
In particular, we are interested in the * global localization*
problem, where no prior location estimate is available.
The formalization of the localization problem is
to determine the position of the robot, which has a compass and a
various alternative sensing alternatives,
such as having
range sensing device. Since several positions in the environment may
generate the same sensory data, we seek to minimize the distance the
robot must travel to determine its exact location.
One example of this class of problem is that of a point robot in
an **n**-vertex polygonal environment with a perfect range sensor.
The view from a single position can have up to an **n**-fold
ambiguity. We have shown that finding the optimal shortest path
to resolve the ambiguity is NP-complete. We are developing both
lower bound results and algorithms with provable good performance in
comparison to the optimal.

G. Dudek, K. Romanik (DIMACS), S. Whitesides

Mon Nov 13 10:43:02 EST 1995