Polynomial-based Online Planning for Autonomous Drone Racing in Dynamic Environments

Qianhao Wang, Dong Wang, Chao Xu, Alan Gao, Fei Gao

Abstract

In recent years, autonomous drone racing has seen significant advancements, primarily focused on minimizing execution times in static environments. However, the challenges of dynamic environments—where gates move and obstacles shift—remain largely unaddressed. High-speed racing requires near-instantaneous replanning to ensure both safety and performance. This paper proposes an online replanning framework utilizing an efficient polynomial trajectory representation. By balancing aggressive speed with flexible obstacle avoidance through an optimization approach, the framework ensures precision via hard constraints for waypoint crossing. To avoid local optima in complex scenarios, we implement parallel multi-topology trajectory planning. The system was validated at the DJI Robomaster Intelligent UAV Championship, where it secured first place, completing the track in less than half the time of the runner-up.

Introduction

Autonomous drone racing is often described as the "Formula 1" of robotics research. While generating time-optimal trajectories for a fixed, known track is a solved problem in many respects, real-world racing is rarely static. Dynamic environments—featuring moving gates, unpredictable obstacles, and shifting race lines—demand a level of agility and computational speed that traditional planners struggle to provide.

Existing autonomous racing systems face two primary hurdles. First is computational latency; high-speed flight leaves no room for long optimization cycles. Many state-of-the-art planners require minutes to converge, rendering them ineffective for real-time reactions. Second is the trade-off between precision and speed. Most planners use "soft constraints" (penalties) to guide the drone through gates. At high velocities, these penalties are often insufficient to prevent the drone from "cutting corners," leading to missed gates or catastrophic collisions with gate frames.

Methodology

To address these challenges, we developed a high-speed online replanning framework based on three technical pillars: Time-uniform MINCO representation, hard waypoint constraints, and parallel multi-topology planning.

1. Time-uniform MINCO Trajectory

We improved upon the Minimum Control (MINCO) trajectory representation by introducing a "time-uniform" approach. By ensuring each segment of the polynomial trajectory has an identical duration, the complex matrix inversions required for trajectory generation can be pre-calculated offline. This mathematical optimization makes the online solver significantly more lightweight, allowing the drone to scale its trajectory in real-time with minimal CPU overhead.

2. Hard Waypoint Constraints

In high-speed racing, the spatial tolerance for error is nearly zero. Rather than treating gate-crossing as a goal to be balanced against speed (a soft constraint), we formulate it as a hard equality constraint. By mathematically eliminating these constraints during the optimization process, we guarantee that the drone passes through the exact center of the gate. This ensures safety and precision without sacrificing the solver's ability to find the fastest possible path through the remaining free space.

3. Parallel Multi-Topology Planning

Dynamic obstacles often create multiple potential paths (e.g., going left vs. right around a moving pillar). Standard optimizers can get trapped in a "local optimum"—a path that is safe but significantly slower than the alternative. Our framework plans multiple trajectories across different "topologies" simultaneously. By evaluating these paths in parallel using the L-BFGS numerical optimization algorithm, the system can proactively select the racing line that preserves the most momentum.

Experimental Results

The framework was integrated into a custom quadrotor system and evaluated through both simulation and real-world competition.

Competition Performance

The ultimate benchmark was the 2022 DJI Robomaster Intelligent UAV Championship. Our system completed the racing track in 22.0 seconds. To put this in perspective, the second-place team finished in 50.3 seconds, and the third-place team took 76.9 seconds. Our framework allowed the drone to maintain high speeds while navigating a complex, dynamic course with perfect gate-crossing precision.

Computational Efficiency

The efficiency of the time-uniform MINCO representation was evident in the system's latency metrics:

  • Standard Racing: Average replanning latency of 7.0 ms.
  • Complex SE(3) Maneuvers: Average latency of 16.6 ms when calculating aggressive tilts to fit through narrow vertical gaps.

Precision Analysis

In comparative ablation studies, the hard-constraint method maintained a 0-meter distance error from the gate center across various time weights. In contrast, soft-constraint methods saw errors spike as the optimization prioritized speed over gate accuracy, often resulting in trajectories that would physically collide with the gate structure.

Discussion and Future Work

While the framework demonstrates exceptional performance, it currently relies on the assumption of perfect perception. In environments with high sensor noise or low light, perception latency could become a bottleneck. Furthermore, while we include a basic drag model, the extreme turbulence (prop wash) encountered in tight indoor racing remains a challenge for future aerodynamic modeling.

Future research will focus on integrating more advanced aerodynamic models and exploring multi-drone coordination to handle head-to-head racing scenarios where the wake of an opponent drone must be considered in the planning phase.

Conclusion

By combining an efficient polynomial representation with hard geometric constraints and parallel topological search, we have developed a planner capable of winning world-class autonomous racing competitions. This work proves that with the right mathematical formulations, drones can navigate dynamic, high-speed environments with both the aggression of a racer and the precision of a surgical instrument.

Summary updated

Abstract

In recent years, there is a noteworthy advancement in autonomous drone racing. However, the primary focus is on attaining execution times, while scant attention is given to the challenges of dynamic environments. The high-speed nature of racing scenarios, coupled with the potential for unforeseeable environmental alterations, present stringent requirements for online replanning and its timeliness. For racing in dynamic environments, we propose an online replanning framework with an efficient polynomial trajectory representation. We trade off between aggressive speed and flexible obstacle avoidance based on an optimization approach. Additionally, to ensure safety and precision when crossing intermediate racing waypoints, we formulate the demand as hard constraints during planning. For dynamic obstacles, parallel multi-topology trajectory planning is designed based on engineering considerations to prevent racing time loss due to local optimums. The framework is integrated into a quadrotor system and successfully demonstrated at the DJI Robomaster Intelligent UAV Championship, where it successfully complete the racing track and placed first, finishing in less than half the time of the second-place.
BibTeX
@inproceedings{wang2023polynomial,
  author = {Qianhao Wang and Dong Wang and Chao Xu and Alan Gao and Fei Gao},
  title = {{Polynomial-based Online Planning for Autonomous Drone Racing in Dynamic Environments}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=LGaRlzRgAk},
}
Figure