PaperlayerView exact revision on arXiv

Source-linked AI summary

An Efficient Sampling-based Method for Online Informative Path Planning in Unknown Environments

Lukas Schmid, Michael Pantic, Raghav Khanna, Lionel Ott, Roland Siegwart, Juan Nieto

arXiv:1909.09548v2cs.ROcs.CV

TL;DR

Online informative path planning must handle unknown environments while avoiding local minima and respecting limited onboard computation. The paper introduces an RRT*-inspired planner that maintains and rewires a single trajectory tree with one objective function, and reports global coverage and improved exploration and TSDF reconstruction performance in simulation and real-MAV experiments.

  • Problem

    Online sampling-based planners can discard much of their tree, incur expensive gain computation, and select locally optimal paths that become sub-optimal or stuck.

  • Method

    The method continuously expands, updates, and rewires one trajectory tree, using a single utility objective plus TSDF reconstruction gain and cost formulations.

  • Results

    The approach achieves full observable-volume exploration in all maze runs after 25 minutes and outperforms state-of-the-art methods across exploration and TSDF reconstruction tasks.

  • Takeaways & Limitations

    A maintained global tree lets the planner retain future branches, reason about global path utility, and refine trajectories while executing online.

Abstract

from arXiv · show

The ability to plan informative paths online is essential to robot autonomy. In particular, sampling-based approaches are often used as they are capable of using arbitrary information gain formulations. However, they are prone to local minima, resulting in sub-optimal trajectories, and sometimes do not reach global coverage. In this paper, we present a new RRT*-inspired online informative path planning algorithm. Our method continuously expands a single tree of candidate trajectories and rewires segments to maintain the tree and refine intermediate trajectories. This allows the algorithm to achieve global coverage and maximize the utility of a path in a global context, using a single objective function. We demonstrate the algorithm's capabilities in the applications of autonomous indoor exploration as well as accurate Truncated Signed Distance Field (TSDF)-based 3D reconstruction on-board a Micro Aerial vehicle (MAV). We study the impact of commonly used information gain and cost formulations in these scenarios and propose a novel TSDF-based 3D reconstruction gain and cost-utility formulation. Detailed evaluation in realistic simulation environments show that our approach outperforms state of the art methods in these tasks. Experiments on a real MAV demonstrate the ability of our method to robustly plan in real-time, exploring an indoor environment solely with on-board sensing and computation. We make our framework available for future research.

I. INTRODUCTION

Online informative path planning must adapt to unknown environments, avoid local minima, and use limited onboard computation efficiently. The paper proposes an RRT*-inspired single-tree approach with new gain and utility formulations for exploration and 3D reconstruction.

  • Motivation: Sampling-based informative path planners support arbitrary map-derived information gains but can be computationally expensive and locally shortsighted.Volumetric gain evaluation can consume up to 95% of planner runtime, while limited look-ahead can produce sub-optimal paths or dead ends.
  • Contribution: The proposed algorithm continuously expands and rewires one trajectory tree, retaining non-executed branches while refining intermediate trajectories.This maintains global context during execution instead of repeatedly discarding most of the tree.
  • Applications and formulations: A single objective function combines path gain and cost across indoor exploration and TSDF-based 3D reconstruction applications.The paper studies common formulations and introduces a TSDF reconstruction gain plus a parameter-free cost-utility formulation.
  • Evaluation: The method is evaluated against existing planners in simulation and on a real MAV using onboard sensing and computation.The framework and associated simulation environments are released for future benchmarking and research.

II. RELATED WORK

Prior informative planning methods use frontier selection, receding-horizon sampling, or additional planning stages to escape local minima. The paper instead maintains one large tree that evaluates local and global path utility with a single objective.

  • Existing approaches: Frontier-based methods repeatedly select boundaries between known and unknown space to achieve complete exploration.They are primarily designed around exploration frontiers rather than arbitrary information-gain formulations.
  • Existing approaches: Sampling-based alternatives include motion-primitive trees, receding-horizon viewpoint trees, history-based reseeding, and hybrid frontier planners.These methods address local exploration and local-minimum avoidance through different additional mechanisms.
  • Surface reconstruction: Specialized surface methods reduce viewpoint sampling around available surfaces and may target low-confidence TSDF regions.The cited surface-quality approach uses TSDF weights but provides no metric accuracy analysis and constant update weights may not reflect quality.
  • Paper's distinction: Many prior methods add a second planning stage to escape local minima, requiring operation-mode switches and relying on frontiers that may not suit arbitrary gains.The proposed alternative expands a single large tree to consider both local and global path utility.
  • Paper's distinction: The planner overview shows tree expansion during execution, followed by map updating and rewiring of non-executed nodes.This preserves useful future branches as the robot's map changes.

III. PROPOSED ALGORITHM

The proposed planner continuously expands, executes, updates, and improves a single trajectory tree. Each node stores trajectory, gain, cost, and value information, enabling application-specific utility selection and efficient updates.

  • Tree execution: The tree expands until the current node finishes, then requests the best adjacent trajectory and updates the tree with an adaptive horizon.Because the look-ahead remains alive, the next node can be requested immediately.
  • Tree structure: Each tree node stores an associated trajectory, gain, cost, and value, while connectivity links nodes into a rooted tree at the robot's current position.This representation separates trajectory candidates from their utility components.
  • Utility model: The gain may depend on the trajectory endpoint, cost must be intrinsic to the node, and value fuses cached gains and costs into total utility.These conditions allow different application-specific objective functions while supporting cached updates.
  • Utility model: Next-node selection considers all nodes and chooses the one whose sub-tree contains the highest value.Any gain, cost, and value definitions satisfying the stated conditions are admissible.

B. Tree Expansion

The tree expands through local or global viewpoint sampling, RRT*-style parent selection, and rewiring. TSDF reconstruction gains emphasize the impact of views on observed surfaces and nearby unknown voxels.

  • Tree Expansion: A two-stage sampler uses local viewpoints when nearby coverage is insufficient and otherwise samples a global viewpoint.Local sampling uses radius rlocal and threshold nlocal to support coverage and reachability.
  • Tree Expansion: RRT*-style insertion tests nearby nodes as parents and rewires neighbors when the resulting value improves.The viewpoint is connected to candidate nodes within lmax rather than only the nearest node.
  • Tree Updating: After execution, the new node becomes the root, non-executed branches are preserved through rewiring, and changed gains are updated near the robot.A breadth-first rewiring step re-optimizes the tree after gain updates.
  • TSDF-based 3D Reconstruction Gain: The reconstruction formulation addresses combining general gains and costs into total utility with a parameter-free efficiency-inspired value.The formulation is introduced for accurate TSDF-based reconstruction under sensing and state-estimation uncertainty.
  • TSDF-based 3D Reconstruction Gain: The TSDF gain evaluates view impact on observed surfaces and unknown voxels near surfaces, combining new-area discovery with improvement of mapped voxels.Low-impact voxels are excluded using ηmin, and visible voxels are aggregated for the viewpoint.

B. Global Normalization Value

The method replaces tuned gain-cost penalties with a globally normalized efficiency measure. This accounts for each node’s subtree and its connection to the tree root rather than optimizing nodes greedily.

  • Global Normalization Value: Expected execution time t is used as the cost of node Vi because tasks often need to be completed quickly.
  • Global Normalization Value: Exponential and linear value formulations can favor long sub-trees or require careful tuning of λ and α.The exponential formulation is strictly increasing, which can favor sub-optimal subsequently executed nodes.
  • Global Normalization Value: The global normalization value uses accumulated gain per cost while accounting for each node’s global tree context instead of greedily maximizing local efficiency.The tree originating at Vi is subtree(Vi), while R(Vi) connects Vi to the root.

V. IMPLEMENTATION DETAILS

The implementation uses a modular active 3D planning framework with Voxblox mapping, yaw optimization, and 30° yaw sections for viewpoint gain computation.

  • Implementation: The framework uses Voxblox for mapping, while other TSDF implementations are also supported.
  • Implementation: Yaw optimization divides the full yaw spectrum into 30° sections and computes gain for each section.The yaw maximizing total gain is selected.

A. Iterative Ray Casting

Iterative ray casting accelerates viewpoint-gain evaluation by avoiding redundant voxel checks while preserving voxel detection. Relative node values remove the need for further compensation after subsampling.

  • Iterative Ray Casting: Iterative ray casting reduces redundant voxel checks by starting subsequent rays only where their lateral distance from previous rays is one voxel size s.The method still detects all voxels and produced an additional 233% computation speedup in the experiments.
  • Iterative Ray Casting: The initial ray spacing is reduced to match voxel size s at maximum ray length, and traversed voxels are accumulated in a visible-voxel set.
  • Iterative Ray Casting: With sub-sampling factor fsub, detected voxel density per volume and surface decreases proportional to fsub^2, while relative-value selection requires no compensation.

VI. SIMULATION ENVIRONMENT

The simulation evaluates online informative path planning in realistic MAV environments, with sensing and state-estimation uncertainty and standardized planner constraints.

  • Simulation setup: The simulator combines photo-realistic Unreal Engine scenes with ROS-based MAV behavior and Gaussian depth noise scaled quadratically with depth.The simulated depth measurement follows zsim = z + N(µ(z), σ(z)), with µ(z) = σ(z) = 0.0024z^2.
  • Simulation setup: State-estimation uncertainty is modeled as a bounded random walk with position error within 5 cm and bounded attitude errors.Roll and pitch vary within ±1.5°, while yaw varies within ±5°.
  • Simulation scenarios: Exploration uses a 40 m×40 m×3 m maze, while reconstruction uses a 40 m×40 m×12 m urban environment with occlusions, narrow passages, and filigree geometry.The simulator and scenarios are released for benchmarking and future research.
  • Evaluation protocol: The proposed method is compared with RH-NBVP and AEP under identical system constraints, tree edge lengths, and TSDF update weights.Additional parameters for the proposed method are listed separately.
  • Evaluation protocol: Performance is measured by exploration ratio and average reconstruction error, with experiments repeated because planner behavior is stochastic.Exploration ratio measures observed environmental percentage, whereas reconstruction error measures average deviation from ground truth.

A. Volumetric Indoor Exploration

In volumetric exploration, the proposed planner achieves complete observable-map coverage while maintaining efficient, smoother trajectories. Compared with competing planners, it explores more effectively within similar time and travel budgets.

  • Exploration performance: The proposed method achieves full exploration of the observable maze volume after 25 minutes in every run.This result is reported despite different paths being taken across experiments.
  • Exploration performance: 330 m versus AEP’s 297 m and RH-NBVP’s 210 m, while RH-NBVP covers only 60% of the environment.RH-NBVP also experiences long computation times in dead ends, on-the-spot turning, and frequent exploration-site changes.
  • Trajectory behavior: Maintaining and refining the trajectory tree gives the proposed method access to more and higher-quality paths than rebuilding a tree at every iteration.The figure caption links this refinement to less jagged paths and a larger explored area at similar time and distance.
  • Evaluation view: The exploration-progress figure reports results for both the maze and building environments, with means and standard deviations over 10 experiments.The same figure also reports average reconstruction error for the building environment.
  • 3D reconstruction: In building reconstruction, the proposed method fully explores the building within 20 minutes in all experiments, whereas competing methods leave unexplored holes.The proposed gain first emphasizes global surfaces, then focuses on low-map-weight regions to reduce reconstruction error and its maximum peaks.

C. Importance of Sampling and Gain Formulation

The ablation studies show that retaining and refining a global tree improves coverage and exploration speed, while gain, cost, and value formulations strongly affect reconstruction quality.

  • C. Importance of Sampling and Gain Formulation: The ablation is summarized in Table III as a city-environment study of the proposed method’s component combinations.The table organizes the comparison around different sampling, tree-maintenance, and gain choices.
  • C. Importance of Sampling and Gain Formulation: Retaining the exploration tree significantly improves global coverage, while RRT* rewiring improves exploration speed and reconstruction quality under identical gains.The ablation compares RRT and RRT* sampling with both unknown-volume and proposed reconstruction gains.
  • C. Importance of Sampling and Gain Formulation: The proposed grec gain outperforms the simpler guv gain independently of the sampling method used.The strongest results come from combining tree retention, continuous RRT*-style refinement, and the novel gain formulation.
  • D. Gain and Value Formulation: Volumetric gains depend heavily on a carefully chosen region of interest, although exploration times remain comparable across gain formulations.The proposed gain quickly explores the building and then refines areas of high uncertainty, obtaining the lowest final reconstruction error.
  • D. Gain and Value Formulation: The gain comparison evaluates voxel impact, unknown-voxel count, surface frontiers, and confidence voxels using fixed cost and value functions.Results are reported as means and standard deviations over 10 experiments.
  • D. Gain and Value Formulation: The proposed value function is compared with linear execution-time and exponential accumulated-path-length penalties while using the proposed voxel-impact gain.The comparison uses α = 3.0 and λ = 0.5.
  • D. Gain and Value Formulation: Neither alternative penalty reliably reconstructs the building because both favor low-cost but sub-optimal viewpoints.The linear penalty increases error by 39% relative to the proposed method and requires parameter tuning for potential improvement.

E. Robot Experiment

A real-MAV deployment demonstrates that the proposed planner can operate with onboard sensing and computation while producing broader, hole-free reconstructions. After three minutes, it yields straighter walls and covers more of the environment than the comparison.

  • Real-MAV deployment: After 3 minutes of flight, the proposed method traverses a larger part of the environment and reconstructs it without holes and with straight walls.The real MAV uses a Realsense D435 sensor and the same parameters as the simulation experiments.
  • Real-MAV deployment: The real-MAV experiment compares the proposed method with RH-NBVP using Vicon state information to remove compounding state-estimation drift.The comparison includes both trajectories and final reconstructed scenes.
  • Conclusion: The paper concludes that the method demonstrates robustness and real-time capabilities on a real MAV and is released for adaptation and future research.The conclusion also reports applications to volumetric exploration and TSDF-based 3D reconstruction.
Loading 1909.09548v2…