PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.40297v1cs.RO

TL;DR

Independent viewpoint estimates can double-count observations along a path, while exact marginal-gain computation with voxel sets is costly. The paper uses GPU depth buffers to compute path-dependent marginal gain; it reports earlier 95% coverage in most evaluated planner-environment combinations and a 30% reduction in real-world coverage time.

  • Problem

    Exact path-dependent marginal gain is costly because it requires merging ancestor voxel sets, while independent estimates can count overlapping observations repeatedly.

    Source: §I · pp. 1–2

  • Method

    The method stores ancestor observations as depth buffers and evaluates candidate rays against them in depth-ordered, GPU-parallel tree levels.

    Source: §I · p. 2

  • Results

    30% lower real-world time to 95% coverage; marginal gain also reached 95% coverage earlier in five of six planner-environment combinations.

    Source: §VII · p. 8

  • Takeaways & Limitations

    The conclusion reports that the benefit increased with larger trees and remained effective for longer execution horizons.

    Source: §VII · p. 8

    In the multi-story environment, absolute gain reached E75 and E95 0.4 min faster with RH-NBVP; marginal gain cannot compensate for sampling-tree access limits.

    Source: C. Exploration Performance · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Sampling-based exploration scores candidate paths by information gain and traversal cost, but independent viewpoint estimates can double-count overlap along a path. This work introduces a GPU method for path-dependent marginal gain using depth buffers.

I. INTRODUCTION

  • Autonomous exploration requires repeated action selection under sensing, flight-time, and onboard-computation constraints, from search-and-rescue to large-scale environmental exploration..Source: §I · p. 1
  • Sampling-based planners build an RRT, rank branches using expected visible unknown volume and traversal cost, then execute the first segment of the best branch.Examples include RH-NBVP and AEP.Source: §I · p. 1
  • Independent viewpoint estimates can count the same unknown regions repeatedly, overestimating path information and potentially changing candidate-branch rankings.Exact marginal gain requires merging ancestor voxel hash maps, which scales poorly with branch depth and map resolution.Source: §I · pp. 1–2
  • Depth buffers store ancestor observations, letting candidate rays identify and exclude overlap instead of merging visible-voxel sets.The method evaluates the tree in depth order, parallelizing nodes and rays at each level while preserving dependencies between ancestor observations and optimized yaws.Source: §I · p. 2
  • The evaluation compares gain accuracy and computation time with exact voxel-hash-map marginal gain, tests RH-NBVP and AEP in simulation, and validates the system onboard a UAV.The method’s stated contributions include GPU-accelerated path-dependent gain and depth-ordered tree evaluation.Source: §I · p. 2

II. RELATED WORK

Prior exploration planners include frontier-based, hybrid, and sampling-based approaches. This work builds on sampling-based planning and addresses the cost and ordering constraints of path-dependent gain evaluation.

II. RELATED WORK

  • Frontier-based methods target free–unknown boundaries, while hybrid methods combine local viewpoint selection with global guidance; FUEL orders frontier targets using an asymmetric traveling-salesperson solution.Reference [11] extends global planning by decomposing connected regions and computing coverage paths.Source: §II · p. 2
  • Sampling-based planners construct trees of candidate viewpoints; RH-NBVP executes the first segment of the highest-scoring branch, and AEP adds a global frontier planner for low-information regions.Other approaches maintain an RRT* [6] or account for feasibility and kinodynamics,.Source: §II · p. 2
  • Existing gain evaluation raycasts occupancy or TSDF maps, and often subsamples rays while treating viewpoints as independent –.GPU evaluation of independent candidates permits parallel processing, whereas marginal gain creates dependencies on prior observations and selected yaws.Source: §II · p. 2
  • ERRT computes trajectory marginal gain with volumetric queries, limiting cost by sparsifying evaluated states or using coarser octree depths.This omits gain at intermediate states; the proposed approach instead changes the representation of prior observations and exploits GPU parallelism while retaining path dependencies.Source: §II · p. 2

A. Exploration as Sequential Next-Best-View Selection

  • Exploration is posed as online, receding-horizon mapping of an initially unknown static 3D environment using a UAV depth camera.At each iteration, the planner builds a tree rooted at the UAV state, with collision-free edges and nodes holding candidate viewpoints, yaw, gain, traversal cost, and path objective.Source: A. Exploration as Sequential… · pp. 2–3

B. Information Gain Formulations

Absolute gain evaluates viewpoints independently, while marginal gain conditions each node on its ancestors. Candidate paths are then ranked using information gain and traversal cost.

B. Information Gain Formulations

  • Absolute gain is the visible unknown-voxel volume at a viewpoint, and its independent yaw optimization ignores overlap with preceding viewpoints.Repeatedly counting shared unknown voxels can overestimate accumulated path gain and alter path rankings.Source: B. Information Gain Formulations · p. 3
  • Marginal gain conditions a node on observations from all preceding nodes in its path, represented by its ancestor set.Its yaw and gain depend on ancestor observations and selected yaws.Source: B. Information Gain Formulations · p. 3
  • Marginal-gain nodes must be evaluated in tree-depth order because their gains and optimized yaws depend on ancestors.Marginal gain is no greater than absolute gain for a node.Source: B. Information Gain Formulations · p. 3

C. Cost and Objective Formulation

  • The path objective combines information gain with cumulative traversal cost.The cumulative cost corresponds to traveled distance along the path.Source: C. Cost and Objective Formulation · p. 3
  • The CPU manages geometric planning and mapping, while the GPU evaluates candidate nodes and rays by tree depth and stores depth buffers for descendants..Source: Figure 2 · p. 3
  • The exponentially decaying objective penalizes traversal cost, favoring informative paths while reducing the contribution of viewpoints farther from the tree root.The penalizing coefficient is λ > 0.Source: C. Cost and Objective Formulation · p. 3

IV. PROPOSED APPROACH

The method evaluates path-dependent marginal gain on the GPU by representing ancestor observations as depth buffers and checking candidate-ray overlap. The CPU builds and scores the planning tree, while the GPU evaluates information gain, optimizes yaw, and processes tree levels in order.

IV. PROPOSED APPROACH

  • The CPU builds the tree and handles planning logic, while the GPU stores ancestor observations as depth buffers, checks overlap with candidate observations, optimizes yaw, and computes gain.The tree is processed sequentially by depth level, with nodes and rays within each level evaluated in parallel.Source: §IV · p. 3

A. Depth Buffer Representation of Viewpoint Observations

  • Each node’s depth buffer stores the camera-frame z-depth of the first occupied voxel along each ray, or the maximum-range endpoint when no occupied voxel is hit.Free and unknown voxels do not terminate the ray.Source: A. Depth Buffer Representation of… · p. 3
  • Figure 3 shows ancestor depth buffers used to identify already observed ray segments and distinguish them from newly visible segments.Once a viewpoint’s yaw is selected, its depth buffer remains on the GPU for evaluating descendants.Source: Figure 3 · p. 4, A. Depth Buffer Representation of… · p. 4

B. Marginal Information Gain Evaluation

Candidate rays are projected into ancestor depth buffers to identify portions already observed along the path. The method merges overlap intervals across ancestors, then raycasts only the remaining segments for marginal gain.

B. Marginal Information Gain Evaluation

  • For marginal gain, each candidate ray is projected into every ancestor’s depth buffer and compared with stored depths to identify overlap in screen space.The camera is modeled with a pinhole camera model for the comparison.Source: B. Marginal Information Gain Evaluation · p. 4
  • Each candidate segment is transformed and clipped in an ancestor camera frame, then projected onto its depth buffer; depth and image clipping keep the overlap check within the valid frustum.The clipping and buffer resolution keep projected-ray sample spacing no greater than voxel size, avoiding undersampling outside the sensing range or field of view.Source: B. Marginal Information Gain Evaluation · p. 4
  • The projected segment is traversed with a 2D DDA, using linear inverse-depth interpolation because depth is nonlinear in screen space.At each pixel, a segment is considered previously observed when its interpolated depth is no greater than the stored ancestor depth.Source: B. Marginal Information Gain Evaluation · p. 4
  • An ancestor can contribute multiple overlap intervals, which are merged sequentially across ancestors when intervals overlap.The 3D DDA traverses merged intervals without counting their voxels; unknown voxels outside them contribute, and occupied voxels terminate traversal.Source: B. Marginal Information Gain Evaluation · p. 4

C. Depth-Level Parallel Evaluation

Marginal gain and selected yaw depend on ancestors, so the GPU evaluates the tree in depth order while processing nodes and rays within each level in parallel.

C. Depth-Level Parallel Evaluation

  • A node’s gain and selected yaw depend on its ancestors, but nodes at the same depth cannot be ancestors of one another and can be evaluated independently once shallower levels are complete.The GPU evaluates all candidate yaws against ancestor depth buffers and selects the yaw maximizing gain.Source: C. Depth-Level Parallel Evaluation · p. 4
  • Evaluation is sequential across depth levels and parallel within each level, preserving ancestor ordering while exploiting GPU parallelism.After each level, the resulting gains and yaws are returned to the CPU.Source: C. Depth-Level Parallel Evaluation · p. 4

D. Integration with Exploration Planners

The CPU constructs and scores the complete candidate tree, while the GPU evaluates node gains in depth order. The depth-buffer and hash-map approaches have the same worst-case time complexity, but differ in space complexity.

D. Integration with Exploration Planners

  • The CPU builds and collision-checks the complete tree before GPU gain evaluation, then computes traversal costs and path objectives and selects the branch to execute.The method replaces per-node gain evaluation in RH-NBVP and AEP while leaving their other planning and replanning logic unchanged.Source: D. Integration with Exploration Planners · pp. 4–5

E. Computational Complexity

  • The depth-buffer and hash-map approaches have the same worst-case time complexity, but differ by a factor of O(v^-1 size) in space complexity; the hash-map approach also constructs merged ancestor maps.The hash-map implementation stores local observations and rebuilds the merged map when needed.Source: E. Computational Complexity · p. 5
  • The depth-buffer method checks independent candidate rays in parallel, with traversal local to each ray.Its stated time complexity is Tdepth = O(AnNrLD), where each ray is checked against the ancestor buffers.Source: E. Computational Complexity · p. 5

V. EXPERIMENTAL EVALUATION

The evaluation uses simulated UAV exploration across three environments and compares marginal with absolute gain in two planners. It also specifies the sensing setup, computing platforms, and coverage-based performance measures.

V. EXPERIMENTAL EVALUATION

  • Simulation uses the MRS UAV System and Gazebo within ROS Noetic, with a RealSense D435i depth camera and Voxblox mapping.The ESDF is used for collision checking, and candidate nodes maintain a minimum safety distance from occupied space.Source: §V · p. 5
  • Figure 4 plots mean information gain by branch depth and its ratio to exact marginal gain for the exact CPU hash map and proposed GPU depth-buffer methods, alongside gsp and gabs.The caption identifies the plotted curves but does not state their numerical outcomes.Source: Figure 4 · p. 5
  • Gain evaluation uses a 5 m sensor range, an 87° × 58° field of view, and a 10° camera pitch.The desktop system has an Intel Core i7-13700K CPU and NVIDIA GeForce RTX 5060; embedded performance is evaluated on a 16 GB Jetson Orin NX.Source: §V · p. 5
  • The proposed marginal gain is compared with absolute gain in RH-NBVP and AEP, keeping planner parameters and initial conditions fixed across 10 runs per condition.Absolute gain is also evaluated on the GPU; results are reported as mean ± standard deviation.Source: §V · p. 5
  • Exploration is evaluated in the school, large maze, and multi-story scenarios using coverage milestones, final coverage, path length, and average velocity.AEP termination time is reported because it self-terminates; RH-NBVP runs for a fixed mission duration.Source: §V · p. 5

A. Gain Evaluation Accuracy and Computation Time

The depth-buffer method closely tracks exact marginal gain while accelerating its computation, and marginal gain improves exploration outcomes as tree size varies. The evaluation also reports the accuracy validation conditions and the mechanisms behind planner-specific effects.

A. Gain Evaluation Accuracy and Computation Time

  • Using fixed yaw angles to evaluate the same viewpoints, GPU depth-buffer marginal gain achieves R2 = 0.9937 and a regression slope of 1.028 against the exact CPU hash-map reference across 166,440 node evaluations.Source: A. Gain Evaluation Accuracy and… · p. 5
  • At N = 10000, desktop marginal-gain evaluation drops from 16.30 s to 0.40 s at 0.2 m and from 181.57 s to 1.95 s at 0.1 m; Jetson speed-ups reach 28×.Across tree sizes, desktop speed-ups are 6–48× at 0.2 m and 12–118× at 0.1 m; Jetson speed-ups are 3–12× and 10–28×, respectively.Source: Table II · p. 6, A. Gain Evaluation Accuracy and… · p. 6
  • The proposed method overestimates exact marginal gain by 5–10%, while single-parent gsp and absolute-gain errors reach 2× and 2.6× the exact gain as branch depth increases.Depth interpolation accumulates approximation error along a beam.Source: A. Gain Evaluation Accuracy and… · p. 6

B. Effect of Tree Size

  • In the school environment, marginal gain reduces E95 for both planners; RH-NBVP benefits more as tree size grows, while AEP benefits even with the smallest tree.For AEP, removing overlap lets low-information branches fall below gzero sooner, prompting an earlier switch to its global planner; accounting for path overlap also improves waypoint selection and yields shorter paths and earlier termination across tree sizes.Source: B. Effect of Tree Size · p. 6, Table III · p. 6

C. Exploration Performance

Marginal gain improves exploration efficiency in most planner-environment combinations, while the effect varies with environment and execution horizon. Longer horizons reduce planning time but trade path efficiency for higher velocity, with similar time to 95% coverage.

C. Exploration Performance

  • AEP reaches every coverage milestone earlier with marginal gain in all three environments, and its advantage grows from E25 to E95.The E25-to-E95 improvement rises from 0.8 to 1.8 min in the school, 1.3 to 2.3 min in the large maze, and 0.2 to 1.1 min in the multi-story environment.Source: C. Exploration Performance · p. 6

D. Effect of Execution Horizon

  • In the large-maze horizon comparison, longer horizons reduce planning time and raise velocity while increasing path length, with E95 remaining similar.Marginal-gain planning time falls from 353 s at h = 1 to 105 s at h = 5; its L95 rises from 565 m to 635 m and 659 m, while absolute gain L95 rises from 635 m to 696 m and 743 m.Source: Table IV · p. 7, D. Effect of Execution Horizon · p. 7

C. Exploration Performance

  • AEP’s shorter paths in the school and multi-story environments accompany earlier termination, while the large-maze path remains similar despite a 2.3 min E95 improvement.Termination is 2.0 min earlier in the school and 0.5 min earlier in the other environments; average velocities are similar between formulations.Source: C. Exploration Performance · p. 7
  • RH-NBVP gains 3.8 min at E95 in the large maze, but marginal gain does not improve E95 in the multi-story environment.In the large maze, explored volume after 15 min rises from 58.8% to 75.0%; final coverage remains similar across formulations in all environments.Source: C. Exploration Performance · p. 7
  • In the multi-story environment, tighter layout and collision-distance constraints limit access to informative regions, which gain ranking alone cannot overcome.The passage attributes the exception to limitations in the sampling process; final coverage remains similar across gain formulations.Source: C. Exploration Performance · p. 7

D. Effect of Execution Horizon

  • Marginal gain retains its path-efficiency benefit at longer horizons: h = 3 and h = 5 achieve similar path efficiency to absolute gain at h = 1.At h = 3, E95 falls from 30.5 min to 26.0 min with comparable planning times of 151 s versus 156 s; h = 5 reaches 26.5 min and needs 24 m more than h = 3.Source: D. Effect of Execution Horizon · p. 7

VI. REAL-WORLD EXPERIMENTAL EVALUATION

Onboard UAV experiments show that marginal gain reaches 95% coverage sooner than absolute gain, alongside earlier termination and a shorter path. The conclusion also reports close agreement with exact marginal gain and earlier 95% coverage in five of six simulated planner-environment combinations.

VI. REAL-WORLD EXPERIMENTAL EVALUATION

  • The real-world system runs mapping, planning, and gain evaluation onboard an NVIDIA Jetson Orin NX during exploration in a 10×13×6 m patio environment.The UAV uses a RealSense D455, Pixhawk flight controller, Voxblox mapping, and RTK-GPS and IMU state estimation.Source: §VI · p. 7
  • 30% less time to 95% coverage: marginal gain reaches that milestone in 2.17±0.44 min versus 3.10±1.05 min with absolute gain onboard the UAV.Termination time falls from 4.58±0.46 to 4.04±0.34 min and path length from 108.5±11.2 to 101.4±7.0 m, while average velocity remains similar.Source: §VI · p. 7

VII. CONCLUSION

  • The depth-buffer method stays within 5–10% of exact marginal gain and achieves speed-ups of up to 118×.The exact comparison uses voxel hash maps.Source: §VII · p. 7
  • Across RH-NBVP and AEP, marginal gain reaches 95% coverage earlier in five of six simulated planner-environment combinations.The conclusion also reports earlier termination and a shorter path in the real-world UAV experiments.Source: §VII · p. 8
Loading 2609.40297v1…