Page 441 - Introduction to AI Robotics

424
11
Localization and Map Making
should reduce the possible states. For example, it the robot starts moving
east, it will encounter different gateways based on where it really is. The
possible progression of the states from the initial set of states is:
a r i , hall
f2 3g 3g, where {3} is a w ! l l g h t lef t , w a l l r o n t f
f
f5 6g 5g, where {5} is a hall ! r i g h t lef t , w a l l r o n t f
, hall
f
f6 7g 6g, where {6} is a w ! l l g h t left , hall fr ont f
a r i , door
Therefore if the robot encounters a door left , the set of possible states rep-
resenting its location on the topological map reduces to f6g.
The above method works very well for indoor environments with orthog-
onal intersections. The challenge becomes how to handle sensor noise; there
is a large possibility the robot will misclassify the door as a hallway. This
would lead to a belief that the robot was more likely to be at {3} rather than
at {6}. The basic solution is to keep track of the probabilities of where the
robot is at and then after many moves, the probability that the robot was at
{6} eventually becomes 1.0.

11.8 Exploration

Exploration attempts to answer the question of where haven’t I been? versus
where am I? A central concern in exploration is how to cover an unknown
area efficiently. One way is to do this with a random search; the robot liter-
ally wanders around randomly (using a random potential field). After some
(often very large) period of time, statistics indicate it should have covered
the entire area. Another reactive method is to permit a short-term persis-
tence of proprioception (odometry). Then the robot is repulsed by areas that
have been recently visited. This can be implemented as a repulsive field,
generated by every visited cell in a coarse occupancy grid or for every previ-
ous heading. This “avoid past” behavior 17 when combined with the random
potential field drives the robot towards new areas.
Another behavioral approach is to exploit evidential information in the
occupancy grid. As the robot explores a new area, many cells on the grid
=
will be unknown, either P (Occupied ) P (E ) in a Bayesian system or
mpty
m(dontknow ) in a Dempster-S =hafer implementation. The robot takes the 1
centroid of the unknown area and uses that as a goal for a move-to-goal.
As it moves to the goal (in conjunction with avoid-obstacle), new sensor