Schur-MI: Fast Mutual Information for Robotic Information Gathering

1. Problem Statement

Robotic Information Gathering (RIG) involves selecting sensing locations (Sensor Placement, SP) or planning paths (Informative Path Planning, IPP) to maximize knowledge about an unknown environment.

• The Objective: Mutual Information (MI) is the gold-standard objective function for RIG because it theoretically guarantees near-optimal information gain and handles uncertainty reduction rigorously within a Gaussian Process (GP) framework.
• The Bottleneck: Calculating MI under a GP requires evaluating matrix determinants and inversions. The standard formulation has a computational complexity of $O(|V|^3)$ per evaluation, where $|V|$ is the number of candidate locations.
• The Consequence: In real-time or adaptive planning scenarios, planners must evaluate the objective function thousands of times. The cubic cost forces practitioners to abandon MI in favor of cheaper, less informative proxies (e.g., variance reduction), creating a gap between theoretical optimality and practical feasibility.

2. Methodology: Schur-MI

The authors propose Schur-MI, a reformulation of the GP-MI objective that reduces the per-evaluation cost from $O(|V|^3)$ to $O(|A|^3)$, where $|A|$ is the number of selected sensing locations (typically $|A| \ll |V|$). The method relies on three key innovations:

A. Precomputation of Invariant Terms

In iterative RIG, the set of candidate locations $V$ remains fixed while the selected set $A$ grows. The standard MI formulation requires re-computing determinants involving $V$ at every step. The authors identify that terms depending solely on $V$ (specifically $K_{VV}$, the covariance matrix of all candidates) can be precomputed and reused across all planning steps.

B. Alternate Objective Formulation

The standard MI is defined as $I(A; V \setminus A)$. The authors propose an alternate objective: $I(A; V)$.

• Challenge: If $A \subset V$, then $A \cup V = V$, causing the MI term to degenerate into the entropy of $A$ alone ($H(A)$), losing the value of information regarding the unsampled region.
• Solution: Introduce a noisy surrogate candidate set $G = V + \epsilon$, where $\epsilon$ is small Gaussian noise. This ensures $A \not\subset G$ strictly, preventing the mathematical degeneracy while maintaining the set $G$ as a near-identical copy of $V$.

C. Schur-Complement Factorization

To evaluate $I(A; V)$ efficiently without computing the determinant of the massive union set $(A \cup V)$, the authors utilize the Schur complement.

• The joint covariance matrix is partitioned into blocks: $K_{AA}$, $K_{AV}$, $K_{VA}$, and $K_{VV}$.
• Using the property $\det(K_{A \cup V}) = \det(K_{VV}) \cdot \det(K_{A|V})$, where $K_{A|V} = K_{AA} - K_{AV}K_{VV}^{-1}K_{VA}$ is the conditional covariance.
• The final Schur-MI objective becomes:
  $$I(A; V) = \frac{1}{2} \ln \left( \frac{\det(K_{AA})}{\det(K_{A|V})} \right)$$
• Complexity Reduction: Since $K_{VV}^{-1}$ is precomputed, evaluating the objective only requires forming the cross-covariance $K_{AV}$ and computing determinants of the small $s \times s$ matrix $K_{A|V}$. This reduces the complexity to $O(|A|^3)$.

3. Key Contributions

1. Algorithmic Reformulation: Derivation of an equivalent MI objective that avoids the $O(|V|^3)$ bottleneck by leveraging the Schur complement and a noisy surrogate set to prevent degeneracy.
2. Precomputation Strategy: A systematic approach to amortize the cost of inverting the full candidate covariance matrix, making it reusable across greedy or adaptive planning steps.
3. Theoretical Guarantees: The method preserves the submodularity of the original MI objective, ensuring that greedy selection still provides a $(1 - 1/e)$ approximation guarantee.
4. Practical Implementation: Integration into a greedy sensor placement algorithm (Algorithm 1) and validation on real-world hardware.

4. Experimental Results

The authors evaluated Schur-MI on four real-world bathymetry datasets (Mississippi, Nantucket, Virgin Islands, Wrangell) and conducted field trials.

• Speedup: Schur-MI with precomputation achieved up to a 12.7× speedup over the standard MI formulation.
• Accuracy:
  • In discrete space, Schur-MI achieved identical reconstruction accuracy (Standardized Mean Squared Error - SMSE) to Standard-MI but with significantly lower runtime.
  • In continuous space, Schur-MI (optimized via CMA-ES or Lazy Greedy) was competitive with A-optimality and Sparse GP baselines, offering a better accuracy-runtime trade-off than gradient-based MI optimization.
  • With non-stationary kernels, Schur-MI outperformed Standard-MI in accuracy, avoiding spatial biases inherent in the standard $V \setminus A$ formulation.
• Field Trial: An Autonomous Surface Vehicle (ASV) successfully performed adaptive Informative Path Planning (IPP) in a lake using Schur-MI on a Raspberry Pi 5. The vehicle reconstructed the bathymetry with an SMSE of 4.54 and RMSE of 0.60, demonstrating real-time viability.

5. Significance

• Bridging Theory and Practice: Schur-MI resolves the decades-old computational bottleneck that prevented the use of principled MI objectives in real-time robotic systems.
• Scalability: By reducing complexity from cubic in the candidate set size to cubic in the selected set size, the method enables high-resolution, large-scale information gathering tasks that were previously intractable.
• Resource-Aware Autonomy: The method allows robots with limited onboard compute (e.g., edge devices) to perform complex, information-theoretic planning, facilitating safer and more efficient exploration in dangerous or inaccessible environments.

In summary, Schur-MI transforms Mutual Information from a theoretically sound but computationally prohibitive metric into a practical, real-time objective for robotic exploration.