MIT researchers present SANDO, a drone path planner with a formal collision-free guarantee

Researchers at MIT have described a trajectory planner for uncrewed aerial vehicles (UAVs) called SANDO, short for Safe AutoNomous trajectory planning for Dynamic unknOwn environments. According to MIT News, which announced the work on 7 October, the system charts a route through surroundings the drone has never mapped, even when objects in them move in ways nobody can predict, and the team proved mathematically that the resulting trajectories avoid collisions. The paper appears in the IEEE Transactions on Robotics. The researchers point to uses such as search-and-rescue flights into collapsed buildings, exploration of hidden tunnel networks in mines, or package delivery in busy neighbourhoods.

Planners of this kind turn camera and sensor data from the aircraft into a path towards its goal. MIT says most existing ones either assume that obstacles in an unknown space stay still, or steer around moving obstacles without any formal promise that no crash will happen; widely used systems that do give such guarantees generally need a static scene or obstacles known in advance. Checking every possible collision in a changing scene would be too slow for practical use, according to the researchers. Lead author Kota Kondo puts it this way in the MIT announcement: “In an unknown dynamic environment, you don’t have many assumptions to rely on.”

SANDO first builds a safety corridor, a chain of connected 3D regions that contain no obstacles and that the drone may fly through. Unlike earlier corridors, this one changes over time. A dedicated module detects moving obstacles, groups them and tracks them to estimate where they are heading. Because their exact future path is unknown, the planner takes each obstacle's maximum speed, works out how far it could get within a given time and wraps it in a sphere covering every point it could reach; the corridor is then shaped around those spheres. A heat-map planner marks crowded “hot” areas so the drone is steered away from them. Inside the corridor, SANDO looks for the fastest route to the goal and keeps revising both corridor and trajectory during the flight. The team simplified the underlying optimisation so the onboard computer can replan quickly.

In simulations, the researchers report, SANDO got to its goal faster than several state-of-the-art systems and had no collisions in any of the environments tested. In 12 test flights with a real UAV, running on the aircraft's own computer and sensors, it avoided all moving obstacles. “The most difficult part of developing SANDO was the math,” Kondo says. Kondo, who recently completed his PhD in aeronautics and astronautics at MIT, wrote the paper with Jesús Tordesillas, now an assistant professor at Comillas Pontifical University in Madrid, and three MIT graduate students, Juan Rached, Lili Sun and Yixuan Jia. Jonathan P. How, who works in MIT's Laboratory for Information and Decision Systems (LIDS) and its Aerospace Controls Laboratory, is the senior author. The Defense Science and Technology Agency of Singapore funded the work in part.

Fei Gao of Zhejiang University in China, an associate professor with no role in the project, summed up the problem the planner targets: “a path that is safe when it is planned may become unsafe as the environment changes.” He credits SANDO's time-varying flight corridors, hard-constrained trajectory optimisation and hardware tests with offering a practical approach for complex dynamic settings. As next steps, the researchers say they could make SANDO less demanding to compute and pair it with machine-learning models so that users can instruct a robot in plain language. MIT News also lists a link to the SANDO code next to the paper.