Chapter 17: Applications and Case Studies
Lesson 4: Exploration (space, ocean, disaster response)
This lesson studies robotic exploration as a control and decision-making problem in extreme environments: planetary surfaces, the deep ocean, and disaster zones. We emphasize how to formalize exploration using state-space models, coverage and information metrics, and probabilistic search, while keeping dynamics simple enough to connect directly to linear control theory.
1. Exploration Robots and Environments
Robotic exploration is the task of sending a robot into an initially unknown or partially known environment to gather information under resource constraints (energy, time, communication). Typical domains are:
- Space: orbital platforms and rovers on planetary bodies with low gravity and severe communication delays.
- Ocean: autonomous underwater vehicles (AUVs) and remotely operated vehicles (ROVs) operating under high pressure and poor visibility.
- Disaster response: ground or aerial robots searching for survivors in partially collapsed, hazardous structures.
In a very abstract sense, we can model the environment as a region \( Q \subset \mathbb{R}^2 \) (for surface exploration) or \( Q \subset \mathbb{R}^3 \) (for volumetric exploration) and define a robot state \( \mathbf{x}(t) \) and control input \( \mathbf{u}(t) \). In many introductory analyses we use a single-integrator mobility model
\[ \dot{\mathbf{p}}(t) = \mathbf{u}(t), \quad \mathbf{p}(t) \in Q,\; \|\mathbf{u}(t)\| \leq v_{\max}, \]
where \( \mathbf{p}(t) \) is robot position and \( v_{\max} \) is a speed bound that encodes environment-specific constraints (gravity and slope for rovers, drag for AUVs, clutter and stability limits for disaster robots).
Exploration is then the problem of choosing a control signal \( \mathbf{u}(\cdot) \) to “cover” or “sense” the region while respecting constraints on time, energy, and safety.
flowchart TD
S["Start mission with prior map (possibly empty)"] --> A["Sense environment with onboard sensors"]
A --> B["Update internal representation (grid or graph)"]
B --> C["Compute exploration metric (coverage, information, risk)"]
C --> D["Select next goal (frontier, high info, high probability of target)"]
D --> E["Plan path with motion constraints"]
E --> F["Track path using low-level controller"]
F --> G{"Termination condition met?"}
G -->|no| A
G -->|yes| H["End mission / return to base"]
2. Simple State-Space Models for Exploratory Platforms
To connect to linear control, we embed the kinematic model into a linear state-space system. For a planar exploring robot with position \( \mathbf{p}(t) \in \mathbb{R}^2 \) and velocity \( \mathbf{v}(t) \in \mathbb{R}^2 \), a double-integrator model is
\[ \dot{\mathbf{x}}(t) = \begin{bmatrix} \dot{\mathbf{p}}(t) \\[4pt] \dot{\mathbf{v}}(t) \end{bmatrix} = \underbrace{\begin{bmatrix} \mathbf{0} & I_2 \\ \mathbf{0} & \mathbf{0} \end{bmatrix}}_{A} \mathbf{x}(t) + \underbrace{\begin{bmatrix} \mathbf{0} \\ I_2 \end{bmatrix}}_{B} \mathbf{u}(t), \]
with \( \mathbf{x}(t) = \begin{bmatrix}\mathbf{p}(t)^\top & \mathbf{v}(t)^\top\end{bmatrix}^\top\in\mathbb{R}^4 \). This is valid for:
- A planetary rover moving on a nearly flat patch of terrain.
- An AUV moving slowly in a horizontal plane at nearly constant depth.
- A ground robot searching a building floor in a disaster response mission.
In discrete time with sampling period \( T_s \), we obtain
\[ \mathbf{x}_{k+1} = A_d \mathbf{x}_k + B_d \mathbf{u}_k, \quad A_d = \begin{bmatrix} I_2 & T_s I_2 \\ \mathbf{0} & I_2 \end{bmatrix}, \quad B_d = \begin{bmatrix} \tfrac{T_s^2}{2} I_2 \\ T_s I_2 \end{bmatrix}. \]
Any stabilizing linear state feedback \( \mathbf{u}_k = -K \left(\mathbf{x}_k - \mathbf{x}_k^{\text{ref}}\right) \) designed using linear control techniques (pole placement, LQR) can then be used to track an exploration reference trajectory \( \mathbf{x}_k^{\text{ref}} \) generated by high-level planners.
Environment-specific effects (for example, orbital dynamics or buoyancy) can be modeled as disturbances or slowly varying parameters, as long as the resulting closed-loop system remains approximately linear around the operating regime of interest.
3. Coverage Metrics and Exploration Objectives
In practice, the exploration region is discretized as a grid of cells \( \mathcal{C} = \{1,\dots,N\} \), or as vertices of a graph. A simple coverage function at time step \( k \) is
\[ C(k) = \frac{1}{N} \sum_{i=1}^{N} \mathbf{1}\{i \text{ has been observed at least once up to time } k\}, \]
where \( C(k)\in[0,1] \) is the fraction of the environment that has been sensed. The indicator can be replaced by a probabilistic confidence that cell \( i \) is known.
We often want to minimize mission time while achieving a target coverage \( C_{\text{target}} \):
\[ \min_{\{\mathbf{u}_k\}} \; T \quad \text{subject to} \quad C(T) \geq C_{\text{target}}, \; \|\mathbf{u}_k\| \leq u_{\max}, \; \mathbf{x}_k \in \mathcal{X}_{\text{safe}}. \]
A more refined objective is to maximize information gain about an uncertain map. Let \( m_i \) be a binary random variable indicating whether cell \( i \) is occupied (rock, obstacle, survivor). We maintain a belief \( p_i(k) = \mathbb{P}(m_i=1 \mid \text{measurements up to }k) \). The joint entropy of the map is
\[ H(\mathbf{m}_k) = - \sum_{i=1}^{N} \big[ p_i(k)\log p_i(k) + (1-p_i(k))\log(1-p_i(k)) \big]. \]
An exploration step that moves the robot from state \( \mathbf{x}_k \) to \( \mathbf{x}_{k+1} \) produces an expected entropy decrease \( \Delta H = H(\mathbf{m}_k) - \mathbb{E}\big[H(\mathbf{m}_{k+1})\big] \). Many “information-based” strategies select the next goal pose to approximately maximize this expected information gain per unit cost (time or energy).
4. Probabilistic Search in Disaster Response
In disaster response, the goal is often to locate a small number of targets (survivors) rather than to fully map the environment. Classical search theory models the environment as sectors \( i \in \{1,\dots,N\} \) with prior probabilities \( \pi_i^{(0)} = \mathbb{P}(\text{target in sector } i) \).
Suppose the robot spends search effort \( e_i \geq 0 \) in sector \( i \). A common detection model is
\[ P_{\text{D},i}(e_i) = 1 - \exp\big(-\alpha_i e_i\big), \]
where \( \alpha_i > 0 \) is a detection effectiveness parameter (quality of sensors and visibility in sector \( i \)). The probability that the target is detected in a given mission is
\[ P_{\text{det}} = \sum_{i=1}^{N} \pi_i^{(0)} P_{\text{D},i}(e_i). \]
With a total effort budget \( E_{\max} \), the search allocation problem becomes
\[ \max_{e_1,\dots,e_N} \sum_{i=1}^{N} \pi_i^{(0)} \big(1-\exp(-\alpha_i e_i)\big) \quad \text{subject to} \quad \sum_{i=1}^{N} e_i \leq E_{\max}, \; e_i \geq 0. \]
This is a concave maximization with linear constraints; standard convex optimization theory guarantees a unique global optimum. The optimality conditions (KKT conditions) imply that, at optimum, all searched sectors with positive effort have equal marginal gain \( \pi_i^{(0)} \alpha_i \exp(-\alpha_i e_i^\star) \).
Bayesian updating is used after a failed search. If sector \( i \) is searched with effort \( e_i \) and no target is found, then
\[ \pi_i^{(1)} = \mathbb{P}(\text{target in sector } i \mid \text{no detection}) = \frac{\pi_i^{(0)} (1-P_{\text{D},i}(e_i))} {1 - P_{\text{det}}}, \]
while priors for unsearched sectors remain unchanged. Robots then re-plan using updated probabilities \( \pi_i^{(1)} \).
5. Simple Exploration Strategies
We now summarize three families of strategies that are used in all three domains (space, ocean, disaster) with appropriate tuning.
5.1. Sweep (Lawnmower) Coverage
For a rectangular region \( Q = [0,L_x]\times[0,L_y] \) and a sensor footprint width \( w \), a simple path consists of parallel lines spaced at most \( w \) apart. Assume a constant speed \( v \). The total path length satisfies
\[ L_{\text{path}} \approx \left\lceil \frac{L_y}{w} \right\rceil L_x, \quad T_{\text{cov}} = \frac{L_{\text{path}}}{v}. \]
In the idealized model where the robot can instantaneously turn at the ends of each line and where there are no obstacles, one can show that any path that covers the entire region with no overlap must have length at least \( L_x L_y / w \), so the lawnmower pattern is within one strip-width of this lower bound.
5.2. Frontier-Based Exploration
In an occupancy grid map, a frontier cell is a free cell adjacent to at least one unknown cell. Frontier-based exploration iteratively:
- Identifies all frontier cells.
- Clusters them into candidate goal regions.
- Selects the “best” frontier cluster according to a utility function (distance, information, risk).
- Plans a path and drives the robot there.
Let \( \mathcal{F}(k) \) be the set of frontier cells at time \( k \), and let \( d(i,k) \) be the path length from the robot to frontier cell \( i \in \mathcal{F}(k) \). A simple utility is
\[ U(i,k) = \beta_1 \Delta H_i(k) - \beta_2 d(i,k), \]
where \( \Delta H_i(k) \) is the local expected entropy reduction and \( \beta_1,\beta_2 > 0 \) weight information versus travel cost. The selected frontier is
\[ i^\star(k) = \arg\max_{i\in\mathcal{F}(k)} U(i,k). \]
flowchart TD
R["Robot pose and map"] --> F1["Detect frontier cells"]
F1 --> F2["Cluster frontiers into goal candidates"]
F2 --> F3["Evaluate utility of each goal"]
F3 --> F4["Choose best goal and plan path"]
F4 --> F5["Execute path with feedback controller"]
F5 --> R
6. Multi-Language Programming Example: Frontier Selection Core
We now implement the core of step (frontier selection) in four
languages. We assume a 2D occupancy grid where a cell value of
-1 means unknown, 0 free, and
1 obstacle. The robot is at grid index
\( (i_r,j_r) \). For simplicity, we ignore entropy and
use Euclidean distance to choose the closest frontier.
6.1. Python (NumPy)
import numpy as np
UNKNOWN = -1
FREE = 0
OBSTACLE = 1
def is_frontier(occ_grid, i, j):
if occ_grid[i, j] != FREE:
return False
# 4-neighborhood
neighbors = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
for ni, nj in neighbors:
if 0 <= ni < occ_grid.shape[0] and 0 <= nj < occ_grid.shape[1]:
if occ_grid[ni, nj] == UNKNOWN:
return True
return False
def select_closest_frontier(occ_grid, robot_idx):
ri, rj = robot_idx
frontiers = []
for i in range(occ_grid.shape[0]):
for j in range(occ_grid.shape[1]):
if is_frontier(occ_grid, i, j):
frontiers.append((i, j))
if not frontiers:
return None # exploration complete
# choose frontier with minimum Euclidean distance
dists = [np.linalg.norm(np.array([i - ri, j - rj])) for (i, j) in frontiers]
idx = int(np.argmin(dists))
return frontiers[idx]
6.2. C++ (STL)
#include <vector>
#include <cmath>
#include <limits>
static const int UNKNOWN = -1;
static const int FREE = 0;
static const int OBSTACLE = 1;
bool is_frontier(const std::vector<std::vector<int>>& grid,
int i, int j) {
if (grid[i][j] != FREE) return false;
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
int rows = static_cast<int>(grid.size());
int cols = static_cast<int>(grid[0].size());
for (int k = 0; k < 4; ++k) {
int ni = i + di[k];
int nj = j + dj[k];
if (0 <= ni && ni < rows && 0 <= nj && nj < cols) {
if (grid[ni][nj] == UNKNOWN) return true;
}
}
return false;
}
std::pair<int,int> select_closest_frontier(
const std::vector<std::vector<int>>& grid,
int ri, int rj,
bool& found) {
found = false;
double bestDist = std::numeric_limits<double>::infinity();
std::pair<int,int> best(-1, -1);
int rows = static_cast<int>(grid.size());
int cols = static_cast<int>(grid[0].size());
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (is_frontier(grid, i, j)) {
double dx = static_cast<double>(i - ri);
double dy = static_cast<double>(j - rj);
double d = std::sqrt(dx*dx + dy*dy);
if (d < bestDist) {
bestDist = d;
best = std::make_pair(i, j);
found = true;
}
}
}
}
return best;
}
6.3. Java
public class FrontierSelector {
public static final int UNKNOWN = -1;
public static final int FREE = 0;
public static final int OBSTACLE = 1;
private static boolean isFrontier(int[][] grid, int i, int j) {
if (grid[i][j] != FREE) return false;
int[][] neigh = {
{-1,0},
{1,0},
{0,-1},
{0,1}
};
int rows = grid.length;
int cols = grid[0].length;
for (int[] d : neigh) {
int ni = i + d[0];
int nj = j + d[1];
if (0 <= ni && ni < rows && 0 <= nj && nj < cols) {
if (grid[ni][nj] == UNKNOWN) {
return true;
}
}
}
return false;
}
public static int[] selectClosestFrontier(int[][] grid, int ri, int rj) {
double bestDist = Double.POSITIVE_INFINITY;
int[] best = null;
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (isFrontier(grid, i, j)) {
double dx = i - ri;
double dy = j - rj;
double d = Math.sqrt(dx*dx + dy*dy);
if (d < bestDist) {
bestDist = d;
best = new int[]{i, j};
}
}
}
}
return best; // null means no frontier left
}
}
6.4. MATLAB / Simulink
UNKNOWN = -1;
FREE = 0;
OBSTACLE = 1;
function idx = selectClosestFrontier(occGrid, robotIdx)
ri = robotIdx(1);
rj = robotIdx(2);
[rows, cols] = size(occGrid);
bestDist = inf;
idx = [];
for i = 1:rows
for j = 1:cols
if isFrontier(occGrid, i, j, FREE, UNKNOWN)
dx = i - ri;
dy = j - rj;
d = sqrt(dx*dx + dy*dy);
if d < bestDist
bestDist = d;
idx = [i, j];
end
end
end
end
end
function flag = isFrontier(occGrid, i, j, FREE, UNKNOWN)
if occGrid(i, j) ~= FREE
flag = false; return;
end
[rows, cols] = size(occGrid);
neigh = [-1 0; 1 0; 0 -1; 0 1];
flag = false;
for k = 1:4
ni = i + neigh(k,1);
nj = j + neigh(k,2);
if ni >= 1 && ni <= rows && nj >= 1 && nj <= cols
if occGrid(ni, nj) == UNKNOWN
flag = true; return;
end
end
end
end
In Simulink, this logic can be realized inside a MATLAB Function block that reads the occupancy grid and robot index from input ports and outputs the chosen frontier index. The low-level controller can then generate velocity commands to drive the robot toward that frontier while respecting the linear state-space dynamics.
7. Problems and Solutions
Problem 1 (Coverage time for a planetary rover): A rover explores a rectangle of size \( L_x = 200 \,\text{m} \) by \( L_y = 100 \,\text{m} \). Its sensor footprint width is \( w = 5 \,\text{m} \) and its maximum safe speed is \( v_{\max} = 0.05 \,\text{m/s} \) (very slow due to rough terrain and communication delays). Using an ideal lawnmower (sweep) pattern with no overlap beyond what is necessary, estimate the coverage time \( T_{\text{cov}} \).
Solution:
The number of required passes (strips) is
\[ n_{\text{strips}} = \left\lceil \frac{L_y}{w} \right\rceil = \left\lceil \frac{100}{5} \right\rceil = 20. \]
Each strip is approximately length \( L_x = 200 \,\text{m} \), so ignoring turn-in-place distances,
\[ L_{\text{path}} \approx n_{\text{strips}} L_x = 20 \cdot 200 = 4000 \,\text{m}. \]
Therefore the coverage time is
\[ T_{\text{cov}} = \frac{L_{\text{path}}}{v_{\max}} = \frac{4000}{0.05} = 80000 \,\text{s} \approx 22.2 \,\text{hours}. \]
This simple calculation highlights why planetary missions span many sols even for modest areas.
Problem 2 (Search allocation optimality condition): Consider the search-effort optimization in Section 4 with two sectors (\( N=2 \)). Derive the necessary condition that relates the optimal efforts \( e_1^\star \) and \( e_2^\star \) when both are strictly positive.
Solution:
The objective is
\[ J(e_1,e_2) = \pi_1^{(0)}(1-\exp(-\alpha_1 e_1)) + \pi_2^{(0)}(1-\exp(-\alpha_2 e_2)), \]
with constraint \( e_1 + e_2 = E_{\max} \). Using a Lagrange multiplier \( \lambda \),
\[ \mathcal{L}(e_1,e_2,\lambda) = J(e_1,e_2) + \lambda(E_{\max}-e_1-e_2). \]
Taking derivatives and setting to zero for an interior optimum:
\[ \frac{\partial \mathcal{L}}{\partial e_1} = \pi_1^{(0)} \alpha_1 \exp(-\alpha_1 e_1) - \lambda = 0, \]
\[ \frac{\partial \mathcal{L}}{\partial e_2} = \pi_2^{(0)} \alpha_2 \exp(-\alpha_2 e_2) - \lambda = 0. \]
Eliminating \( \lambda \) yields the necessary condition
\[ \pi_1^{(0)} \alpha_1 \exp(-\alpha_1 e_1^\star) = \pi_2^{(0)} \alpha_2 \exp(-\alpha_2 e_2^\star). \]
Thus at optimum, the marginal gain (increase in detection probability per unit of effort) is equalized between sectors.
Problem 3 (Frontier termination condition): Suppose an exploration robot uses the frontier-based scheme from Section 5. Let \( \mathcal{F}(k) \) denote the frontier set at step \( k \). Prove that if the occupancy grid is finite and every cell is reachable from the start through free space, then termination condition \( \mathcal{F}(k) = \emptyset \) implies that all reachable cells have been observed.
Solution:
Assume the contrary: there exists at least one reachable cell \( c^\star \) that is still unknown when \( \mathcal{F}(k) = \emptyset \). Consider a shortest free-space path (in the true environment) from the start cell to \( c^\star \). Let \( c' \) be the first unknown cell on this path when traversing from the start. Its predecessor \( c_{\text{prev}} \) on the path must be free and known (since it is before the first unknown). Because \( c' \) is unknown and adjacent to a free known cell \( c_{\text{prev}} \), the definition of frontier implies that \( c_{\text{prev}} \) is a frontier cell. This contradicts the assumption \( \mathcal{F}(k) = \emptyset \). Therefore, no such \( c^\star \) exists and all reachable cells are known.
Problem 4 (Simple exploration decision flow): A disaster-response robot has limited battery and must decide between (i) sweeping a corridor completely, (ii) prioritizing high-probability rooms first, or (iii) returning to base to recharge. Sketch a logical decision flow that considers coverage fraction, probability of finding survivors, and remaining energy.
Solution (flow):
flowchart TD
ST["Start decision step"] --> E1["Check remaining energy vs. reserve"]
E1 -->|below reserve| RB["Return to base"]
E1 -->|enough energy| C1["Compute corridor coverage fraction"]
C1 --> P1["Estimate probability of survivors in unexplored rooms"]
P1 --> D1{"High probability in specific rooms?"}
D1 -->|yes| OPT1["Go to highest-probability room first"]
D1 -->|no| OPT2["Sweep remaining corridor segments"]
A quantitative implementation would compute expected detection gain per unit energy and choose the action (room-first or sweep) with maximum ratio, subject to the constraint that enough energy remains to safely return.
8. Summary
In this lesson we cast exploration in space, ocean, and disaster environments into a common mathematical framework: linear or near-linear state-space mobility models, coverage and information metrics on discretized environments, and probabilistic search models over sectors. We studied sweep and frontier-based strategies and saw how they relate to optimization of coverage and detection probability. Finally, we connected these high-level concepts to concrete multi-language implementations of a frontier selection core that can be embedded in a full robot control stack.
9. References
- Choset, H. (2001). Coverage for robotics – A survey of recent results. Annals of Mathematics and Artificial Intelligence, 31(1–4), 113–126.
- Bourgault, F., Makarenko, A. A., Williams, S. B., Grocholsky, B., & Durrant-Whyte, H. F. (2002). Information based adaptive robotic exploration. IEEE/RSJ International Conference on Intelligent Robots and Systems, 540–545.
- Thrun, S. (2002). Robotic mapping: A survey. In G. Lakemeyer & B. Nebel (Eds.), Exploring Artificial Intelligence in the New Millennium, 1–35.
- Yamauchi, B. (1997). A frontier-based approach for autonomous exploration. IEEE International Symposium on Computational Intelligence in Robotics and Automation, 146–151.
- Bourgault, F., Furukawa, T., & Durrant-Whyte, H. F. (2003). Coordinated decentralized search for a lost target in a Bayesian world. Advanced Robotics, 18(10), 979–1000.
- Hollinger, G. A., & Singh, S. (2012). Multirobot coordination with periodic connectivity: Theory and experiments. IEEE Transactions on Robotics, 28(4), 967–973.
- Koenig, S., & Simmons, R. G. (1998). A formal basis for mapping and navigation in unknown environments. Robotics and Autonomous Systems, 22(1), 1–18.
- Koopman, B. O. (1956). The theory of search II: Target detection. Operations Research, 4(5), 503–531.
