CSCE 452/752: Homework 9 Solutions

A robot, represented below by the small dot, wants to solve the Dudek-Romanik-Whitesides localization problem discussed in class. The environment is represented as a polygon, and the robot has a sensor that reports the visibility polygon of its position within the environment and a compass that reports the robot's orientation relative to the environment map.

1. Draw the visibility polygon for the robot's position.

Solution:

The visibility polygon looks like this:

Within the environment:

a localization problem in a key-shaped environment

2. Find all of the positions consistent with this initial sensor information. Mark each with a star.

Solution:

Notice that the similar room on the right side is not included. The robot has a compass, so it can distinguish the difference in orientations.

3. Draw a path that would allow the robot to eliminate at least one of these candidates.

Solution:

a localization problem with a movement path marked

After this motion, if the robot is on the left side, it will observe this visibility polygon:

But if it's on the right, it will observe this visibility polygon instead:

Depending on which of these two sensor readings is received, the robot can eliminate one or the other of the two hypotheses.

Extra learning opportunity #1: Draw the visibility cell decomposition of the environment above.

Extra learning opportunity #2: Construct a decision tree that localizes the robot in the environment above.

Extra learning opportunity #3: Suppose instead that the robot in this environment, with the same starting visibility polygon:

Construct a decision tree that localizes the robot.