MIT Students Develop Algorithm to Help Drones Race Past Obstacles

Technology inspired by drone racing could be used for time-critical rescue work.

MIT aerospace engineering students have found a new and innovative way for drones to navigate complex terrain faster—and without running into obstacles.

Influenced in part by the increasingly popular sport of drone racing—where the crashes along the way to the finish line are as entertaining as the race across it—the researchers have developed a new algorithm that trains drones to navigate better around obstacles.

The main challenge that drone racing pilots face is how to navigate the drone through a complicated obstacle course as fast as possible without crashing into something. Training drones to avoid obstacles at high speeds is vastly different from when they fly slowly. At higher speeds, aerodynamic forces such as drag come into play—and how the vehicle handles those forces gets harder to anticipate. A drone’s flight software often doesn’t take these factors into account. And at top speed, even the slightest delay in sensor reading, lag between input and software response, or noisy signal environment could result in a costly accident.

The research team of associate professor Sertac Karaman and graduate students Ezra Tal and Gilhyun Ryou at MIT has created a new algorithm to address that challenge.

“When you’re flying fast, it’s hard to estimate where you are,” said Ryou. “There could be delays in sending a signal to a motor, or a sudden voltage drop which could cause other dynamics problems. These effects can’t be modeled with traditional planning approaches.”

The researchers used a hybrid approach to develop the algorithm and began by designing a physics-based flight planning model. They then tested the model virtually, running it through thousands of simulated obstacle course races, each with a different flight path and speed pattern. They sorted the results into scenarios that were either successful or resulted in a crash and chose the most promising scenarios. These scenarios were then tested using a physical drone flying through the same course in a real-world space.

“We can do this low-fidelity simulation cheaply and quickly, to see interesting trajectories that could be both fast and feasible. Then we fly these trajectories in experiments to see which are actually feasible in the real world,” said Tal. “At high speeds, there are intricate aerodynamics that are hard to simulate, so we use experiments in the real world to fill in those black holes to find, for instance, that it might be better to slow down first to be faster later. It’s this holistic approach we use to see how we can make a trajectory overall as fast as possible.”

The algorithm is a multi-fidelity Bayesian optimization framework that uses analytical approximation, the numbers generated from simulations, and real-world flights to create models of flight paths. It is evaluated for two scenarios: connecting predetermined waypoints and planning in obstacle-rich environments. For each scenario, the team ran both simulated and real-world flight experiments at speeds up to 11 meters per second.

A Gaussian process (GP) black-box model is employed to determine whether any proposed trajectory is feasible or not—and is able to plan increasingly fast flight paths as more and more trajectories are analyzed and the model is improved. The algorithm uses GP within a Bayesian optimization, or BayesOpt, framework that employs machine learning techniques to solve optimization problems. In this framework, evaluation points are used to model unknown factors efficiently, which helps to keep the number of evaluations to a minimum and allows the algorithm to be more responsive and more accurately model the drone’s trajectory even with unknowns and/or noisy measurements.

Overview of the proposed algorithm. (Image courtesy of Karaman et al.)

Overview of the proposed algorithm. (Image courtesy of Karaman et al.)

Early results for the algorithm have been promising. The trajectories planned with the algorithm were noticeably faster than those generated from minimum-snap trajectory planning, which is the algorithm that conventional drone navigation software uses to generate drone flight paths around obstacles. In fact, the MIT drones trained with the algorithm won every head-to-head match, sometimes finishing 20 percent faster than their competitors, which were outfitted with standard obstacle avoidance software. The drones also won despite taking counterintuitive and sometimes unconventional routes to the finish line: they would take longer, slower and safer routes around trickier obstacles. They would also give up some speed to conserve their energy at certain points, in exchange for a burst of acceleration later in the race. Since the internal resistance in batteries can cause the voltage to drop under large currents, very high motor speeds can only be sustained for short periods of time—forcing the drone’s navigation software to pick and choose when to go for that burst of acceleration.

This is where the real-world tests made a real difference. While the current drone navigation software relies exclusively on virtual scenarios, the MIT algorithm factors in scenarios from real trial flights—and the smart decisions made by human pilots to clear obstacles without crashing. The enhanced algorithm can pick between a simulated trajectory and a human-piloted one from one situation to the next.

“If a human pilot is slowing down or picking up speed, that could inform what our algorithm does,” said Tal. “We can also use the trajectory of the human pilot as a starting point, and improve from that to see (things) humans don’t do that our algorithm can figure out [how] to fly faster. Those are some future ideas we’re thinking about.”

Simulation experiments for the drone algorithm.

The MIT team’s research comes at an opportune time. The team predicts that current algorithms are reaching a state of maturity and running up against the limits of what is physically possible with a drone’s design. New algorithms will need to fully exploit not only the drone’s design specs, but also the complex physical vehicle dynamics that can’t be accounted for by simplified models created exclusively via simulation.

By combining virtual and real-world flight path evaluations, optimized trajectories can be found—while minimizing the cost of smashed-up drones along the way.

“These kinds of algorithms are a very valuable step toward enabling future drones that can navigate complex environments very fast,” said Karaman, who is also the director of the MIT Laboratory for Information and Decision Systems. “We are really hoping to push the limits in a way that they can travel as fast as their physical limits will allow.”

While it’ll undoubtedly be looked at with interest by racing teams, the MIT team hopes that the technology could also be put to use in time-critical scenarios such as natural disaster response and search and rescue operations. If drones can navigate obstacle-ridden terrain faster to locate survivors or identify trouble spots, it could mean the difference between life and death.

This technology could also find military applications. The research was partly funded by the U.S. Navy, which has a long-standing interest in drones.

The MIT team’s research shows a promising and innovative next step in the way engineers program drones to navigate their environments in scenarios that push the limits of their capabilities. And while we may still see dramatic wipeouts in the drone racing circuit, it’s possible that this algorithm will make them noticeably less frequent—on and off the racecourse.

Read more about developments in drone technology at Ring-Shaped Drone Flies Twice as Long as Others.