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.

Autonoma system är viktiga komponenter i utvecklingen av det moderna samhället genom intelligenta transporter, energi och byggnader. Komplexiteten i beslut och mänskliga interaktioner i dessa system växer enormt. Därför utvecklar vi i denna avhandling styrenheter som ger låg beräkningskomplexitet och tar hänsyn till mänsklig interaktion.

I den första delen av avhandlingen formaliserar vi komplexitet i beslutsfattande, föreslår kontrollalgoritmer med låg komplexitet och beräkningseffektiva designmetoder. Mer exakt presenterar vi först ett planeringsobjektiv för styrsystem som modelleras som finita tillståndsmaskiner, vilket ger en explicit avvägning mellan en styrlags prestanda och dess Kolmogorov-komplexitet. Detta mål är svårt att optimera eftersom dynamisk programmering visar sig vara ogenomförbar. Trots detta föreslår vi två heuristiska algoritmer för att beräkna styrlagar med låg komplexitet, vilka empiriskt ger goda resultat. Vi undersöker sedan planering av kortaste vägen i stora system som modelleras som hierarkiska finita tillståndsmaskiner. Vi presenterar en planeringsalgoritm med låg tidskomplexitet som skalar väl med systemstorleken. Beräkningstiden  minskas genom att man i förväg beräknar optimala utgångskostnader för varje maskin och sedan använder dem för att ta bort irrelevanta delar av hierarkin. Vi presenterar också en algoritm för kortaste vägen för grafer, som först hittar en hierarkisk dekomposition och sedan använder den för att snabbt beräkna kortaste vägen. I värsta fall har algoritmen nästan samma tidskomplexitet som Dijkstras algoritm, men är betydligt snabbare om det finns en hierarkisk struktur i grafen. Slutligen visar vi hur man effektivt kan beräkna styrlagar baserade på Hamilton-Jacobi-Bellman-ekvationen med hjälp av tensor dekompositioner.

I den andra delen av avhandlingen behandlar vi human-in-the-loop-system och förutser mänskligt beslutsfattande i sådana system. Vi börjar med att förutse interaktionen mellan en robot och en människa i ett styrsystem, med fokus på en autonom lastbilskonvoj som interagerar med en människostyrd bil. Förutsägelsemodellen är ett hierarkiskt dynamiskt spel med en högupplöst taktisk horisont, som förutsäger omedelbara interaktioner, och en lågupplöst strategisk horisont med, som uppskattar långsiktigt beteende. Modellen ger naturliga och säkra interaktioner i simuleringar. Slutligen söker vi modeller som förklarar mänskligt beslutsfattande i ett scenario med omkörning av en förare. Vi föreslår och analyserar numeriskt riskagnostiska och riskmedvetna beslutsmodeller, som bedömer om en omkörning är önskvärd, och jämför dessa modeller på en experimentell testbädd med mänskliga förare.