Skip to main content

Towards complexity-aware-decision-making for robots

Published Oct 03, 2022

Is it possible to optimise robots' decision-making so that decisions are good and simple? Yes, doctoral student Elis Stefansson's research has shown that. Now, he has won the Outstanding Student Paper Prize 2022 by the IEEE Control Systems Society Technical Committee on Hybrid Systems. This prize is given annually at the IEEE Conference on Decision and Control.

Artificial intelligence has advanced tremendously in the past decade, developing superhuman performance in, for example, video games. However, this increase in performance often comes with a significant accumulation of needed computer power. One might therefore ask: is all this computing power required? After all, the human brain has less energy consumption than a light bulb and often performs well in various settings with relative ease. In other words, humans use their resources efficiently. Can robots do that too?

In his research, Elis Stefansson, a doctoral student at EECS, addressed this problem by looking at the complexity of a robot's decision-making. A simple way to explain it is that when you want to go from one side of a room to another, there might be several options for how to go. Some of these options are better, and some are worse, but also importantly, some are simpler to do, while others are more complex. Elis has looked at how one can formalise the complexity of a robot's decision and optimise it. 

"I want to find a good decision that is also of low complexity for the robot. There I had first to define what I meant by the complexity of a decision. After I defined it, I looked at the trade-off between performance and complexity of a decision. I tried to find algorithms that optimised this trade-off. Many have only looked at performance in the past, but if you also consider complexity, what works then?"

The addition of complexity in the decision-making, which Elis formally defines using Kolmogorov complexity, introduces new challenges. He shows that dynamic programming, the primary method used for maximising performance alone, cannot be used anymore. 

"Therefore, we have explored other algorithms to obtain control laws with good performance and low complexity. Then we evaluated the methods for simple navigation problems for a robot. Then we see that we get results consistent with intuition and simple in the decision problems. It is the first step towards more general systems."

Elis Stefansson's research contributes to one of the critical questions in control theory: how to develop optimal control algorithms that are easy to implement. And for Elis, the goal of his research is very clear.

"My big motivation is that we need automated decision-making that considers how many resources those decisions require. And there I ask myself, are the large systems that exist today necessary to get the same performance."

Computing Complexity-aware Plans using Kolmogorov complexity (pdf 4.8 MB)