Uncrewed aerial vehicles (UAVs) could fly deep into the heart of a raging wildfire, avoiding sudden flare-ups and dodging falling tree branches to gather critical information for rescuers. But in this dangerous situation, the UAV could easily be damaged or destroyed by falling debris.
The UAV — and the rescuers who rely on it — would benefit from a new, autonomous navigation system that is guaranteed to avoid collisions, even in completely unfamiliar surroundings.
Developed by MIT researchers, this method plans a flight path for a UAV that eludes unknown obstacles that may move in unpredictable ways. It charts an efficient course through an unmapped environment that is mathematically proven to be safe from collisions.
Many popular navigation systems can only offer formal safety guarantees when the environment is static, or when the obstacles are known in advance.
By enabling the UAV to avoid moving obstacles while it is discovering its environment, this trajectory planner, which the researchers call “SANDO” (for “Safe AutoNomous trajectory planning for Dynamic unknOwn environments”) could be especially useful for applications like search and rescue missions into collapsed buildings, mine explorations through networks of hidden tunnels, or package delivery across a crowded neighborhood.
“In the hardest possible environment, where the UAV has no map of the area and there are unknown obstacles moving around, we established a mathematical guarantee of safety. The only thing the planner needs to know is the top speed the obstacles could reach. Given that, you could use it in any environment, without a map, and you know the UAV is not going to crash into anything,” says Kota Kondo SM ’23, PhD ’26, who recently earned his doctorate in aeronautics and astronautics at MIT and is lead author of a paper on this new system.
He is joined on the paper by Jesús Tordesillas PhD ’22, an assistant professor at Comillas Pontifical University in Madrid; MIT graduate students Juan Rached, Lili Sun, and Yixuan Jia; and senior author Jonathan P. How, a Ford Professor of Aeronautics and Astronautics and a principal investigator in the Laboratory for Information and Decision Systems (LIDS) and the Aerospace Controls Laboratory (ACL) at MIT. The research appears in the IEEE Transactions on Robotics.
Safety first
Trajectory planners use images and data from a UAV’s onboard cameras and sensors to chart a flight path that reaches the vehicle’s goal.
Most existing planners are either designed for unknown static environments, where the obstacles don’t move, or they loosely avoid dynamic obstacles without providing a formal guarantee that the robot won’t crash.
Formal safety guarantees are important in high-stakes situations, such as if a UAV were delivering medical supplies to the site of a remote natural disaster. But trying to compute every possible crash in a dynamic environment would take too long for real-world deployments.
“In an unknown dynamic environment, you don’t have many assumptions to rely on. In those types of environments, researchers haven’t yet been able to mathematically guarantee that a trajectory is safe,” Kondo explains.
The MIT researchers used a rigorous mathematical approach to develop SANDO, their safe trajectory planner. They theoretically proved the algorithm always computes trajectories which are guaranteed to avoid collisions with moving obstacles in unknown environments.
SANDO starts by mapping out a safety corridor through the robot’s environment. This corridor is a series of connected regions of 3D space the robot can travel through, which are guaranteed not to contain any obstacles.
But unlike other systems, SANDO creates a time-sensitive safety corridor that considers the possible future movements of dynamic obstacles. It employs a special module that detects, groups, and monitors dynamic obstacles to estimate where they will move next.
While the system doesn’t know exactly where an obstacle will move in the future, it uses that obstacle’s maximum velocity to compute how far it could possibly go in a certain timespan. It puts a sphere around the obstacle that captures the farthest distance it could travel in all directions.
SANDO builds the safety corridor around these spheres to ensure the UAV will not collide with a moving object.
“In the real world, obstacles are going to move, so the safety corridor you create at one point won’t be useful as things move into the corridor. But because we consider this time component, we can now guarantee safety into the future,” Kondo says.
The system uses a heat-map based planner to identify “hot” regions of the environment with many obstacles and guides the UAV away from these dangerous areas. This helps the robot chart a more efficient course around danger zones.
Fast reactions
Once it has established a collision-free safety corridor, SANDO optimizes the trajectory within that corridor to find the fastest path to reach the goal.
As the robot travels, SANDO adjusts the safety corridor and reformulates the trajectory to ensure the robot’s path remains collision-free until it reaches its goal.
The researchers employed a few tricks to make the optimization easier to solve so the UAV can rapidly recalculate trajectories using its onboard computer, quickly reacting to sudden changes.
“The most difficult part of developing SANDO was the math,” Kondo says. “When you try to guarantee safety, you need to be rigorous and ensure your theory covers every possible case, even edge cases. Once we had that mathematical guarantee, it was very easy to fly the UAVs.”
In simulations, SANDO reached the robot’s goal faster than several state-of-the-art systems while completely avoiding collisions in all environments.
SANDO also avoided all dynamic obstacles in 12 test flights with a real UAV, using the robot’s onboard computer and sensors to rapidly replan safe trajectories.
In the future, researchers could make SANDO more computationally efficient and combine the system with machine-learning models that allow the user to give instructions to a robot using plain language.
A central challenge in autonomous flight is that a path that is safe when it is planned may become unsafe as the environment changes. SANDO addresses this challenge with time-varying safe flight corridors and hard-constrained trajectory optimization that supports frequent onboard replanning. Its combination of spatiotemporal planning, formal safety analysis, and hardware validation provides a practical approach to autonomous flight in complex dynamic environments,” says Fei Gao, an associate professor at Zhejiang University in China, who was not involved with this research.
This research is funded, in part, by the Defense Science and Technology Agency of Singapore.
