MIT's SANDO Planner Guarantees Collision-Free Drone Flight Among Moving Obstacles

A safety guarantee where existing planners fall short

Trajectory planners use images and data from a UAV's onboard cameras and sensors to chart a path to the vehicle's goal. According to the MIT team, most existing planners are either designed for unknown static environments, where obstacles do not move, or they avoid dynamic obstacles only loosely, without a formal guarantee that the robot will not crash.

SANDO stands for "Safe AutoNomous trajectory planning for Dynamic unknOwn environments." The researchers say it provides a formal safety guarantee in what lead author Kota Kondo called "the hardest possible environment, where the UAV has no map of the area and there are unknown obstacles moving around." Kondo recently earned his doctorate in aeronautics and astronautics at MIT.

Such guarantees matter in high-stakes cases, for example when a UAV delivers medical supplies to a remote disaster site. But the researchers note that computing every possible crash in a dynamic environment would take too long for real-world deployment.

How SANDO builds a time-sensitive safety corridor

The planner starts by mapping a safety corridor through the environment. This corridor is a series of connected regions of 3D space that the robot can travel through and that are guaranteed not to contain obstacles. Unlike other systems, SANDO creates a corridor that accounts for the possible future movements of dynamic obstacles.

A dedicated module detects, groups and monitors the moving obstacles. The system does not know exactly where an obstacle will go, but it uses the obstacle's maximum velocity to compute how far it could travel in a given timespan. It places a sphere around the obstacle covering the farthest distance it could reach in all directions, and builds the corridor around these spheres.

A heat-map based planner also identifies "hot" regions with many obstacles and steers the UAV away from them, which helps the robot chart a more efficient course around danger zones.

Once a collision-free corridor exists, SANDO optimizes the trajectory inside it to find the fastest path to the goal. As the robot moves, the system adjusts the corridor and reformulates the trajectory so the path stays collision-free until the goal is reached. The researchers used several tricks to make the optimization easier to solve, so the UAV can recalculate trajectories rapidly on its onboard computer and react to sudden changes.

Test results and what comes next

In simulations, SANDO reached the robot's goal faster than several state-of-the-art systems while completely avoiding collisions in all environments. It also avoided all dynamic obstacles in 12 test flights with a real UAV, using the robot's onboard computer and sensors to replan safe trajectories quickly.

Kondo said the hardest part of the project was the math. "When you try to guarantee safety, you need to be rigorous and ensure your theory covers every possible case, even edge cases," he said. Once the guarantee was established, he added, "it was very easy to fly the UAVs."

Fei Gao, an associate professor at Zhejiang University in China who was not involved in the research, said the combination of spatiotemporal planning, formal safety analysis and hardware validation "provides a practical approach to autonomous flight in complex dynamic environments."

The paper appears in the IEEE Transactions on Robotics. Kondo is joined by Jesús Tordesillas of Comillas Pontifical University in Madrid, MIT graduate students Juan Rached, Lili Sun and Yixuan Jia, and senior author Jonathan P. How of MIT. The work is funded in part by the Defense Science and Technology Agency of Singapore.

Where it could be used

The researchers point to search and rescue missions in collapsed buildings, mine exploration through networks of hidden tunnels, and package delivery across a crowded neighborhood. They also describe a scenario in which a UAV flies into a wildfire to gather information for rescuers while avoiding flare-ups and falling branches.

For future work, the team suggests making SANDO more computationally efficient and combining it with machine-learning models that would let users give a robot instructions in plain language.