EDEN: Efficient Dual-Layer Exploration Planning for Fast UAV Autonomous Exploration in Large 3-D Environments

Technical Summary of "EDEN: Efficient Dual-Layer Exploration Planning for Fast UAV Autonomous Exploration in Large 3-D Environments"

Problem Statement
Efficient autonomous exploration in large-scale 3-D environments remains a significant challenge for Unmanned Aerial Vehicles (UAVs). Existing methods generally fall into three categories: greedy methods, optimal-routing-based methods, and learning-based methods. Greedy approaches often suffer from inefficient back-and-forth maneuvers in large environments due to a lack of long-term planning. Optimal-routing-based methods, which formulate exploration as an Asymmetric Traveling Salesman Problem (ATSP), incur high computational costs that grow rapidly with the number of nodes, often forcing UAVs to stop and wait for planning results in large-scale scenarios. Furthermore, many state-of-the-art methods fail to fully exploit UAV speed potential, resulting in low-speed trajectories. Learning-based methods are limited by discrete action spaces and hardware constraints regarding parallel computing. Consequently, there is a need for a planning method that is computationally efficient, far-sighted, and capable of enabling high-speed continuous exploration while ensuring safety.

Methodology
The authors propose EDEN (Efficient Dual-Layer Exploration plaNning), a framework designed to plan efficient exploration motions in real-time for hundred-meter-level 3-D environments. The system operates on a dual-layer architecture:

1. Long-Term Region Routing (Global Layer):
   Instead of solving ATSP for every precise frontier, EDEN formulates the problem as finding a satisfactory routing of boundary regions. The authors introduce the Exploration-Oriented Heuristic Double-Tree (EOHDT) algorithm. This algorithm constructs a Minimum Spanning Tree (MST) of boundary regions and tailors the double-tree approach for ATSP by:

   • Identifying the leaf node farthest from the robot and executing its corresponding branch last to minimize return costs.
   • Heuristically selecting the next branch by choosing the child node closest to the current node.
   • Achieving a computational complexity of $O(n^2)$, where $n$ is the number of history nodes, ensuring real-time performance even in large environments.

2. Short-Term Viewpoint Selection (Local Layer):
   Within the first region of the computed routing, EDEN selects three specific viewpoints: an exploring viewpoint, a continuous viewpoint, and a safety viewpoint.

   • Curvature-Penalized Scoring: To enable high-speed flight, the method evaluates viewpoints using a curvature-penalized score. Based on the circular motion model, the maximum velocity is constrained by trajectory curvature. The system calculates a motion cost that penalizes sharp turns (high curvature) which would necessitate deceleration.
   • Viewpoint Pairing: The algorithm selects the pair of exploring and continuous viewpoints that maximizes a score function balancing the cost to reach the target and the cost to continue to the next target, ensuring the UAV can maintain high speed without sharp turns.
   • Safety Viewpoint: A backup safety viewpoint is selected near the exploring viewpoint to ensure the UAV can return to a safe space if new obstacles are detected.

3. Aggressive and Safe Exploration-Oriented (ASEO) Trajectory Planning:
   Inspired by the FASTER planner, EDEN generates a 4-D trajectory (position + yaw) composed of three connected MINCO (Minimum Control) segments:

   • Exploring Part: From the current position to the exploring viewpoint.
   • Continuous Part: From the exploring viewpoint to the continuous viewpoint.
   • Safety Part: From the exploring viewpoint to the safety viewpoint.
     These three trajectories are optimized simultaneously to ensure smoothness, feasibility, and collision avoidance. The objective function minimizes time costs for the exploring and continuous parts while penalizing violations of collision-free corridors and dynamic constraints (velocity, acceleration, yaw rates).

Key Contributions
The paper outlines four primary contributions:

1. EOHDT Algorithm: A novel algorithm for efficiently solving large-scale ATSP to find satisfactory region routings with real-time performance.
2. Curvature-Penalized Evaluation: A method for determining short-term exploration targets that explicitly accounts for trajectory curvature to enable high-speed continuous flight.
3. ASEO Trajectory Planning: A trajectory generation method that simultaneously optimizes efficiency and safety by planning an aggressive exploration path alongside a backup safety path.
4. Comprehensive Validation: Extensive comparative simulations and real-world experiments demonstrating the method's effectiveness.

Experimental Results
The proposed method was evaluated against state-of-the-art methods (FALCON and FUEL) in four challenging simulation environments (DARPA Tunnel, Classical Office, Large Maze, and City) and one extremely large environment (Large Tunnel), as well as in two real-world outdoor environments (Courtyard and Park).

• Efficiency: EDEN demonstrated 5.2% to 89.7% higher exploration efficiency compared to existing methods. In the "City" environment, it was 89.7% more efficient than FALCON and 93.5% more efficient than FUEL.
• Speed: The UAV achieved speeds 10.4% to 69.7% faster than comparative methods.
• Computational Cost: The method reduced computational costs by 28.9% to 93.9%. In the "Large Tunnel" experiment (251.5 × 327.5 × 2 m³), comparative methods failed due to memory and computation limits, while EDEN maintained an average planning time of 20.48 ms.
• Real-World Performance: In outdoor tests, EDEN successfully navigated complex environments with trees and slopes, achieving average velocities of ~1.77 m/s with average planning times of 14–18 ms.

Significance and Claims
The paper claims that EDEN successfully addresses the trade-off between computational efficiency and exploration performance in large-scale 3-D environments. By decoupling long-term region routing from short-term high-speed trajectory planning, the method enables UAVs to fly faster and more continuously without the frequent stops required by traditional optimal-routing methods. The authors state that the method allows for real-time planning in environments with hundreds of meters of scale while maintaining safety through the integrated safety trajectory.

The authors acknowledge a limitation: the continuity-enhanced planning strategy may lead to a slightly longer traveled distance compared to some methods, as it prioritizes high-speed paths over visiting isolated corners immediately. They suggest future work could prioritize isolated unknown regions to further reduce redundant movements. The source code for the method is intended to be open-sourced.