Charting a Safe Path for Autonomous Robots in a Highly Uncertain Environment


May 19, 2022

(News from Nanowerk) An autonomous spacecraft exploring the distant regions of the universe descends through the atmosphere of a distant exoplanet. The vehicle, and the researchers who programmed it, don’t know much about this environment.

With so much uncertainty, how can the spacecraft chart a course that will prevent it from being crushed by a randomly moving obstacle or confused by sudden high winds?

MIT researchers have developed a technique that could help this spacecraft land safely. Their approach can allow an autonomous vehicle to chart a proven safe course in highly uncertain situations where there are multiple uncertainties about environmental conditions and objects the vehicle might collide with. illustration of path planning system for autonomous vehicles MIT researchers have developed a path planning system for autonomous vehicles that allows them to move from a starting point to a target location even when there are many different uncertainties in the environment. (Image: Jose-Luis Olivares, MIT based on figure courtesy of researchers)

The technique could help a vehicle find a safe path around obstacles that move randomly and change shape over time. It plots a safe path to a targeted region even when the vehicle’s starting point is not precisely known and when it is not clear exactly how the vehicle will move due to environmental disturbances such as wind, ocean currents or rough terrain.

It is the first technique to solve the problem of trajectory planning with many simultaneous uncertainties and complex safety constraints, says co-lead author Weiqiao Han, a graduate student in the Department of Electrical and Computer Engineering and the Computer Science and Artificial Intelligence Laboratory (CSAIL).

“Future robotic space missions require risk-aware autonomy to explore remote and extreme worlds for which only highly uncertain prior knowledge exists. To achieve this, path planning algorithms must reason about uncertainties and manage complex uncertain patterns and safety constraints,” adds co-lead author Ashkan Jasour, a former CSAIL researcher who now works on robotic systems at the NASA Jet Propulsion Laboratory.

Join Han and Jasour on the paper (“Risk-limited non-Gaussian trajectory optimization for stochastic nonlinear systems in uncertain environments”) is lead author Brian Williams, professor of aeronautics and astronautics and member of CSAIL. The research will be presented at the IEEE International Conference on Robotics and Automation and was nominated for the Outstanding Paper Award.

Avoid assumptions

Because this path planning problem is so complex, other methods for finding a safe path to follow make assumptions about the vehicle, obstacles, and surroundings. These methods are too simplistic to be applied in most real-world contexts, and therefore cannot guarantee that their trajectories are safe in the presence of complex and uncertain safety constraints, Jasour explains.

“This uncertainty could stem from the randomness of nature or even the imprecision of the autonomous vehicle’s perception system,” adds Han.

Instead of guessing the exact environmental conditions and locations of obstacles, the algorithm they developed reasons about the likelihood of observing different environmental conditions and obstacles at different locations. It would perform these calculations using a map or images of the environment from the robot’s perception system.

Using this approach, their algorithms formulate path planning as a probabilistic optimization problem. It is a mathematical programming framework that allows the robot to achieve planning goals, such as maximizing speed or minimizing fuel consumption, while taking into account safety constraints, such as avoiding obstacles. obstacles. The probabilistic algorithms they developed reason about risk, which is the probability of not meeting those security constraints and planning goals, Jasour explains.

But because the problem involves different uncertain patterns and constraints, from the location and shape of each obstacle to the starting location and behavior of the robot, this probabilistic optimization is too complex to solve with standard methods. The researchers used higher-order statistics of the probability distributions of the uncertainties to convert this probabilistic optimization into a more straightforward and simpler deterministic optimization problem that can be solved efficiently with commercially available solvers.

“Our challenge was to reduce the size of the optimization and consider more practical constraints to make it work. Going from a good theory to a good application took a lot of effort,” says Jasour.

The optimization solver generates a risk-limited trajectory, which means that if the robot follows the trajectory, the probability of it colliding with an obstacle is no greater than a certain threshold, such as 1%. From there, they get a sequence of control inputs that can direct the vehicle safely to its target region.

Cartography course

They evaluated the technique using several simulated navigation scenarios. In one, they modeled an underwater vehicle tracing a course from an uncertain position, around a number of oddly shaped obstacles, to a target region. He was able to reach the goal safely at least 99% of the time. They also used it to map a safe trajectory for an aerial vehicle which avoided several 3D flying objects which have uncertain sizes and positions and which could move in time, while in the presence of strong winds which affected its movement. . Using their system, the aircraft reached its target region with high probability.

Depending on the complexity of the environment, the algorithms took between a few seconds and a few minutes to develop a safe trajectory.

Researchers are now working on more efficient processes that would drastically reduce execution time, potentially allowing them to get closer to real-time planning scenarios, Jasour says.

Han is also developing feedback controllers to apply to the system, which would help the vehicle stay closer to its intended path even if it sometimes deviates from the optimal path. He is also working on a hardware implementation that would allow researchers to demonstrate their technique in a real robot.


Leave a Reply