betaFeedback

WorksComputer Science

Informative Path Planning with Gaussian Processes: Error Bounds, Algorithms, and Benchmarks

Abstract

Accurate environmental monitoring relies on Informative Path Planning (IPP) to deploy autonomous systems that maximize information gain. While Gaussian Processes (GPs) provide a robust mathematical foundation for modeling the environment, contemporary IPP approaches remain hindered by heuristic operational constraints and the lack of simultaneous theoretical guarantees for worst-case estimation error and approximation quality. Rather than introducing yet another heuristic, this paper presents a rigorous theoretical analysis of existing error bounds and algorithms to further develop the mathematical foundation for IPP. By evaluating probabilistic and deterministic bounds on reconstruction error, we establish that predictive variance is the theoretically ideal optimization objective for GP-based IPP. Furthermore, we analyze GreedyCover, a recent approach for optimizing predictive variance, and demonstrate that its near-optimal approximation guarantee matches the fundamental hardness-of-approximation limit for the problem. Comprehensive benchmarking confirms that this approach delivers superior estimation accuracy and computational efficiency compared to prominent information-theoretic objectives and optimization methods used in IPP. Finally, this theoretical analysis establishes a rigorous, near-optimal foundation for discrete offline IPP under bounded uncertainty constraints, offering clear and principled guidance for future work in continuous-space and online formulations.

Introduction

Motivation: Environmental Monitoring

In an era defined by rapid climate change, ecological degradation, and shifting global ecosystems, accurate environmental monitoring has become critical for scientific understanding and informed decision-making. Characterizing complex, large-scale natural phenomena—such as ocean salinity, atmospheric pollutants, soil moisture, or glacial bathymetry—requires high-resolution data that is often dangerous, time-consuming, or prohibitively expensive to collect manually. To address this, an overarching framework of Robotic Information Gathering (RIG) has emerged, focusing on deploying autonomous systems to maximize information gain regarding these environmental data fields [1, 2]. At its core, RIG shares fundamental

Corresponding author: Kalvik Jakkala. K. Jakkala and J. M. O’Kane are with the Department of Computer Science and Engineering, Texas A&M University, College Station, TX 77843 USA (e-mail: [email protected]). J. Wakulicz and D. G. Dansereau are with the Australian Centre for Robotics, School of Aerospace, Mechanical and Mechatronic Engineering, University of Sydney, NSW 2006, Australia. S. Akella is with the University of North Carolina at Charlotte, Charlotte, NC 28223 USA. L. Liu is with the Luddy School of Informatics, Computing, and Engineering, Indiana University Bloomington, IN 47408 USA.

similarities with active learning; both domains seek to select the most informative data points to query in order to maximize model accuracy with minimal data collection effort.

Figure 1. Informative path generated by GREEDYCOVER on the SRTM elevation dataset (45°N, 123°W). By leveraging a non-stationary kernel, the method adapts sampling density to spatial variations while guaranteeing bounded minimum posterior variance. Red: informative path and sensing locations.

Shortcomings of Geometric Coverage

Traditionally, environmental monitoring tasks have relied on geometric planners, such as boustrophedon (lawnmower) sweeps [3] or Voronoi-based coverage methods [4]. While these strategies successfully guarantee spatial visitation, they are inherently inefficient. By entirely ignoring the probabilistic data correlations within the environment, geometric sweeps frequently oversample highly predictable and redundant regions, wasting valuable time and energy.

Sensor Placement and Informative Path Planning

Overcoming the limitations of geometric coverage requires addressing two interconnected problems: Sensor Placement (SP) and Informative Path Planning (IPP). While SP focuses on identifying optimal locations for static sensors, IPP routes mobile robots through informative regions while respecting operational constraints, such as motion constraints and limited onboard compute. To model data correlations, the vast majority of these approaches rely on Gaussian Processes (GPs) [5] because of their high sample efficiency and principled uncertainty quantification.

Within this GP framework, IPP encompasses two primary operational paradigms:

  • Offline IPP: The GP hyperparameters describing the environment are assumed to be known a priori. This serves as a critical theoretical foundation to study the core problem structure.

  • Online IPP: The GP hyperparameters are unknown beforehand and must be learned dynamically by the robot during the mission.

Research Gap: Heuristics, Compute Costs, and Guarantees

Despite the mathematical foundation provided by GPs, a critical gap remains regarding the strength of theoretical guarantees offered by IPP algorithms. A persistent trade-off exists between discrete and continuous planning methods. While optimizing submodular objectives like mutual information enables discrete greedy planners to achieve strict approximation factor guarantees, these approaches suffer from severe computational bottlenecks due to expensive matrix operations.

Conversely, planners operating in continuous spaces—such as Rapidly-exploring Random Trees (RRTs) [6] or Ergodic Control [7]—can offer asymptotic convergence, but they inherently lack finite-time approximation guarantees. Indeed most IPP approaches on continuous domains provide anytime algorithms that provide better solutions the longer they run.

Furthermore, a fundamental limitation persists across both paradigms: the reliance on heuristic operational constraints. Most contemporary approaches require explicitly setting a predefined cardinality limit on sensing locations or an ad hoc travel distance budget. Ideally, a planner would instead allow users to specify a maximum allowable uncertainty or error, autonomously determining the necessary sensing budget and travel distance required to satisfy that bound.

Crucially, because existing continuous methods—including ergodic exploration and sampling-based planners—typically plan over predetermined operational budgets (such as fixed time horizons or path lengths) and optimize spatial proxy distributions, they lack finite-time approximation guarantees on the resulting GP predictive variance and worst-case field estimation error.

Key Contributions

To bridge the gap between heuristic planning and verifiable mapping quality, this work establishes a rigorous theoretical foundation for Informative Path Planning. Our core contributions are as follows:

  • Squared Error Bounds and Objective Formulation: By leveraging existing probabilistic and deterministic error bounds, we contextualize the role of GP predictive variance in bounding true field reconstruction error—showing that it both lower-bounds expected mean squared error and, scaled by the RKHS norm, upper-bounds deterministic pointwise squared error. This formally establishes predictive variance as the mathematically ideal objective for offline GP-based IPP and provides a grounded blueprint for online formulations.

  • Theoretically Grounded Discrete Offline IPP: We analyze a recent optimization algorithm, GreedyCover [8], for predictive variance and establish that its near-optimal approximation guarantee matches the fundamental hardness-of-approximation limit for the problem. Consequently, this establishes a theoretically grounded, complexity-optimal foundation for discrete offline GP-based IPP under bounded uncertainty constraints.

  • Comprehensive Benchmarking and Analysis: We evaluate prominent information-theoretic metrics and optimization methods, empirically demonstrating that GreedyCover delivers strong error reduction with substantial computational efficiency. These results establish the method as a robust solution for offline GP-based IPP under bounded uncertainty constraints while highlighting critical implications for tackling continuous-space and online formulations.

Foundational Problems: RIG, SP, and IPP

The overarching framework of Robotic Information Gathering (RIG) focuses on maximizing information gain regarding an unknown environmental field [9, 5]. Within this domain, two foundational and heavily overlapping challenges are the Sensor Placement (SP) problem and the Informative Path Planning (IPP) problem.

The SP problem seeks to identify an optimal set of fixed locations for sensors to maximize the informativeness of the collected data, with applications ranging from soil sampling to glacial monitoring [10, 11, 9]. Building directly upon SP concepts, IPP addresses the routing aspect, aiming to plan optimal sensing paths for mobile robots while adhering to operational constraints such as travel budgets and vehicle kinematics [12, 13, 14]. Both problems share analogous formulations with broader fields, such as active learning for machine learning [15] and next-best-view planning in robotics [16].

To effectively model the data correlations of the target environment, the vast majority of modern RIG approaches rely on Gaussian Processes (GPs) [5]. GPs are ubiquitous in this domain due to their exceptional data efficiency and superior capacity to provide mathematically rigorous uncertainty estimation for unobserved locations [9, 5].

Information-Theoretic Metrics

A common strategy for solving SP and IPP involves selecting sampling locations that maximize specific information-theoretic objectives [9, 17]. These metrics define the fundamental trade-off between the quality of the environmental reconstruction and the computational cost required for planning.

  • Variance and Entropy: Selecting locations with the highest variance, a metric closely related to entropy, is an intuitive and computationally fast approach [9]. However, variance-based metrics often yield less informative, suboptimal sensing locations, frequently clustering sensors along the boundaries of the search space instead of providing comprehensive coverage [9].

  • Optimal Experimental Design Metrics: Classical criteria from the field of optimal experimental design—such as B-, D-, and E-optimality [14]—have been heavily utilized, but they suffer from similar limitations regarding sensing locations.

  • Predictive Variance: Despite the limitations of naive variance minimization, mapping with respect to an explicit threshold for worst-case predictive variance is a robust, computationally efficient approach for bounding estimation uncertainty [18, 19].

  • Mutual Information (MI): Caselton and Zidek Caselton and Zidek [17] proposed the application of MI for quantifying the reduction

in uncertainty across all unobserved locations, naturally encouraging highly informative placements [9, 20, 2]. MI consistently outperforms variance-based and optimal experimental design criteria in terms of informativeness. Nevertheless, this superior performance incurs a severe computational cost; for an environment discretized into nn locations, computing MI requires O(n3)O(n^3) operations, rendering it a massive bottleneck for real-time IPP applications where the objective must be evaluated repeatedly.

Optimization Methods

Given an information-theoretic metric, various optimization and planning algorithms have been proposed to compute paths that optimize the selected objective.

  • Graph-Based, Convex, and Greedy Approaches: One foundational approach discretizes the environment and formulates the SP or IPP task as an integer program or a convex optimization problem [21, 22, 14]. While mathematically elegant, this confines potential sampling locations to a finite, predefined subset and scales poorly with high-resolution discretizations. Leveraging the submodularity of metrics like MI, discrete-space greedy algorithms iteratively select the most informative candidate locations, offering high efficiency but remaining tied to discrete grids [10, 11, 9, 23, 24, 25].

  • Continuous-Space and Sampling-Based Planners: To overcome the restrictions of discrete methods, sampling-based planners, such as Rapidly-exploring Random Trees (RRTs), have been employed to maximize MI in continuous domains [6]. Alternatively, derivative-free black-box optimizers—including genetic algorithms [12, 26] and Bayesian optimization [27, 20]—have been used. However, these methods scale poorly with dimensionality and demand numerous objective function evaluations, quickly becoming intractable when the objective is computationally expensive.

  • Gradient-Based and Ergodic Control Methods: While prone to getting stuck in local minima, gradient-based approaches have emerged to enable fast, continuous-space optimization by utilizing differentiability of MI or by leveraging Sparse Gaussian Processes (SGPs) [28, 29, 30, 31]. For settings with known utility functions, continuous-space ergodic control algorithms are leveraged to efficiently guide exploration over the data field [7, 32, 33].

  • POMDPs and Learning-Based Approaches: To address the adaptive nature of IPP, some methods frame the problem as a Partially Observable Markov Decision Process (POMDP), utilizing Monte Carlo tree search [34, 14]. Furthermore, Deep Reinforcement Learning (DRL) and Imitation Learning (IL) are increasingly used to train reactive planning policies [35, 36], although generalizing to novel environments remains an open challenge [36].

  • Coverage Planners: Baseline geometric planners—such as boustrophedon (lawnmower) sweeps [3, 37, 38], Voronoi-based coverage methods [4], and art-gallery algorithms [39]—ensure spatial visitation but typically oversample predictable regions by entirely ignoring probabilistic data correlations [40, 41].

Theoretical Guarantees

A critical axis of comparison among IPP algorithms is their theoretical guarantees concerning both optimization performance and error bounds [24, 18, 8].

Although the SP problem is NP-complete [9], the submodular nature of mutual information (MI) allows discrete greedy algorithms to achieve a (1−1/e)(1-1/e)-approximation guarantee [9]. However, these methods require repeated MI evaluations involving costly matrix operations, creating a persistent trade-off between theoretical optimality and computational tractability.

Conversely, continuous-domain planners, such as RRTs, sacrifice finite-time approximation guarantees in exchange for continuous-space placements with asymptotic optimality guarantees [6, 42]. Similarly, ergodic methods and SGP-based formulations offer rigorous asymptotic convergence guarantees for continuous space mapping [7, 30].

Recent advances have specifically targeted the lack of formal estimation quality guarantees [19, 18]. Worst-case upper bounds on reconstruction error have been developed within Reproducing Kernel Hilbert Space frameworks for the noise-free [43] and bounded observation noise [44] cases. While Wakizuka et al. [44] leverage these bounds to guide informative path planning, their planner provides no near-optimal approximation guarantees on the resulting sensing set. Meanwhile, Jakkala et al. [8] leveraged the property that predictive variance lower bounds the GP Mean Squared Error (MSE) to establish near-optimal approximation guarantees for predictive variance optimization under bounded uncertainty.

Research Gap: While the GP MSE lower bound helps establish the required sensing budget under bounded uncertainty constraints, three key limitations remain unaddressed: (i) existing worst-case upper bounds have not been studied within this formulation to provide near-optimal approximation guarantees on predictive variance; (ii) hardness-of-approximation results for the GP predictive variance are lacking, leaving the theoretical tightness of the approximation guarantees unproven; and (iii) previous empirical evaluations have been restricted to just two baselines, obscuring performance relative to prominent existing methods. This work addresses all three limitations.

Preliminaries: Gaussian Processes

We model the monitored field as an unknown function f:X→Rf:\mathcal{X}\to\mathbb{R} over a domain X⊆Rd\mathcal{X}\subseteq\mathbb{R}^{d} and use Gaussian processes (GPs) [5] to capture correlations and uncertainty.

GP Prior: A Gaussian process is a stochastic process such that any finite collection of function values is jointly Gaussian. Equivalently, a GP induces a distribution over functions, making it an expressive Bayesian prior for regression. We place a GP prior on the latent function ff:

f(x)∼GP(m(x),k(x,x′)),f(x)\sim\mathcal{GP}(m(x),k(x,x')),

where m(x)m(x) is the mean function (often taken to be 0 after normalization) and kernel k(x,x′)k(x,x') is a covariance function. The kernel specifies prior correlations:

k(x,x′)=cov⁡(f(x),f(x′)).k(x,x')=\operatorname{cov}(f(x),f(x')).

Noisy Observations and Posterior Prediction: Given nn noisy samples D={(xi,yi)}i=1n\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n} with yi=f(xi)+ϵiy_i = f(x_i) + \epsilon_i and i.i.d. Gaussian noise ϵi∼N(0,σn2)\epsilon_i \sim\mathcal{N}(0, \sigma_n^2), define the training inputs X=[x1,…,xn]X = [x_1, \ldots, x_n] and outputs y=[y1,…,yn]⊤y = [y_1, \ldots, y_n]^{\top}. For a query location xx, GP regression yields a Gaussian predictive distribution p(f(x)∣X,y)=N(μpost(x∣X),σpost2(x∣X))p(f(x)|X,y) = \mathcal{N}(\mu_{\mathrm{post}}(x|X), \sigma_{\mathrm{post}}^2(x|X)), with

μpost(x∣X)=Kxn(Knn+σn2I)−1y,\mu_{\mathrm{post}}(x|X) = K_{xn}(K_{nn} + \sigma_n^2 I)^{-1}y,
σpost2(x∣X)=k(x,x)−Kxn(Knn+σn2I)−1Knx.\sigma_{\mathrm{post}}^2(x|X) = k(x,x) - K_{xn}(K_{nn} + \sigma_n^2 I)^{-1}K_{nx}.

Here, KnnK_{nn} is the n×nn \times n covariance matrix with (Knn)ij=k(xi,xj)(K_{nn})_{ij} = k(x_i,x_j), KxnK_{xn} is the 1×n1 \times n vector of cross-covariances with (Kxn)i=k(x,xi)(K_{xn})_i = k(x,x_i), Knx=Kxn⊤K_{nx} = K_{xn}^{\top}, and k(x,x)k(x,x) is the prior variance at xx. The posterior (or predictive) variance, σpost2(x∣X)\sigma_{\mathrm{post}}^2(x \mid X), quantifies intrinsic uncertainty based solely on input locations and Gaussian process hyperparameters, making it particularly well-suited for planning.

Hyperparameter Optimization: The covariance function k(x,x′)k(x,x') and the noise model typically depend on a set of hyperparameters θ\theta (e.g., lengthscales, signal variance, and the noise variance). To properly fit the GP to the observed data, these hyperparameters are optimized by maximizing the log marginal likelihood:

log⁡p(y∣X,θ)=−12y⊤(Knn+σn2I)−1y−12log⁡∣Knn+σn2I∣−n2log⁡2π.\log p(y|X,\theta) = -\frac{1}{2}y^{\top}(K_{nn}+\sigma_n^2I)^{-1}y -\frac{1}{2}\log|K_{nn}+\sigma_n^2I|-\frac{n}{2}\log2\pi.

This objective naturally balances data fit (the first term, which penalizes large residuals) against model complexity (the second term, which penalizes highly flexible covariance matrices). This allows the GP to adapt to the scale and smoothness of the target function without overfitting.

Problem: Informative Path Planning Under Bounded Uncertainty Constraints

Informative Path Planning (IPP)

The fundamental goal of Informative Path Planning (IPP) is to determine an optimal data collection strategy that maximizes the information gathered about an environmental data field (e.g., salinity, temperature, bathymetry) over a domain X⊂Rd\mathcal{X} \subset\mathbb{R}^{d}. Let the true data field be denoted by f:X→Rf:\mathcal{X} \rightarrow\mathbb{R}.

System Setup

For planning and performance evaluation, we define a finite set of evaluation locations V={x1,…,xN}⊂X\mathcal{V} = \{x_1, \ldots, x_N\} \subset\mathcal{X} where accurate estimates are required. A robot can only sample from a restricted set of candidate sensing locations C={c1,…,cM}⊆X\mathcal{C} = \{c_1, \ldots, c_M\} \subseteq\mathcal{X}. A feasible path is represented by waypoints P=(p1,…,pT)\mathcal{P} = (p_1, \ldots, p_T), where each pt∈Cp_t \in\mathcal{C}. In typical IPP scenarios, T≪M≤NT \ll M \le N. Furthermore, we assume that neither V\mathcal{V} nor C\mathcal{C} is labeled, and that both are discretized over the continuous domain (e.g., using uniform grids).

Gaussian Process (GP) Environmental Modeling

Directly minimizing the data field prediction error is infeasible because the ground truth f(x)f(x) is unknown, and the realized error inherently depends on the specific measurement values observed along a path. To obtain a tractable surrogate objective, we model the unknown field ff as a Gaussian Process (GP). Under a GP, the prediction at any point is given by the posterior mean μpost(x∣P)\mu_{\mathrm{post}}(x|\mathcal{P}).

Problem Statement

To prevent regions of unacceptably high uncertainty, we require the posterior variance, σpost2(x∣P)\sigma_{\mathrm{post}}^2(x|\mathcal{P}), to remain strictly bounded across the discretized environment. We formulate the problem as finding the minimum-cost path P⋆\mathcal{P}^{\star} such that the posterior variance at every evaluation point xi∈Vx_i \in\mathcal{V} satisfies a specified target threshold σtar2\sigma_{\mathrm{tar}}^2:

P⋆∈argmin⁡P∈C∗cost⁡(P)\mathcal{P}^{\star} \in\operatorname*{argmin}_{\mathcal{P}\in\mathcal{C}^{*}} \operatorname{cost}(\mathcal{P})
s.t.σpost2(xi∣P)≤σtar2,∀xi∈V,(1)\text{s.t.}\quad\sigma_{\mathrm{post}}^2(x_i|\mathcal{P}) \le\sigma_{\mathrm{tar}}^2,\quad\forall x_i \in\mathcal{V}, \tag*{(1)}

where cost⁡(P)\operatorname{cost}(\mathcal{P}) denotes a path execution cost (e.g., total path length or cardinality ∣P∣|\mathcal{P}|), and C∗\mathcal{C}^{*} represents the set of all finite waypoint sequences formed from C\mathcal{C}.

Optimization Objective: Predictive Variance

To quantify the performance of our data field estimation, we must first ground our objective in the theoretical bounds of Gaussian Process (GP) regression.

Probabilistic MSE Lower Bound

Theorem 1. MSE Lower Bound [45]

When the true hyperparameters are known, the mean squared error (MSE) at any point x∈Xx \in\mathcal{X} from the domain is lower bounded:

MSE⁡=Ef∼GP(μpost,σpost2)[(f(x)−μpost(x∣P))2]≥k(x,x)−Kxn(Knn+σn2I)−1Knx=σpost2(x∣P)\operatorname{MSE} = \mathbb{E}_{f\sim\mathcal{GP}(\mu_{\mathrm{post}},\sigma_{\mathrm{post}}^2)}\left[(f(x)-\mu_{\mathrm{post}}(x|\mathcal{P}))^2\right] \ge k(x,x)-K_{xn}(K_{nn}+\sigma_n^2I)^{-1}K_{nx} = \sigma_{\mathrm{post}}^2(x|\mathcal{P})

This theorem establishes that the GP predictive variance, σpost2(x∣P)\sigma_{\mathrm{post}}^2(x|\mathcal{P}), inherently acts as a mathematical lower bound on the predictive MSE in the offline formulation where GP hyperparameters are known a priori.

To validate the bound, we first train a GP with an Attentive kernel [46] on 1D observations sampled uniformly from F(x)=sin⁡(6x)+cos⁡(2x)\mathbb{F}(x) = \sin(6x) + \cos(2x) over x∈[−1.5,1.5]x \in[-1.5,1.5], as shown in Figure 2. Using the posterior predictive distribution from this fitted model, Figure 3 empirically validates the theoretical MSE lower bound, demonstrating tight agreement between the predicted bound and empirical error statistics computed across repeated stochastic realizations.

Figure 3. Empirical validation of the GP MSE lower bound from Theorem 1. The observed MSE and its theoretical lower bound are plotted alongside the pointwise squared errors from 1,000 realizations of the underlying stochastic process used to compute the MSE. y-axis shown on a logarithmic scale with a linear region near zero. The central peak reflects the spatial distribution of sensing locations (Figure 2), which are placed symmetrically in the outer regions and leave an unobserved gap in the center.

In online applications where hyperparameters are unknown and must be estimated dynamically, the tightness and validity of this bound fluctuate:

Figure 2. GP regression on an illustrative non-stationary 1D data field. Observations (dashed vertical lines) are sampled near the outer intervals, leaving an unobserved gap in the middle. The estimated GP predictive mean μpost(x∣P)\mu_{\mathrm{post}}(x \mid\mathcal{P}) closely fits the ground-truth function f(x)f(x), while the 95% confidence interval (±1.96σpost\pm1.96\sigma_{\mathrm{post}}) expands across the unsampled center to reflect increased predictive uncertainty.

  • When the estimated lengthscales are shorter than the true environmental lengthscales, the GP underestimates data correlation, causing the model to rapidly revert to the prior variance and rendering the resulting bound overly conservative and loose.

  • If the estimated lengthscales are larger than reality, the model becomes overconfident, which artificially shrinks the predictive variance and distorts the bound’s reliability.

While predictive variance serves as an ideal optimization objective for MSE under known hyperparameters, it acts only as a lower bound, leaving the true MSE uncharacterized. Furthermore, since MSE evaluates the expected error, bounding it does not prevent large errors in individual stochastic realizations of the function of interest. To establish strict, worst-case performance guarantees, we therefore transition to a deterministic framework.

Deterministic Worst-Case Error Upper Bounds

To overcome the limitations of probabilistic bounds, we analyze existing bounds from interpolation theory within Reproducing Kernel Hilbert Spaces (RKHS), starting with the worst-case absolute error.

Theorem 2 establishes a relationship between the worst-case absolute error and the standard deviation of the predictive distribution, which holds even in the online case where the GP hyperparameters are unknown.

Theorem 2. Absolute Error Upper Bound [44] Let f∈Hkf \in\mathcal{H}_k where Hk\mathcal{H}_k is a Reproducing Kernel Hilbert Space defined by an arbitrary positive definite kernel kk. Given a set of nn noisy observations y=[y1,…,yn]T\mathbf{y} = [y_1,\ldots,y_n]^{\mathsf{T}} collected at sensing locations P=(p1,…,pn)\mathcal{P} = (p_1,\ldots,p_n), assume the measurement noise is strictly bounded such that εi2≤ε∗2\varepsilon_i^2 \le\varepsilon_*^2 for all nn observations. The absolute error of the Gaussian Process predictive mean, μpost(x∣P)\mu_{\mathrm{post}}(x \mid\mathcal{P}), at any point x∈Xx \in\mathcal{X} satisfies:

∣f(x)−μpost(x∣P)∣≤∥f∥HkPP(x)+nε∗Λk(x)\lvert f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P}) \rvert\le\lVert f \rVert_{\mathcal{H}_k} P_{\mathcal{P}}(x) + \sqrt{n}\varepsilon_* \Lambda_k(x)

where ∥f∥Hk2\lVert f \rVert_{\mathcal{H}_k}^2 is the RKHS complexity term, PP(x)=σpost2(x∣P)P_{\mathcal{P}}(x) = \sqrt{\sigma_{\mathrm{post}}^2(x \mid\mathcal{P})} is the power function corresponding to the standard deviation of the predictive distribution, and Λk(x)=∥Knn−1Kn∗∥2\Lambda_k(x) = \lVert K_{nn}^{-1}K_{n*} \rVert_2 represents the norm of the kernel matrix projection vector at the evaluation point.

Because the underlying data field is modeled as a deterministic function residing in an RKHS—where the RKHS norm ∥f∥Hk\lVert f \rVert_{\mathcal{H}_k} characterizes the function’s complexity—minimizing this deterministic upper bound guarantees that the realized absolute estimation error remains strictly upper bounded.

Using the GP model trained in Figure 2, Figure 4 empirically validates the theoretical bound (Theorem 2), demonstrating that the upper bound strictly envelopes the observed absolute error.

Figure 4. Empirical validation of the deterministic absolute error upper bound from Theorem 2. y-axis shown on a logarithmic scale with a linear region near zero.

Squaring the above bound (Theorem 2) gives the direct connection between the GP predictive variance and pointwise squared error formalized in the following corollary.

Corollary 1. Squared Error Upper Bound Let f∈Hkf \in\mathcal{H}_k be a target function within a Reproducing Kernel Hilbert Space defined by kernel kk, and suppose we have nn noisy observations subject to bounded measurement noise εi2<ε∗2\varepsilon_i^2 < \varepsilon_*^2. The pointwise squared estimation error of the Gaussian Process predictive mean, μpost(x∣P)\mu_{\mathrm{post}}(x \mid\mathcal{P}), at any point x∈Xx \in\mathcal{X} is strictly upper bounded by:

(f(x)−μpost(x∣P))2≤2∥f∥Hk2σpost2(x∣P)+2nε∗2Λk2(x)\left(f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P})\right)^2 \leq2\|f\|_{\mathcal{H}_k}^2 \sigma_{\mathrm{post}}^2(x \mid\mathcal{P}) + 2n\varepsilon_*^2\Lambda_k^2(x)

Please refer to the Appendix for the proof.

By isolating the predictive variance σpost2(x∣P)\sigma_{\mathrm{post}}^2(x \mid\mathcal{P}), Corollary 1 demonstrates that minimizing predictive variance directly drives down the worst-case squared error.

We adopt the current bound formulation to clearly isolate the contribution of predictive variance from the sensor noise. Although a tighter bound can be derived, it would introduce additional terms that couple these two sources of uncertainty, making their individual contributions less transparent.

Using the GP model trained in Figure 2, the results in Figure 5 empirically validate Corollary 1 by demonstrating that the theoretical upper bound strictly envelopes the observed squared error across the domain. Finally, Figure 6 summarizes the complete theoretical envelope, contrasting both the MSE lower bound and the squared error upper bound relative to the realized estimation errors.

Empirical validation of the deterministic squared error upper bound

Figure 5. Empirical validation of the deterministic squared error upper bound from Corollary 1. yy-axis shown on a logarithmic scale with a linear region near zero.

GP error upper and lower bounds along with corresponding errors

Figure 6. GP error upper and lower bounds along with corresponding errors. yy-axis shown on a logarithmic scale with a linear region near zero.

In environments with negligible measurement noise, this relationship simplifies considerably, as formalized next. Theorem 3 establishes a clear relationship between the GP predictive variance σpost2(x∣P)\sigma_{\mathrm{post}}^2(x \mid\mathcal{P}) and the pointwise squared error. In this formulation, the RKHS norm ∥f∥Hk\|f\|_{\mathcal{H}_k} directly dictates the tightness of the upper bound.

Theorem 3. Noise-Free Squared Error Upper Bound [43] Assume a noiseless sensing scenario where the measurement noise variance σn2=0\sigma_n^2 = 0. The pointwise squared estimation error of the Gaussian Process predictive mean μpost(x∣P)\mu_{\mathrm{post}}(x \mid\mathcal{P}) for a target function f∈Hkf \in\mathcal{H}_k is strictly bounded by the product of the squared RKHS norm of ff and the GP predictive variance:

(f(x)−μpost(x∣P))2≤∥f∥Hk2σpost2(x∣P),\left(f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P})\right)^2 \leq\|f\|_{\mathcal{H}_k}^2 \sigma_{\mathrm{post}}^2(x \mid\mathcal{P}),

where ∥f∥Hk2\|f\|_{\mathcal{H}_k}^2 is the RKHS complexity term and σpost2(x∣P)\sigma_{\mathrm{post}}^2(x \mid\mathcal{P}) is the predictive variance.

Interpretation of the RKHS Norm

To fully contextualize these error bounds, it is essential to understand the mathematical definition of the RKHS norm, ∥f∥Hk\|f\|_{\mathcal{H}_k}, and its role within GP regression.

Kernel Space and RKHS Connection: By the Moore–Aronszajn Theorem [5], the positive-definite GP kernel k(⋅,⋅)k(\cdot,\cdot) uniquely specifies a Reproducing Kernel Hilbert Space Hk\mathcal{H}_k. The kernel function and its hyperparameters (e.g., lengthscale, signal variance) completely determine the inner product and geometry of Hk\mathcal{H}_k, embedding structural assumptions regarding the continuity, differentiability, and allowable spatial variation of functions residing in the space.

Spectral Perspective and Model Complexity: The norm is best understood through Mercer’s Theorem [5], which decomposes the kernel into an orthonormal basis of continuous eigenfunctions ϕj\phi_j and associated non-negative eigenvalues λj\lambda_j.

k(x,x′)=∑j=1∞λjϕj(x)ϕj(x′).(2)k(x,x') = \sum_{j=1}^{\infty} \lambda_j \phi_j(x)\phi_j(x'). \tag*{(2)}

Any function f∈Hkf \in\mathcal{H}_k can be expanded in this eigenbasis as f(x)=∑j=1∞wjϕj(x)f(x) = \sum_{j=1}^{\infty} w_j\phi_j(x), yielding the squared RKHS norm:

∥f∥Hk2=∑j=1∞wj2λj.(3)\|f\|_{\mathcal{H}_k}^2 = \sum_{j=1}^{\infty} \frac{w_j^2}{\lambda_j}. \tag*{(3)}

For standard stationary kernels (such as the Squared Exponential or Matérn families), the eigenvalues λj\lambda_j decay rapidly toward zero as the index jj increases, with higher indices corresponding to higher-frequency spatial harmonics. Because λj\lambda_j appears in the denominator, any spectral energy wj2w_j^2 allocated to high frequencies inflates the norm. Consequently, ∥f∥Hk2\|f\|_{\mathcal{H}_k}^2 acts as a complexity metric over the RKHS.

Implications for Informative Path Planning (IPP)

Ultimately, the true RKHS norm is fully determined by the GP kernel and its hyperparameters. Since computing $|f|_{\mathcal{H}_k}^2 directly is generally intractable, this relationship dictates how IPP optimization must be formulated:

  • Offline IPP: In this paradigm, GP hyperparameters are assumed to be known a priori. Consequently, the RKHS norm directly quantifies the intrinsic spatial roughness of the ground-truth data field—independent of any observation set. If the underlying field exhibits high curvature or sharp spatial gradients, the resulting large RKHS norm inflates the theoretical error bound regardless of the executed sensing path. Crucially, because the kernel structure and hyperparameters remain fixed, the RKHS norm acts as a fixed (albeit unknown) constant.

Therefore, minimizing GP predictive variance to determine the solution sensing locations serves as the mathematically ideal objective function for offline GP-based IPP.

  • Online IPP: When GP hyperparameters are estimated adaptively from streaming observations, the norm ∥f∥Hk2\lVert f\rVert_{\mathcal{H}_k}^2 measures complexity relative to the estimated RKHS rather than to the true field. Discrepancies between this estimated space and the true underlying field geometry can lead to model misspecification, potentially invalidating the theoretical error bounds.

Therefore, online IPP methods must balance data collection for predictive variance reduction with sampling to refine hyperparameter estimates, ensuring the model operates within the true RKHS and tightly bounds the squared estimation error.

Optimization Method: GreedyCover

The preceding section established Gaussian process (GP) predictive variance as a theoretically ideal objective for Informative Path Planning (IPP). However, naively selecting sensing locations to minimize this metric not only yields suboptimal paths, but also fails to provide theoretical approximation guarantees.

To address this challenge, we adopt the GREEDYCOVER algorithm [8], which presents a decoupled approach to IPP by separating sensor placement from path generation. First, it identifies a near-minimal set of sensing locations with provable approximation guarantees to strictly bound predictive variance below a user-specified threshold. Second, it routes the robot across the selected locations using an approximation algorithm for the Traveling Salesperson Problem (TSP) [47]. Unlike conventional IPP methods that impose heuristic travel distance or cardinality limits, GREEDYCOVER directly certifies a formal bound on the maximum predictive variance.

While Sections VI-A–VI-D review the GREEDYCOVER algorithm [8], our key contribution lies in analyzing its theoretical limits: under the standard assumption that P≠NPP \ne NP, we prove that its approximation factor matches the fundamental hardness-of-approximation threshold, demonstrating that it attains the optimal polynomial-time bound (Section VI-E).

Theoretical Foundations

To achieve these approximation guarantees, the approach reframes predictive variance optimization as a Set Cover problem. It begins by establishing the mathematical conditions under which a single data field observation guarantees a target bound on posterior uncertainty. After extending these conditions to multiple observations, these theoretical foundations are used to generate a binary coverage matrix, effectively reframing the continuous optimization problem as a tractable submodular set cover problem that can be efficiently solved.

Theorem 4. Minimum Required Prior Covariance [8]

Let f∼GP(0,k)f \sim\mathcal{GP}(0,k) with independent Gaussian observation noise variance σn2\sigma_n^2, and consider a single noisy observation at candidate location c∈Cc \in\mathcal{C}. Fix an evaluation location x∈Vx \in\mathcal{V}. For any target posterior variance σtar2∈(0,k(x,x))\sigma_{\mathrm{tar}}^2 \in(0,k(x,x)), the condition

σpost2(x∣c)≤σtar2\sigma_{\mathrm{post}}^2(x \mid c) \le\sigma_{\mathrm{tar}}^2

holds if and only if

∣k(c,x)∣≥(k(x,x)−σtar2)(k(c,c)+σn2).(4)\lvert k(c,x)\rvert\ge\sqrt{\left(k(x,x)-\sigma_{\mathrm{tar}}^2\right)\left(k(c,c)+\sigma_n^2\right)}. \tag*{(4)}

Thus, achieving a posterior variance of at most σtar2\sigma_{\mathrm{tar}}^2 at xx requires that the prior covariance between cc and xx exceed the threshold in Equation (4).

Theorem 5. Variance Reduction with Multiple Locations [8]

Under the setup of Theorem 4, consider nn candidate sensing locations c1,…,cn∈Cc_1,\ldots,c_n \in\mathcal{C}. Fix an evaluation location x∈Vx \in\mathcal{V} and a target variance σtar2∈(0,k(x,x))\sigma_{\mathrm{tar}}^2 \in(0,k(x,x)). Suppose there exists j∈{1,…,n}j \in\{1,\ldots,n\} such that

∣k(cj,x)∣≥(k(x,x)−σtar2)(k(cj,cj)+σn2).\lvert k(c_j,x)\rvert\ge\sqrt{\left(k(x,x)-\sigma_{\mathrm{tar}}^2\right)\left(k(c_j,c_j)+\sigma_n^2\right)}.

Then the posterior variance at xx conditioned on all observations satisfies

σpost2(x∣c1:n)≤σtar2.\sigma_{\mathrm{post}}^2(x \mid c_{1:n}) \le\sigma_{\mathrm{tar}}^2.

Greedy Optimization Algorithm

To efficiently optimize the GP predictive variance, the method first constructs a spatial binary coverage map. Following Theorems 4 and 5, a candidate sensing location cjc_j effectively covers an evaluation point xix_i if the prior covariance k(cj,xi)k(c_j,x_i) strictly exceeds the minimum threshold in Equation (4). This coverage relationship is formalized with a binary matrix B∈{0,1}M×NB \in\{0,1\}^{M \times N}. For every candidate sensing location cj∈Cc_j \in\mathcal{C} and evaluation point xi∈Vx_i \in\mathcal{V}, the corresponding matrix entry is defined as:

Bji=I{∣k(cj,xi)∣≥(k(xi,xi)−σtar2)(k(cj,cj)+σn2)}.B_{ji} = \mathbb{I}\left\{\lvert k(c_j,x_i)\rvert\ge\sqrt{\left(k(x_i,x_i)-\sigma_{\mathrm{tar}}^2\right)\left(k(c_j,c_j)+\sigma_n^2\right)}\right\}.

Here, I{⋅}\mathbb{I}\{\cdot\} is an indicator function returning 1 if the condition holds and 0 otherwise. This binary representation offers significant practical advantages by enabling fast updates during planning via simple set operations. This also circumvents the computationally expensive process of repeatedly evaluating GP posterior variances across candidate subsets. Leveraging this binary matrix, the GreedyCover algorithm (Algorithm 1) iteratively selects sensing locations that maximize the marginal gain of newly covered points, efficiently optimizing the predictive variance. The algorithm operates with a worst-case time complexity of O(M2N)O(M^{2}N), when M≤NM \le N. Once optimized, the resulting set of sensing locations, SS, is routed using a TSP solver (such as the Christofides algorithm [47]) to generate a low-cost route visiting all locations {cj:j∈S}\{c_j : j \in S\}.

Algorithm 1 GreedyCover: Estimation Uncertainty Guaranteed Placement [8]
Require: Coverage matrix B∈{0,1}M×NB \in\{0,1\}^{M \times N}, evaluation set V={x1,…,xN}\mathcal{V} = \{x_1,\ldots,x_N\}.
Ensure: Selected index set S⊆{1,…,M}S \subseteq\{1,\ldots,M\}.
1: S←∅S \leftarrow\emptyset ▷ selected sensing-location indices
2: U←∅U \leftarrow\emptyset ▷ covered evaluation points
3: while ∣U∣<N|U| < N do
4: for each candidate j∈{1,…,M}∖Sj \in\{1,\ldots,M\}\setminus S do
5: g(j)←{xi∈V:Bji=1, xi∉U}g(j) \leftarrow\{x_i \in\mathcal{V}: B_{ji}=1,\ x_i \notin U\}
6: ▷ marginal gain
7: end for
8: j⋆←arg⁡max⁡jg(j)j^{\star} \leftarrow\arg\max_j g(j)
9: if g(j⋆)=0g(j^{\star})=0 then
10: break ▷ no further improvement possible
11: end if
12: S←S∪{j⋆}S \leftarrow S \cup\{j^{\star}\}
13: U←U∪{xi∈V:Bj⋆i=1}U \leftarrow U \cup\{x_i \in\mathcal{V}: B_{j^{\star}i}=1\}
14: end while
15: return SS

Table 1.

Monotone Submodular Objective

The objective implicitly optimized by the GreedyCover algorithm is a classic monotone submodular set function [48, 49]. By maximizing coverage encoded in the binary matrix BB, the algorithm effectively optimizes the underlying GP predictive variance. For any selected index set S⊆{1,…,M}S \subseteq\{1,\ldots,M\}, the objective function is defined as:

F(S):=∣⋃j∈S{xi∈V:Bji=1}∣.(5)F(S) := \left|\bigcup_{j \in S}\{x_i \in\mathcal{V}: B_{ji}=1\}\right|. \tag*{(5)}

This function F(S)F(S) counts the total number of evaluation points whose predictive variance is bounded below the target threshold by the selected sensing locations. Because F(S)F(S) exhibits diminishing returns—the marginal benefit of adding a new sensing location decreases as more of the environment already meets the target variance—it is a monotone and submodular objective [8].

Near-Optimal Approximation Guarantees

Finding the exact minimal sensing set SS to cover all evaluation points in V\mathcal{V} is computationally intractable in general, as the underlying combinatorial problem is NP-hard. However, because the coverage objective F(S)F(S) in Equation (5) is nonnegative, monotone, and submodular, GREEDYCOVER provides two complementary, near-optimal polynomial-time guarantees depending on the termination criterion:

  1. Bounded-Uncertainty Regime (Cardinality Guarantee): When GREEDYCOVER runs until complete domain coverage (F(S)=NF(S)=N) to strictly satisfy σpost2(xi∣S)≤σtar2\sigma_{\mathrm{post}}^{2}(x_i\mid S)\le\sigma_{\mathrm{tar}}^{2} across all xi∈Vx_i\in\mathcal{V}, it solves a submodular Set Cover instance. As established by Wolsey [49], the greedy algorithm achieves an approximation ratio bounded by the harmonic number of the maximum single-element coverage. If SgreedyS_{\mathrm{greedy}} denotes the sensing set returned upon termination and SoptS_{\mathrm{opt}} denotes the minimum-cardinality optimal set achieving full coverage, the required number of sensing locations is strictly bounded by:

∣Sgreedy∣≤(1+ln⁡(max⁡jF({j})))∣Sopt∣.(6)|S_{\mathrm{greedy}}| \le\left(1+\ln\left(\max_j F(\{j\})\right)\right)|S_{\mathrm{opt}}|. \tag*{(6)}
  1. Fixed-Budget Anytime Regime (Placement Quality Guarantee): Because GREEDYCOVER iteratively selects the candidate location maximizing marginal coverage gain g(j)g(j), its prefix sequence of placements simultaneously solves the submodular Maximum Coverage problem [48, 9]. Specifically, if execution is terminated early after selecting any fixed budget of TT sensing locations (denoted STS_T), the number of evaluation points satisfying the target variance threshold σtar2\sigma_{\mathrm{tar}}^{2} is guaranteed to be within a (1−1/e)(1-1/e) factor of the optimal TT-sensor placement ST⋆S_T^{\star}:

F(ST)≥(1−1e)max⁡∣S∣≤TF(S)=(1−1e)F(ST⋆).(7)F(S_T) \ge\left(1-\frac{1}{e}\right)\max_{|S|\le T}F(S)=\left(1-\frac{1}{e}\right)F(S_T^{\star}). \tag*{(7)}

Thus, GREEDYCOVER simultaneously guarantees (1−1/e)(1-1/e)-optimal spatial coverage at every intermediate budget TT and (1+ln⁡N)(1+\ln N)-optimal sensing cardinality upon reaching complete domain coverage (F(S)=NF(S)=N).

Note that both approximation guarantees hold with respect to the discrete coverage instance encoded by the binary matrix BB. Directly optimizing raw GP predictive variance over combinatorial subsets is intractable because multi-point variance reduction does not, in general, exhibit submodularity. By leveraging the single-observation sufficient coverage threshold (Theorems 4 and 5), this formulation maps continuous uncertainty constraints into a monotone submodular set function—circumventing the non-submodularity of raw predictive variance while certifying that the resulting sensing set satisfies the target uncertainty bound.

Hardness of Approximation

The approximation guarantees achieved by GREEDYCOVER are not merely artifacts of the greedy heuristic; they represent the fundamental computational limits of the problem. To establish this, we prove a bidirectional equivalence between the GP uncertainty bounded sensing formulation and combinatorial coverage problems. As shown in Section VI-B, Theorems 4 and 5 directly map any continuous GP uncertainty bounded planning problem into a discrete coverage instance encoded by the binary matrix B∈{0,1}M×NB \in\{0,1\}^{M \times N}.

To establish that the computational hardness of combinatorial coverage applies to our problem, we prove the converse reduction: any arbitrary binary incidence matrix BB can be realized within the GP uncertainty bounded sensing formulation by constructing an appropriate non-stationary covariance kernel. By establishing an approximation-preserving reduction, Lemma 1 demonstrates that uncertainty bounded IPP inherits the fundamental hardness-of-approximation lower bounds of both Minimum Set Cover and Maximum Coverage.

Lemma 1. Embedding Arbitrary Set Cover Instances

Let (U,S)(U, S) be an arbitrary instance of the minimum Set Cover problem with ground universe U={u1,…,uN}U = \{u_1, \ldots, u_N\} and subsets S={S1,…,SM}S = \{S_1, \ldots, S_M\}, described by the binary incidence matrix B∈{0,1}M×NB \in\{0,1\}^{M \times N}, where Bji=1B_{ji} = 1 if and only if ui∈Sju_i \in S_j. For any spatial dimension d≥2d \ge2, there exist distinct candidate locations C⊂RdC \subset\mathbb{R}^d, evaluation locations V⊂RdV \subset\mathbb{R}^d, observation noise σn2>0\sigma_n^2 > 0, a target threshold σtar2>0\sigma_{\mathrm{tar}}^2 > 0, and a valid non-stationary positive semi-definite kernel function kk such that

∣k(cj,xi)∣≥(k(xi,xi)−σtar2)(k(cj,cj)+σn2)⟺Bji=1.\lvert k(c_j,x_i)\rvert\ge\sqrt{\left(k(x_i,x_i)-\sigma_{\mathrm{tar}}^2\right)\left(k(c_j,c_j)+\sigma_n^2\right)} \Longleftrightarrow B_{ji}=1.

Please refer to the Appendix for the proof.

Because the exact spatial kernel embedding in Lemma 1 is independent of the termination criterion, it directly establishes matching polynomial-time inapproximability thresholds for both operational regimes:

  1. Bounded-Uncertainty Regime (Cardinality Hardness): When requiring complete domain coverage (F(S)=NF(S) = N), finding the minimum-cardinality sensing set is mathematically equivalent to the Minimum Set Cover problem. Feige [50] demonstrated that Set Cover admits no polynomial-time approximation ratio better than (1−o(1))ln⁡N(1-o(1))\ln N unless NP problems are solvable in slightly superpolynomial time, and Dinur and Steurer [51] subsequently tightened this bound under the standard complexity assumption that P≠NPP \ne NP. Therefore, over general non-stationary kernels, any polynomial-time algorithm yielding a valid sensing subset SapproxS_{\mathrm{approx}} is strictly bounded in the worst case by:

sup⁡I∣Sapprox(I)∣∣Sopt(I)∣≥(1−o(1))ln⁡N,(8)\sup_{\mathrm{I}} \frac{\lvert S_{\mathrm{approx}}(\mathrm{I})\rvert}{\lvert S_{\mathrm{opt}}(\mathrm{I})\rvert} \ge(1-o(1))\ln N, \tag*{(8)}

where the supremum (sup⁡I\sup_{\mathrm{I}}) is taken over all valid problem instances I\mathrm{I}, and Sopt(I)S_{\mathrm{opt}}(\mathrm{I}) denotes the minimal valid sensing subset. While an algorithm may efficiently solve trivial or uniform geometric configurations, adversarial non-stationary instances mathematically force its worst-case cardinality sub-optimality factor to scale logarithmically with NN.

  1. Fixed-Budget Anytime Regime (Placement Quality Hardness): When a strict cardinality budget ∣S∣≤T\lvert S\rvert\le T prevents full domain coverage, maximizing the number of evaluation points satisfying σpost2(xi∣S)≤σtar2\sigma_{\mathrm{post}}^2(x_i \mid S) \le\sigma_{\mathrm{tar}}^2 is mathematically equivalent to the maximum TT-Coverage problem. In the same landmark study [50], Feige proved that no polynomial-time algorithm can approximate Maximum TT-Coverage within a factor better than (1−1/e+ϵ)(1-1/e+\epsilon) for any ϵ>0\epsilon> 0 unless P=NPP = NP. Consequently, for any polynomial-time algorithm returning a TT-sensor placement Sapprox,TS_{\mathrm{approx},T}, its worst-case coverage ratio against the optimal TT-sensor placement ST∗S_T^* is upper-bounded:

inf⁡IF(Sapprox,T(I))F(ST∗(I))≤1−1e+o(1).(9)\inf_{\mathrm{I}} \frac{F(S_{\mathrm{approx},T}(\mathrm{I}))}{F(S_T^*(\mathrm{I}))} \le1-\frac{1}{e}+o(1). \tag*{(9)}

By achieving the (1+ln⁡N)(1+\ln N) cardinality upper bound of Wolsey [49] upon full coverage and the (1−1/e)(1-1/e) coverage lower bound of Nemhauser et al. [48] at every intermediate budget TT, GreedyCover asymptotically matches both theoretical hardness thresholds. Under the assumption that P≠NPP \ne NP, GreedyCover is simultaneously complexity-optimal in polynomial time for both bounded-uncertainty termination and fixed-budget sensor placement.

Experiments

The preceding theoretical analysis established predictive variance as the ideal objective function for Gaussian Process (GP)-based Informative Path Planning (IPP). It also established that GreedyCover achieves the theoretical performance limit when optimizing this metric in discrete settings. To empirically validate these findings and explore their practical implications, this section presents two benchmarks:

  1. Information-Theoretic Objectives Benchmark: Evaluating the performance of using predictive variance as an optimization objective versus other prominent metrics.

  1. Optimization Methods Benchmark: Evaluating the computational efficiency and estimation error quality of GreedyCover against prominent optimization algorithms.

Experimental Setup and Methodology

All benchmark evaluations were executed on a workstation equipped with an AMD EPYC CPU with 16 cores and 32 GB of RAM, utilizing CPU-only operations. We conducted experiments using the SRTM dataset [52], presenting results for one primary location (45°N, 123°W) in this section and three additional locations in the appendix.

The evaluation focuses on offline single-robot IPP, which assumes the GP hyperparameters are known a priori. To guarantee hyperparameter consistency across evaluations, we trained an oracle GP using an Attentive kernel [46] on the SRTM data, and sampled a true function from this model to generate our ground-truth evaluation data.

Most IPP methods consider heuristic distance or cardinality constraints on sensing locations rather than the more useful maximum predictive variance (i.e., uncertainty) constraint. Therefore, we used the GreedyCover algorithm to establish a universal cardinality constraint. Specifically, we configured GreedyCover to bound the maximum predictive variance at 85% of the maximum prior variance, yielding a budget of 102 sensing locations. This sensing budget was subsequently enforced across all methods in both benchmarks to ensure a fair comparison.

The quality of the generated paths is assessed using the following metrics, computed by comparing the GP predictive mean to the sampled ground-truth test data:

  • Mean Squared Error (MSE): The average squared discrepancy between predictions and ground truth:

MSE=1∣V∣∑xi∈V(f(xi)−μpost(xi∣P))2.(10)\mathrm{MSE} = \frac{1}{|\mathcal{V}|} \sum_{x_i \in\mathcal{V}} \left(f(x_i) - \mu_{\mathrm{post}}(x_i \mid\mathcal{P})\right)^2 . \tag*{(10)}
  • Path Length: The total Euclidean distance traveled along the planned path P=(p1,…,pT)\mathcal{P} = (p_1, \ldots, p_T):

L(P)=∑t=1T−1∥pt+1−pt∥2.(11)L(\mathcal{P}) = \sum_{t=1}^{T-1} \lVert p_{t+1} - p_t \rVert_2 . \tag*{(11)}
  • Runtime: The total computation time required for an algorithm to yield the solution path.

Each benchmark experiment was repeated ten times, with the mean and standard deviation reported in the results.

Benchmark I: Information-Theoretic Objectives

Research Question: How does GreedyCover’s discrete predictive variance optimization compare against prominent information-theoretic metrics optimized with a black-box optimizer, such as CMA-ES?

Key Takeaway: GreedyCover demonstrates a clear advantage. Despite operating over a discrete domain, it attains the lowest estimation error. Moreover, it incurs a notably lower computational cost by avoiding repetitive objective function evaluations across candidate solutions.

The first benchmark empirically evaluates prominent information-theoretic objective functions detailed in Table I. To assess these objectives without imposing discrete grid constraints, we employed the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). As a derivative-free, black-box genetic algorithm, CMA-ES generally outperforms Bayesian Optimization when handling the complex, continuous-space utility functions typical of IPP [12]. The results of this evaluation are shown in Figure 7 and Figure 8.

Bar charts showing MSE and path length across information-theoretic objectives

Figure 7. (45°N, 123°W) Estimation error (MSE) and path length across information-theoretic objectives. GreedyCover achieves lower overall error despite its discrete-space constraints, outperforming baseline objectives optimized in continuous space using CMA-ES.

Figure 8. (45°N, 123°W) Runtime comparison of prominent information-theoretic objectives (right: zoomed version of the left). While continuous-space optimization severely inflates the search space and computational overhead for CMA-ES, GreedyCover leverages its discrete formulation to deliver solutions orders of magnitude faster.

Analysis: Consistent with our theoretical analysis establishing predictive variance as the optimal objective for minimizing worst-case estimation error in offline GP-based IPP, GreedyCover empirically achieves the greatest error reduction. In contrast, the continuous optimization baselines using CMA-ES—regardless of the objective metric—fail to match the performance floor established by GreedyCover. This shortcoming stems from CMA-ES operating over the unconstrained continuous domain, which drastically expands the search space. metric, can scale cubically with the number of sensing locations per evaluation. In contrast, GreedyCover only computes the covariances of individual candidate sensing locations and relies on efficient binary operations to achieve fast execution.

ObjectiveEquation Formulation
Mutual Information [9]log⁡∣KPP∣+log⁡∣KVV∣−log⁡∣Kcombined∣\log|K_{PP}| + \log|K_{VV}| - \log|K_{\mathrm{combined}}|
Schur MI [2]log⁡∣KPP∣−log⁡∣KPP−KPVKVV−1KVP∣\log|K_{PP}| - \log|K_{PP} - K_{PV}K_{VV}^{-1}K_{VP}|
B-Optimal [34]Tr⁡(KPP−1)\operatorname{Tr}(K_{PP}^{-1})
D-Optimal [9]−log⁡∣KPP∣-\log|K_{PP}|
Predictive Variance [5]−Tr⁡(Σpost)-\operatorname{Tr}(\Sigma_{\mathrm{post}})
Entropy [5]−0.5log⁡∣Σpost∣-0.5\log|\Sigma_{\mathrm{post}}|

Table 1 (PDF p. 11). Information-theoretic objective functions used in the benchmark.

Benchmark II: Optimization Methods

Research Question: How does GreedyCover compare to prominent optimization methods in balancing estimation error and runtime efficiency?

Key Takeaway: GreedyCover consistently achieves the best balance between error reduction and runtime, while matching the individual best-in-class performance across both metrics. Moreover, GreedyCover is the only algorithm that achieves the theoretical limit of approximation for its problem class, providing provable near-optimality that guarantees high-quality solutions across varied environments and GP hyperparameters.

The second benchmark compares prominent IPP optimization methods detailed in Table II. Except for Continuous SGP, all evaluated algorithms are configured to optimize predictive variance. Note that while the Greedy Objective optimizer greedily optimizes the raw predictive variance, GreedyCover leverages its submodular formulation. The comparative results are presented in Figure 9 and Figure 10.

Bar charts comparing estimation error and path length across optimization methods

Figure 9. (45∘N,123∘W)(45^\circ\mathrm{N}, 123^\circ\mathrm{W}) Estimation error (MSE) and path length across prominent optimization methods. GreedyCover matches the best-in-class accuracy of continuous planners while avoiding the susceptibility to local minima inherent in gradient-based approaches.

Figure 10. (45∘N,123∘W)(45^\circ\mathrm{N}, 123^\circ\mathrm{W}) Runtime comparison of prominent optimization methods (right: zoomed version of the left). GreedyCover delivers unparalleled computational speed, sharply contrasting with competing baselines that are hindered by the need for numerous, expensive objective function evaluations.

Optimization MethodDescription
GreedyCover [8]A near-optimal discrete algorithm that utilizes a submodular set-cover formulation to strictly constrain predictive variance.
Bayesian Optimization [27]A continuous-space black-box Bayesian optimization method utilizing surrogate modeling for objective maximization.
CMA-ES [12]A derivative-free, continuous-space evolutionary algorithm based on covariance matrix adaptation.
Continuous SGP [31]A gradient-based continuous space path planner leveraging variational Sparse Gaussian Process approximations.
Gradient Descent [2]A continuous-space method using exact analytical gradients with the Adam optimizer.
Ergodic Control [7]A continuous-space trajectory planner that optimizes paths to match the spatial distribution of an underlying information map.
POMDP Planner [53]A Partially Observable Markov Decision Process formulation solved via Monte Carlo Tree Search with Upper Confidence Bounds.
Greedy Objective [9]A discrete algorithm that sequentially selects candidate locations to maximize marginal objective gains.

Table II. Informative path planning optimization methods used in the benchmark.

Note: Baseline methods were implemented using established Python libraries where possible. While these offer practical runtime approximations, they may not capture the absolute optimal performance of each approach. Implementation details are available in the code appendix.

Analysis: GreedyCover consistently achieves low estimation error while maintaining fast execution times. With the exception of Gradient Descent, all baseline methods exhibit comparable MSE and path length performance. In terms of runtime, however, GreedyCover outperforms all baselines, consistently converging in under one second across all experimental trials.

Moreover, Continuous SGP does not optimize predictive variance, thereby foregoing the theoretical error bounds associated with this objective. While Ergodic Control proves to be a viable continuous-space planner—achieving estimation errors comparable to GreedyCover with reasonable execution times—its practical deployment remains challenging. Specifically, there is currently no principled approach to determine the sensing budget required to satisfy bounded uncertainty constraints, nor does the method provide finite-time convergence guarantees.

Key Findings and Conclusion

Our theoretical analysis and empirical evaluations yield critical insights into Informative Path Planning (IPP), enabling us to formally establish rigorous bounds in offline Gaussian Process (GP)-based IPP and identify fundamental gaps in continuous-space and online paradigms.

The Resolution of Discrete Offline IPP

Theorem 3 establishes that the pointwise squared error is upper-bounded by the product of the RKHS norm ∥f∥Hk\lVert f\rVert_{\mathcal{H}_k} and the GP predictive variance σpost2\sigma_{\mathrm{post}}^2. In offline IPP, a priori knowledge of the hyperparameters ensures that the RKHS norm is a fixed constant reflecting the complexity of the underlying data field. Consequently, minimizing the predictive variance across candidate sensing locations emerges as the mathematically ideal objective to reduce the worst-case estimation error.

GreedyCover (Algorithm [1]) operationalizes this property by enforcing a maximum predictive variance threshold, thereby bounding pointwise squared error up to an unknown RKHS norm scaling factor. Formulated as a submodular Set Cover problem, GreedyCover attains near-optimal approximation guarantees that match the fundamental hardness-of-approximation limits for the problem class. Coupled with an efficient O(M2N)O(M^2N) complexity and thorough empirical validation, the algorithm provides a theoretically and practically ideal solution.

Nevertheless, a key limitation of GREEDYCOVER is its decoupled approach, which separates sensor placement from path generation via TSP post-processing. While this decoupling guarantees polynomial-time optimality with respect to sensing set cardinality and fixed-budget coverage alongside a constant-factor approximation on the subsequent path length, minimizing the number of sensing locations does not necessarily minimize total travel distance; multiple valid sensing sets of identical cardinality may satisfy the uncertainty threshold, yet their spatial configurations can yield different path lengths. Extending these complexity-optimal error and approximation guarantees to a fully coupled formulation remains an important direction for future work.

Callout stating that GreedyCover optimizes predictive variance and achieves the tightest possible approximation guarantee

Figure 1 (PDF p. 12).

The Frontier of Continuous-Space Planning

Establishing similarly rigorous bounds for continuous-space IPP is the next logical frontier. Currently, GreedyCover empirically outperforms most continuous-space planners in both runtime and error reduction. Ergodic Control represents a promising continuous-space alternative, although it currently relies on heuristic path-length constraints and provides only asymptotic convergence guarantees.

Callout stating that continuous-space IPP remains an open problem

Figure 2 (PDF p. 12).

Online IPP and Model Uncertainty

Online IPP—where hyperparameters must be learned dynamically during deployment—also remains an open challenge. Although predictive variance provides a theoretically grounded objective, naively optimizing it using deterministic estimates of GP hyperparameters is insufficient. Existing online methods focus exclusively on spatial uncertainty arising from data sparsity, an assumption valid only in offline settings with fixed, known hyperparameters. In online IPP, planners must also account for epistemic model uncertainty by explicitly incorporating the uncertainty in the hyperparameters themselves.

Online IPP must explicitly account for hyperparameter uncertainty, enabling planners to collect informative data that jointly reduces spatial uncertainty from data sparsity and epistemic model uncertainty.

Appendix

Proofs

The proof of Corollary 1 and Lemma 1 are presented in this appendix.

Corollary 1. Squared Error Upper Bound Let f∈Hkf \in\mathcal{H}_k be a target function within a Reproducing Kernel Hilbert Space defined by kernel kk, and suppose we have nn noisy observations subject to bounded measurement noise εi2≤ε⋆2\varepsilon_i^2 \le\varepsilon_\star^2. The pointwise squared estimation error of the Gaussian Process predictive mean, μpost(x∣P)\mu_{\mathrm{post}}(x \mid\mathcal{P}), at any point x∈Xx \in\mathcal{X} is strictly upper bounded by:

(f(x)−μpost(x∣P))2≤2∥f∥Hk2σpost2(x∣P)+2nε⋆2Λk2(x)(f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P}))^2 \le2\lVert f \rVert_{\mathcal{H}_k}^2 \sigma_{\mathrm{post}}^2(x \mid\mathcal{P}) + 2n\varepsilon_\star^2\Lambda_k^2(x)

Proof. Starting from the absolute deterministic prediction error bound established previously, we square both sides to map the bound to the squared estimation error objective:

(f(x)−μpost(x∣P))2≤(∥f∥HkPP(x)+nε⋆Λk(x))2(f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P}))^2 \le\left(\lVert f \rVert_{\mathcal{H}_k}P_{\mathcal{P}}(x) + \sqrt{n}\varepsilon_\star\Lambda_k(x)\right)^2

To decouple the variance term from the measurement noise term, we apply the standard algebraic identity (a+b)2≤2a2+2b2(a+b)^2 \le2a^2 + 2b^2:

(f(x)−μpost(x∣P))2≤2(∥f∥HkPP(x))2+2(nε⋆Λk(x))2(f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P}))^2 \le2\left(\lVert f \rVert_{\mathcal{H}_k}P_{\mathcal{P}}(x)\right)^2 + 2\left(\sqrt{n}\varepsilon_\star\Lambda_k(x)\right)^2

Because the power function PP(x)P_{\mathcal{P}}(x) represents the worst-case interpolation error norm in a noise-free setting, its square is precisely equal to the Gaussian Process predictive variance σpost2(x∣P)\sigma_{\mathrm{post}}^2(x \mid\mathcal{P}). Distributing the squares and substituting PP(x)2=σpost2(x∣P)P_{\mathcal{P}}(x)^2 = \sigma_{\mathrm{post}}^2(x \mid\mathcal{P}) yields the final squared bound:

(f(x)−μpost(x∣P))2≤2∥f∥Hk2σpost2(x∣P)+2nε⋆2Λk2(x)(f(x) - \mu_{\mathrm{post}}(x \mid\mathcal{P}))^2 \le2\lVert f \rVert_{\mathcal{H}_k}^2 \sigma_{\mathrm{post}}^2(x \mid\mathcal{P}) + 2n\varepsilon_\star^2\Lambda_k^2(x)

:::

Lemma 1. Embedding Arbitrary Set Cover Instances Let (U,S)(U, \mathcal{S}) be an arbitrary instance of the minimum Set Cover problem with ground universe U={u1,…,uN}U = \{u_1, \ldots, u_N\} and subsets S={S1,…,SM}\mathcal{S} = \{S_1, \ldots, S_M\}, described by the binary incidence matrix B∈{0,1}M×NB \in\{0,1\}^{M \times N}, where Bji=1B_{ji} = 1 if and only if ui∈Sju_i \in S_j. For any spatial dimension d≥2d \ge2, there exist distinct candidate locations C⊂Rd\mathcal{C} \subset\mathbb{R}^d, evaluation locations V⊂Rd\mathcal{V} \subset\mathbb{R}^d, observation noise σn2>0\sigma_n^2 > 0, a target threshold σtar2>0\sigma_{\mathrm{tar}}^2 > 0, and a valid non-stationary positive semi-definite kernel function kk such that

∣k(cj,xi)∣≥(k(xi,xi)−σtar2)(k(cj,cj)+σn2)⟺Bji=1.\lvert k(c_j, x_i) \rvert\ge\sqrt{\left(k(x_i, x_i) - \sigma_{\mathrm{tar}}^2\right)\left(k(c_j, c_j) + \sigma_n^2\right)} \Longleftrightarrow B_{ji} = 1.

Proof. This instance of the minimum Set Cover problem is uniquely encoded by the binary incidence matrix B∈{0,1}M×NB \in\{0,1\}^{M \times N}, where Bji=1B_{ji} = 1 if ui∈Sju_i \in S_j and 00 otherwise. We construct an exact spatial embedding in Rd\mathbb{R}^d for d≥2d \ge2 through the following sequence of steps.

Spatial embedding. Select MM candidate locations C={c1,…,cM}\mathcal{C} = \{c_1, \ldots, c_M\} and NN evaluation locations V={x1,…,xN}\mathcal{V} = \{x_1, \ldots, x_N\} in Rd\mathbb{R}^d such that all M+NM+N locations are distinct. Let δ>0\delta> 0 be the minimum Euclidean distance between any two distinct locations in C∪V\mathcal{C} \cup\mathcal{V}.

High-dimensional feature space. We construct a latent feature map ϕ:Rd→RM+N\phi: \mathbb{R}^d \to\mathbb{R}^{M+N} to represent the Set Cover topology. Let {e1,…,eM}\{e_1, \ldots, e_M\} form the standard orthonormal basis for the first MM dimensions and {v1,…,vN}\{v_1, \ldots, v_N\} form the basis for the remaining NN dimensions. We assign discrete feature vectors at the designated spatial locations. For each candidate sensor cj∈Cc_j \in\mathcal{C}, define ϕ(cj)=ej\phi(c_j) = e_j. For each evaluation location xi∈Vx_i \in\mathcal{V}, define

ϕ(xi)=∑m=1MBmiem+M−di vi,\phi(x_i) = \sum_{m=1}^{M} B_{mi}e_m + \sqrt{M-d_i}\,v_i,

where di=∑m=1MBmi≥1d_i = \sum_{m=1}^{M} B_{mi} \ge1 is the degree of element uiu_i.

Continuous domain extension. To ensure the Gaussian process is mathematically valid over the entire continuous domain Rd\mathbb{R}^d, we extend the discrete feature map ϕ\phi into a globally continuous function Φ:Rd→RM+N\Phi: \mathbb{R}^d \to\mathbb{R}^{M+N}. Let b:Rd→[0,1]b : \mathbb{R}^d \to[0,1] be a smooth, compactly supported radial bump function such that b(0)=1b(0)=1 and b(z)=0b(z)=0 for all ∥z∥≥δ/2\lVert z\rVert\ge\delta/2. Define the continuous field

Φ(z)=∑j=1Mϕ(cj)b(z−cj)+∑i=1Nϕ(xi)b(z−xi).\Phi(z) = \sum_{j=1}^{M} \phi(c_j)b(z-c_j) + \sum_{i=1}^{N} \phi(x_i)b(z-x_i).

Because the bump functions’ supports are strictly disjoint, the summation evaluates to exactly Φ(cj)=ϕ(cj)\Phi(c_j)=\phi(c_j) and Φ(xi)=ϕ(xi)\Phi(x_i)=\phi(x_i) at the locations of the sensors and evaluation points, and yields the zero vector in empty space.

Kernel construction. Define the non-stationary covariance kernel via the inner product k(z,z′)=⟨Φ(z),Φ(z′)⟩k(z,z') = \langle\Phi(z), \Phi(z')\rangle. As the inner product of an explicit feature map Φ(z)\Phi(z), k(z,z′)=⟨Φ(z),Φ(z′)⟩k(z,z') = \langle\Phi(z), \Phi(z')\rangle is symmetric and positive semi-definite by construction. Evaluating the covariance at our specific points yields a prior variance at candidates of k(cj,cj)=∥ej∥2=1k(c_j,c_j)=\lVert e_j\rVert^2=1, and a prior variance at evaluation points of k(xi,xi)=∥∑m=1MBmiem∥2+∥M−divi∥2=di+(M−di)=Mk(x_i,x_i)=\left\lVert\sum_{m=1}^{M}B_{mi}e_m\right\rVert^2+\left\lVert\sqrt{M-d_i}v_i\right\rVert^2=d_i+(M-d_i)=M. The cross-covariance evaluates exactly to the incidence matrix

k(cj,xi)=⟨ej,∑m=1MBmiem+M−divi⟩=Bji.k(c_j,x_i)=\left\langle e_j,\sum_{m=1}^{M}B_{mi}e_m+\sqrt{M-d_i}v_i\right\rangle=B_{ji}.

Threshold calibration. To map this back to the continuous informative path planning threshold, we select an observation noise σn2>0\sigma_n^2>0 and target variance σtar2∈(0,k(xi,xi))\sigma_{\mathrm{tar}}^2 \in(0,k(x_i,x_i)) such that the threshold τ=(k(xi,xi)−σtar2)(k(cj,cj)+σn2)\tau=\sqrt{\left(k(x_i,x_i)-\sigma_{\mathrm{tar}}^2\right)\left(k(c_j,c_j)+\sigma_n^2\right)} perfectly acts as a binary classifier. Let σn2=0.25\sigma_n^2=0.25 and σtar2=M−0.2\sigma_{\mathrm{tar}}^2=M-0.2. Since M≥1M\ge1, we satisfy 0<σtar2<M0<\sigma_{\mathrm{tar}}^2<M.

Equivalence to Set Cover incidence. Substituting the prior variances yields

Estimation error and path length across prominent information-theoretic objectives

Figure 11. (17°N, 073°W) Estimation error (MSE and path length) across prominent information-theoretic objectives.

Figure 12. (17°N, 073°W) Runtime evaluation across information-theoretic objectives (right: zoomed version of the left).

τ=(M−(M−0.2))(1+0.25)=0.2×1.25=0.5\tau= \sqrt{(M - (M - 0.2))(1 + 0.25)} = \sqrt{0.2 \times1.25} = 0.5

According to the cross-covariance computed previously, k(cj,xi)=1k(c_j, x_i) = 1 if Bji=1B_{ji} = 1, and 0 if Bji=0B_{ji} = 0. Therefore, we achieve the strict equivalence

∣k(cj,xi)∣≥τ⟺Bji≥0.5⟺Bji=1\lvert k(c_j, x_i) \rvert\ge\tau\Longleftrightarrow B_{ji} \ge0.5 \Longleftrightarrow B_{ji} = 1

This proves that the predictive variance bounds derived from this constructed non-stationary Gaussian process kernel exactly reproduce the arbitrary Set Cover incidence matrix BB. □\square

Additional Benchmark Results

This section evaluates benchmark performance across three additional regions from the SRTM dataset. Specifically, regions at 17°N, 073°W, 02°N, 021°W, and 47°N, 124°W require 103, 119, and 117 sensing locations, respectively, to satisfy the 85% uncertainty bound.

Estimation error and path length across prominent optimization methods

Figure 13. (17∘17^\circN, 073∘073^\circW) Estimation error (MSE and path length) across prominent optimization methods.

Runtime evaluation across prominent optimization methods

Figure 14. (17∘17^\circN, 073∘073^\circW) Runtime evaluation across prominent optimization methods (right: zoomed version of the left).

Estimation error and path length across prominent information-theoretic objectives

Figure 15. (02∘02^\circN, 021∘021^\circW) Estimation error (MSE and path length) across prominent information-theoretic objectives.

Figure 16. (02∘02^\circN, 021∘021^\circW) Runtime evaluation across information-theoretic objectives (right: zoomed version of the left).

MSE and path length across prominent optimization methods

Figure 17. (02∘^\circN, 021∘^\circW) Estimation error (MSE and path length) across prominent optimization methods.

Runtime evaluation across prominent optimization methods

Figure 18. (02∘^\circN, 021∘^\circW) Runtime evaluation across prominent optimization methods (right: zoomed version of the left).

MSE and path length across prominent information-theoretic objectives

Figure 19. (47∘^\circN, 124∘^\circW) Estimation error (MSE and path length) across prominent information-theoretic objectives.

Figure 20. (47∘^\circN, 124∘^\circW) Runtime evaluation across information-theoretic objectives (right: zoomed version of the left).

Estimation error and path length across prominent optimization methods

Figure 21. (47∘N47^\circ\mathrm{N}, 124∘W124^\circ\mathrm{W}) Estimation error (MSE and path length) across prominent optimization methods.

Figure 22. (47∘N47^\circ\mathrm{N}, 124∘W124^\circ\mathrm{W}) Runtime evaluation across prominent optimization methods (right: zoomed version of the left).

References

  1. [1]W. Chen, L. Liu, and R. Khardon, “POAM: Probabilistic Online Attentive Mapping for Efficient Robotic Information Gathering,” in Robotics: Science and Systems, 2024.arxiv.org/abs/2406.03669
  2. [2]K. Jakkala, J. O’Kane, and S. Akella, “Schur-MI: Fast Mutual Information for Robotic Information Gathering,” in IEEE/RSJ International Conference on Intelligent Robots and Systems, Pittsburgh, USA, Sep. 2026, pp. 1522–1529.arxiv.org/abs/2602.12346
  3. [3]H. Choset and P. Pignon, “Coverage Path Planning: The Boustrophedon Cellular Decomposition,” in Field and Service Robotics. London: Springer London, 1998, pp. 203–209.DOI
  4. [4]A. Breitenmoser, M. Schwager, J.-C. Metzger, R. Siegwart, and D. Rus, “Voronoi coverage of non-convex environments with a group of networked robots,” in 2010 IEEE International Conference on Robotics and Automation, 2010, pp. 4982–4989.DOI
  5. [5]C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning. Cambridge, USA: MIT Press, 2005.DOI
  6. [6]G. A. Hollinger and G. S. Sukhatme, “Sampling-based robotic information gathering algorithms,” The International Journal of Robotics Research, vol. 33, no. 9, pp. 1271–1287, 2014.DOI
  7. [7]L. M. Miller, Y. Silverman, M. A. MacIver, and T. D. Murphey, “Ergodic Exploration of Distributed Information,” IEEE Transactions on Robotics, vol. 32, no. 1, pp. 36–52, 2016.DOI
  8. [8]K. Jakkala, S. Agarwal, J. O’Kane, and S. Akella, “Informative Path Planning with Guaranteed Estimation Uncertainty,” in Robotics: Science and Systems (RSS), 2026.arxiv.org/abs/2602.05198
  9. [9]A. Krause, A. Singh, and C. Guestrin, “Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies,” Journal of Machine Learning Research, vol. 9, no. 8, pp. 235–284, 2008.
  10. [10]M. C. Shewry and H. P. Wynn, “Maximum entropy sampling,” Journal of Applied Statistics, vol. 14, no. 2, pp. 165–170, 1987.
  11. [11]S. Wu and J. V. Zidek, “An entropy-based analysis of data from selected NADP/NTN network sites for 1983–1986,” Atmospheric Environment. Part A. General Topics, vol. 26, no. 11, pp. 2089–2103, 1992.DOI
  12. [12]G. Hitz, E. Galceran, M.-E. Garneau, F. Pomerleau, and R. Siegwart, “Adaptive continuous-space informative path planning for online environmental monitoring,” Journal of Field Robotics, vol. 34, no. 8, pp. 1427–1449, 2017.DOI
  13. [13]K.-C. Ma, L. Liu, H. K. Heidarsson, and G. S. Sukhatme, “Data-driven learning and planning for environmental sampling,” Journal of Field Robotics, vol. 35, no. 5, pp. 643–661, 2018.arxiv.org/abs/1702.01848
  14. [14]J. Ott, M. J. Kochenderfer, and S. Boyd, “Approximate sequential optimization for informative path planning,” Robotics and Autonomous Systems, vol. 182, p. 104814, 2024.arxiv.org/abs/2402.08841
  15. [15]P. Ren, Y. Xiao, X. Chang, P.-Y. Huang, Z. Li, B. B. Gupta, X. Chen, and X. Wang, “A Survey of Deep Active Learning,” ACM Comput. Surv., vol. 54, no. 9, oct 2021.arxiv.org/abs/2009.00236
  16. [16]R. Zeng, Y. Wen, W. Zhao, and Y.-J. Liu, “View planning in robot active vision: A survey of systems, algorithms, and applications,” Computational Visual Media, vol. 6, no. 3, pp. 225–245, Sep 2020.DOI
  17. [17]W. Casselton and J. Zidek, “Optimal monitoring network designs,” Statistics & Probability Letters, vol. 2, no. 4, pp. 223–227, 1984.
  18. [18]S. Dutta, N. Wilde, P. Tokekar, and S. L. Smith, “Approximation Algorithms for Robot Tours in Random Fields with Guaranteed Estimation Accuracy,” in 2023 IEEE International Conference on Robotics and Automation (ICRA), 2023, pp. 7830–7836.arxiv.org/abs/2210.08107
  19. [19]V. Suryan and P. Tokekar, “Learning a Spatial Field in Minimum Time With a Team of Robots,” IEEE Transactions on Robotics, vol. 36, no. 5, pp. 1562–1576, 2020.arxiv.org/abs/1909.01895
  20. [20]X. Lin, A. Chowdhury, X. Wang, and G. Terejanu, “Approximate computational approaches for Bayesian sensor placement in high dimensions,” Information Fusion, vol. 46, pp. 193–205, 2019.arxiv.org/abs/1703.00368
  21. [21]S. Shoja and S. Boyd, “Sensor Selection via Convex Optimization,” IEEE Transactions on Signal Processing, vol. 57, no. 2, pp. 451–462, 2009.
  22. [22]S. Dutta, N. Wilde, and S. L. Smith, “Informative Path Planning in Random Fields via Mixed Integer Programming,” in 2022 IEEE 61st Conference on Decision and Control (CDC), 2022, pp. 7222–7228.arxiv.org/abs/2204.09571
  23. [23]J. Binney, A. Krause, and G. S. Sukhatme, “Informative Path Planning for an Autonomous Underwater Vehicle,” in 2010 IEEE International Conference on Robotics and Automation (ICRA), 2010, pp. 4791–4796.DOI
  24. [24]A. Krause and C. Guestrin, “Submodularity and Its Applications in Optimized Information Gathering,” ACM Trans. Intell. Syst. Technol., vol. 2, no. 4, Jul. 2011.DOI
  25. [25]J. Binney, A. Krause, and G. S. Sukhatme, “Optimizing waypoints for monitoring spatiotemporal phenomena,” The International Journal of Robotics Research, vol. 32, no. 8, pp. 873–888, 2013.DOI
  26. [26]M. Popović, T. Vidal-Calleja, G. Hitz, J. J. Chung, I. Sa, R. Siegwart, and J. Nieto, “An informative path planning framework for UAV-based terrain monitoring,” Autonomous Robots, vol. 44, no. 6, pp. 889–911, Jul 2020.arxiv.org/abs/1809.03870
  27. [27]G. Francis, L. Ott, R. Marchant, and F. Ramos, “Occupancy map building through Bayesian exploration,” The International Journal of Robotics Research, vol. 38, no. 7, pp. 769–792, 2019.arxiv.org/abs/1703.00227
  28. [28]A. Asgharivaskasi, S. Koga, and N. Atanasov, “Active Mapping via Gradient Ascent Optimization of Shannon Mutual Information over Continuous SE(3) Trajectories,” in 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2022, pp. 12 994–13 001.arxiv.org/abs/2204.07623
  29. [29]K. Jakkala and S. Akella, “Multi-Robot Informative Path Planning from Regression with Sparse Gaussian Processes,” in 2024 IEEE International Conference on Robotics and Automation (ICRA), 2024.
  30. [30]K. Jakkala, “Fully Differentiable Adaptive Informative Path Planning,” in 2025 IEEE International Conference on Robotics and Automation, Atlanta, GA, May 2025, pp. 5431–5437.DOI
  31. [31]K. Jakkala, “Fully differentiable sensor placement and informative path planning,” International Journal of Robotics Research, vol. 45, no. 8, p. 1247–1284, Jul. 2026.DOI
  32. [32]A. Rao, A. Breitfeld, A. Candela, B. Jensen, D. Wettergreen, and H. Choset, “Multi-Objective Ergodic Search for Dynamic Information Maps,” in 2023 IEEE International Conference on Robotics and Automation (ICRA), 2023, pp. 10 197–10 204.DOI
  33. [33]A. Rao, H. Choset, and D. Wettergreen, “Wavelet-Based Distributed Coverage for Heterogeneous Agents,” in 2025 IEEE International Conference on Robotics and Automation (ICRA), 2025, pp. 6630–6637.DOI
  34. [34]J. Ott, E. Balaban, and M. J. Kochenderfer, “Sequential Bayesian Optimization for Adaptive Informative Path Planning with Multimodal Sensing,” in 2023 IEEE International Conference on Robotics and Automation (ICRA), 2023, pp. 7894–7901.arxiv.org/abs/2209.07660
  35. [35]S. Manjanna and G. Dudek, “Data-driven selective sampling for marine vehicles using multi-scale paths,” in 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017.DOI
  36. [36]J. Ruckin, L. Jin, and M. Popović, “Adaptive Informative Path Planning Using Deep Reinforcement Learning for UAV-based Active Sensing,” in 2022 International Conference on Robotics and Automation (ICRA), 2022, pp. 4473–4479.arxiv.org/abs/2109.13570
  37. [37]N. Karapetyan, J. Moulton, J. S. Lewis, A. Q. Li, J. M. O’Kane, and I. M. Rekleitis, “Multi-robot Dubins Coverage with Autonomous Surface Vehicles,” 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 2373–2379, 2018.DOI
  38. [38]S. Agarwal and S. Akella, “Area Coverage With Multiple Capacity-Constrained Robots,” IEEE Robotics and Automation Letters, vol. 7, no. 2, pp. 3734–3741, 2022.DOI
  39. [39]H. González-Baños and J.-C. Latombe, “A Randomized Art-Gallery Algorithm for Sensor Placement,” in Proceedings of the Seventeenth Annual Symposium on Computational Geometry, New York, NY, USA, 2001, p. 232–240.
  40. [40]M. Schwager, M. P. Vitus, S. Powers, D. Rus, and C. J. Tomlin, “Robust Adaptive Coverage Control for Robotic Sensor Networks,” IEEE Transactions on Control of Network Systems, vol. 4, no. 3, 2017.
  41. [41]A. Bouman, J. Ott, S.-K. Kim, K. Chen, M. J. Kochenderfer, B. Lopez, A.-a. Agha-mohammadi, and J. Burdick, “Adaptive Coverage Path Planning for Efficient Exploration of Unknown Environments,” in 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2022, pp. 11 916–11 923.arxiv.org/abs/2302.03164
  42. [42]M. G. Jadidi, J. V. Miro, and G. Dissanayake, “Sampling-based incremental information gathering with applications to robotic exploration and environmental monitoring,” The International Journal of Robotics Research, vol. 38, no. 6, pp. 658–685, 2019.DOI
  43. [43]T. Karvonen, S. Särkkä, and K. Tanaka, “Kernel-based interpolation at approximate Fekete points,” Numerical Algorithms, vol. 87, no. 1, pp. 445–468, May 2021.arxiv.org/abs/1912.07316
  44. [44]J. Wakulicz, K. M. Brian Lee, C. Yoo, T. Vidal-Calleja, and R. Fitch, “Informative Planning for Worst-Case Error Minimisation in Sparse Gaussian Process Regression,” in 2022 IEEE International Conference on Robotics and Automation (ICRA), 2022, pp. 11 066–11 072.DOI
  45. [45]J. Wagberg, D. Zachariah, T. Schon, and P. Stoica, “Prediction Performance After Learning in Gaussian Process Regression,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, vol. 54. PMLR, 20–22 Apr 2017, pp. 1264–1272.arxiv.org/abs/1606.03865
  46. [46]W. Chen, R. Khardon, and L. Liu, “AK: Attentive Kernel for Information Gathering,” in Proceedings of Robotics: Science and Systems, New York City, NY, USA, June 2022.arxiv.org/abs/2205.06426
  47. [47]N. Christofides, “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem,” Operations Research Forum, vol. 3, no. 1, p. 20, Mar 2022.DOI
  48. [48]G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions-I,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, Dec 1978.DOI
  49. [49]L. A. Wolsey, “An analysis of the greedy algorithm for the submodular set covering problem,” Combinatorica, vol. 2, pp. 385–393, 1982.
  50. [50]U. Feige, “A threshold of ln n for approximating set cover,” J. ACM, vol. 45, no. 4, p. 634–652, Jul. 1998.
  51. [51]I. Dinur and D. Steurer, “Analytical approach to parallel repetition,” in Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, ser. STOC ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 624–633.arxiv.org/abs/1305.1979
  52. [52]T. G. Farr, P. A. Rosen, E. Caro, R. Crippen, R. Duren, S. Hensley, M. Kobrick, M. Paller, E. Rodriguez, L. Roth et al., “The Shuttle Radar Topography Mission,” Reviews of geophysics, vol. 45, no. 2, 2007.
  53. [53]I. M. Rayas Fernández, C. E. Denniston, D. A. Caron, and G. S. Sukhatme, “Informative Path Planning to Estimate Quantiles for Environmental Analysis,” IEEE Robotics and Automation Letters, vol. 7, no. 4, pp. 10280–10287, 2022.

Paper details

vlnc:W_gtzq6z6y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents