Dynamic Q-planning for Online UAV Path Planning in Unknown and Complex Environments

Lídia Rocha, Kenny A. Q. Caldas, Marco H. Terra, Fábio Ramos, Kelen Cristiane Teixeira VivaldiniResearch Square 2024 · DOI

TL;DR

Researchers have developed a "Dynamic Q-planning" approach that allows Unmanned Aerial Vehicles (UAVs) to navigate unknown, complex environments in real-time. By dynamically calculating the optimal number of reinforcement learning iterations based on environmental complexity, the system achieves the path-finding accuracy of heavy-duty algorithms like A* but with significantly lower computational overhead and sub-second replanning capabilities.

What Problem Does This Paper Address?

Navigating a drone through a forest or a cluttered warehouse is a high-stakes balancing act. Traditional "exact" algorithms like A* are great at finding the shortest path, but they are computationally expensive—often too slow for the split-second decisions required during high-speed flight. On the other hand, sampling-based methods like RRT (Rapidly-exploring Random Trees) are faster but can produce jagged, inefficient paths or fail entirely in tight spaces.

Reinforcement Learning (RL), specifically Q-learning, offers a middle ground. It’s model-free and fast, but it has a "Goldilocks" problem: the number of training iterations. If you set the iterations too low, the drone fails to find a safe path. Set them too high, and you waste precious battery and CPU cycles "overthinking" a simple environment. Most researchers pick a fixed number of iterations based on trial and error, which doesn't work when a drone moves from an empty room into a crowded hallway.

Methods

The authors introduce Dynamic Q-planning, which treats path planning as a Markov Decision Process (MDP). The core innovation is a complexity formula used to determine the iteration count on the fly.

  1. Complexity-Based Iteration Selection: Instead of a hardcoded number, the algorithm calculates environmental complexity using factors like obstacle density, the distance to the goal, and a "Spatial Distribution Factor" (SDF). If the environment is simple, the drone performs fewer iterations; if it's a "maze," it scales up.
  2. Q-Learning Core: The agent uses an epsilon-greedy strategy to balance exploring new areas versus exploiting known safe paths, updating a Q-table to store the "value" of moving in specific directions.
  3. Trajectory Refinement: Once a discrete path is found, the algorithm runs a "Trajectory Refinement" step to prune unnecessary waypoints (e.g., if you can go straight from point A to C, why stop at B?).
  4. Cubic Spline Smoothing: To make the path flyable for a real quadcopter, the jagged grid-based path is converted into a smooth curve using cubic splines, which reduces "jerk" and respects the drone's aerodynamic constraints.

Datasets

The study utilized simulated environments built in the Gazebo simulator using the Robot Operating System (ROS).

  • Indoor Environment: A 30x30 meter space constructed with cardboard box obstacles.
  • Outdoor Environment: A 40x40 meter space simulating a dense forest with trees.
  • Hardware Emulation: The simulations targeted the specs of a DJI F-450 quadcopter equipped with an RPLidar (2D laser scanner) and an onboard computer (like an NVIDIA Jetson).

Key Insights and Ideas

  • The "Aha" Moment on Complexity: The researchers realized that complexity isn't just about the number of obstacles, but how they are distributed. Their formula for "Spatial Distribution Factor" allows the drone to recognize when it is in a "cluttered" vs. "open" space, adjusting its computational effort accordingly.
  • Efficiency vs. Completeness: One of the most striking findings was that while RRT and PSO (Particle Swarm Optimization) are often touted for speed, they frequently failed to find any valid path in complex outdoor scenes (completeness as low as 31-71%). Dynamic Q-planning maintained 100% completeness—it always found a way through.
  • Smoothing is Non-Negotiable: The paper emphasizes that a "mathematically optimal" path on a grid is often "physically impossible" for a drone. The integration of cubic splines ensures the output isn't just a list of coordinates, but a flyable trajectory that won't burn out the motors or cause crashes due to abrupt turns.

Key Results

The proposed method was compared against A*, RRT, and PSO across 100 simulation runs:

  • Speed: In indoor environments, Dynamic Q-planning generated paths in just 0.08 seconds (Best Time), significantly faster than standard Q-learning with fixed high iterations.
  • Path Quality: The paths found were nearly as short as A* (35.37m vs 35.22m indoor), but with a much lower CPU load.
  • Reliability: In the dense outdoor "forest" scenario, Dynamic Q-planning achieved 100% completeness, whereas RRT only succeeded 71% of the time.
  • Real-time Replanning: The system can detect an obstacle and replan a safe route in under 1 second, which is the "safety threshold" for a drone flying at 4 m/s (allowing it to react to obstacles 4-5 meters away).

Limitations and Future Work

While the results are promising, the authors and the methodology suggest a few areas for growth:

  • 2D vs. 3D: The current mapping relies on a 2D Lidar. While the authors claim the logic extends to 3D, navigating multi-level environments (like flying through a multi-story building via stairs) would require more complex state-space management.
  • Dynamic Obstacles: The paper focuses on "unknown" but static environments. Future work would need to address how the algorithm handles other moving drones or people.
  • Physical Flight Tests: The study is currently limited to high-fidelity "Software-in-the-loop" (SITL) simulations. The next step is deploying this on physical hardware in a real-world forest or warehouse to account for sensor noise and wind.

Summary updated

Abstract

<title>Abstract</title> Unmanned Aerial Vehicles need an online path planning capability to move in high-risk missions in unknown and complex environments to complete them safely. However, many algorithms reported in the literature may not return reliable trajectories to solve online problems in these scenarios. The Q-Learning algorithm, a Reinforcement Learning Technique, can generate trajectories in real-time and has demonstrated fast and reliable results. This technique, however, has the disadvantage of defining the iteration number. If this value is not well defined, it will take a long time or not return an optimal trajectory. Therefore, we propose a method to dynamically choose the number of iterations to obtain the best performance of Q-Learning. The proposed method is compared to the Q-Learning algorithm with a fixed number of iterations, A*, Rapid-Exploring Random Tree, and Particle Swarm Optimization. As a result, the proposed Q-learning algorithm demonstrates the efficacy and reliability of online path planning with a dynamic number of iterations to carry out online missions in unknown and complex environments.
BibTeX
@inproceedings{rocha2024dynamic,
  author = {Lídia Rocha and Kenny A. Q. Caldas and Marco H. Terra and Fábio Ramos and Kelen Cristiane Teixeira Vivaldini},
  title = {{Dynamic Q-planning for Online UAV Path Planning in Unknown and Complex Environments}},
  booktitle = {Research Square},
  year = {2024},
  doi = {10.21203/rs.3.rs-3942682/v1},
}
Figure