# How does information gain based exploration differ from frontier based?

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?

• I think the case you describe is special in that there is no difference between the two choices. In general, following a wall will guarantee discovery of boundaries, but not the interior. Depending on you robot's objective (e.g. discovering the whole interior of the map and not just the convex hull), it may be more efficient to traverse the interior. – Paul Feb 14 '16 at 5:13
• Sorry if I misunderstood your comment - well, I was not suggesting that we follow the wall, really. The question I was wondering about was that when I am looking for the 'next best view', let's say there's abig set of frontier voxels in a certain area. There really is no guarantee that I wouldn't hit a wall right next to those frontier voxels (which I would only know of when I move close enough to them), correct? So then, wouldn't information gain based exploration result in an unnecessary traversal just like frontier based? – HighVoltage Feb 14 '16 at 5:28

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).