Source-linked AI summary
Autonomous UAV Exploration of Dynamic Environments via Incremental Sampling and Probabilistic Roadmap
Zhefan Xu, Di Deng, Kenji Shimada
TL;DR
UAV exploration planners often waste computation by failing to reuse samples and have limited demonstrated safety in dynamic environments. This paper proposes DEP, an incremental PRM planner that updates roadmap utilities, selects informative trajectories, and refines paths for obstacle-aware execution. DEP outperforms benchmark planners on exploration time, path length, and computational time, while safely completing exploration in tested dynamic environments.
Problem
Existing sampling-based UAV exploration methods may repeatedly recompute previously sampled regions and provide limited explicit evidence of safe exploration with dynamic obstacles.
Method
DEP incrementally samples and updates a PRM, evaluates node utilities, generates gain-rate trajectories, and applies ESDF-based optimization for efficient, safer exploration.
Results
DEP outperforms benchmark planners in exploration time, path length, and computational time, with no collisions across tested dynamic environments.
Takeaways & Limitations
Incremental PRM reuse supports efficient UAV exploration while retaining alternative trajectories for safe operation around dynamic obstacles.
Takeaways & Limitations
Because the robot sensor cannot completely detect dynamic obstacles, avoiding only detected obstacles may not guarantee safety.
Abstract
from arXiv · showhide
Autonomous exploration requires robots to generate informative trajectories iteratively. Although sampling-based methods are highly efficient in unmanned aerial vehicle exploration, many of these methods do not effectively utilize the sampled information from the previous planning iterations, leading to redundant computation and longer exploration time. Also, few have explicitly shown their exploration ability in dynamic environments even though they can run real-time. To overcome these limitations, we propose a novel dynamic exploration planner (DEP) for exploring unknown environments using incremental sampling and Probabilistic Roadmap (PRM). In our sampling strategy, nodes are added incrementally and distributed evenly in the explored region, yielding the best viewpoints. To further shortening exploration time and ensuring safety, our planner optimizes paths locally and refine them based on the Euclidean Signed Distance Function (ESDF) map. Meanwhile, as the multi-query planner, PRM allows the proposed planner to quickly search alternative paths to avoid dynamic obstacles for safe exploration. Simulation experiments show that our method safely explores dynamic environments and outperforms the benchmark planners in terms of exploration time, path length, and computational time.
I. INTRODUCTION
The paper introduces DEP, a PRM-based dynamic exploration planner that incrementally reuses roadmap information for efficient and safe UAV exploration. It combines incremental sampling, gain-aware trajectory selection, and safety-oriented planning for dynamic environments.
- DEP is a multi-query dynamic exploration planner based on Probabilistic Roadmap (PRM).
- Incremental PRM grows the roadmap evenly, evaluates node utilities, and selects the highest-utility trajectory for execution.
- DEP explicitly targets safe exploration in unknown environments containing dynamic obstacles.
- The planner evaluates benchmark performance using exploration efficiency, including exploration time, computational time, and path length.
II. RELATED WORK
Related work contrasts frontier-based and sampling-based exploration, emphasizing sampling methods for UAVs because they scale better with robot dimension and support information-gain viewpoints. Existing approaches nevertheless motivate roadmap reuse and more flexible replanning for dynamic obstacles.
- Sampling-based exploration selects viewpoints using information gain and is preferred for UAV exploration because computation does not increase significantly with robot dimension.
- Frontier-based exploration guides robots toward boundaries and has been extended from 2D ground robots to fast-flying UAV exploration and 3D reconstruction.
- RH-NBV grows a tree from the robot and executes the first segment of the branch with highest information gain, motivating several later sampling-based planners.
- The problem formulation requires collision-free exploration paths that map all reachable space while replanning promptly when detected dynamic obstacles occupy the executing path.
IV. PROPOSED METHOD
The proposed method incrementally constructs and updates a PRM, evaluates exploration gains, generates candidate trajectories, and refines them for safe, efficient execution. Its roadmap construction emphasizes even coverage and its node evaluation prioritizes informative unknown voxels.
- The planner follows four stages: roadmap construction, node evaluation and update, trajectory generation, and ESDF-based optimization.
- Roadmap Construction: Incremental sampling combines local samples near the robot with global samples to improve coverage of newly observed regions and avoid uneven node density.
- Roadmap Construction: Roadmap connections enforce traversability, distance, and sensor-range constraints so connected nodes support feasible exploration and obstacle observation.
- Node Evaluation and Update Rule: Node gain weights normal, frontier, and surface unknown voxels, with surface unknowns identified by adjacency to both free and occupied voxels.
- Node Evaluation and Update Rule: Only a subset of previously evaluated nodes is recomputed, while low-gain or sufficiently distant nodes can be assigned zero gain without reevaluation.
C. Trajectory Generation
DEP generates trajectories by selecting candidate goals with high information gain and scoring paths by gain per unit execution time. It can rapidly replan around dynamic obstacles without adding nodes or recomputing information gain.
- C. Trajectory Generation: Trajectory candidates are selected from roadmap nodes whose gain exceeds a fraction λ of the maximum node gain.The candidate set includes nodes with gain at least λ·Gain(nmax), where 0 < λ < 1.
- C. Trajectory Generation: Each candidate trajectory is scored by expected information gain divided by total execution time, and the highest-scoring trajectory is executed.Shortest paths are found with graph-search methods such as A* or Dijkstra.
- C. Trajectory Generation: The planner automatically determines waypoint yaw angles by interpolating previously stored orientation-specific gains.Execution time is calculated from predefined robot velocity and acceleration.
- C. Trajectory Generation: When a potential collision is predicted, DEP increases λ and generates an alternative trajectory without adding nodes or recomputing information gain.This enables immediate replanning to avoid dynamic obstacles safely.
D. ESDF-based Optimization
DEP locally optimizes already generated trajectories using ESDF distances to reduce execution time and path length while increasing clearance from obstacles. The objective balances normalized trajectory time and obstacle distance under collision, sensor-range, and minimum-distance constraints.
- D. ESDF-based Optimization: ESDF-based optimization jointly targets shorter execution time, shorter paths, and greater obstacle distance.The optimization operates locally because the trajectory already has high information gain.
- D. ESDF-based Optimization: The objective normalizes trajectory time and obstacle distance by their non-optimized values and balances them with weights w_t and w_d.This formulation trades off execution efficiency against obstacle clearance.
- D. ESDF-based Optimization: Connected waypoint pairs are constrained by collision, sensor-range, and minimum-distance conditions represented with binary satisfaction values.A value of 1 indicates that the corresponding condition is satisfied.
V. IMPLEMENTATION DETAILS
The implementation uses Octomap for planning and Voxblox for TSDF/ESDF generation. The planner limits information-gain sensing range, uses motion-aligned yaw for most nodes, and bounds optimization iterations for fast planning.
- V. IMPLEMENTATION DETAILS: DEP uses Octomap for planner implementation and Voxblox to generate the TSDF/ESDF map.The ESDF supports local obstacle-distance optimization around trajectory nodes.
- V. IMPLEMENTATION DETAILS: Information-gain computation uses a planner range smaller than the actual maximum sensor range, d_planner < d_max.This setting follows the cited prior recommendation.
- V. IMPLEMENTATION DETAILS: Yaw is optimized for the goal node, while other nodes use the robot’s moving direction to maximize visible range for dynamic-obstacle detection.The optimization averages obstacle distance after discretizing the trajectory at TSDF/ESDF-map resolution.
- V. IMPLEMENTATION DETAILS: Planning terminates after N consecutive steps without new nodes, and ESDF optimization stops after N_opt iterations to preserve fast planning.Each node’s local region is represented by a predefined bounding box.
VI. RESULTS AND PERFORMANCE BENCHMARKING
The evaluation uses a quadcopter with an RGB-D camera and compares DEP against RH-NBV, a frontier-based planner, and AEP. The experiments use target-environment and quadcopter-parameter tables to assess exploration performance and safety.
- VI. RESULTS AND PERFORMANCE BENCHMARKING: DEP is evaluated against RH-NBV, a frontier-based exploration algorithm, and AEP using a quadcopter equipped with an RGB-D camera.The experiments run on an Intel i7-7700HQ processor at 2.4 GHz.
- VI. RESULTS AND PERFORMANCE BENCHMARKING: The study evaluates exploration performance and safety using the target environments listed in Table II.Table II is identified as the environment-information table.
- VI. RESULTS AND PERFORMANCE BENCHMARKING: Robot parameters and settings are reported in Table III for the quadcopter used in the experiments.The supplied passage identifies Table III but does not provide its parameter values.
A. Environments and Parameters
Experiments use six environments spanning small, medium, and large static spaces, plus three dynamic settings with unknown pedestrian trajectories. Common robot parameters and benchmark-recommended planner parameters support fair comparisons.
- Environments: Six environments comprise Cafe (Small), Maze (Medium), Office (Large), Dynamic Auditorium, Dynamic Tunnel, and Dynamic Field.The first three test overall exploration performance across scales, while the dynamic environments test safe path generation around unknown moving people.
- Parameters: Benchmark comparisons use each method’s suggested parameters, while robot parameters remain identical across planners.Planner settings target even roadmap distribution, reliable gain estimation, fast replanning, and reasonable optimization constraints.
B. Exploration Performance
DEP achieves the strongest overall exploration performance across the evaluated static environments, while its exploration-rate advantage is clearest in Cafe and Maze. In Office, rates are similar, but DEP still completes exploration with lower computational time.
- Overall comparison: DEP records the best overall performance in Cafe and Maze, including 4.77 minutes and 43.12 m in Cafe and 17.75 minutes in Maze.In Cafe, DEP also uses 0.17 minutes of computation; AEP takes 23.23 minutes in Maze, 30.9% longer than DEP.
- Overall comparison: DEP has the shortest computational time in Office, requiring 36.9% of AEP’s time and nearly 20% of frontier exploration and RH-NBV’s time.Frontier exploration has the shortest Office path at 253.63 m, versus DEP’s 318.53 m.
- Exploration rate: DEP maintains the highest exploration rate in Cafe and Maze, whereas four planners have similar rates in Office except near the end.The Maze visualization after 10 minutes also shows DEP covering the largest explored area.
- Exploration rate: DEP’s Maze exploration rate remains nearly highest because its slope does not decrease while competing planners experience rate drops.In Office, larger open regions provide multiple similarly good viewpoints and trajectories, reducing rate differences.
C. Exploration in Dynamic Environments
DEP safely explores the tested dynamic environments without collisions, while its roadmap reuse supports rapid replanning. The evaluation also attributes performance differences to trajectory quality and utility-guided viewpoint selection.
- Dynamic-environment performance: DEP completes all three dynamic environments safely with no collisions across ten experiments per environment.The tested settings contain walking people whose trajectories are unknown to the robot.
- Performance analysis: DEP’s incremental roadmap and trajectory optimization support high-utility viewpoint selection, whereas frontier and RH-NBV can produce myopic, back-and-forth, or crooked trajectories.These differences are especially consequential in complex Maze environments, while open Office spaces offer multiple similarly good trajectories.
- Replanning: DEP has the least replanning time in dynamic environments, while RH-NBV and frontier exploration take approximately twice as long.AEP’s replanning time is 61.3% longer than DEP’s, with the reduction attributed to reusing the maintained roadmap.
B. Evaluation of ESDF-based Optimization
ESDF-based trajectory optimization improves DEP’s execution efficiency and obstacle clearance, while roadmap reuse reduces replanning time. The paper reports that DEP outperforms benchmarks overall but acknowledges incomplete detection of dynamic obstacles.
- ESDF-based optimization: Trajectory optimization reduces total exploration time to 77.01% and total path length to 76.09% of the non-optimized planner.Across planning iterations, optimized trajectories average 87.28% of the execution time and 91.86% of the path length of non-optimized trajectories.
- ESDF-based optimization: Optimization increases the nearest-obstacle average distance by 20.58% relative to non-optimized trajectories.This indicates improved clearance alongside shorter execution time and path length.
- Replanning time: DEP has the lowest replanning time in dynamic environments because it reuses the previously maintained roadmap.RH-NBV and frontier exploration take approximately twice DEP’s replanning time, while AEP is 61.3% longer.
- Overall assessment: The paper reports that DEP beats benchmark planners in exploration time, path length, and computational time while safely exploring dynamic environments.However, the robot’s limited sensing cannot completely detect dynamic obstacles, so avoiding only detected obstacles may not guarantee safety.