Fast Shannon Mutual Information (FSMI)
A fast information theoretic algorithm for robotic exploration.
This work was done in collaboration with Zhengdong Zhang, Sertac Karamn and Vivienne Sze and presented at ICRA 2019.
paper
In scenarios where it might be dangerous or impossible for humans to navigate, like search and rescue, it would be great if we could send robots out to autonomously explore the environment. Completing this task may consist of a number of capabilities like creating a map or planning paths through the space. Among these critical components is the ability to decide where to move next. In this work, we created a new state of the art algorithm to answer this exploration problem.
Problem Setup
In the English language "exploration" can mean a several related things, but here it has a very specific meaning:
A robot is placed in an unknown environment and as it moves through that environment it creates a map. The robot's exploration goal is to create the most useful map by expending the least amount of energy. The "usefulness" of the map is measured by how much information the map describes about the environment.
We will assume that robot maps the space with some sort of device that can measure distance to obstacles. For example a lidar, a sonar, or an rgb-d camera. In the animation below we show a simulated car driving around and creating a map. The rainbow dots represent the distances that the car is detecting using lidar.
Since the car drives on the ground, we can represent its map with a picture, just like a street map. If the car could fly we would need a 3D map --- but let's not get into that right now. This work assumes that the map is an occupancy grid map as shown in the animation. Each pixel on the map represents a point in space and has an associated "occupancy probability" represented by the shade of the pixel. Light pixels are most likely free, drive-able space, dark pixels are most likely obstacles, and the grey pixels are unknown.
Anytime the range sensor makes a measurement this information as well as the car's position is used to update the map. If a robot were to explore forever, it would eventually turn all of the reachable pixels either black or white. Pixels that aren't reachable, like the inside of obstacles, will always remain unknown.
A Brief History of Exploration Strategies
The exploration problem has been studied for decades. The early strategies were intuitive heuristics that were simple to implement, but performed moderately. For example, "frontier exploration" (Yamauchi, 1997) declares that the robot should move to the nearest boundary between free and unknown space. If the sensor is pretty noiseless, this method will eventually explore the entire space, but it doesn't do it very efficiently. It tends to waste a lot of time completely exploring all crevices before moving on as shown in the trajectory below:
A number of methods rely on some measure of "information gain": the amount of information the robot expects to gain about the map from measuring at a particular location. By choosing to measure at the location that maximizes information gain (or choosing to measure at the place that maximizes information per travel distance, etc.), the robot will surely explore the space faster.
Heuristic methods to compute information gain have existed for a long time (Connolly, 1985), but exact methods have been historically difficult. The exact way to compute information gain is to measure the mutual information, $I(M; Z)$, between the map $M$ and measurement $Z$. This measures how the entropy is expected to change if measurement $Z$ is made:
$$ I(M; Z) = H(M) - H(M|Z) $$
If $Z$ is a one-dimensional range measurement, Julian et al. (2013) showed that this is equal to:
$$ I(M; Z) = \sum_{i = 1}^n \int_{z\geq 0}P(Z = z) f(\delta_i(z),r_i)\; dz $$
The indices $i\in\{1\ldots n\}$ refer to the $n$ occupancy cells that the range measurement beam could pass through. $r_i$ is the odds that the cell is occupied, $\delta_i(z)$ is the inverse sensing model and $f$ is a nonlinear function specified in the paper.
The "FSMI algorithm" is simply an efficient way of computing that expression. By taking advantage of quantization and symmetries the complexity is reduced to $O(n)$ where $n$ is the number of cells. This is an asymptotic improvement over previous methods. In practice it is three orders of magnitude faster than Julian et al. and twice as fast as a comparable method that computes a slightly different quantity, CSQMI.
Experimental results
We tested the FSMI algorithm in synthetic environments and on a real robot to verify its usefulness. Here for example is a demonstration of one of the synthetic experiments:
We use RRT* to plan feasible paths (the red tree above) and then rank the tree of paths, based on the mutual information computed along the path. Good paths are labeled green and bad paths are labeled red.
Here is a video of a 1/10th scale car performing exploration. The mutual information surface is plotted in the bottom right.
Since the car drives on the ground, we can represent its map with a picture, just like a street map. If the car could fly we would need a 3D map --- but let's not get into that right now. This work assumes that the map is an occupancy grid map as shown in the animation. Each pixel on the map represents a point in space and has an associated "occupancy probability" represented by the shade of the pixel. Light pixels are most likely free, drive-able space, dark pixels are most likely obstacles, and the grey pixels are unknown.
Anytime the range sensor makes a measurement this information as well as the car's position is used to update the map. If a robot were to explore forever, it would eventually turn all of the reachable pixels either black or white. Pixels that aren't reachable, like the inside of obstacles, will always remain unknown.
A Brief History of Exploration Strategies
The exploration problem has been studied for decades. The early strategies were intuitive heuristics that were simple to implement, but performed moderately. For example, "frontier exploration" (Yamauchi, 1997) declares that the robot should move to the nearest boundary between free and unknown space. If the sensor is pretty noiseless, this method will eventually explore the entire space, but it doesn't do it very efficiently. It tends to waste a lot of time completely exploring all crevices before moving on as shown in the trajectory below:
A number of methods rely on some measure of "information gain": the amount of information the robot expects to gain about the map from measuring at a particular location. By choosing to measure at the location that maximizes information gain (or choosing to measure at the place that maximizes information per travel distance, etc.), the robot will surely explore the space faster.
Heuristic methods to compute information gain have existed for a long time (Connolly, 1985), but exact methods have been historically difficult. The exact way to compute information gain is to measure the mutual information, $I(M; Z)$, between the map $M$ and measurement $Z$. This measures how the entropy is expected to change if measurement $Z$ is made:
$$ I(M; Z) = H(M) - H(M|Z) $$
If $Z$ is a one-dimensional range measurement, Julian et al. (2013) showed that this is equal to:
$$ I(M; Z) = \sum_{i = 1}^n \int_{z\geq 0}P(Z = z) f(\delta_i(z),r_i)\; dz $$
The indices $i\in\{1\ldots n\}$ refer to the $n$ occupancy cells that the range measurement beam could pass through. $r_i$ is the odds that the cell is occupied, $\delta_i(z)$ is the inverse sensing model and $f$ is a nonlinear function specified in the paper.
The "FSMI algorithm" is simply an efficient way of computing that expression. By taking advantage of quantization and symmetries the complexity is reduced to $O(n)$ where $n$ is the number of cells. This is an asymptotic improvement over previous methods. In practice it is three orders of magnitude faster than Julian et al. and twice as fast as a comparable method that computes a slightly different quantity, CSQMI.
Experimental results
We tested the FSMI algorithm in synthetic environments and on a real robot to verify its usefulness. Here for example is a demonstration of one of the synthetic experiments:
We use RRT* to plan feasible paths (the red tree above) and then rank the tree of paths, based on the mutual information computed along the path. Good paths are labeled green and bad paths are labeled red.
Here is a video of a 1/10th scale car performing exploration. The mutual information surface is plotted in the bottom right.