An autonomous spacecraft exploring the far-flung regions of the universe descends through the atmosphere of a remote exoplanet. The vehicle, and the researchers who programmed it, don’t know much about this environment.

With so much uncertainty, how can the spacecraft plot a trajectory that will keep it from being squashed by some randomly moving obstacle or blown off course by sudden, gale-force winds?

MIT researchers have developed a technique that could help this spacecraft land safely. Their approach can enable an autonomous vehicle to plot a provably safe trajectory in highly uncertain situations where there are multiple uncertainties regarding environmental conditions and objects the vehicle could collide with.

The technique could help a vehicle find a safe course around obstacles that move in random ways and change their shape over time. It plots a safe trajectory to a targeted region even when the vehicle’s starting point is not precisely known and when it is unclear exactly how the vehicle will move due to environmental disturbances like wind, ocean currents, or rough terrain.

This is the first technique to address 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 Engineering and Computer Science and the Computer Science and Artificial Intelligence Laboratory (CSAIL).

“Future robotic space missions need risk-aware autonomy to explore remote and extreme worlds for which only highly uncertain prior knowledge exists. In order to achieve this, trajectory-planning algorithms need to reason about uncertainties and deal with complex uncertain models and safety constraints,” adds co-lead author Ashkan Jasour, a former CSAIL research scientist who now works on robotics systems at the NASA Jet Propulsion Laboratory.

Joining Han and Jasour on the paper is senior author Brian Williams, professor of aeronautics and astronautics and a member of CSAIL. The research will be presented at the IEEE International Conference on Robotics and Automation and has been nominated for the outstanding paper award.

Avoiding assumptions

Because this trajectory planning problem is so complex, other methods for finding a safe path forward make assumptions about the vehicle, obstacles, and environment. These methods are too simplistic to apply in most real-world settings, and therefore they cannot guarantee their trajectories are safe in the presence of complex uncertain safety constraints, Jasour says.

“This uncertainty might come from the randomness of nature or even from the inaccuracy in the perception system of the autonomous vehicle,” Han adds.

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

Using this approach, their algorithms formulate trajectory planning as a probabilistic optimization problem. This is a mathematical programming framework that allows the robot to achieve planning objectives, such as maximizing velocity or minimizing fuel consumption, while considering safety constraints, such as avoiding obstacles. The probabilistic algorithms they developed reason about risk, which is the probability of not achieving those safety constraints and planning objectives, Jasour says.

But because the problem involves different uncertain models 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 probability distributions of the uncertainties to convert that probabilistic optimization into a more straightforward, simpler deterministic optimization problem that can be solved efficiently with existing off-the-shelf solvers.

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

The optimization solver generates a risk-bounded trajectory, which means that if the robot follows the path, the probability it will collide with any obstacle is not greater than a certain threshold, like 1 percent. From this, they obtain a sequence of control inputs that can steer the vehicle safely to its target region.

Charting courses

They evaluated the technique using several simulated navigation scenarios. In one, they modeled an underwater vehicle charting a course from some uncertain position, around a number of strangely shaped obstacles, to a goal region. It was able to safely reach the goal at least 99 percent of the time. They also used it to map a safe trajectory for an aerial vehicle that avoided several 3D flying objects that have uncertain sizes and positions and could move over time, while in the presence of strong winds that affected its motion. Using their system, the aircraft reached its goal 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.

The researchers are now working on more efficient processes that would reduce the runtime significantly, which could allow 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 stick closer to its planned trajectory even if it deviates at times from the optimal course. He is also working on a hardware implementation that would enable the researchers to demonstrate their technique in a real robot.

This research was supported, in part, by Boeing.