PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Frontier-based Information-driven Autonomous Exploration with an MAV

Anna Dai, Sotiris Papatheodorou, Nils Funk, Dimos Tzoumanikas, Stefan Leutenegger

arXiv:2002.04440v2cs.RO

TL;DR

Fast, onboard exploration of unknown environments is important for autonomous MAV operation, so this paper combines frontier-based and sampling-based planning with efficient octree mapping and sparse-raycast utility evaluation. Simulations and a real-world experiment show faster, computationally cheaper exploration and real-time onboard feasibility.

  • Problem

    Autonomous MAV exploration must map unknown environments efficiently onboard while handling online path planning, collision avoidance, and exploration planning.

  • Method

    The planner samples candidate views from map frontiers and evaluates entropy-versus-travel-time utility using octree grouping and sparse raycasting.

  • Results

    The proposed strategy improves exploration speed and computational cost over state-of-the-art methods, while running in real time onboard an MAV.

  • Takeaways & Limitations

    The experiments demonstrate that the hybrid planner is feasible for real-world, real-time autonomous MAV exploration.

Abstract

from arXiv · show

Exploration and collision-free navigation through an unknown environment is a fundamental task for autonomous robots. In this paper, a novel exploration strategy for Micro Aerial Vehicles (MAVs) is presented. The goal of the exploration strategy is the reduction of map entropy regarding occupancy probabilities, which is reflected in a utility function to be maximised. We achieve fast and efficient exploration performance with tight integration between our octree-based occupancy mapping approach, frontier extraction, and motion planning-as a hybrid between frontier-based and sampling-based exploration methods. The computationally expensive frontier clustering employed in classic frontier-based exploration is avoided by exploiting the implicit grouping of frontier voxels in the underlying octree map representation. Candidate next-views are sampled from the map frontiers and are evaluated using a utility function combining map entropy and travel time, where the former is computed efficiently using sparse raycasting. These optimisations along with the targeted exploration of frontier-based methods result in a fast and computationally efficient exploration planner. The proposed method is evaluated using both simulated and real-world experiments, demonstrating clear advantages over state-of-the-art approaches.

I. INTRODUCTION

The paper presents a lightweight exploration strategy designed for real-time onboard operation on MAVs. It combines targeted frontier sampling with octree-based grouping and sparse raycasting to reduce computational cost.

  • Motivation: MAV exploration must be fast, lightweight, and thorough for safe operation in applications including mining, inspection, agriculture, and search and rescue.MAV agility and speed make them well suited to mapping 3D environments, while onboard execution constrains computational resources.
  • Contribution: The proposed exploration strategy achieves real-time performance onboard an MAV.
  • Contributions: Frontier-based and sampling-based exploration are combined by sampling candidate next-views from map frontiers, focusing exploration with fewer candidates.Targeted frontier sampling retains focused exploration while avoiding the larger candidate sets typical of sampling-based methods.
  • Contributions: Frontier voxel clustering is avoided by treating voxels in the same octree octant as a cluster through implicit voxel grouping.This removes a computationally expensive step used in classical frontier-based exploration.
  • Contributions: Sparse raycasting replaces expected sensor-measurement map updates because only relative candidate ranking is required for faster map-entropy estimation.The method avoids the computational cost of conventional information-theoretic map updates.

II. RELATED WORK · III. PROBLEM STATEMENT

Related work organizes autonomous exploration around map-entropy or unknown-volume utilities implemented through sampling-based or frontier-based strategies. The paper frames online MAV exploration as efficient occupancy mapping and navigation in unknown space, with an iterative strategy tightly coupled to volumetric mapping.

  • II. RELATED WORK: Autonomous exploration utilities primarily measure either map entropy or unknown volume, supporting sampling-based and frontier-based strategies.
  • II. RELATED WORK: Frontier-based methods range from selecting the closest frontier to maintaining MAV velocity, tracking visited topological nodes, and autonomous inspection.
  • II. RELATED WORK: Sampling-based exploration samples poses that can map unknown volume, avoiding map-wide frontier computation but requiring evaluation of each sample.
  • II. RELATED WORK: The 3D Next-Best-View method, grows an RRT to sample a free-space position and yaw angle.
  • II. RELATED WORK: Entropy-driven exploration commonly uses Shannon entropy,,, with related work combining Shannon and Renyi entropy or reducing planning complexity through 2D motion planning.
  • II. RELATED WORK: Unknown-volume metrics estimate unseen space in the view frustum by ray casting and have been used in,,,,.
  • III. PROBLEM STATEMENT: Autonomous exploration seeks to update occupancy probabilities and map observable space despite unobservable regions, while path planning, collision avoidance, and exploration must run online onboard.
  • III. PROBLEM STATEMENT: The paper proposes an iterative MAV exploration strategy using a depth sensor and volumetric map, tightly coupled to the underlying map representation.

IV. FRONTIER-BASED INFORMATION-DRIVEN EXPLORATION ALGORITHM

The algorithm combines frontier-based focus with sampling-based planning by sampling candidate views directly from frontier voxels, avoiding explicit frontier clustering. A continuously running mapping server supports iterative collision-free path planning and utility-based selection of the next pose.

  • Algorithm overview: The planner samples candidate next-views directly from frontier voxels, combining frontier-based focus with sampling-based exploration while avoiding computationally expensive voxel clustering.Frontiers identify regions requiring exploration, while direct sampling removes the need to cluster individual frontier voxels into larger frontiers.
  • Mapping and replanning: An occupancy mapping server continuously integrates depth images with pose data, updates the map, and extracts frontiers while the exploration planner is invoked repeatedly.Planning begins at exploration startup and resumes after measurements have been integrated into the map.
  • Planning pipeline: Each planning iteration samples frontier-based candidate positions, plans collision-free paths, assigns yaw angles, evaluates information gain over time, and selects the highest-utility pose.The sequence integrates candidate generation, path planning, pose formation, utility evaluation, and goal selection.
  • Mapping and replanning: The mapping system runs in the background while the planner produces a new path whenever the previous path is completed.This background mapping and repeated path generation support ongoing exploration.

A. MAV Model · B. Map Representation · C. Frontier Detection

The method models MAV motion and sensing constraints, uses an octree occupancy map for collision-free planning and entropy-based quality assessment, and detects frontiers incrementally at voxel-block resolution. This representation avoids map-wide frontier updates and computationally intensive clustering.

  • A. MAV Model: The MAV state comprises 3D position and yaw, subject to maximum linear velocity and yaw-rate constraints.
  • A. MAV Model: A fixed depth camera provides sensing with bounded range and horizontal and vertical fields of view.
  • A. MAV Model: Collision checking models the MAV as a sphere centered at its position with safety radius R.
  • B. Map Representation: The occupancy map represents free space for collision-free path planning, integrates noisy measurements, and provides map-quality information through entropy.
  • B. Map Representation: supereight stores the map in an octree, using Morton codes for spatial indexing and efficient map updates and queries.
  • B. Map Representation: The map extension stores frontier status per voxel and propagates occupancy probabilities upward to support efficient collision queries after depth updates.
  • C. Frontier Detection: Frontiers are updated continuously during sensor integration and grouped implicitly by voxel blocks, avoiding map-wide updates and computationally intensive clustering.
  • C. Frontier Detection: Frontiers are free voxels with occupancy probability below 0.5 adjacent through a face to voxels with probability exactly 0.5.

D. Candidate Position Sampling · E. Path Planning to Candidate Positions

Candidate viewpoints are sampled uniformly from sufficiently populated frontier voxel blocks, then connected to the MAV through collision-free paths that terminate at safe endpoints. Unlike receding-horizon approaches,, the MAV follows each planned path to completion before selecting another frontier.

  • D. Candidate Position Sampling: Candidate positions p_i=[x_i,y_i,z_i]^T are uniformly sampled from frontier voxel blocks at each planning iteration.The planner samples a predefined number N_c of candidates from the frontier representation.
  • D. Candidate Position Sampling: Frontier voxel blocks containing fewer than a threshold number of frontier voxels are excluded during sampling, producing a filtered frontier list F̃.The frontier blocks are evaluated for frontier-voxel counts before candidate generation.
  • E. Path Planning to Candidate Positions: OMPL computes candidate paths using informed RRT* [24] with path simplification.The octree map supports efficient collision checking during planning.
  • E. Path Planning to Candidate Positions: Collision checking queries occupancy first at a higher octree level and then at voxel level, using a sphere around the MAV.Free-space validity is determined by comparing occupancy probabilities with a threshold.
  • E. Path Planning to Candidate Positions: Because frontier candidates lie near unknown space, paths typically end near the MAV’s safety radius rather than at the sampled candidate position.The candidate is updated to this safe endpoint, defining a path W_i(p,p_i) composed of one or more line segments.
  • E. Path Planning to Candidate Positions: Receding-horizon methods, can move the MAV back and forth when successive iterations select different path endpoints.This behavior can temporarily leave the MAV stuck in a small region.
  • E. Path Planning to Candidate Positions: The proposed approach follows each path to its endpoint, committing the MAV to exploring one frontier before moving toward another goal.This replaces the first-point-only motion behavior described for receding-horizon exploration.

F. Yaw Optimisation and Candidate Pose Evaluation · 1) Sparse Raycasting and Yaw Optimisation:

The method evaluates candidate MAV poses using sparse 360° raycasting to estimate map entropy and optimises yaw toward the highest-entropy view. It selects the pose maximising entropy gained per estimated travel time, balancing nearby coverage with distant unexplored frontiers.

  • F. Yaw Optimisation and Candidate Pose Evaluation: Each candidate position p_i becomes a pose x_i = [x_i,y_i,z_i,ψ_i]^T after optimising yaw using the 360° raycast.H(x_i) denotes the map entropy obtained by raycasting from the resulting candidate pose.
  • 1) Sparse Raycasting and Yaw Optimisation:: Travel time assumes maximum linear speed υ_max and maximum yaw rate ω_max, with total time determined by the slower translational or rotational motion.The estimate compares travel from p to p_i at υ_max with rotation from ψ to ψ_i at the maximum rate.
  • F. Yaw Optimisation and Candidate Pose Evaluation: The candidate pose with the highest utility is selected as the MAV’s next goal pose.Utility combines the sparse-raycast entropy estimate with the estimated path-completion time.
  • 1) Sparse Raycasting and Yaw Optimisation:: Sparse 360° raycasting estimates map entropy at each candidate position while avoiding random yaw sampling with informed RRT* [26].Sparse raycasting approximates full raycasting at a fraction of the computational cost.
  • 1) Sparse Raycasting and Yaw Optimisation:: Ray entropy sums voxel uncertainties until the first occupied voxel or maximum sensor range, capturing both unknown regions and low-quality mapped areas.The resulting measure reflects both map coverage and map quality.
  • 1) Sparse Raycasting and Yaw Optimisation:: Yaw is selected by sliding-window summation over the entropy map, choosing ψ_i with the highest cumulative entropy within the sensor’s horizontal field of view.The resulting yaw defines the candidate pose x_i, as illustrated by the red camera-frustum boundaries in Figure 3.
  • F. Yaw Optimisation and Candidate Pose Evaluation: Candidate-pose utility is visible map entropy divided by path travel time, favouring high-information distant frontiers while penalising time-consuming paths.This ratio balances immediate-surroundings exploration against movement toward potentially unexplored regions.

2) Utility Function:

The utility function evaluates candidate poses and selects the candidate with the highest utility as the next goal pose. The selected path is refined by assigning yaw angles to intermediate points before controller execution, with limited computational impact.

  • Utility Function: The candidate pose with the highest utility is selected as the next goal pose.
  • Utility Function: Intermediate path points receive yaw angles through the same yaw optimisation used for candidate paths, producing the final controller path.The initial and final points retain the current and candidate poses’ associated yaw angles.
  • Utility Function: Because only the simplified path to the best candidate undergoes intermediate yaw optimisation, its computation-time effect is limited.The number of intermediate points depends on space geometry and is generally low after OMPL path simplification.

V. EXPERIMENTAL EVALUATION · A. Apartment Environment Simulation

In simulated apartment experiments, the proposed exploration method was evaluated against an NBV planner and explored the environment substantially faster, particularly with high-resolution maps. The evaluation used a RotorS MAV simulation setup with fixed candidate-pose sampling and documented exploration parameters.

  • V. EXPERIMENTAL EVALUATION: The simulated experiments used Ubuntu 18.04, ROS Melodic, and the RotorS simulator.The MAV model was an Ascending Technologies FireFly hexacopter equipped with a VI-Sensor mounted at a 15◦ angle.
  • V. EXPERIMENTAL EVALUATION: Each simulation planner iteration sampled 20 candidate poses on an Intel Core i7-8750H CPU operating at 2.20 GHz.The experiments used the specified simulation hardware and software environment; Table I lists the exploration parameters.
  • A. Apartment Environment Simulation: The proposed method explored the entire apartment environment substantially faster than the compared NBV planner, especially at high map resolution.Figure 4 reports explored volume over time averaged across 10 runs for voxel resolutions r = 0.1 m and r = 0.4 m.
  • A. Apartment Environment Simulation: The apartment experiments used a 10 m × 20 m × 3 m environment previously used in,.
  • A. Apartment Environment Simulation: The proposed algorithm was compared with the NBV planner presented in.
  • A. Apartment Environment Simulation: Exploration performance was measured as explored volume over time, averaged over 10 runs.The comparison was conducted at voxel resolutions r = 0.1 m and r = 0.4 m.

B. Maze Environment Simulation · C. Powerplant Environment Simulation

In the maze simulation, the proposed planner explored significantly faster than NBVP by using frontiers to guide the MAV toward unexplored regions. In the powerplant simulation, exploration speed depended on MAV velocity, while unobservable space prevented complete coverage.

  • B. Maze Environment Simulation: NBVP’s random sampling sometimes missed unexplored regions, leaving the MAV stuck in one map portion before it moved onward.
  • B. Maze Environment Simulation: The planners were not evaluated at 0.4 m resolution because narrow maze corridors become unnavigable for the MAV at that coarseness.
  • B. Maze Environment Simulation: The maze experiment produced a top-down map with the MAV’s path, starting position, final position, and voxel heights represented visually.
  • C. Powerplant Environment Simulation: In the 33 m × 31 m × 26 m powerplant simulation, explored volume over time was averaged over 10 runs for multiple MAV maximum linear velocities.
  • C. Powerplant Environment Simulation: The planner could not explore the entire powerplant because a large portion of the environment was unobservable, including the building interior.
  • C. Powerplant Environment Simulation: Lower MAV velocities slowed exploration both through slower movement and reduced information gain from distant candidate views, favoring nearby regions first.
  • C. Powerplant Environment Simulation: The powerplant results included a generated map and corresponding MAV path alongside the explored-volume-over-time evaluation.

D. Computational Complexity

The planner’s onboard computational complexity is analyzed per iteration, covering candidate sampling, collision-free path computation, sparse raycasting, yaw optimization, and utility evaluation. Simulated per-iteration computation times are compared with NBVP across environments and map resolutions, with higher-resolution efficiency attributed to sparse raycasting and efficient collision checking.

  • D. Computational Complexity: Per-iteration complexity combines candidate sampling, path computation, sparse raycasting, yaw optimization, utility evaluation, and final-path yaw computation.The analysis gives component-wise asymptotic costs, including O(Nc) for candidate sampling, O(Np) for utility evaluation, and O(Np(nm_r+n)) for final-path yaw computation.
  • D. Computational Complexity: Measured per-iteration planner computation times for three simulated environments and multiple map resolutions are compared with NBVP in Table II.The comparison is reported using means and standard deviations, although the supplied passages do not provide the table’s numerical values.
  • D. Computational Complexity: At higher map resolutions, the planner’s computation-time reduction is attributed to sparse raycasting and efficient collision checking.The planner also performs relatively few planning iterations because each computed path is followed to its end before replanning.

E. Real World Experiments · VI. CONCLUSIONS AND FUTURE WORK

The hybrid frontier- and sampling-based exploration strategy improves exploration speed and computational cost in simulation, while real-world experiments demonstrate real-time onboard MAV operation. Future work targets richer mapping, trajectory generation, sensing, and deployment environments.

  • E. Real World Experiments: The complete mapping and exploration-planning system ran onboard a DJI F550 hexacopter using an ASUS Xtion Pro RGBD camera and Intel NUC.The onboard computer used an Intel Core i7-7567U CPU operating at 3.5 GHz.
  • E. Real World Experiments: The real-world test took place in a 7 m × 5.5 m × 5 m room equipped with a VICON motion-capture system for MAV pose estimation.The experiment environment and MAV-obstacle configuration are illustrated in Fig. 8.
  • VI. CONCLUSIONS AND FUTURE WORK: The proposed hybrid frontier- and sampling-based strategy improves exploration speed and computational cost in simulation and operates in real time onboard an MAV.The real-world experiment demonstrates feasibility of deploying the complete strategy in practice.
  • VI. CONCLUSIONS AND FUTURE WORK: Future work includes a multi-resolution mapping pipeline like the one in and dynamically feasible drone trajectories instead of waypoint sequences.These changes are intended to improve mapping and trajectory generation.
  • VI. CONCLUSIONS AND FUTURE WORK: Planned extensions include additional sensor types such as LIDARs and robust operation in real-world outdoor environments.The authors identify both sensing expansion and outdoor robustness as future improvements.
  • VI. CONCLUSIONS AND FUTURE WORK: The authors also plan to enable exploration and navigation in dynamic environments.This extends the strategy beyond the demonstrated static real-world setting.
Loading 2002.04440v2…