Source-linked AI summary
FUEL: Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning
Boyu Zhou, Yichen Zhang, Xinyi Chen, Shaojie Shen
TL;DR
FUEL addresses low exploration rates caused by greedy global planning, conservative motions, and low decision frequencies in autonomous UAV exploration. It combines an incrementally updated frontier information structure with hierarchical planning and completes exploration 3-8 times faster than state-of-the-art methods in benchmark and real-world tests.
Problem
Existing UAV exploration methods demonstrate low or medium exploration rates because greedy planning sacrifices global efficiency, motions are conservative, and decisions are made infrequently.
Method
FUEL incrementally maintains frontier information and uses hierarchical planning to find global tours, select local viewpoints, and generate minimum-time trajectories.
Results
3-8 times faster: FUEL completes exploration in much shorter time than classic and state-of-the-art methods across simulation cases, with benchmark and real-world tests demonstrating its performance.
Takeaways & Limitations
High-frequency planning enables rapid responses to environmental changes while global tours reduce revisiting and produce shorter coverage paths.
Takeaways & Limitations
The method assumes perfect state estimation and does not evaluate pose drift, although the authors plan to address state-estimation uncertainty in future work.
Abstract
from arXiv · showhide
Autonomous exploration is a fundamental problem for various applications of unmanned aerial vehicles. Existing methods, however, were demonstrated to insufficient exploration rate, due to the lack of efficient global coverage, conservative motion plans and low decision frequencies. In this paper, we propose FUEL, a hierarchical framework that can support Fast UAV Exploration in complex unknown environments. We maintain crucial information in the entire space required by exploration planning by a frontier information structure (FIS), which can be updated incrementally when the space is explored. Supported by the FIS, a hierarchical planner plans exploration motions in three steps, which find efficient global coverage paths, refine a local set of viewpoints and generate minimum-time trajectories in sequence. We present extensive benchmark and real-world tests, in which our method completes the exploration tasks with unprecedented efficiency (3-8 times faster) compared to state-of-the-art approaches. Our method will be made open source to benefit the community.
I. INTRODUCTION
FUEL addresses slow autonomous UAV exploration with an incrementally maintained frontier information structure and hierarchical planning for efficient, responsive motion. Simulation and real-world tests report complete exploration 3–8 times faster than compared methods.
- Autonomous exploration lets UAVs map unknown environments and gather information for applications including inspection, agriculture, and search and rescue.
- Existing planners often use greedy decisions, conservative motions, and infrequent replanning, limiting exploration rate and responsiveness to environmental changes.
- FUEL incrementally updates a frontier information structure that captures essential information across the explored space for high-frequency exploration planning.
- Its hierarchical planner generates efficient global coverage paths, safe agile local maneuvers, and dynamically feasible minimum-time trajectories.
B. Quadrotor Trajectory Planning
The paper situates its trajectory planner among hard- and soft-constrained quadrotor methods, then extends B-spline optimization to minimize total trajectory time. The broader framework combines this trajectory generation with incremental mapping and hierarchical exploration planning.
- B. Quadrotor Trajectory Planning: Hard-constrained trajectory methods enforce feasibility through approaches including minimum-snap formulations, safe regions, time allocation, and B-spline-based curves.
- B. Quadrotor Trajectory Planning: Soft-constrained methods optimize multiple objectives nonlinearly and have been applied to local replanning with B-splines and continuous-time trajectories.
- B. Quadrotor Trajectory Planning: FUEL extends prior B-spline trajectory planning by optimizing all spline parameters so total trajectory time can be minimized for higher navigation speed.
- B. Quadrotor Trajectory Planning: The framework updates the frontier information structure incrementally after map changes, then finds a global tour, refines viewpoints, and generates a trajectory to a selected viewpoint.
IV. INCREMENTAL FRONTIER INFORMATION STRUCTURE
FUEL incrementally maintains rich frontier information to support fine-grained, high-frequency exploration planning. The structure updates only affected regions while storing viewpoints and connection costs needed for global tour planning.
- Frontiers are known-free voxels adjacent to unknown voxels, grouped into clusters that guide navigation.
- The frontier information structure stores cluster cells, average position, bounding box, candidate viewpoints, and inter-cluster connection costs.
- Incremental detection removes clusters whose bounding boxes intersect the updated map region, then searches for and clusters new frontier groups.
- Candidate viewpoints are uniformly sampled around each cluster, with yaw optimized for sensor coverage while excluding occupied or insufficiently useful viewpoints.
- Connection costs use collision-free A* paths and motion limits, while incremental updates reduce recomputation from O(N_cls^2) searches to O(k_new · N_cls).
V. HIERARCHICAL EXPLORATION PLANNING
FUEL uses hierarchical exploration planning to replace greedy, conservative motion selection with efficient global coverage and agile local trajectories. Its coarse-to-fine pipeline computes a global frontier tour, refines nearby viewpoints, and generates a safe trajectory.
- V. HIERARCHICAL EXPLORATION PLANNING: The planner avoids greedy exploration by producing global paths that efficiently cover frontier clusters and dynamically feasible minimum-time motions.
- A. Global Exploration Tour Planning: The first planning phase finds a shortest open-loop tour covering frontier clusters across the environment.
- A. Global Exploration Tour Planning: The global-tour problem is reduced to an Asymmetric TSP by designing a connection-cost matrix for the current viewpoint and frontier clusters.
- A. Global Exploration Tour Planning: A motion-consistency cost penalizes large flight-direction changes, reducing back-and-forth maneuvers when tours have comparable time lower bounds.
- A. Global Exploration Tour Planning: Zero costs from clusters back to the current viewpoint let a closed-loop ATSP solution yield an equal-cost open-loop tour.
- A. Global Exploration Tour Planning: Local refinement considers multiple viewpoints along a truncated global-tour segment and selects an optimal viewpoint set using graph search.
B. Local Viewpoint Refinement
Local viewpoint refinement expands beyond the single viewpoint selected for each globally ordered cluster. It searches a truncated sequence of nearby clusters and favors coverage-based viewpoint choices for speed.
- Global tour planning selects one viewpoint per cluster, which may not be the best joint viewpoint combination.
- The refinement stage considers richer viewpoint sets for consecutive clusters within radius Rrf of the current position.
- A graph connects candidate viewpoints from the considered clusters with the current viewpoint for local graph-search refinement.
- The selected viewpoint sequence minimizes a cost combining time lower bounds and motion consistency.
- Coverage-based viewpoint selection is faster than evaluating information gain across numerous viewpoints while producing consistently satisfactory results.
C. Minimum-time B-spline Trajectory
FUEL generates smooth, safe, dynamically feasible B-spline trajectories while optimizing their parameters to minimize total flight time. The formulation balances smoothness, duration, safety, feasibility, and boundary constraints.
- B-spline optimization minimizes total trajectory time while preserving smoothness, safety, dynamic feasibility, and boundary state constraints.
- The trajectory objective combines elastic-band smoothness, total time, safety, dynamic-feasibility, and boundary-state penalties.
- Safety is evaluated from control-point distance to the nearest obstacle using the ESDF maintained by the mapping module.
- A clearance typically satisfying dmin ≥0.5 m is described as sufficient for safety relative to the quadrotor’s radius in complex scenes.
- Velocity and acceleration penalties discourage dynamically infeasible trajectories, with feasibility efficiently enforced through the B-spline convex hull property.
- Cubic B-splines use the current instantaneous state at the start and the next viewpoint at the end to support smooth motion.
A. Implementation Details
The implementation configures local refinement, trajectory optimization, incremental mapping, onboard localization, and trajectory tracking for UAV exploration. It uses specified numerical parameters and onboard computing hardware.
- Local refinement reserves at most Nview = 15 viewpoints per FIS and truncates the global tour within Rrf = 5.0.
- Trajectory optimization uses cubic B-splines with pb = 3 and specified smoothness, time, safety, and feasibility weights.
- The mapping framework maintains an occupancy grid and incrementally updated ESDF to support trajectory planning.
- Field experiments use visual-inertial localization, geometric trajectory tracking, and an Intel RealSense Depth Camera D435i.
- The onboard modules run on an Intel Core i7-8550U CPU.
B. Benchmark and Analysis
The simulation benchmark compares FUEL with NBVP, a classic frontier method, and a rapid frontier method in bridge and large-maze scenarios. Common dynamic and sensor settings are used across methods.
- The benchmark evaluates four methods: FUEL, NBVP, the classic frontier method, and the rapid frontier method.
- Tests use bridge and large-maze simulation scenarios.
- All methods share dynamic limits of vmax = 2.0 m/s and ξ̇max = 0.9 rad/s.
- The sensor field of view is [80 × 60] degrees with a maximum range of 4.5 m.
1) Bridge Scenario:
In the bridge scenario, FUEL explored faster with shorter, smoother paths than the compared methods. Its global tours, local refinement, and minimum-time trajectories supported efficient and agile motion.
- Bridge Scenario:: FUEL achieved shorter exploration time and lower time variance than the three compared methods in a 10 × 20 × 5 m3 bridge environment.The compared paths are shown for FUEL, classic frontier, rapid frontier, and NBVP methods.
- Bridge Scenario:: Global tour planning made FUEL’s overall exploration path significantly shorter.The method plans coverage globally rather than selecting motions greedily.
- Bridge Scenario:: Local motion refinement and smooth trajectory generation produced a smoother executed path.The local refinement stage supports safe and agile maneuvers.
- Bridge Scenario:: Minimum-time trajectory planning enabled FUEL to navigate at a higher flight speed.The trajectory stage complements global coverage and local motion refinement.
2) Large Maze Scenario:
FUEL was evaluated in a large maze and challenging real-world indoor and forest environments. The results support rapid exploration through hierarchical planning, while the method’s evaluation assumes perfect state estimation and does not consider pose drift.
- Large Maze Scenario:: In a 20×80×3 m3 maze, FUEL completed exploration more than 4 times faster on average than the benchmarked methods.It also explored in a more sensible order, revisited locations less frequently, and produced a shorter coverage path with an approximately linear exploration rate.
- Large Maze Scenario:: The maze results attribute FUEL’s reduced revisiting and shorter coverage path to global planning.The larger scene also increased computation time because it contained more frontier clusters.
- Field Exploration Tests: The real-world tests used onboard state estimation without external localization devices.Experiments imposed vmax = 1.5 m/s, amax = 0.8 m/s, and ξ̇max = 0.9 rad/s dynamics limits.
- Field Exploration Tests: Field experiments covered two indoor scenes with obstacles and a forest environment.The indoor spaces were bounded by 10 × 6 × 2 m3 and 15 × 11 × 2 m3 boxes, while the forest area measured 11 × 10 × 2 m3.
- Field Exploration Tests: Benchmark and real-world tests demonstrated the capability of the hierarchical framework in complex exploration scenarios.The system’s state estimation and mapping modules were also described as crucial to fulfilling the real-world tasks.
- Limitations: The method assumes perfect state estimation, and the simulation evaluation does not consider pose drifts.The authors identify incorporating state-estimation uncertainty and evaluating under pose drift as future work.