A new algorithm reduces travel time by identifying shortcuts a robot could take on the way to its destination.

CAMBRIDGE, MA – If a robot traveling to a destination has just two possible paths, it needs only to compare the routes’ travel time and probability of success. But if the robot is traversing a complex environment with many possible paths, choosing the best route amid so much uncertainty can quickly become an intractable problem.

MIT researchers developed a method that could help this robot efficiently reason about the best routes to its destination. They created an algorithm for constructing roadmaps of an uncertain environment that balances the tradeoff between roadmap quality and computational efficiency, enabling the robot to quickly find a traversable route that minimizes travel time.

The algorithm starts with paths that are certain to be safe and automatically finds shortcuts the robot could take to reduce the overall travel time. In simulated experiments, the researchers found that their algorithm can achieve a better balance between planning performance and efficiency in comparison to other baselines, which prioritize one or the other.

This algorithm could have applications in areas like exploration, perhaps by helping a robot plan the best way to travel to the edge of a distant crater across the uneven surface of Mars. It could also aid a search-and-rescue drone in finding the quickest route to someone stranded on a remote mountainside.

“It is unrealistic, especially in very large outdoor environments, that you would know exactly where you can and can’t traverse. But if we have just a little bit of information about our environment, we can use that to build a high-quality roadmap,” says Yasmin Veys, an electrical engineering and computer science (EECS) graduate student and lead author of a paper on this technique.

Veys wrote the paper with Martina Stadler Kurtz, a graduate student in the MIT Department of Aeronautics and Astronautics, and senior author Nicholas Roy, an MIT professor of aeronautics and astronautics and a member of the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). The research will be presented at the International Conference on Robotics and Automation.

Generating graphs

To study motion planning, researchers often think about a robot’s environment like a graph, where a series of “edges,” or line segments, represent possible paths between a starting point and a goal.

Veys and her collaborators used a graph representation called the Canadian Traveler’s Problem (CTP), which draws its name from frustrated Canadian motorists who must turn back and find a new route when the road ahead is blocked by snow.

In a CTP, each edge of the graph has a weight associated with it, which represents how long that path will take to traverse, and a probability of how likely it is to be traversable. The goal in a CTP is to minimize travel time to the destination.

The researchers focused on how to automatically generate a CTP graph that effectively represents an uncertain environment.

“If we are navigating in an environment, it is possible that we have some information, so we are not just going in blind. While it isn’t a detailed navigation plan, it gives us a sense of what we are working with. The crux of this work is trying to capture that within the CTP graph,” adds Kurtz.

Their algorithm assumes this partial information — perhaps a satellite image — can be divided into specific areas (a lake might be one area, an open field another, etc.)

Each area has a probability that the robot can travel across it. For instance, it is more likely a nonaquatic robot can drive across a field than through a lake, so the probability for a field would be higher.

The algorithm uses this information to build an initial graph through open space, mapping out a conservative path that is slow but definitely traversable. Then it uses a metric the team developed to determine which edges, or shortcut paths through uncertain regions, should be added to the graph to cut down on the overall travel time.

Selecting shortcuts

By only selecting shortcuts that are likely to be traversable, the algorithm keeps the planning process from becoming needlessly complicated.

“The quality of the motion plan is dependent on the quality of graph. If that graph doesn’t have good paths in it, then the algorithm can’t give you a good plan,” Veys explains.

After testing the algorithm in more than 100 simulated experiments with increasingly complex environments, the researchers found that it could consistently outperform baseline methods that don’t consider probabilities. They also tested it using an aerial campus map of MIT to show that it could be effective in real-world, urban environments.

In the future, they want to enhance the algorithm so it can work in more than two dimensions, which could enable its use for complicated robotic manipulation problems. They are also interested in studying the mismatch between CTP graphs and the real-world environments those graphs represent.

This research was funded, in part, by the U.S. Army Research Labs under the Distributed Collaborative Intelligent Systems and Technologies Collaborative Research Alliance and by the Joseph T. Corso and Lily Corso Graduate Fellowship.