New research enables a robot to chart a better course

A figure shows multiple flight pathways as a UAV starts from the center and flies toward 24 goals (dots around perimeter). The flight pathways are mainly red and end in cool colors, showing reduced speed. The rainbow clouds represent obstacles, with cooler colors representing taller obstacles. Credit: Courtesy of the researchers.

By Adam Zewe

In the aftermath of a devastating earthquake, unpiloted aerial vehicles (UAVs) could fly through a collapsed building to map the scene, giving rescuers information they need to quickly reach survivors.

But this remains an extremely challenging problem for an autonomous robot, which would need to swiftly adjust its trajectory to avoid sudden obstacles while staying on course.

Researchers from MIT and the University of Pennsylvania developed a new trajectory-planning system that tackles both challenges at once. Their technique enables a UAV to react to obstacles in milliseconds while staying on a smooth flight path that minimizes travel time.

Their system uses a new mathematical formulation that ensures the robot travels safely to its destination along a feasible path, and that is less computationally intensive than other techniques. In this way, it generates smoother trajectories faster than state-of-the-art methods.

The trajectory planner is also efficient enough for real-time flight using only the robot’s onboard computer and sensors.

Named MIGHTY, the open-source system does not require proprietary software packages that can cost hundreds of thousands of dollars. It could be more readily deployed in a wider variety of real-world settings.

In addition to search-and-rescue, MIGHTY could be utilized in applications like last-mile delivery in urban spaces, where UAVs need to avoid buildings, wires, and people, or in industrial inspection of complex structures, such as wind turbines.

“MIGHTY achieves comparable or better performance using only open-source tools, which means any researcher, student, or company — anywhere in the world — can use it freely. By removing this cost barrier, MIGHTY helps democratize high-performance trajectory planning and opens the door for a much broader community to build on this work,” says Kota Kondo, an aeronautics and astronautics graduate student and lead author of a paper on this trajectory planner.

Kondo is joined on the paper by Yuwei Wu, a graduate student at the University of Pennsylvania; Vijay Kumar, a professor at UPenn; 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 IEEE Robotics and Automation Letters.

Overcoming trade-offs

When Kondo was a child, the Fukushima Daiichi nuclear accident occurred following the Great East Japan Earthquake. With school cancelled, Kondo was stuck at home and watched the news every day as workers explored and secured the reactor site. Some workers still had to enter hazardous areas to contain the damage and assess the situation, exposing them to high doses of radioactive material.

“I became passionate about creating autonomous robots that can go into these dynamic and dangerous situations, then come back and report to humans who stay out of harm’s way,” Kondo says.

This task requires a strong trajectory planner, which is software that decides the path a robot should follow to safely get from point A to point B.

But many existing systems force tradeoffs that limit performance.

While some commercial systems can rapidly generate smooth trajectories, they can cost hundreds of thousands of dollars. Open-source alternatives often underperform compared to commercial solvers or are difficult to use.

With MIGHTY, Kondo and his colleagues developed an open-source system that produces high-quality, smooth trajectories while reacting to obstacles in real-time, and which runs fast enough for flight using only onboard components.

To do this, they overcame a key challenge that limits many open-source systems.

These methods usually estimate how long it will take the robot to get from point A to point B as a first step. From that fixed estimation of travel time, the planner finds the best path to reach the destination.

While using a fixed travel time allows the planner to rapidly generate a trajectory, it has drawbacks. For one, if the UAV must go far out of its way to avoid obstacles, it could be forced to crank up the speed to meet the fixed travel-time budget. This makes it harder to avoid sudden hazards.

A MIGHTY method

Instead, MIGHTY uses a mathematical technique, called a Hermite spline, that optimizes the travel time and flight path together, in a single step, to form a smooth trajectory that can be precisely controlled.

“Optimizing the spatial and temporal components together gets us better results, but now the optimization becomes so much bigger that it is harder to solve in a feasible amount of time,” Kondo says.

The researchers used a clever technique to reduce this computational overhead.

Instead of generating a trajectory from scratch each time, MIGHTY makes an initial guess of a trajectory. Then it refines the trajectory through an iterative optimization, using a map of the scene generated by the UAV’s lidar sensors.

“We can make a decent guess of what the trajectory should be, which is a lot faster than generating the entire thing from nothing,” Kondo says.

This enables MIGHTY to react in real-time to unknown obstacles while keeping the trajectory smooth and minimizing travel time. The system utilizes the UAV’s onboard components, which is important for applications where a robot might travel far from a base station.

In simulated experiments, MIGHTY needed only about 90 percent of the computation time required by state-of-the-art methods, while safely reaching its destination about 15 percent faster than these approaches.

When they tested the system on real robots, it reached a speed of 6.7 meters per second while avoiding every obstacle that appeared in its path.

“With MIGHTY, everything is integrated in one piece. It doesn’t need to talk to any other piece of software to get a solution. This helps us be even faster than some of the commercial solvers,” Kondo says.

In the future, the researchers want to enhance MIGHTY so it can be used to control multiple robots at once and conduct more flight experiments in challenging environments. They hope to continue improving the open-source system based on user feedback.

“MIGHTY makes an important contribution to agile robot navigation by revisiting the trajectory representation itself. Hermite splines have already been successfully used in visual simultaneous localization and mapping, and it is nice to see their advantages now being exploited for trajectory planning in mobile robots. By enabling joint optimization of path geometry, timing, velocity, and acceleration while retaining local control of the trajectory, MIGHTY gives robots more freedom to compute fast, dynamically feasible motions in cluttered environments,” says Davide Scaramuzza, professor and director of the Robotics and Perception Group at the University of Zurich, who was not involved with this research.

This research was funded, in part, by the United States Army Research Laboratory and the Defense Science and Technology Agency in Singapore.