Researchers help robots navigate efficiently in uncertain environments

A new algorithm reduces travel time by identifying shortcuts a robot could take on the way to its destination. 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.