Evolution Algorithm and Online Learning for Racing Drone

Sangyun Shin, Yongwon Kang, Yong-Guk KimNeurIPS 2019 · OpenReview

Autonomous drone racing is the "Formula 1" of robotics. It requires a vehicle to navigate complex, three-dimensional obstacle courses at breakneck speeds, demanding a perfect marriage of computer vision, path planning, and control. While deep learning has mastered obstacle avoidance, optimizing for pure speed remains a stubbornly high hurdle.

In their paper presented at the NeurIPS 2019 Competition Track, researchers from Sejong University describe how they combined evolutionary algorithms with online gradient-based learning to take home first place in the "Game of Drones" competition.

The Challenge of Speed Optimization

In drone racing, "fast and accurate" is the name of the game. Most modern approaches use Deep Neural Networks (DNNs) for vision-based navigation. However, these models are typically trained using gradient descent, which requires a differentiable loss function.

While it’s easy to write a loss function for "stay in the center of the gate," it is notoriously difficult to design one for "go as fast as possible without crashing." Speed optimization involves discrete, non-differentiable parameters—like acceleration limits and distance thresholds—that don't play well with standard backpropagation. Furthermore, traditional navigation methods like SLAM often struggle with the dynamic, high-speed scene changes inherent in racing.

A Two-Pronged Strategy: Evolution Meets Gradient Descent

To overcome this, the authors developed a hybrid system that optimizes both the differentiable steering controls and the non-differentiable speed parameters simultaneously.

System Architecture

1. Online Gradient-Based Learning (The "Steering")

The drone uses an object detection model (SSD MobileNet) to identify racing gates in a monocular First Person View (FPV) image. This data is fed into a control network that outputs linear velocities.

Vision to Control Pipeline

Crucially, the model undergoes online training during the race. It calculates a loss based on the distance between the drone's predicted path and the actual center of the detected gate, allowing the drone to "learn" the specific nuances of a track as it flies.

2. Evolutionary Algorithm (The "Speed")

To handle the parameters that gradient descent can't touch, the team used a Genetic Algorithm (GA). They defined a "gene" as a set of three parameters: maximum velocity, acceleration, and a distance threshold for command termination.

  • Population: Multiple processes (genes) run racings in parallel.
  • Fitness Function: The simplest metric possible—total travel time.
  • Selection: The fastest drones are selected as "parents" to produce the next generation of parameters through mutation and recombination.

Key Insights and Results

The hybrid approach was highly successful, leading to a 1st place finish in both Tier 2 and Tier 3 of the NeurIPS 2019 Game of Drones competition, evaluated in the Microsoft AirSim environment.

  • Record Times: The system achieved a shortest travel time of 56 seconds in Tier 2 (after 9,000 generations) and 71 seconds in Tier 3.
  • Simplicity is a Feature: By using an evolutionary algorithm for speed, the authors bypassed the need for a complex, handcrafted "speed loss function." They let the stopwatch be the judge.
  • Parameter Sensitivity: The researchers found that even when the control network produces the same directional output, changing the "latent" racing parameters significantly alters the drone's trajectory and success rate, highlighting the importance of hyperparameter optimization in robotics.
  • Efficiency: By using SSD MobileNet, they achieved high frame rates (26-27 FPS), which reduced "lag" in the control loop—a critical factor for high-speed stability.

Limitations and Future Work

While highly effective in simulation, the "sim-to-real" gap remains a challenge for future implementation on physical hardware, as real-world lighting, wind, and sensor noise must be accounted for. Additionally, running hundreds of thousands of simulations to evolve parameters is computationally expensive. Future work may focus on more sample-efficient evolutionary strategies to speed up convergence and reduce computational overhead.

Summary updated

Abstract

Drone racing has become one of the challenging topics in robotics and machine learning because such a drone requires to equip with high performing modules that carry out demanding tasks, such as ob...
BibTeX
@inproceedings{shin2019evolution,
  author = {Sangyun Shin and Yongwon Kang and Yong-Guk Kim},
  title = {{Evolution Algorithm and Online Learning for Racing Drone}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=pSYBeuN3Dw},
}
Figure