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.
“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.”
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.
“Robots that operate in the real world are plagued by uncertainty, whether in the available sensor data, prior knowledge about the environment, or about how other agents will behave,” says Seth Hutchinson, professor and KUKA Chair for Robotics in the School of Interactive Computing at Georgia Tech, who was not involved with this research. “Unfortunately, dealing with these uncertainties incurs a high computational cost. This work addresses these issues by proposing a clever approximation scheme that can be used to efficiently compute uncertainty-tolerant plans.”
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.
Their algorithm assumes that this partial information—perhaps a satellite image—can be divided into specific areas (e.g., a lake might be one area, an open field another).
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.
“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.
The researchers focused on how to automatically generate a CTP graph that effectively represents an uncertain environment.
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.
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 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.
“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 says.
Published March 14, 2024, in MIT News.
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 road maps of an uncertain environment that balances the tradeoff between road map quality and computational efficiency, enabling the robot to quickly find a traversable route that minimizes travel time.
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.
By only selecting shortcuts that are likely to be traversable, the algorithm keeps the planning process from becoming needlessly complicated.
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
‘This work addresses these issues by proposing a clever approximation scheme that can be used to efficiently compute uncertainty-tolerant plans.’
—Seth Hutchinson
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.
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