Drones Do Donuts, Figure-Eights Around Obstacles

Estimated reading time: 6 minutes

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.”

Page 2 of 4

• < Previous Page
• Next Page >