A quantitative theory of the size–accuracy tradeoff of finite abstractions and their fundamental scalability limits.
Finite abstractions are discrete models of dynamical systems whose trajectories contain all system trajectories. Their main bottleneck is scalability: obtaining sufficient accuracy often requires an abstraction so large that computation becomes infeasible, especially for complex, high-dimensional systems. With Gabriel Gleizer, we develop a statistical, quantitative theory of this size–accuracy tradeoff for autonomous systems through rate–distortion theory—the information theory of lossy compression. Through this theory, we have uncovered the fundamental scalability limits of abstractions of uncontrolled systems.
From a dynamical system to its abstraction. Partition the continuous state space into regions, represent each region by a discrete state, and connect states according to possible transitions between regions. The resulting finite model captures the system’s behaviours, while potentially admitting additional ones. Click to enlarge the complete figure.
Main idea: We view abstractions as encoders compressing system trajectories, and employ rate-distortion theory to quantify their size-accuracy tradeoff. Rate measures abstraction size, while distortion measures accuracy through the spatial average deviation between abstract and system trajectories. We derive a fundamental lower bound on the minimum achievable distortion for a given abstraction size, and conversely on the minimum size needed for a prescribed distortion. The bounds depend on the dynamics through trajectory entropy and the geometry of the trajectory manifold. We demonstrate tightness on certain systems and show how the theory enables the construction of a minimal abstraction for a chaotic system.
Fundamental limits and potentially vast, unexploited scalabity potential. The size-accuracy tradeoff of standard uniform-grid abstractions of a three-dimensional nonlinear system with the paper’s fundamental lower bounds. The large gap suggests substantial room for more efficient abstractions. How much of this gap can be closed remains to be established. Click to enlarge.
G. Delimpaltadakis and G. Gleizer An Information Theory of Finite Abstractions and their Fundamental Scalability Limits
Enforcing state constraints at all times while preserving stability and convergence in feedback optimization.
Feedback optimization steers a control system to a steady state that solves an optimization problem. Despite substantial progress and several successful applications, enforcing state constraints throughout the transient has remained unresolved. Safety enforcement must be reconciled with closed-loop stability, while ensuring that closed-loop equilibria correspond to the optimization problem’s critical points. With Pol Mestres, Jorge Cortés and Maurice Heemels, we address these challenges using safe gradient flows and high-order control barrier functions.
Our controller is defined by a quadratic program solved online and enforces both state and input constraints. We provide conditions for feasibility and well-posedness, safety guarantees, equivalence between equilibria and critical points, and local asymptotic stability of optima. Under additional assumptions, we also establish global asymptotic stability in certain convex cases.
A safe destination is not enough. In this simulation, the proposed method (blue) respects the state constraint throughout the transient; the comparison method (orange) violates it. Click to enlarge.
G. Delimpaltadakis*, P. Mestres*, J. Cortés and W. P. M. H. Heemels Safe Feedback Optimization through Control Barrier Functions * Equal contribution.
Interval Markov decision processes with continuous action spaces
Optimal robust control with continuous actions and uncertain transition probabilities.
Interval Markov decision processes (IMDPs) are finite-state MDps whose
transition probabilities belong to intervals. They model uncertain stochastic environments, and are also widely used as
abstractions of stochastic systems for control synthesis. However, there have been no algorithms for control synthesis for IMDPs with continuous action spaces. Existing methods discretize continuous actions, and thus can be computationally expensive and introduce suboptimality. With Morteza Lahijanian, Manuel Mazo Jr. and Luca Laurenti, we introduce
continuous-action IMDPs (caIMDPs), in which the transition
probability bounds are functions of the action variables.
We study value iteration in caIMDPs for maximizing finite-horizon expected cumulative
rewards under worst-case transition uncertainty. Our main result exactly
decomposes each value-iteration max–min problem into
|Q| maximization problems, where |Q| is the number of states.
This reveals cases solvable through linear or convex programming, depending
on the structure of the transition bounds and action set. We also identify
conditions under which considering only the vertices of a polytopic action
set is sufficient for optimality.
Better rewards with continuous actions.
The figure compares the caIMDP optimal reward (solid line) with
rewards from discrete-action IMDPs with randomly sampled actions
(dashed lines).
Table: computation time vs. suboptimality
Action set
Average CPU time (s)
Average suboptimality
1 sampled action
88
16.51%
8 sampled actions
668
7.86%
27 sampled actions
2,170
5.17%
64 sampled actions
6,225
4.59%
125 sampled actions
9,736
4.32%
caIMDP (continuous actions)
2,212
0%
Suboptimality is the maximum relative reward loss across states,
averaged over trials. The caIMDP solution is the reference.
G. Delimpaltadakis, M. Lahijanian, M. Mazo Jr. and L. Laurenti
Interval Markov Decision Processes with Continuous Action-Spaces
ACM HSCC, 2023
