We assume that a robot aims to locate itself in the windy maze as shown in the above. The robot
will perform two kinds of actions: sensing and moving.
ˆ Sensing: In a square, the robot will sense the four directions to see if there is an obstacle in
this direction. We assume that the whole maze is surrounded by obstacles and the black squares
are also obstacle. However, the sensing is not perfect. We assume that the robot can detect
the obstacle with 85% if there is and might mistake an open square as a obstacle with 5%. The
detections in all directions are done independently.
ˆ Moving: In the windy situation, the robot can drift to the left or the right with probability 0.1. If
the drifting direction is an obstacle, it will be bounced back to the original position. For example,
in the square of left bottom, if the robot moves northward, it will reach the square to the north
with 80% and reach the square to the east with 10% and be bounced back to the original position
with 10%.
We assume that the robot initially stays in one open square, but it doesn’t know its exact location
except that it knows that it can’t be in any obstacle square. Then the robot performs the following
sequence of actions: