If a robot traveling to a destination has only two possible paths, simply compare the travel times of these paths and the probability of success. However, if a robot traverses a intricate environment with many possible paths, choosing the best route in the face of so much uncertainty can quickly become an intractable problem.
MIT researchers have developed a method that could support this robot efficiently determine the best route to its destination. They created an algorithm for constructing action plans in uncertain environments that balances the trade-off between plan quality and computational efficiency, enabling the robot to quickly find a feasible route, thus minimizing travel time.
The algorithm starts with routes that are certain to be protected and automatically finds shortcuts that the robot can take to reduce the overall travel time. In simulated experiments, the researchers found that their algorithm could achieve a better balance between scheduling performance and efficiency compared to other benchmarks that prioritize one or the other.
This algorithm could have applications in areas such as exploration, perhaps helping a robot plan the best way to travel to the rim of a distant crater on Mars’ rugged surface. It can also support a search and rescue drone find the fastest route to a person stranded on a remote mountainside.
“It’s unrealistic, especially in very enormous outdoor spaces, for you to know exactly where you can and can’t move. However, if we have even a little bit of information about our environment, we can employ it to create a high-quality action plan,” says Yasmin Veys, an electrical engineering and computer science (EECS) graduate and lead author of the book article about this technique.
Veys wrote the paper with Martina Stadler Kurtz, a graduate student in MIT’s Department of Aeronautics and Astronautics, and senior author Nicholas Roy, an MIT professor of aeronautics and astronautics and a member of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL). The research results will be presented at the International Conference on Robotics and Automation.
Chart generation
Veys and her colleagues used a graphical representation of the Canadian Traveler Problem (CTP), which takes its name from the frustration of Canadian drivers having to turn around and find a recent route when the road ahead is blocked by snow.
In CTP, each edge of the graph has a weight associated with it, which represents how long it will take to traverse that path, and the probability of being able to traverse that path. The goal of CTP is to minimize travel time to your destination.
Researchers focused on automatically generating a CTP graph that effectively represents an uncertain environment.
“If we are navigating an environment, it is possible that we have some information, so we will not act in the dark. While this is not a detailed navigation plan, it gives us an idea of what we are working on. The essence of this work is to try to capture this in the CTP chart,” adds Kurtz.
Their algorithm assumes that this partial information – perhaps a satellite image – can be divided into specific areas (a lake could be one area, an open field another, etc.)
For each area, there is a probability that the robot can pass through it. For example, a seine robot is more likely to be able to drive through a field than a lake, so it will be more likely to end up in a field.
The algorithm uses this information to build an initial graph in the open, mapping out a conservative path that is leisurely but definitely possible to follow. It then uses a metric developed by the team to determine which edges or shortcuts through uncertain regions should be added to the graph to reduce the overall travel time.
Choosing shortcuts
By only selecting shortcuts that are likely to be traversable, the algorithm prevents the planning process from becoming unnecessarily intricate.
“The quality of the movement plan depends on the quality of the chart. If there are no good paths in the graph, the algorithm cannot produce a good plan,” explains Veys.
After testing the algorithm in more than 100 simulated experiments with increasingly intricate environments, the researchers found that it could consistently outperform baseline methods that do not take probability into account. They also tested it using an aerial map of the MIT campus to show that it could be effective in real, urban environments.
In the future, they want to improve the algorithm so that it can operate in more than two dimensions, which could enable its application to intricate robotic manipulation problems. They are also interested in exploring the mismatch between CTP graphs and the real-world environments that these graphs represent.
“Robots operating in the real world face uncertainty, whether about available sensor data, prior knowledge of the environment, or how other agents will behave. Unfortunately, dealing with these uncertainties comes at a high computational cost,” says Seth Hutchinson, professor and KUKA chair of robotics at the School of Interactive Computing at Georgia Tech, who was not involved in this research. “This work addresses these issues by proposing a clever approximation scheme that can be used to efficiently compute uncertainty-tolerant plans.”
This research was funded in part by the U.S. Army Research Laboratories under the Distributed Collaborative Bright Systems and Technologies Collaborative Research Alliance and by the Joseph T. Corso and Lily Corso Graduate Fellowship.