Researchers have created a trajectory-planning system for autonomous vehicles that allows them to safely travel from a starting point to a target location even when there are numerous uncertainties in the environment, such as unknown variations in the shapes, sizes, and locations of obstacles.
An autonomous spacecraft exploring the far reaches of the universe enters the atmosphere of a distant exoplanet. The vehicle, as well as the researchers who programmed it, are unfamiliar with this environment. With so much uncertainty, how can the spacecraft plot a course that will keep it from being squashed by a randomly moving obstacle or blown off course by strong winds?
MIT researchers have developed a technique that may aid in the safe landing of this spacecraft. Their method can allow an autonomous vehicle to plot a provably safe trajectory in highly uncertain situations with multiple uncertainties about environmental conditions and objects the vehicle could collide with.
The method could aid a vehicle in finding a safe path around obstacles that move in unpredictable ways and change shape over time. It plots a safe path to a specific location even when the vehicle’s starting point is unknown and it is unclear how the vehicle will move due to environmental disturbances such as wind, ocean currents, or rough terrain.
Future robotic space missions will require risk-aware autonomy to explore remote and extreme worlds where prior knowledge is highly uncertain. To make it work, we needed to reduce the size of the optimization and consider more practical constraints. It took a lot of effort to move from good theory to good application
Ashkan Jasour
According to 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, this is the first technique to address the problem of trajectory planning with many simultaneous uncertainties and complex safety constraints (CSAIL).
“Future robotic space missions will require risk-aware autonomy to explore remote and extreme worlds where prior knowledge is highly uncertain. To accomplish this, trajectory-planning algorithms must reason about uncertainties and deal with complex uncertain models as well as safety constraints” Co-lead author Ashkan Jasour, a former CSAIL research scientist who now works on robotics systems at NASA’s Jet Propulsion Laboratory, concurs.
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
Other methods for finding a safe path forward make assumptions about the vehicle, obstacles, and environment because this trajectory planning problem is so complex. According to Jasour, these methods are too simplistic to be applied in most real-world settings, and thus they cannot guarantee their trajectories are safe in the presence of complex uncertain safety constraints.
“This uncertainty may stem from nature’s randomness or from inaccuracy in the autonomous vehicle’s perception system,” 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.
Their algorithms formulate trajectory planning as a probabilistic optimization problem using this approach. This is a mathematical programming framework that allows the robot to achieve planning objectives like maximizing velocity or minimizing fuel consumption while taking safety constraints like avoiding obstacles into account. According to Jasour, the probabilistic algorithms they developed reason about risk, which is the probability of not meeting those safety constraints and planning objectives.
However, because the problem involves multiple uncertain models and constraints, ranging from the location and shape of each obstacle to the robot’s starting location and behavior, this probabilistic optimization is too complex to solve using standard methods. The researchers used higher-order statistics of uncertainty probability distributions to convert the probabilistic optimization problem into a more straightforward, simpler deterministic optimization problem that can be solved efficiently with existing off-the-shelf solvers.
“To make it work, we needed to reduce the size of the optimization and consider more practical constraints. It took a lot of effort to move from good theory to good application “According to Jasour.
The optimization solver produces a risk-bounded trajectory, which means that if the robot follows the path, the likelihood of colliding with any obstacle is less than a certain threshold, such as 1%. They obtain a sequence of control inputs from this that can safely steer the vehicle to its target region.
Charting courses
They tested the technique on a variety of simulated navigation scenarios. In one, they modeled an underwater vehicle navigating a path from an unknown location to a goal region by navigating a series of oddly shaped obstacles. It was able to reach the target safely 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 with uncertain sizes and positions that could move over time, all while being affected by strong winds. The aircraft reached its target region with a high probability thanks to their system.
The algorithms took between a few seconds and a few minutes to develop a safe trajectory, depending on the complexity of the environment. According to Jasour, the researchers are now working on more efficient processes that would significantly reduce runtime, allowing them to get closer to real-time planning scenarios.
Han is also working on feedback controllers for the system, which will help the vehicle stay closer to its planned trajectory even if it deviates from it at times. He is also working on a hardware implementation, which will allow the researchers to demonstrate their technique on a real robot.
