Ships often use the coasts of continents for navigation in the absence of better tools such as GPS, since being close to the land allows sailors to determine with high accuracy where they are.
One of the problems that Minerva faces, is that she can't see very well. She has laser sensors for finding obstacles up to 20 meters away, but the laser is often blocked by people standing around. Also, there are some areas of the museum where the objects are more than 20 meters away.
Minerva also has a camera that looks at the ceiling; she uses a map of the ceiling to navigate around the museum. However, the camera works best near the ceiling lights. If there are no ceiling lights near by, it's hard for her to tell where she is.
These different problems all make it hard for Minerva to tell where she is sometimes. If there isn't enough information in the sensor data, Minerva becomes less and less certain as to where she is, until eventually she decides she is lost.
Minerva, therefore, has learned to identify what are good and bad places to go to avoid getting lost. Minerva uses the occupancy map to simulate sensor data and determines whether or not each location in the museum contains enough information to prevent getting lost. When the robot moves to a new location, she follows a trajectory that balances finding the shortest distance against the probability of getting lost. Minerva also takes into account the possibility of people blocking the sensors, based on the number of people in the museum.
The following shows a map of the museum with the information about the sensor usefulness. The lighter a place is, the more information is available to the sensor, and the less likely the robot is to get lost there. Notice that in the middle of the large central foyer is the darkest region -- this is region contains the least amount of information that can help Minerva identify where she is.
One of the results of using a laser sensor that points out from the side of Minerva, is that standing close to walls helps her to know where she is. So, balancing the sensor information means that Minerva travels closer to obstacles than she would otherwise, hence the name coastal navigation. The left hand image above shows a path planned using the traditional, shortest-distance planner. The right-hand image shows a path planned using the entropy measure. Notice how Minerva hugs the wall, so as not to become lost.
Clicking the images enlarges them.
Travelling close to obstacles, while useful for localization, is potentially dangerous. Therefore, an additional measure (a potential field around obstacles) is used to ensure that the robot doesn't get too close to obstacles. The path planner then arbitrates between the three criteria: shortest distance, most reliable paths, and safety around obstacles.