Elis Stefansson

Elis Stefansson, Karl H. Johansson

We consider optimal planning in a large-scale system formalised as a hierarchical finite state machine (HFSM). A planning algorithm is proposed computing an optimal plan between any two states in the HFSM, consisting of two steps: A pre-processing step that computes optimal exit costs of the machines in the HFSM, with time complexity scaling with the number of machines; and a query step that efficiently computes an optimal plan by removing irrelevant subtrees of the HFSM using the optimal exit costs. The algorithm is reconfigurable in the sense that changes in the HFSM are handled with ease, where the pre-processing step recomputes only the optimal exit costs affected by the change. The algorithm can also exploit compact representations that groups together identical machines in the HFSM, where the algorithm only needs to compute the optimal exit costs for one of the identical machines within each group, thereby avoid unnecessary recomputations. We validate the algorithm on large systems with millions of states and a robotic application. It is shown that our approach outperforms Dijkstra's algorithm, Bidirectional Dijkstra and Contraction Hierarchies.

Elis Stefansson, Karl H. Johansson

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.

Jaime F. Fisac, Eli Bronstein, Elis Stefansson et al.

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.