Autonomous Decision Making Under Uncertainty

In an age of self-driving cars, industrial robots, and intelligent systems that help humans in a variety of situations, time and computational resources are valuable assets. These systems are required to react quickly to circumstances in a changing environment, and under conditions in which information is lacking (i.e., conditions of uncertainty). Furthermore, economic constraints limit the complexity of elements such as hardware, and the systems must be cheap enough for potential consumers to be willing to pay for them.

Research conducted at the Technion – Israel Institute of Technology and published in the International Journal of Robotics Research presents a theoretical and computational breakthrough in this context: the simplification of planning problems and decision-making under uncertainty in a way that reduces the amount of data that the computer is required to analyze.

The study was headed by Professor Vadim Indelman, head of the Autonomous Navigation and Perception Lab (ANPL) in the Faculty of Aerospace Engineering, and Khen Elimelech, who recently completed his doctorate in the Technion Autonomous Systems Program (TASP).

Prof. Vadim Indelman

“We demonstrate that we can significantly reduce computation time, without harming the successful execution of the task,” explained the researchers. “We also demonstrate that computation efforts can be reduced even further if we accept a certain loss in performance – loss that our approach can evaluate online. In an age of self-driving cars and other robots, this is an approach likely to enable autonomous online decision-making in challenging scenarios, reduce response times, and achieve considerable savings in the cost of hardware and other resources.”

Prof. Indelman’s research deals with autonomous decision making under uncertainty – a fundamental problem in AI and robotics. This capability is particularly essential for autonomous agents that are required to perform reliably over time, under conditions of uncertainty and in a changing environment. Furthermore, in many cases the agent does not have direct access to the problem’s state variables, and it functions based on a probability distribution or “belief”. This belief reflects the knowledge that the agent possesses about itself and its environment, based on probabilistic models, actions performed, and measurements obtained from its sensors.

Khen Elimelech

One of the key directions explored by the research group is computationally efficient decision-making under these conditions, also known as “belief space planning” (BSP). Solving this problem (i.e., calculating the entire set of optimal actions or policies necessary to achieve the goal) requires that potential actions be evaluated under a reward or cost function, such as the distance to the goal or an “uncertainty” measure. According to the researchers, this challenge requires the prediction of how the “belief” will develop in the future for different possible actions, while predicting different future scenarios. As a result, decision-making under these conditions is computationally costly, which challenges the autonomous action of intelligent agents in real time. Additionally, in problems with numerous state variables (for example, when the environment changes or is not known in advance), the computational challenge is even greater. All the above are accompanied by economic considerations, time constraints, and computation time, which mandate a reduction in the necessary computational resources. Therefore, the simplification of decision-making under uncertainty problems is an important goal in these research directions.

Prof. Indelman’s research group refers to all these aspects in the development of simplification approaches, which enable these problems to be solved in a way that is more computationally efficient, for example, through the sparsification of matrices. Crucially, these approaches are accompanied with performance guarantees that quantify the worst-case degradation in performance as a result of the simplification process; such guarantees are of key importance in safety-critical applications such as autonomous driving.

The researchers’ findings lay the foundations for solving decision-making problems through simplification and demonstrate that these approaches are able to lead to considerable savings in computation times, without significant loss in terms of outcomes.

Recently, it was announced that doctoral student Khen Elimelech, who led the study, will receive the Outstanding Ph.D. Research Award, The Israeli Smart Transportation Research Center (ISTRC).

The ANPL team

The study was sponsored by the Israel Science Foundation.

For the full article in the International Journal of Robotics Research click here.