MOBILITY ENGINEERING Produced by SAE Media Group
MOBILITY ENGINEERING
Magazines
Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

Magazine cover

Current Issue

Archives

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.

MIT researchers developed an algorithm that can automatically select the best shortcuts for a robot to take on its way to a destination that will reduce the overall travel time while limiting the likelihood that the robot will meet an impassable obstacle. (Image: Jose-Luis Olivares, MIT iStock)

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.

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.

“It is unrealistic, especially in very large outdoor environments, that you would know exactly where you can and can’t traverse. But if we have just a little bit of information about our environment, we can use that to build a high-quality roadmap,” says Yasmin Veys, an Electrical Engineering and Computer Science (EECS) Graduate Student and Lead Author of a paper on this technique.

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).

Generating Graphs

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.

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 a CTP, each edge of the graph has a weight associated with it, which 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 researchers focused on how to automatically generate a CTP graph that effectively represents an uncertain environment.

“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.

Their algorithm assumes this partial information — perhaps a satellite image — can be divided into specific areas (a lake might be one area, an open field another, etc.)

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.

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

By only selecting shortcuts that are likely to be traversable, the algorithm keeps the planning process from becoming needlessly complicated.

“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 explains.

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 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.

This research was performed by Yasmin Veys, an Electrical Engineering and Computer Science (EECS) Graduate Student for the Massachusetts Institute of Technology (Cambridge, MA). The research was funded, in part, by the U.S. Army Research Labs. For more information, download the Technical Support Package below. ADTTSP-05241

Topics:
Aerospace Artificial Intelligence Automation Computers Electronics Electronics & Computers Robotics Robotics
This Brief includes a Technical Support Package (TSP).
Document cover
Generating Sparse Probabilistic Graphs for Efficient Planning in Uncertain Environments

(reference ADTTSP-05241) is currently available for download from the TSP library.

Don't have an account?

More From SAE Media Group

    Magazine cover
    Aerospace & Defense Technology Magazine

    This article first appeared in the May, 2024 issue of Aerospace & Defense Technology Magazine (Vol. 9 No. 3).

    Read more articles from this issue here.

    Read more articles from the archives here.

    Overview

    The document presents a research study focused on generating sparse, high-quality probabilistic graphs for efficient navigation in uncertain environments. The authors aim to develop an algorithm that constructs roadmaps enabling uncertainty-aware planners to generate low-cost plans while managing the complexities associated with environmental uncertainty.

    The core challenge addressed is the trade-off between graph sparsity and the representation of potential paths in the environment. A sparse graph ensures computational feasibility for planning, while a denser graph may capture more paths but at a higher computational cost. The authors propose a method to optimize the graph structure by selectively adding edges that represent high-quality paths, particularly through uncertain regions. This involves comparing the cost and traversability probability of potential shortcut edges against existing paths.

    The document outlines the limitations of existing approaches, which often rely on hand-designed graphs or deterministic methods that do not account for environmental uncertainty. The authors highlight the need for a more adaptive approach that can efficiently model uncertainty while still providing high-quality navigation solutions.

    The research includes practical experiments conducted in a real-world campus environment, where the authors tested their approach with various configurations of the graph. The results demonstrate that their method allows agents to generate effective navigation plans, even in the presence of uncertainty. The authors provide metrics on graph generation time, the number of vertices and edges, and planning success rates, showcasing the efficiency and effectiveness of their approach.

    In conclusion, the study emphasizes the importance of generating roadmaps that accurately represent environmental uncertainty while remaining computationally efficient. The authors suggest future work could involve using real-world, semantically segmented satellite images for roadmap generation and extending their algorithm to higher dimensions, such as for quadrotor navigation in 3D environments. Overall, the research contributes to the field of robotics and artificial intelligence by providing a framework for improving navigation in uncertain settings, ultimately enhancing the capabilities of autonomous agents.

    Top Stories

    INSIDERDesign

    Feature Image Venus Aerospace’s Rotating Detonation Rocket Engine Completes First Flight...

    INSIDERDesign

    Feature Image Bombardier is Digitally Upgrading its Aircraft Design, Engineering and...

    INSIDERDefense

    Feature Image How the US Army is Advancing Research in Robotics, AI and Autonomy

    INSIDERManned Systems

    Feature Image New Copper Alloy Could Provide Breakthrough in Durability for Military Systems

    Original EquipmentManned Systems

    Feature Image ACT Expo 2025: Heavy-Duty EVs, H2 Trucks and Tariff Talk Dominate Day One

    Technology ReportPower

    Feature Image ICE and Hybrid-Electric Propulsion Show Staying Power

    Webcasts