| 1. |
- Fisac, Jaime F., et al.
(författare)
-
Hierarchical Game-Theoretic Planning for Autonomous Vehicles
- 2019
-
Ingår i: 2019 International Conference on Robotics and Automation, (ICRA). - : Institute of Electrical and Electronics Engineers (IEEE). - 9781538660263 ; , s. 9590-9596
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 2. |
- Stefansson, Elis
(författare)
-
Complexity-aware Decision-making with Applications to Large-scale and Human-in-the-loop Systems
- 2023
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 3. |
- Stefansson, Elis, et al.
(författare)
-
Computing Complexity-aware Plans Using Kolmogorov Complexity
- 2021
-
Ingår i: 2021 60th IEEE conference on decision and control (CDC). - : Institute of Electrical and Electronics Engineers (IEEE). ; , s. 3420-3427
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 4. |
- Stefansson, Elis, et al.
(författare)
-
Efficient and Reconfigurable Optimal Planning in Large-Scale Systems Using Hierarchical Finite State Machines
- 2023
-
Ingår i: 2023 62nd IEEE Conference on Decision and Control, CDC 2023. - : Institute of Electrical and Electronics Engineers (IEEE). ; , s. 7380-7387
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 5. |
- Stefansson, Elis, et al.
(författare)
-
Hierarchical Finite State Machines for Efficient Optimal Planning in Large-scale Systems
- 2023
-
Ingår i: Proceedings 2023 European Control Conference, ECC. - : Institute of Electrical and Electronics Engineers (IEEE).
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 6. |
- Stefansson, Elis, et al.
(författare)
-
Human-robot interaction for truck platooning using hierarchical dynamic games
- 2019
-
Ingår i: Proceedings 2019 18TH EUROPEAN CONTROL CONFERENCE (ECC). - : IEEE. ; , s. 3165-3172
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 7. |
- Stefansson, Elis, et al.
(författare)
-
Modeling the decision-making in human driver overtaking
- 2020
-
Ingår i: IFAC PAPERSONLINE. - : Elsevier BV. - 2405-8963. ; , s. 15338-15345
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 8. |
- Stefansson, Elis, et al.
(författare)
-
Sequential alternating least squares for solving high dimensional linear Hamilton-Jacobi-Bellman equation
- 2016
-
Ingår i: IEEE International Conference on Intelligent Robots and Systems. - : IEEE. - 9781509037629 ; , s. 3757-3764
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
