MIT’s SANDO planner mathematically guarantees collision-free drone flight in unknown environments

Uncrewed aerial vehicles are increasingly being sent into places no human pilot would dare to go: the smoke-choked interior of a raging wildfire, the collapsed skeleton of an earthquake-damaged building, or a maze of unmapped mine tunnels. In these settings, the greatest danger is not the mission itself but the unknown — falling debris, shifting rubble, other aircraft, or obstacles that appear without warning and move in unpredictable ways. Most navigation systems on today’s drones can either promise safety only when the world around them is static and well mapped, or they can react to moving obstacles without ever offering a formal assurance that a crash will not occur. A team of researchers at the Massachusetts Institute of Technology has now closed that gap with a trajectory planning system that provides a mathematical guarantee of collision-free flight, even in environments the robot has never seen and where obstacles are moving.

The system, called SANDO — short for Safe AutoNomous trajectory planning for Dynamic unknOwn environments — was developed by Kota Kondo, who recently completed his doctorate in aeronautics and astronautics at MIT, together with 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, the Ford Professor of Aeronautics and Astronautics at MIT. The work appears in the journal IEEE Transactions on Robotics. Its central claim is striking in its simplicity: the only prior knowledge the planner requires is the maximum speed an obstacle could possibly reach. Given that single number, the algorithm can chart a course through a completely unmapped, dynamic environment and prove, before the drone ever takes off, that the resulting trajectory will remain free of collisions.

“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,” Kondo says. “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.” That guarantee matters because formal safety proofs have long been the missing ingredient in autonomous flight. Trajectory planners typically rely on images and data streamed from a drone’s onboard cameras and sensors to chart a path toward a goal, and most existing approaches fall into one of two camps. Some are designed for unknown but static environments, where obstacles never move. Others handle dynamic obstacles loosely, steering around them heuristically without any formal proof that the robot will not crash. Computing every possible collision scenario in a dynamic world, meanwhile, would take far too long to be useful in real deployments.

“In an unknown dynamic environment, you don’t have many assumptions to rely on,” Kondo explains. “In those types of environments, researchers haven’t yet been able to mathematically guarantee that a trajectory is safe.” The MIT team’s answer was to build rigor into the mathematics from the ground up. Rather than treating safety as a property to be checked after a path is generated, they designed an algorithm whose output is provably safe by construction, covering every possible case, including the awkward edge cases that often break real-world robotic systems. The result is a planner that does not merely hope to avoid obstacles but can demonstrate, mathematically, that it will.

The key to SANDO’s guarantee lies in how it structures the space around the drone. The system begins by mapping out what the researchers call a safety corridor: a series of connected regions of three-dimensional space that the robot can travel through, each of which is guaranteed to contain no obstacles. Safety corridors are not new in themselves, but conventional versions suffer from a fundamental weakness in dynamic settings. A corridor that is clear at one moment can be invaded seconds later by a moving obstacle, silently invalidating the safety proof. SANDO addresses this by making the corridor time-sensitive. Instead of treating obstacles as fixed points, the system explicitly considers their possible future movements when constructing the corridor, so that the guaranteed-clear regions remain valid as the world changes around them.

To make those future predictions possible without knowing exactly where an obstacle will go, SANDO employs a dedicated module that detects, groups, and monitors dynamic obstacles in the environment. For each moving object it identifies, the module uses the obstacle’s maximum velocity to compute how far it could possibly travel within a given timespan. It then encloses the obstacle in a sphere that captures the farthest distance it could reach in any direction over that interval. Even without knowing the obstacle’s actual trajectory, the drone knows the obstacle must remain inside that sphere. SANDO then builds its safety corridor around these spheres, ensuring the planned path can never intersect a region a moving obstacle could occupy. “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,” Kondo says. “But because we consider this time component, we can now guarantee safety into the future.”

Safety alone, however, is not enough if the resulting path is slow or wasteful. To keep flights efficient, SANDO adds a second layer of intelligence: a heat-map-based planner that identifies the “hot” regions of the environment — areas crowded with obstacles — and steers the drone away from them. By biasing the search away from danger zones before the fine-grained trajectory optimization begins, the system charts a more direct and efficient course around hazardous areas rather than threading through them. Once a collision-free safety corridor has been established, SANDO optimizes the trajectory within that corridor to find the fastest possible path to the goal, all while respecting the corridor’s boundaries.

The optimization itself is where much of the engineering effort went. As the robot travels, SANDO continuously adjusts the safety corridor and reformulates the trajectory, ensuring the path remains collision-free all the way to the destination. To make this feasible in real time, the researchers developed a set of mathematical tricks that simplify the optimization problem, allowing the drone’s onboard computer to rapidly recalculate trajectories and react to sudden changes in the environment without relying on offboard processing. The payoff of that rigor, Kondo notes, came in flight testing. “The most difficult part of developing SANDO was the math,” he 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.”

The experimental results support the theory. In simulation, SANDO reached the robot’s goal faster than several state-of-the-art planning systems while completely avoiding collisions in every environment tested. The team then moved from simulation to the physical world, flying a real UAV equipped with SANDO across twelve test flights. In every one of those flights, the system avoided all dynamic obstacles it encountered, using only the robot’s onboard computer and sensors to replan safe trajectories on the fly. For a field in which simulated guarantees frequently dissolve on contact with real sensors, wind, and latency, that record of zero collisions across both simulated and physical trials is a notable demonstration that the mathematical proof translates into practice.

The potential applications extend well beyond the laboratory. A drone carrying SANDO could fly deep into a wildfire, dodging falling branches and sudden flare-ups while gathering critical information for rescuers on the ground. It could search collapsed buildings for survivors, explore networks of hidden mine tunnels, or deliver packages across a crowded neighborhood where pedestrians, vehicles, and other drones share the airspace. The researchers see several directions for future work: making the system even more computationally efficient, and combining it with machine-learning models that would let users issue instructions to the robot in plain language rather than through technical interfaces. The research was funded in part by the Defense Science and Technology Agency of Singapore. For now, SANDO stands as a rare example of a promise kept in robotics: a planner whose safety is not a hope or a statistic, but a theorem — one that holds even when the world ahead is entirely unknown and everything in it is moving.

Subject of Research: Guaranteed collision-free autonomous trajectory planning for drones in dynamic unknown environments

Article Title: Planning system ensures a robot’s flight path will remain collision-free

Article References: Planning system ensures a robot’s flight path will remain collision-free. (n.d.). Original publication

Image Credits: AI Generated

DOI: Not provided

Keywords: UAV, trajectory planning, MIT, SANDO, collision avoidance, autonomous navigation, safety corridor, dynamic obstacles, robotics, IEEE Transactions on Robotics, search and rescue, motion planning