Complexity in Decision-making with Applications to Large-scale and Human-in-the-loop Systems

QC 20241118

Abstract

Autonomous systems are important components in the development of the modern society through intelligent transportation, energy and buildings. The complexity of decisions and human interactions in these systems is growing tremendously. To this end, this thesis develops controllers yielding low computational complexity and account for human interaction. 

In the first part of the thesis, we formalise complexity of decision-making, propose low-complexity control algorithms and computationally efficient design methods. More precisely, we first present a planning objective for control systems modelled as finite state machines, yielding an explicit trade-off between a policy’s performance and its Kolmogorov complexity. This objective is difficult to optimise because dynamic programming is shown to be infeasible. Nonetheless, we propose two heuristic algorithms for computing low-complexity policies, which are empirically shown to give good results. We then consider shortest-path planning in large systems modelled as hierarchical finite state machines. A novel planning algorithm with low time complexity is shown to scale well with system size. Speed-up is achieved by precomputing optimal exit costs for each machine, and then use them at query time to truncate irrelevant parts of the hierarchy. We also present a shortest-path algorithm for graphs, which first finds a hierarchical decomposition and then use it to compute shortest paths fast. In the worst case, the algorithm has almost the same time complexity as Dijkstra’s algorithm but is significantly faster if there is hierarchical structure in the graph. Finally, we show how to efficiently compute control policies based on the Hamilton-Jacobi-Bellman equation using tensor decompositions. 

In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. We first predict the interaction between a robot and a human in a control system, focusing on an autonomous truck platoon interacting with a human-driven car. The prediction model is a hierarchical dynamic game with a high-fidelity tactical horizon, predicting immediate interactions, and a low-fidelity strategic horizon, estimating long-term behaviour. The model yields natural and safe interactions in simulations. Finally, we seek models that explains human decision-making in a driver overtaking scenario. We propose and numerically analyse risk-agnostic and risk-aware decision models, judging if an overtaking is desirable, and compare these models on an experimental testbed with human drivers.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-356552