Page 440 - Introduction to AI Robotics

11.7 Localization
3 2-3 A 2 1 423

3-4
4
4-5

5 5-6 6 6-7 7 8
B
5-9
9
9-10 N
10 W E

S

Figure 11.21 State-sets of a topological layout of an office building.

a wall had a 30% chance of being seen as a closed door. To factor in this
sensor uncertainty, most roboticists use techniques based on a probabilistic
method known as Partially Observable Markov Decision Processes (POMDP,
pronounced “pom D P”). POMDPs are beyond the scope of this book, but the
STATE-SET basic idea is illustrated by the quasi-evidential state-set progression methodol-
PROGRESSION ogy developed by Illah Nourbakhsh. 112
Returning to Fig. 11.21, it can be seen that there are 10 gateways. The
gateways are labeled with a single number and represent a state where the
robot can localize itself relative to the map. (The numbering is arbitrary.)
Notice that the hallways are not gateways. The robot knows that it is in a
hallway, but unless it uses continuous localization and mapping, it does not
know where it is in the hallway (e.g., how close it is to the next gateway).
Since hallways can be considered as the state of the robot which is between
gateways, the hallway are labeled with two numbers, g a t e g w a at e y w a y
,
representing the pair of gateways the robot is between.
If the robot “wakes up” and senses it is in a hallway facing east, it knows it
is in one of the following states: {{2-3},{5-6},{6-7}}. So it is currently in one of
three possible states. As it moves and detects a gateway, the new information