GPU-Accelerated Path-Dependent Marginal Information Gain for Autonomous Exploration

João Félix Mendes; Rodrigo Ventura; Meysam Basiri

cs.ROSep 30, 2026

GPU-Accelerated Path-Dependent Marginal Information Gain for Autonomous Exploration

Authors: João Félix Mendes, Rodrigo Ventura, Meysam Basiri

Organizations: Institute for Systems and Robotics, Department of Electrical and Computer Engineering, Instituto Superior Técnico, Lisboa, Portugal

Abstract

Autonomous exploration demands that robots continuously evaluate candidate viewpoints based on their expected information gain and execution cost. Sampling-based planners estimate this gain by volumetric raycasting and, due to its computational cost, evaluate candidates under an assumption of mutual independence, ignoring the overlap between viewpoints along the same path. This work presents a GPU-accelerated method for computing path-dependent marginal information gain, where instead of storing and merging the observed unknown voxels along each candidate path, previous observations are represented using depth buffers. Candidate rays are projected into the depth buffers of their ancestors to identify observation overlap and exclude regions expected to be observed. The planning tree is evaluated in depth order to maintain the dependency between viewpoints and their optimized yaws, while candidate nodes and rays at each level are processed in parallel on the GPU. The proposed method stays within 5-10% of the exact marginal gain computed using voxel hash maps, with speed-ups of up to 118x on a desktop GPU and 28x on an NVIDIA Jetson Orin NX. The method was integrated into two sampling-based exploration planners and evaluated in three simulation environments, where marginal gain reduced the time to 95% coverage in five of the six evaluated planner-environment combinations. Real-world experiments also showed a 30% reduction in the time to 95% coverage, as well as earlier exploration termination times.

Figures & tables

Panel of Figure 1 — Fig. 1: Reconstruction of the Patio environment after $150$ s using AEP with absolute gain (a) and marginal gain (b).

Fig. 2: System architecture of the proposed framework. The CPU manages geometric planning and mapping, while the GPU evaluates the candidate tree in depth order, parallelizing nodes and rays within each depth level and storing the resulting depth buffers for descendant evaluation.

Fig. 3: Marginal gain calculation using depth buffers in 2D. Top left: candidate branch of the planning tree shown by the black path, with the candidate viewpoint in orange, its ancestors in blue, and their fields of view. Top right: depth buffer of an ancestor viewpoint, where each ray stores the camera-frame

z

-depth of the first occupied voxel. Bottom left: depth buffers of the ancestor viewpoints and the projected raycast of the candidate viewpoint. Bottom right: projection of the candidate rays into the ancestor depth buffers, identifying observed segments (red) and newly visible segments (green).

Parameter	School	Large maze	Multi-story
Size [ $\text{\,}\mathrm{m}$ ]	$50{\times}35{\times}20$	$50{\times}50{\times}3$	$24{\times}22{\times}6$
$v_{\mathrm{size}}$ [ $\text{\,}\mathrm{m}$ ]	0.2	0.1	0.1
Step size [ $\text{\,}\mathrm{m}$ ]	2.0	1.5	1.0
$N_{\max}$	250	250	400
$N_{\mathrm{termination}}$	500	1000	1600
$d_{\mathrm{collision}}$ [ $\text{\,}\mathrm{m}$ ]	1.5	0.8	0.5

TABLE I: Main simulation parameters.

Panel of Figure 5 — Fig. 4: Mean information gain as a function of branch depth (a), and its ratio to the exact marginal gain (b). Curves show $g_{\mathrm{all}}$ from the exact CPU hash map implementation and the proposed GPU depth buffer method, with $g_{\mathrm{sp}}$ and $g_{\mathrm{abs}}$ .

		Desktop					Jetson Orin NX
		Absolute		Marginal			Absolute		Marginal
$\boldsymbol{v_{\mathrm{size}}}$	$\boldsymbol{N}$	CPU	GPU	CPU	GPU	Speed-up	CPU	GPU	CPU	GPU	Speed-up
$0.2\text{\,}\mathrm{m}$	50	40.6	0.8	57.7	9.2	$\times 6$	65.0	3.1	183.6	53.1	$\times 3$
	100	88.6	0.6	201.9	26.9	$\times 8$	112.1	5.4	189.4	61.5	$\times 3$
	500	491.2	1.9	1097.4	46.5	$\times 24$	570.5	24.4	866.5	138.5	$\times 6$
	1000	921.7	3.6	2945.5	70.6	$\times 42$	1197.0	49.2	3145.6	259.9	$\times 12$

TABLE II: Gain evaluation time per replanning iteration [ms], averaged over 10 iterations. Speed-up is the CPU/GPU marginal gain ratio. The resolution factor is the mean increase in evaluation time when reducing

v_{\mathrm{size}}

from

0.2\text{\,}\mathrm{m}

0.1\text{\,}\mathrm{m}

			$\boldsymbol{N_{\max}}$
Planner	Metric	Gain	50	250	500
RH- NBVP	$E_{95}$ [min]	A	$20.6{\pm}3.5$	$21.6{\pm}1.9$	$23.8{\pm}1.9$
	$E_{95}$ [min]	M	$\mathbf{20.3{\pm}2.4}$	$\mathbf{20.9{\pm}2.7}$	$\mathbf{21.6{\pm}2.5}$
	$L$ [m]	A	$1010{\pm}3$	$\mathbf{913{\pm}6}$	$\mathbf{806{\pm}20}$
	$L$ [m]	M	$\mathbf{1007{\pm}5}$	$935{\pm}8$	$877{\pm}7$
	$\bar{v}$ [m/s]	A	$0.56{\pm}0.01$	$0.50{\pm}0.01$	$0.45{\pm}0.01$

TABLE III: Effect of tree size in the school environment. A/M denote absolute and marginal gain.

Panel of Figure 8 — Fig. 5: Comparison of remaining unexplored volume obtained with RH-NBVP and AEP using absolute and marginal gain in school (a), large maze (b), and multi-story (c) environments.

Panel of Figure 9 — Fig. 6: Large-maze reconstruction after $15$ min with RH-NBVP using absolute (a) and marginal gain (b).

$\boldsymbol{h}$	Gain	$\boldsymbol{E_{95}}$ [min]	$\boldsymbol{L_{95}}$ [m]	$\boldsymbol{\bar{v}_{95}}$ [m/s]	$\boldsymbol{T_{\mathrm{plan}}}$ [s]
1	A	$30.5{\pm}3.7$	$635{\pm}79$	$0.35{\pm}0.01$	$\mathbf{156{\pm}2}$
1	M	$\mathbf{26.7{\pm}2.6}$	$\mathbf{565{\pm}60}$	$0.35{\pm}0.01$	$353{\pm}6$
3	A	$28.9{\pm}2.8$	$696{\pm}77$	$0.40{\pm}0.01$	$\mathbf{69{\pm}4}$
3	M	$\mathbf{26.0{\pm}1.5}$	$\mathbf{635{\pm}39}$	$\mathbf{0.41{\pm}0.01}$	$151{\pm}6$
5	A	$30.1{\pm}5.7$	$743{\pm}152$	$0.41{\pm}0.01$	$\mathbf{55{\pm}4}$
5	M	$\mathbf{26.5{\pm}1.8}$	$\mathbf{659{\pm}46}$	$\mathbf{0.42{\pm}0.01}$	$105{\pm}9$

TABLE IV: Effect of the execution horizon in the large maze. A/M denote absolute and marginal gain.

Explore similar work

Feb 12, 2026cs.RO

Schur-MI: Fast Mutual Information for Robotic Information Gathering

Mutual information (MI) is a principled and widely used objective for robotic information gathering (RIG), providing strong theoretical guarantees for sensor placement (SP) and informative path planning (IPP). However, its high computational cost - dominated by repeated log-determinant evaluations - has limited its use in real-time planning. This paper presents Schur-MI, a Gaussian process (GP) MI formulation that (i) leverages the iterative structure of RIG to precompute and reuse expensive intermediate quantities across planning steps, and (ii) uses a Schur-complement factorization to avoid large determinant computations. Together, these methods reduce the per-evaluation cost of MI from

\mathcal{O}(|\mathcal{V}|^3)

\mathcal{O}(|\mathcal{A}|^3)

, where

\mathcal{V}

and

\mathcal{A}

denote the candidate and selected sensing locations, respectively. Experiments on real-world bathymetry datasets show that Schur-MI achieves up to a

12.7\times

speedup over the standard MI formulation. Field trials with an autonomous surface vehicle (ASV) performing adaptive IPP further demonstrate the method's practicality. By making MI computation tractable for online planning, Schur-MI helps bridge the gap between information-theoretic objectives and real-time robotic exploration. Our code is available at: www.sgp-tools.com

Kalvik Jakkala, Jason O'Kane, Srinivas Akella

Texas A&M University · University of North Carolina at Charlotte

Path Planning Mutual Information Autonomous Surface Vehicles Geometric Bathymetric Data Information-Theoretic Limits Gaussian Process

Ask PDF

May 25, 2026cs.RO

OPAL: Omnidirectional Path-efficient Aerial 3D expLoration

Autonomous exploration is critical for robot mapping unknown environments. Desirable characteristics of exploration algorithms include compute efficiency and small traversed distance during the exploration process. Motivated by these, we present Omnidirectional Path-efficient Aerial 3D expLoration (OPAL), an exploration framework centered on deliberate 360-degree yaw rotation at ambiguous branch points rather than compute-heavy global tour planning. We devise multiple variants of OPAL to determine the frontier-selection strategy once the yaw pan is completed. One variant is model-free, while others use large language models (LLMs) or vision-language models (VLMs). We characterize the performance of these variants while varying the vicinity search radius to include frontiers in the selection process. Through simulations we find that although the time-consuming in-place yaw rotation increases total exploration time relative to more computationally complex baselines such as EDEN and FALCON, OPAL is computationally simpler and achieves shorter travel distances and higher coverage-versus-distance area under the curve. We also show that adjusting the frontier-selection search radius enables a tradeoff between travel distance and total exploration time. We verify our results on a Modal AI drone in two indoor environments by comparing OPAL against FALCON, and find that the traveled distance for a variant of OPAL to be as much as 25% lower than FALCON.

Yoga Satwik Chappidi, Avideh Zakhor

Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA, USA.

Exploration Path Planning Autonomous Drones

Ask PDF

Apr 21, 2026cs.RO

Multi-Step Gaussian Process Propagation for Adaptive Path Planning

Efficient and robust path planning hinges on combining all accessible information sources. In particular, the task of path planning for robotic environmental exploration and monitoring depends highly on the current belief of the world. To capture the uncertainty in the belief, we present a Gaussian process based path planning method that adapts to multi-modal environmental sensing data and incorporates state and input constraints. To solve the path planning problem, we optimize over future waypoints in a receding horizon fashion, and our cost is thus a function of the Gaussian process posterior over all these waypoints. We demonstrate this method, dubbed OLAhGP, on an autonomous surface vessel using oceanic algal bloom data from both a high-fidelity model and in-situ sensing data in a monitoring scenario. Our simulated and experimental results demonstrate significant improvement over existing methods. With the same number of samples, our method generates more informative paths and achieves greater accuracy in identifying algal blooms in chlorophyll a rich waters, measured with respect to total misclassification probability and binary misclassification rate over the domain of interest.

Alex Beaudin, Bjørn Andreas Kristiansen, Kristoffer Gryte +4

Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720, USA · Department of Engineering Cybernetics, Norwegian University of Science and Technology (NTNU), NO-7491, Norway · Department of Electronic Systems, Norwegian University of Science and Technology (NTNU), NO-7491, Norway

Gaussian Process Path Planning Robot Navigation

Ask PDF