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.

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.

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.

 …