Autonomous drones are cautious when navigating the unknown. They creep forward, frequently mapping unfamiliar areas before proceeding lest they crash into undetected objects. But this slowdown isn’t ideal for drones carrying out time-sensitive tasks, such as flying search-and-rescue missions through dense forests.
Now MIT researchers have developed a trajectory-planning model that helps drones fly at high speeds through previously unexplored areas, while staying safe.
The model — aptly named “FASTER” — estimates the quickest possible path from a starting point to a destination point across all areas the drone can and can’t see, with no regard for safety. But, as the drone flies, the model continuously logs collision-free “back-up” paths that slightly deviate from that fast flight path. When the drone is unsure about a particular area, it detours down the back-up path and replans its path. The drone can thus cruise at high speeds along the quickest trajectory while occasionally slowing down slightly to ensure safety.
“We always want to execute the fastest path, but we don’t always know it’s safe. If, as we move along this fastest path, we discover there’s a problem, we need to have a backup plan,” says Jesus Tordesillas, a graduate student in the Department of Aeronautics and Astronautics (AeroAstro) and first author on a paper describing the model being presented at next month’s International Conference on Intelligent Robots and Systems. “We obtain a higher velocity trajectory that may not be safe and a slow-velocity trajectory that’s completely safe. The two paths are stitched together at first, but then one deviates for performance and the other for safety.”
In forest simulations, where a virtual drone navigates around cylinders representing trees, FASTER-powered drones safely completed flight paths about two times quicker than traditional models. In real-life tests, FASTER-powered drones maneuvering around cardboard boxes in a large room achieved speeds of 7.8 meters per second. That’s pushing limits for how fast the drones can fly, based on weight and reaction times, the researchers say.
“That’s about as fast as you can go,” says co-author Jonathan How, the Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics. “If you were standing in a room with a drone flying 7 to 8 meters per second in it, you’d probably take a step back."
The paper’s other co-author is Brett T. Lopez, a former PhD student in AeroAstro and now a postdoc at NASA’s Jet Propulsion Laboratory.
Splitting paths
Drones use cameras to capture environment as voxels, 3D cubes generated from depth information. As the drone flies, each detected voxel gets labeled as “free-known space,” unoccupied by objects, and “occupied-known space,” which contains objects. The rest of the environment is “unknown space.”
FASTER utilizes all of those areas to plan three types of trajectories — “whole,” “safe,” and “committed.” The whole trajectory is the entire path from starting point A to goal location B, through known and unknown areas. To do so, “convex decomposition,” a technique that breaks down complex models into discrete components, generates overlapping polyhedrons that model those three areas in an environment. Using some geometric techniques and mathematical constraints, the model uses these polyhedrons to compute an optimal whole trajectory.
Simultaneously, the model plans a safe trajectory. Somewhere along the whole trajectory, it plots a “rescue” point that indicates the last moment a drone can detour to unobstructed free-known space, based on its speed and other factors. To find a safe destination, it computes new polyhedrons that cover the free-known space. Then, it locates a spot inside these new polyhedrons. Basically, the drone stops in a spot that’s safe but as close as possible to unknown space, enabling a very quick and efficient detour.
Committed trajectory
The committed trajectory consists of the first interval of the whole trajectory, as well as the entire safe trajectory. But this first interval is independent of the safe trajectory, and therefore it is not affected by the braking needed for the safe trajectory.
The drone computes one whole trajectory at a time, while always keeping track of the safe trajectory. But it’s given a time limit: When it reaches the rescue point, it must have successfully computed the next whole trajectory through known or unknown space. If it does, it will continue following the whole trajectory. Otherwise, it diverts to the safe trajectory. This approach enables the drone to maintain high velocities along the committed trajectories, which is key to achieving high overall speeds.
For this to all work, the researchers designed ways for the drones to process all the planning data very quickly, which was challenging. Because the maps are so varied, for instance, the time limit given to each committed trajectory initially varied dramatically. That was computationally expensive and slowed down the drone’s planning, so the researchers developed a method to quickly compute fixed times for all the intervals along the trajectories, which simplified computations. The researchers also designed methods to reduce how many polyhedrons the drone must process to map its surroundings. Both of those methods dramatically increased planning times.
"How to increase the flight speed and maintain safety is one of the hardest problems for drone’s motion planning,” says Sikang Liu, a software engineer at Waymo, formerly Google’s self-driving car project, and an expert in trajectory-planning algorithms. “This work showed a great solution to this problem by enhancing the existing trajectory generation framework. In the trajectory optimization pipeline, the time allocation is always a tricky problem that could lead to convergence issue and undesired behavior. This paper addressed this problem through a novel approach … which could be an insightful contribution to this field."
The researchers are currently building larger FASTER-powered drones with propellers designed to enable steady horizontal flight. Traditionally, drones will need to roll and pitch as they’re flying. But this custom drone would stay completely flat for various applications.
A potential application for FASTER, which has been developed with support by U.S. Department of Defense, could be improving search-and-rescue missions in forest environments, which present many planning and navigational challenges for autonomous drones. “But the unknown area doesn’t have to be forest,” How says. “It could be any area where you don’t know what’s coming, and it matters how quickly you acquire that knowledge. The main motivation is building more agile drones.”
