*Published March 14, 2024, in MIT News.*

If a robot traveling to a destination has just two possible paths, it only needs 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.

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.

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.

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 a CTP, each edge of the graph has a weight associated with it that 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 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

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

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.