This thesis considers control systems governed by autonomous decision-makers and humans. We formalise and compute low-complex control policies with applications to large-scale systems, and propose human interaction models for controllers to compute interaction-aware decisions.

In the first part of the thesis, we consider complexity-aware decision-making, formalising the complexity of control policies and constructing algorithms that compute low-complexity control policies. More precisely, first, we consider large-scale control systems given by hierarchical finite state machines (HFSMs) and present a planning algorithm for such systems that exploits the hierarchy to compute optimal policies efficiently. The algorithm can also handle changes in the system with ease. We prove these properties and conduct simulations on HFSMs with up to 2 million states, including a robot application, where our algorithm outperforms both Dijkstra's algorithm and Contraction Hierarchies. 

Second, we present a planning objective for control systems modelled as finite state machines yielding an explicit trade-off between a policy's performance and complexity. We consider Kolmogorov complexity since it captures the ultimate compression of an object on a universal Turing machine. We prove that this trade-off is hard to optimise in the sense that dynamic programming is infeasible. Nonetheless, we present two heuristic algorithms obtaining low-complexity policies and evaluate the algorithms on a simple navigation task for a mobile robot, where we obtain low-complexity policies that concur with intuition. 

In the second part of the thesis, we consider human-in-the-loop systems and predict human decision-making in such systems. First, we look at how the interaction between a robot and a human in a control system can be predicted using game theory, focusing on an autonomous truck platoon interacting with a human-driven car. The interaction is modelled as a hierarchical dynamic game, where the hierarchical decomposition is temporal with a high-fidelity tactical horizon predicting immediate interactions and a low-fidelity strategic horizon estimating long-term behaviour. The game enables feasible computations validated through simulations yielding situation-aware behaviour with natural and safe interactions. 

Second, we seek models to explain human decision-making, focusing on driver overtaking scenarios. The overtaking problem is formalised as a decision problem with perceptual uncertainty. We propose and numerically analyse risk-agnostic and risk-aware decision models, judging if an overtaking is desirable. We show how a driver's decision time and confidence level can be characterised through two model parameters, which collectively represent human risk-taking behaviour. We detail an experimental testbed for evaluating the decision-making process in the overtaking scenario and present some preliminary experimental results from two human drivers.

Denna avhandling studerar styrsystem med autonoma beslutsfattare och människor. Vi formaliserar och beräknar styrlagar av låg komplexitet med tillämpningar på storskaliga system samt föreslår modeller för mänsklig interaktion som kan användas av regulatorer för att beräkna interaktionsmedvetna beslut.

I den första delen av denna avhandling studerar vi komplexitet-medveten beslutsfattning, där vi formaliserar styrlagars komplexitet samt konstruerar algoritmer som beräknar styrlagar med låg komplexitet. Mer precist, först studerar vi storskaliga system givna av hierarkiska finita tillståndsmaskiner (HFSMs) och presenterar en planeringsalgoritm för sådana system som utnyttjar hierarkin för att beräkna optimala styrlagar effektivt. Algoritmen kan också lätt hantera förändringar i systemet. Vi bevisar dessa egenskaper och utför simuleringar på HFSMs med upp till 2 miljoner tillstånd, inklusive en robot-applikation, där vår algorithm överträffar både Dijkstra's algoritm och så kallade Contraction Hierarchies.

För det andra så presenterar vi ett planeringsobjektiv för finita tillståndsmaskiner som ger en explicit avvägning mellan ett styrlags prestanda och komplexitet. Vi använder Kolmogorovkomplexitet då den fångar den ultimata komprimeringen av ett objekt i en universell Turing-maskin. Vi bevisar att detta objektiv är icke-trivial att optimera över i avseendet att dynamisk programming är omöjligt att utföra. Vi presenterar två algoritmer som beräknar styrlagar med låg komplexitet och evaluerar våra algoritmer på ett enkelt navigationsproblem där vi erhåller styrlagar av låg komplexitet som instämmer med intuition.

I den andra delen av denna avhandling behandlar vi reglersystem där en människa interagerar med systemet och studerar hur mänskligt beslutsfattande i sådana system kan förutspås. Först studerar vi hur interaktionen mellan en maskin och en människa i ett reglersystem can förutspås med hjälp av spelteori, med fokus på en självkörande lastbilskonvoj som interagerar med en mänskligt styrd bil. Interaktionen är modellerad som ett hierarkiskt dynamiskt spel, där den hierarkiska indelningen är tidsmässig med en högupplöst taktil horisont som förutspår omedelbara interaktioner samt en lågupplöst strategisk horisont som estimerar långtgående interaktioner. Indelning möjliggör beräkningar som vi validerar via simuleringar där vi får situations-medvetet beteende med naturliga och säkra interaktioner.

För det andra söker vi en model med få parametrar som förklarar mänskligt beteende där vi fokuserar på omkörningar. Vi formaliserar omkörningsproblemet som ett beslutfattningsproblem med perceptuell osäkerhet. Vi presenterar och analyserar numeriskt risk-agnostiska och risk-medvetna beslutsmodeller som avväger om en omkörning är önskvärd. Vi visar hur en förares beslutstid och konfidensnivå kan karakteriserar via två modellparametrar som tillsammans representerar mänskligt risk-beteende. Vi beskriver en experimentell testbädd och presentar preliminära resultat från två mänskliga förare.

In this paper, we consider a planning problem for a large-scale system modelled as a hierarchical finite state machine (HFSM) and develop a control algorithm for computing optimal plans between any two states. The control algorithm consists of two steps: a preprocessing step computing optimal exit costs for each machine in the HFSM, with time complexity scaling linearly with the number of machines, and a query step that rapidly computes optimal plans, truncating irrelevant parts of the HFSM using the optimal exit costs, with time complexity scaling near-linearly with the depth of the HFSM. The control algorithm is reconfigurable in the sense that a change in the HFSM is efficiently handled, updating only needed parts in the preprocessing step to account for the change, with time complexity linear in the depth of the HFSM. We validate our algorithm on a robotic application, comparing it with Dijkstra's algorithm and Contraction Hierarchies. Our algorithm outperforms both.

In this paper, we consider a planning problem for a hierarchical finite state machine (HFSM) and develop an algorithm for efficiently computing optimal plans between any two states. The algorithm consists of an offline and an online step. In the offline step, one computes exit costs for each machine in the HFSM. It needs to be done only once for a given HFSM, and it is shown to have time complexity scaling linearly with the number of machines in the HFSM. In the online step, one computes an optimal plan from an initial state to a goal state, by first reducing the HFSM (using the exit costs), computing an optimal trajectory for the reduced HFSM, and then expand this trajectory to an optimal plan for the original HFSM. The time complexity is near-linearly with the depth of the HFSM. It is argued that HFSMs arise naturally for large-scale control systems, exemplified by an application where a robot moves between houses to complete tasks. We compare our algorithm with Dijkstra's algorithm on HFSMs consisting of up to 2 million states, where our algorithm outperforms the latter, being several orders of magnitude faster.

In this paper, we introduce complexity-aware planning for finite-horizon deterministic finite automata with rewards as outputs, based on Kolmogorov complexity. Kolmogorov complexity is considered since it can detect computational regularities of deterministic optimal policies. We present a planning objective yielding an explicit trade-off between a policy's performance and complexity. It is proven that maximising this objective is non-trivial in the sense that dynamic programming is infeasible. We present two algorithms obtaining low-complexity policies, where the first algorithm obtains a low-complexity optimal policy, and the second algorithm finds a policy maximising performance while maintaining local (stage-wise) complexity constraints. We evaluate the algorithms on a simple navigation task for a mobile robot, where our algorithms yield low-complexity policies that concur with intuition.

We propose models for the decision-making process of human drivers in an overtaking scenario. First, we mathematically formalize the overtaking problem as a decision problem with perceptual uncertainty. Then, we propose and numerically analyze risk-agnostic and risk-aware decision models, which are able to judge whether an overtaking is desirable or not. We show how a driver's decision-making time and confidence level can be primarily characterized through two model parameters, which collectively represent human risk-taking behavior. We detail an experimental testbed for evaluating the decision-making process in the overtaking scenario. Finally, we present some preliminary experimental results from two human drivers. 

The actions of an autonomous vehicle on the road affect and are affected by those of other drivers, whether overtaking, negotiating a merge, or avoiding an accident. This mutual dependence, best captured by dynamic game theory, creates a strong coupling between the vehicle's planning and its predictions of other drivers' behavior, and constitutes an open problem with direct implications on the safety and viability of autonomous driving technology. Unfortunately, dynamic games are too computationally demanding to meet the real-time constraints of autonomous driving in its continuous state and action space. In this paper, we introduce a novel game-theoretic trajectory planning algorithm for autonomous driving, that enables real-time performance by hierarchically decomposing the underlying dynamic game into a long-horizon "strategic" game with simplified dynamics and full information structure, and a short-horizon "tactical" game with full dynamics and a simplified information structure. The value of the strategic game is used to guide the tactical planning, implicitly extending the planning horizon, pushing the local trajectory optimization closer to global solutions, and, most importantly, quantitatively accounting for the autonomous vehicle and the human driver's ability and incentives to influence each other. In addition, our approach admits non-deterministic models of human decision-making, rather than relying on perfectly rational predictions. Our results showcase richer, safer, and more effective autonomous behavior in comparison to existing techniques.

This paper proposes a controller design framework for autonomous truck platoons to ensure safe interaction with a human-driven car. The interaction is modelled as a hierarchical dynamic game, played between the human driver and the nearest truck in the platoon. The hierarchical decomposition is temporal with a high-fidelity tactical horizon predicting immediate interactions and a low-fidelity strategic horizon estimating long-horizon behaviour. The hierarchical approach enables feasible computations where human uncertainties are represented by the quantal response model, and the truck is supposed to maximise its payoff. The closed-loop control is validated via case studies using a driving simulator, where we compare our approach with a short-horizon alternative using only the tactical horizon. The results indicate that our controller is more situation-aware resulting in natural and safe interactions.

This paper presents a technique to efficiently solve the Hamilton-Jacobi-Bellman (HJB) equation for a class of stochastic affine nonlinear dynamical systems in high dimensions. The HJB solution provides a globally optimal controller to the associated dynamical system. However, the curse of dimensionality, commonly found in robotic systems, prevents one from solving the HJB equation naively. This work avoids the curse by representing the linear HJB equation using tensor decomposition. An alternating least squares (ALS) based technique finds an approximate solution to the linear HJB equation. A straightforward implementation of the ALS algorithm results in ill-conditioned matrices that prevent approximation to a high order of accuracy. This work resolves the ill-conditioning issue by computing the solution sequentially and introducing boundary condition rescaling. Both of these additions reduce the condition number of matrices in the ALS-based algorithm. A MATLAB tool, Sequential Alternating Least Squares (SeALS), that implements the new method is developed. The performance of SeALS is illustrated using three engineering examples: an inverted pendulum, a Vertical Takeoff and Landing aircraft, and a quadcopter with state up to twelve.