Page 237 - Introduction to Autonomous Mobile Robots

Chapter 5
222
Turning to the other node in Dervish’s prior belief state, 1-2 will potentially progress to
states 2, 2-3, 3, 3-4, and 4. Again, states 2-3, 3, and 3-4 can all be eliminated since the like-
lihood of detecting an open door when a wall is present is zero. The likelihood of state 2 is
the product of the prior likelihood for state 1-2, (1.0), the likelihood of detecting the door
on the right as an open door, 0.6 0 +⋅[ 0.4 0.9⋅ ] , and the likelihood of correctly detecting
an open hallway to the left, 0.9. The likelihood for being at state 2 is then
1.0 0.4 0.9 0.9⋅ ⋅ ⋅ = 0.3 . In addition, 1-2 progresses to state 4 with a certainty factor of
⋅
4.3 10 – 6 , which is added to the certainty factor above to bring the total for state 4 to
0.00328. Dervish would therefore track the new belief state to be {2, 4}, assigning a very
high likelihood to position 2 and a low likelihood to position 4.
Empirically, Dervish’s map representation and localization system have proved to be
sufficient for navigation of four indoor office environments: the artificial office environ-
ment created explicitly for the 1994 National Conference on Artificial Intelligence; and the
psychology, history, and computer science departments at Stanford University. All of these
experiments were run while providing Dervish with no notion of the distance between adja-
cent nodes in its topological map. It is a demonstration of the power of probabilistic local-
ization that, in spite of the tremendous lack of action and encoder information, the robot is
able to navigate several real-world office buildings successfully.
One open question remains with respect to Dervish’s localization system. Dervish was
not just a localizer but also a navigator. As with all multiple hypothesis systems, one must
ask the question, how does the robot decide how to move, given that it has multiple possible
robot positions in its representation? The technique employed by Dervish is a common
technique in the mobile robotics field: plan the robot’s actions by assuming that the robot’s
actual position is its most likely node in the belief state. Generally, the most likely position
is a good measure of the robot’s actual world position. However, this technique has short-
comings when the highest and second highest most likely positions have similar values. In
the case of Dervish, it nonetheless goes with the highest-likelihood position at all times,
save at one critical juncture. The robot’s goal is to enter a target room and remain there.
Therefore, from the point of view of its goal, it is critical that Dervish finish navigating only
when the robot has strong confidence in being at the correct final location. In this particular
case, Dervish’s execution module refuses to enter a room if the gap between the most likely
position and the second likeliest position is below a preset threshold. In such a case, Der-
vish will actively plan a path that causes it to move further down the hallway in an attempt
to collect more sensor data and thereby increase the relative likelihood of one position in
the multiple-hypothesis belief state.
Although computationally unattractive, one can go further, imagining a planning system
for robots such as Dervish for which one specifies a goal belief state rather than a goal posi-
tion. The robot can then reason and plan in order to achieve a goal confidence level, thus
explicitly taking into account not only robot position but also the measured likelihood of