Drones do donuts, figure-eights around obstacles

January 19, 2016 by Adam Conner-Simons
In a forest simulation, algorithms segment space into “obstacle-free regions” and then link them together to find a single collision-free route.

Getting drones to fly around without hitting things is no small task. Obstacle-detection and motion-planning are two of computer science's trickiest challenges, because of the complexity involved in creating real-time flight plans that avoid obstacles and handle surprises like wind and weather.

In a pair of projects announced this week, researchers from MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) demonstrated software that allow drones to stop on a dime to make hairpin movements over, under, and around some 26 distinct obstacles in a simulated "forest."

One team's video shows a small quadrotor doing donuts and figure-eights through an obstacle course of strings and PVC pipes. Weighing just over an ounce and clocking in at 3 and a half inches from rotor to rotor, the drone can fly through the 10-square-foot space at speeds upwards of 1 meter per second.

The team's algorithms, which are available online and were previously used to plan footsteps for CSAIL's Atlas robot at last year's DARPA Robotics Challenge, segment space into "obstacle-free regions" and then link them together to find a single collision-free route.

"Rather than plan paths based on the number of obstacles in the environment, it's much more manageable to look at the inverse: the segments of space that are 'free' for the drone to travel through," says recent graduate Benoit Landry '14 MNG '15, who was first author on a related paper just accepted to the IEEE International Conference on Robotics and Automation (ICRA). "Using free-space segments is a more 'glass-half-full' approach that works far better for drones in small, cluttered spaces."

The video will load shortly

In a second CSAIL project, PhD student Anirudha Majumdar showed off a fixed-wing plane that is guaranteed to avoid obstacles without any advanced knowledge of the space, and even in the face of wind gusts and other dynamics. His approach was to pre-program a library of dozens of distinct "funnels" that represent the worst-case behavior of the system, calculated via a rigorous verification algorithm.

"As the drone flies, it continuously searches through the library to stitch together a series of paths that are computationally guaranteed to avoid obstacles," says Majumdar, who was lead author on a related technical report. "Many of the individual funnels will not be collision-free, but with a large-enough library you can be certain that your route will be clear."

Both papers were co-authored by MIT professor Russ Tedrake; the ICRA paper, which will be presented in May in Sweden, was also co-written by PhD students Robin Deits and Peter R. Florence.

Drones in high-density

A bird might make it seem simple, but flight is a highly complicated endeavor. A flying object can change position in six distinct directions—forward/backward ("surge"), up/down ("heave"), left/right ("sway"), and by rotating front-to-back ("pitch"), side-to-side ("roll"), and horizontally ("yaw").

"At every moment in time there are 12 distinct numbers needed to describe where the system it is and how quickly it is moving, on top of simultaneously tracking other objects in the space that could get in your way," says Majumdar. "Most techniques typically can't handle this sort of complexity in real-time."

One common motion-planning approach is to sample the whole space through algorithms like the "rapidly-exploring random tree." Although often effective, sampling-based approaches are generally less efficient and have trouble navigating small gaps between obstacles.

Landry's team opted to use Deits' new free-space-based technique, which he calls the "Iterative Regional Inflation by semidefinite programming" algorithm (IRIS). They then coupled IRIS with a "mixed-integer semidefinite program" (MISDP) that assigns specific flight movements to each "space-free region" and then executes the full plan.

To sense its surroundings, the drone used motion-capture optical sensors and an on-board inertial measurement unit (IMU) that help estimate the precise positioning of obstacles.

"I'm most impressed by the team's ingenious technique of combining on- and off-board sensors to determine the drone's location," says Jingjin Yu, an assistant professor of computer science at Rutgers University. "This is key to the system's ability to create unique routes for each set of obstacles."

In its current form, MISDP has been optimized such that it can't do real-time planning; it takes an average of 10 minutes to create a route for the obstacle course. But Landry says that making certain sacrifices would let them generate plans much more quickly.

"For example, you could define 'free-space regions' more broadly as links between areas where two or more free-space regions overlap," says Landry. "That would let you solve for a general motion-plan through those links, and then fill in the details with specific paths inside of the chosen regions. Currently we solve both problems at the same time to lower energy consumption, but if we wanted to run plans faster that would be a good option."

Majumdar's software, meanwhile, generates more conservative plans, but can do so in real-time. He first developed a library of 40 to 50 trajectories that are each given an outer bound that the drone is guaranteed to remain within. These bounds can be visualized as "funnels" that the planning algorithm chooses between to stitch together a sequence of steps that allow the drone to plan its flying on the fly.

A flexible approach like this comes with a high level of guarantees that the software will work, even in the face of uncertainties with both the surroundings and the hardware itself. The algorithm can easily be extended to drones of different sizes and payloads, as well as ground vehicles and walking robots.

As for the environment, imagine the drone choosing between making a forceful roll maneuver that will avoid a tree by a large margin, versus flying straight and avoiding a tree by a small amount.

"A traditional approach might prefer the first since avoiding obstacles by a significant amount seems 'safer,'" Majumdar says. "But a move like that actually may be riskier because it's more susceptible to wind gusts. Our method makes these decisions in real-time, which is critical if we want drones to move out of the labs and operate in real-world scenarios."

A clear path to avoiding obstacles

CSAIL researchers have been working on this problem for many years. Professor Nick Roy has been honing algorithms for drones to develop maps and avoid objects in real-time; in November a team led by PhD student Andrew Barry published a video demonstrating algorithms that allow a drone to dart between trees at speeds of 30 miles per hour.

While these two cannot travel quite as fast as Barry's, their maneuvers are generally more complex, meaning that they can navigate in smaller, denser environments.

"Enabling dynamic flight of small, off-the-shelf quadcopters is a marvelous achievement, and one that has many potential applications," Yu says. "With additional development, I can imagine these machines being used as probes in hard-to-reach places, from exploring caves to doing search-and-rescue in collapsed buildings."

Landry, who now works for 3D Robotics in California, is hopeful that other academics will build on and refine the researchers' work, which is all open-source and available on github.

"A big challenge for industry is determining which technologies are actually mature enough to use in real products," Landry says. "The best way to do that is to conduct experiments that focus on all of the corner cases and can demonstrate that algorithms like these will actually work 99.999 percent of the time."

Explore further: Autonomy expert led team in developing "self-flying planes"

More information: Aggressive Quadrotor Flight through Cluttered Environments Using Mixed Integer Programming. groups.csail.mit.edu/robotics-center/public_papers/Landry15b.pdf

Funnel Libraries for Real-Time Robust Feedback Motion Planning. arxiv.org/abs/1601.04037

Related Stories

Autonomy expert led team in developing "self-flying planes"

September 12, 2014

Friends and colleagues were aware, at some level, that Nick Roy, a researcher in MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL), had been using his sabbatical to take on some sort of robotics-related ...

Augmented reality for drones

April 3, 2015

Affordable eyes in the sky, drones have fast become a popular and versatile tool for land mapping. Now ESA-backed startup Sysveo has developed a way of integrating user-made augmented reality objects into a drone's video ...

Snapdragon Flight platform: Qualcomm smartens drones

January 3, 2016

CES will be the venue for numerous headlines for a while as business after business announces a new concept in smart cars, smart kitchens and smarter robots and as booths keen on attracting business partners tell their stories ...

Recommended for you

Inferring urban travel patterns from cellphone data

August 29, 2016

In making decisions about infrastructure development and resource allocation, city planners rely on models of how people move through their cities, on foot, in cars, and on public transportation. Those models are largely ...

How machine learning can help with voice disorders

August 29, 2016

There's no human instinct more basic than speech, and yet, for many people, talking can be taxing. 1 in 14 working-age Americans suffer from voice disorders that are often associated with abnormal vocal behaviors - some of ...

Sponge creates steam using ambient sunlight

August 22, 2016

How do you boil water? Eschewing the traditional kettle and flame, MIT engineers have invented a bubble-wrapped, sponge-like device that soaks up natural sunlight and heats water to boiling temperatures, generating steam ...

3 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

ForFreeMinds
5 / 5 (1) Jan 19, 2016
Congratulations to the engineers who wrote the algorithms and accomplished this. I expect it will be part of future drone capability to make them safer.
Lord_jag
not rated yet Jan 25, 2016
It's amazing that a drone can do all these maneuvers while flying but the idea of a car picking a "tunnel" on ground where it's path doesn't intersect any other objects is somehow impossible to imagine.

antialias_physorg
not rated yet Jan 25, 2016
It's amazing that a drone can do all these maneuvers while flying but the idea of a car picking a "tunnel" on ground where it's path doesn't intersect any other objects is somehow impossible to imagine.

Drones have more degrees of freedom. That makes pathing in full 3D actually easier. Not easier algorithmically, but the chance of having to calculate a complicated path - or even not finding a path at all - becomes much smaller. So even though the extra degree of freedom has to be taken into account the time until a result is reached is usually lower for 3D planning than for 2D planning in a cluttered environment.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.