PaperlayerView exact revision on arXiv

Source-linked AI summary

A Multi-Resolution Frontier-Based Planner for Autonomous 3D Exploration

Ana Batinović, Tamara Petrović, Antun Ivanovic, Frano Petric, Stjepan Bogdan

arXiv:2011.02182v1cs.RO

TL;DR

Autonomous exploration of large, unknown 3D environments demands efficient mapping and navigation. The paper proposes a multi-resolution frontier planner using mapped submap data, and reports improved exploration and computation time in simulation and a UAV LiDAR experiment. A direct comparison with prior results remains limited by differing environments and setups.

  • Problem

    The paper addresses how to guide a robot through unknown 3D space toward a complete map while limiting exploration time and energy expenditure.

    Source: §I · p. 1, §III · p. 2

  • Method

    The planner detects frontiers from Cartographer submaps, filters and clusters them across OctoMap resolutions, and selects a target by potential information gain.

    Source: §I · p. 1

  • Results

    The authors report improved total exploration and computation time, including a 0.343s average calculation time in the outdoor UAV experiment.

    Source: B. Results and discussion · p. 7, §VI · p. 8

  • Takeaways & Limitations

    The planner was tested in simulation and a real-world quadcopter LiDAR experiment, with reported processing suitable for real-time applications.

    Source: §VI · p. 8

    Comparison with prior experimental results is constrained by differing environments, equipment, and setups, so the authors call for testing under the same setting.

    Source: C. Simulation results discussion · p. 7

Abstract

from arXiv · show

In this paper we propose a planner for 3D exploration that is suitable for applications using state-of-the-art 3D sensors such as lidars, which produce large point clouds with each scan. The planner is based on the detection of a frontier - a boundary between the explored and unknown part of the environment - and consists of the algorithm for detecting frontier points, followed by clustering of frontier points and selecting the best frontier point to be explored. Compared to existing frontier-based approaches, the planner is more scalable, i.e. it requires less time for the same data set size while ensuring similar exploration time. Performance is achieved by not relying on data obtained directly from the 3D sensor, but on data obtained by a mapping algorithm. In order to cluster the frontier points, we use the properties of the Octree environment representation, which allows easy analysis with different resolutions. The planner is tested in the simulation environment and in an outdoor test area with a UAV equipped with a lidar sensor. The results show the advantages of the approach.

I. INTRODUCTION

The paper targets autonomous 3D exploration of large, unknown environments, where mapping and navigation impose substantial memory and computation demands. It presents a submap-based, multi-resolution frontier planner and positions it against prior frontier- and next-best-view approaches.

I. INTRODUCTION

  • Large-scale 3D mapping and autonomous navigation are challenging because they require substantial memory and computation.The planner is intended to guide a robot through an environment without prior knowledge toward a complete map.Source: §I · p. 1
  • Cartographer submaps provide the frontier detector with one point per occupied submap cell, rather than raw 3D sensor readings.The authors describe the scan-matched, fused submap as a more stable input than raw readings used by prior methods,,,.Source: §I · p. 1
  • The planner uses OctoMap resolution changes to filter frontier points, then applies mean-shift clustering and selects a target by estimated information benefit.The paper identifies submap-based frontier detection, multi-resolution refinement, and selection based on potential information gain as contributions.Source: §I · p. 1

II. RELATED WORK

  • Prior 3D-FBET work produced noisy, unreliable local frontiers and environment-insensitive clustering, which the authors associate with longer exploration time.The paper was inspired by 3D-FBET, a three-phase frontier-based approach.Source: §II · p. 2
  • Rather than maintain two resource-intensive OctoMaps for local and global frontiers as in Mannucci et al., the planner uses multiple resolutions in one map.Mannucci et al. assign global frontiers when local frontiers are empty and evaluate targets with a cost-utility approach,.Source: §II · p. 2
  • The authors combine dense 2D frontier detection with multi-resolution clustering and target selection, and report simulation and experimental evaluation with datasets for comparison.They state that the planner can run online on a robot with limited resources.Source: §II · p. 2, §I · p. 2

III. PROPOSED APPROACH

The approach treats exploration as selecting waypoints that balance information benefit and cost while traversing unknown space toward a complete map. It uses an OctoMap for frontier detection and collision-free navigation, assuming suitable mapping, localization, and path-planning components.

III. PROPOSED APPROACH

  • The environment is represented as an OctoMap, whose voxels are free, occupied, or unknown.These voxel states partition the represented space into free, occupied, and unknown subspaces.Source: §III · p. 2
  • Exploration seeks waypoints that traverse unknown space quickly and with low energy expenditure, and is complete when no unknown space remains.The planner directs the robot toward frontier points with the best benefit-cost trade-off.Source: §III · p. 2
  • The UAV is assumed to have no prior environmental knowledge, while suitable SLAM, sensing, path-planning, and path-following components are assumed available.The resulting OctoMap supports both frontier detection and collision-free navigation.Source: §III · pp. 2–3
  • Cartographer SLAM submaps feed OctoMap generation, followed by frontier detection, clustering, and best-frontier selection; the selected voxel is a navigation target.The navigation target is chosen using the OctoMap built so far.Source: Figure 2 · p. 3

A. Frontier detection

Frontiers are free voxels adjacent to unknown space, detected from OctoMap data built from scan-matched submaps. The planner updates local and global frontiers incrementally, then clusters them into candidate targets.

A. Frontier detection

  • Frontier voxels are free voxels with at least one unknown neighbor; their centers are frontier points.Source: A. Frontier detection · p. 3
  • Completed submaps become point clouds with one point per occupied voxel, then contribute to an OctoMap that provides a more stable frontier-detection input than raw scans.Each submap is built from N_s consecutive LiDAR scans aligned using IMU and odometry data.Source: A. Frontier detection · p. 3
  • Each new submap triggers an OctoMap update and frontier cycle; local frontiers track changed voxels, while global frontiers combine past local frontiers and remove discovered voxels.Source: A. Frontier detection · p. 3
  • Because frontier evaluation is costly, the planner clusters frontier voxels with multi-resolution and mean-shift methods, using cluster centers as potential exploration targets.Source: A. Frontier detection · p. 3

B. Multi-resolution frontier clustering

The planner uses Octree hierarchy to aggregate fine-resolution frontier voxels at a chosen exploration depth. This reduces the points considered for later planning while retaining high-resolution mapping for navigation.

B. Multi-resolution frontier clustering

C. Mean-shift frontier clustering

Mean-shift clustering groups the parent frontier voxels into candidate UAV waypoints. Its bandwidth is selected to balance runtime against the desired outcome for the environment and map resolution.

C. Mean-shift frontier clustering

D. Best frontier voxel selection

Candidate frontier voxels are scored by expected information gain and travel distance, with a parameter controlling their relative weight. The highest-gain voxel becomes a waypoint for path planning.

D. Best frontier voxel selection

IV. SIMULATION-BASED EVALUATION

The simulations use a Gazebo environment and a modeled quadcopter equipped with a Velodyne VLP-16 LiDAR. The evaluation includes a house scenario and reports metrics for specified mapping and exploration resolutions.

IV. SIMULATION-BASED EVALUATION

  • The simulated UAV uses a Velodyne VLP-16 LiDAR with its maximum range reduced to 20 m, and tests run on an Intel i7 8550U.The modeled quadcopter is identical to the one used in the outdoor experiments.Source: §IV · p. 5
  • The house scenario is shown as a Gazebo world alongside an OctoMap generated during exploration.The OctoMap is the map representation shown for the scenario.Source: Figure 5 · p. 5
  • The house-scenario metrics use rmax = 0.25m, rexp = 1m, and bandwidth = 2.Simulation velocity is set to 0.8 m/s, matching the speed used in outdoor experiments for safety reasons.Source: Figure 6 · p. 5, §IV · p. 5

A. House Exploration Scenario

In the 30x40x5m house scenario, the planner explores the environment in less than 200 seconds. The evaluation reports frontier and module-computation metrics under the stated voxel and clustering settings.

A. House Exploration Scenario

  • For each waypoint-calculation iteration, the evaluation reports frontier counts and computation times for OctoMap creation, detection, clustering, and best-frontier selection.Clustering includes multi-resolution and mean-shift algorithms; detection includes local-frontier detection and global-frontier updates.Source: A. House Exploration Scenario · p. 5
  • The 30x40x5m house scenario uses rmax = 0.25m, exploration level dexp = 14 (rexp = 1m), and mean-shift bandwidth 2.The average computation time is 0.197s, with standard deviation 0.062s.Source: A. House Exploration Scenario · p. 5
  • Less than 200s are needed to explore the house scenario, with Fig. 7 tracking free, occupied, and unmapped volume over time.Total exploration time includes computation, execution, and RRT-based path planning.Source: A. House Exploration Scenario · p. 5, Figure 7 · p. 6

B. Large Exploration Scenario

In the larger 130x160x5m scenario, the planner averages 0.095s per calculation and completes exploration in about 350s. Global frontiers are clustered into candidates before the UAV follows a path to the selected frontier voxel.

B. Large Exploration Scenario

  • The large scenario covers a 130x160x5m space and uses rmax = 0.5 m, dexp = 14, and bandwidth 2.The authors allow lower resolution and exploration depth than in the house environment.Source: B. Large Exploration Scenario · p. 6
  • Global frontiers are clustered into candidates, and the UAV follows a planned path to the best frontier voxel.Fig. 10 marks global frontiers red, candidates yellow, the best frontier voxel pink, and the path green.Source: B. Large Exploration Scenario · p. 6, Figure 10 · p. 6
  • 0.095s is the average calculation time (standard deviation 0.058s), while total exploration takes about 350s in the large scenario.Fig. 8 shows free, occupied, and unmapped volumes over time.Source: B. Large Exploration Scenario · p. 6

C. Simulation results discussion

Outdoor testing reported an average calculation time of 0.343 s and exploration time of about 350 s. In simulation, total computation time grew approximately linearly with frontier size, though comparison with other approaches is limited by differing setups.

C. Simulation results discussion

  • Total computation time grew approximately linearly with frontier size, with average planner-iteration times of 0.197 s and 0.095 s across the reported settings.The authors report that computation remained suitable for the applications considered, but note that direct comparison with state-of-the-art simulations is difficult because setups differ.Source: C. Simulation results discussion · p. 6

A. Setup

  • The outdoor platform was a custom quadcopter carrying a Velodyne VLP-16 LiDAR, with maximum velocity limited to 0.8 m/s.The UAV also carried an onboard computer for collecting and processing sensory data.Source: A. Setup · p. 7, Figure 11 · p. 7

B. Results and discussion

  • 0.343 s average calculation time (SD 0.043 s) and about 350 s total exploration time were reported outdoors with rmax = 0.5 m, dexp = 14, and bandwidth = 2.The experiment used the same parameters as the large exploration scenario.Source: B. Results and discussion · p. 7, Figure 13 · p. 7
  • Thorough comparison with other experimental approaches was not possible because environments, equipment, and setups differed.The authors provide simulation and experiment datasets to support future comparisons.Source: B. Results and discussion · p. 7

VI. CONCLUSION

The paper presents a multi-resolution frontier-based planner that maps unknown areas using Cartographer SLAM and generates an OctoMap. Simulation and a LiDAR-equipped quadcopter experiment showed improvements in exploration and computation time suitable for real-time applications.

VI. CONCLUSION

  • The planner autonomously explores unknown areas, creating an occupancy grid map with Cartographer SLAM and generating an OctoMap.The approach may be applied in indoor and outdoor environments.Source: §VI · pp. 7–8
  • Simulation and a real-world LiDAR-equipped quadcopter experiment showed improvements in total exploration and computation time suitable for real-time applications despite large input data sizes.The authors identify more frequent waypoint assignment and multi-robot exploration as future work.Source: §VI · p. 8
Loading 2011.02182v1…