FUEL: Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning
FUEL uses FIS plus hierarchical planning to make UAV exploration 3–8× faster on bridge and maze benchmarks.
Key Findings
Methodology
FUEL separates exploration into two coupled layers: an incrementally maintained frontier information structure (FIS) and a coarse-to-fine planner. The FIS stores each frontier cluster’s cell set Ci, centroid pavg,i, axis-aligned bounding box Bi, candidate viewpoints VPi, and connection-cost list Lcost,i. When the map updates, only clusters intersecting the new-observation AABB are rechecked. Planning then proceeds in three stages: build a global open tour via time-lower-bound costs tlb and ATSP, refine a local segment with a DAG + Dijkstra search over multiple viewpoints, and generate a minimum-time cubic B-spline trajectory under safety and dynamics constraints.
Key Results
- In the 10×20×5 m^3 bridge scene, FUEL completes exploration in 104 s on average, versus 575 s for Classic frontier [7], 288 s for Rapid frontier [1], and 857 s for NBVP [12]. The average traveled distance is 165 m, also shorter than 250/286/322 m.
- In the 20×80×3 m^3 large maze, FUEL averages 168 s to full coverage, compared with 814 s, 669 s, and 1037 s for Classic, Rapid, and NBVP, respectively. The executed path is also much shorter: 280 m versus 419/469/1539 m.
- The online computation remains low enough for high-frequency replanning: total time is 24.17 ms in the bridge scene and 36.23 ms in the maze. Frontier maintenance takes 4.69–5.21 ms; viewpoint and cost updates take 5.16–10.97 ms, showing the incremental FIS is the enabler of real-time performance.
Significance
This paper tackles three persistent pain points in UAV exploration: poor global coverage, overly conservative motion, and low decision frequency. FUEL shows that exploration can be treated as a structured online optimization problem rather than a greedy next-target selection. By making frontier information incremental and planning hierarchical, it enables both rapid response to map changes and globally efficient coverage. The impact is practical: a 3–8× reduction in completion time in complex indoor environments, with paths that are shorter, smoother, and more dynamically aggressive. For research, it provides a clean blueprint for integrating mapping, tour optimization, and kinodynamic trajectory generation in one loop.
Technical Contribution
Technically, FUEL introduces an incremental frontier maintenance scheme that replaces full-map frontier rescans with AABB-based local updates, broad/narrow-phase style filtering, and recursive PCA splitting of oversized clusters. It also upgrades frontier clusters into planning entities by attaching rich viewpoint sets and incremental inter-cluster costs. On top of this representation, the paper reduces global exploration to an ATSP solved with a Lin-Kernighan-Helsgaun heuristic, and adds a motion consistency cost cc to suppress back-and-forth oscillations. Finally, it extends B-spline planning by optimizing both control points and knot span Δtb, minimizing total trajectory time while enforcing safety, velocity, acceleration, and boundary constraints.
Novelty
The novelty lies in combining two ideas that are usually treated separately: frontier structure maintenance and hierarchical motion planning. FIS is not just a frontier list; it is a structured, incrementally updated object that carries viewpoints and connection costs. The planner is also unusually complete for exploration: it does not stop at selecting a goal, but explicitly solves global ordering, local viewpoint refinement, and minimum-time trajectory generation in sequence. Compared with classic frontier, NBV, or sampling-based planners, this is a much more system-level formulation.
Limitations
- The method depends on accurate voxel maps, ESDFs, and frontier detection. If depth sensing is noisy, localization drifts, or updates lag behind the real scene, cluster splitting and connection costs can become unreliable, which may degrade ATSP ordering and local refinement.
- Although the incremental scheme is efficient, the global stage still requires pairwise costs and ATSP solving. In extremely fragmented environments with many clusters and viewpoints, computational and memory demands can still grow.
- The evaluation is strong but limited to bridge, maze, and indoor cluttered scenes. Robustness to moving obstacles, multi-robot coordination, and much larger-scale environments remains unverified.
Future Work
Natural extensions include incorporating information gain, semantic priority, and multi-robot task allocation into the FIS and ATSP cost, so the system optimizes not only speed but also utility. Another direction is robust replanning under dynamic obstacles and localization uncertainty, plus more aggressive viewpoint compression and learning-based cost prediction to scale to larger or more cluttered spaces.
AI Executive Summary
Deep Dive
Abstract
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.