How does information gain based exploration differ from frontier based?

Question

I've recently come across the concept of using information gain (or mutual information criteria) as a metric for minimizing entropy on a map to aid in robotic exploration. I have somewhat of a basic question about it.

A lot of papers that talk about minimizing entropy consider an example case of something like a laser scanner and try to compute the 'next best pose' so that the maximum entropy reduction is achieved. Usually this is mentioned like "information gain based approaches help finding the best spot to move the robot such that the most entropy is minimized using raycasting techniques, as opposed to frontier based exploration which is greedy" etc. But I don't understand what the underlying reason is for information gain/entropy based exploration being better.

Let's say a robot in a room with three walls and open space in front. Because of range limitations, it can only see two walls: so in frontier based exploration, the robot has two choices; move towards the third wall and realize it's an obstacle, or move towards the open space and keep going. How does an information gain based method magically pick the open space frontier over the wall frontier? When we have no idea what's beyond our frontiers, how can raycasting even help?

Answer 1

Frontier based exploration is concerned primarily with exploring the physical space in order to produce an occupancy grid (or cost map) of the terrain traversibility. The control actions follow a set of rules which work empirically well (but not theoretically optimally) to achieve for the frontier-exploration goal.

Information-gain methods can be used to specify any objective that you can model mathematically. Because they are probabilistic the prior beliefs of the system can also be modelled, which gives the system a better idea than a set of simple rules.

Take the example of the Mars Rover Curiosity looking for stromatolites (fossilised bacteria) on an unexplored region of Mars:

• A grid of 100x100 represents the area to be explored
  • For each point on the grid, the grid could be either a Ordinary rock, Interesting rock or Stromatolite (class labels $\{O, I, S\}$)
• The roboticists work with the geologists to provide Curiosity with expert knowledge of geology concerning stromatolite discovery:
  • $P(x=S | x_n=I) = 0.05$, which means the probability of the grid at x being a stromatolite, given that any if x's neighbour is an Interesting rock, is 5%.
  • $P(x=S | x_n=S) = 0.35$, similarly this encodes the domain knowledge that stromatolites occur spatially close to one another

In such a system, the info-gain system would choose the action that would tell us the most about the population of rock classes in this map, taking in to account the domain knowledge, sensor uncertainty model and current state of the map.

This is contrasted to the frontier mapping method which can only find the shape of the map, generally using non-probabilistic methods (probabilistic frontier-exploration exist).