Watch: MIT Drone Autonomously Navigates Obstacle Course
A new MIT motion-planning algorithm allows drones to do donuts and figure-eights in object-filled environments.
“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,’” says Majumdar. “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 drones 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,” says Yu. “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.”
“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.”