Quantify the safety of trajectories using occupation measure techniques
Peak estimation is the practice of finding the maximum value of a state function over trajectories of a dynamical system. Instances of peak estimation include finding the speed of a car, the height of an aircraft, the voltage in a power line, etc. Peak estimation can be applied towards safety quantification, such as by measuring the safety of a trajectory by its distance of closest approach to an unsafe set. This project extends the occupation measure framework developed for optimal control and peak estimation. The Moment-Sum-of-Squares hierarchy is employed to obtain convergent bounds to the true peak value when all system data is polynomial.
Our first step to perform this quantification involved measuring the constraint violation using maximin optimization, yielding a safety margin (with safety verified if this margin is negative) (Miller et al., 2021). Peak estimation may also occur for dynamics with compact-valued time-dependent or time-independent uncertainty (including switching) (Miller et al., 2021).
An extension of this includes quantifying the safety of trajectories by finding the distance of closest approach to an unsafe set (missing reference).
All plots certify safety of trajectories with respect to the red half-circle unsafe set. Left plot: a barrier certificate of safety, in which the green curve is the 0-level set. Center-plot: a safety margin, along with the optimizing-trajectory in dark blue. Right-plot: the trajectory that achieves a distance of closest approach, along with the contour of all similarly-close points.
Extensions of the peak/distance estimation framework include adding (bounded) uncertainty into dynamics, allowing for piecewise distance functions (e.g. L1 or L-infinity normed distances), and ensuring the safety of all points on a moving shape with respect to the unsafe set.
Left plot: a distance estimate under an uncertainty process. Center plot: the closest approach with respect to L1 distance. Right plot: closest approach betwen a point on the translating shape (pink square) and the unsafe set.
Peak estimation can be used in a data-driven framework to formulate safety quantification of unknown systems. When the dynamics are input-affine and the corruption is semidefinite-representable (e.g., box-bounded), infinite-dimensional robust counterparts may be applied to drastically reduce the size of PSD matrices (Miller & Sznaier, 2023). This robust counterpart framework can be applied to peak estimation, reachable set estimation, distance estimation, and to the peak-minimizing control problem that finds minimum possible data corruption needed to crash into the unsafe set (Miller & Sznaier, 2023).
Left plot: 40 observations of the Flow dynamical system, with perfect knowledge of the horizontal coordinate and 0.5-bounded-noise in the vertical coordinate. Center plot: Distance estimate for all systems with cubic polynomial dynamics in the vertical coordinate consistent with the data. Right plot: Increasing the data corruption from 0.5 to 0.5499 will allow for a controlled trajectory starting at the initial point to crash into the unsafe set.
Peak and Distance Estimation may be applied to dynamical systems that do not follow Ordinary Differential Equations. Peak estimation may be applied to hybrid systems by modifying hybrid Optimal Control Programs (Miller & Sznaier, 2023). Stochastic Differential Equations (SDEs) can also be analyzed by finding the peak Value-at-Risk (epsilon-quantile) of the state function (Miller et al., 2023).
Left plot: Hybrid system with Left→Top and Right→Bottom transitions. Right plot: sample paths of an SDE, with 50% (dashed) and 85% (solid) probability bounds for the Value-at-Risk of the Distance.
Peak estimation problems can be posed over Time-Delay systems, in which the trajectory dynamics depend on past and present functions of state (Miller et al., 2023).
Histories (gray) are constrained to be inside the cylinder spanned by the two black circles. The histories have no assumption of continuity. The red plane upper-bounds the maximum extent of the horizontal coordinate x1 over the course of system execution.
Relevant Publications
Theses
PhD
Safety Quantification for Nonlinear and Time-Delay Systems using Occupation Measures
This research extends an occupation measure framework to analyze and quantify the safety of dynamical systems. A motivating application of trajectory analysis is in peak estimation, which finds the extreme values of a state function along trajectories. Examples of peak estimation include finding the maximum height of a wave, voltage on a power line, speed of a vehicle, and infected population in an epidemic. Peak estimation can be applied towards safety quantification, such as by measuring the safety of a trajectory by its distance of closest approach to an unsafe set.
A finite-dimensional but nonconvex peak estimation problem can be converted into an infinite-dimensional linear program (LP) in measures, which is in turn bounded by a convergent sequence of semidefinite programs. The LP is posed in terms of an initial, a terminal, and an occupational measure, where the occupation measure contains all possible information about the dynamical systems’ trajectories. This research applies measure-based methods towards safety quantification (e.g. distance estimation, control effort needed to crash), hybrid systems, bounded-uncertain systems (including for data-driven analysis), stochastic systems, and time-delay systems. The modularity of this measure-based framework allows for multiple problem variations to be applied simultaneously (e.g., distance estimation under time-delays), and for optimization models to be synthesized using MATLAB. Solving these optimization problems results in certifiable guarantees on system performance and behavior.
@phdthesis{miller2023thesis,title={Safety Quantification for Nonlinear and Time-Delay Systems using Occupation Measures},author={Miller, Jared},year={2023},school={Northeastern University},bibtex_show={true},selected={true},abbr={PhD},pdf={Thesis_Final.pdf},url={https://repository.library.northeastern.edu/files/neu:4f196v79r},html={https://repository.library.northeastern.edu/files/neu:4f196v79r},slides={Thesis_Presentation_Merged.pdf},poster={Safety_Poster__PhD_Expo.pdf},tag={peakddc}}
Journal Articles
EJC
Peak Estimation of Rational Systems using Convex Optimization
This paper presents algorithms that upper-bound the peak value of a state function along trajectories of a continuous-time system with rational dynamics. The finite-dimensional but nonconvex peak estimation problem is cast as a convex infinite-dimensional linear program in occupation measures. This infinite-dimensional program is then truncated into finite-dimensions using the moment-Sum-of-Squares (SOS) hierarchy of semidefinite programs. Prior work on treating rational dynamics using the moment-SOS approach involves clearing dynamics to common denominators or by adding lifting variables to handle reciprocal terms under new equality constraints. Our solution method uses a sum-of-rational method based on absolute continuity of measures. The Moment-SOS truncations of our program possess lower computational complexity and (empirically demonstrated) higher accuracy of upper bounds on example systems as compared to prior approaches.
@article{miller2023rational,title={{Peak Estimation of Rational Systems using Convex Optimization}},author={Miller, Jared and Smith, Roy S.},year={2024},arxiv={2311.08321},journal={European Journal of Control},pages={101088},issn={0947-3580},doi={https://doi.org/10.1016/j.ejcon.2024.101088},url={https://www.sciencedirect.com/science/article/pii/S0947358024001481},html={https://www.sciencedirect.com/science/article/pii/S0947358024001481},abbr={EJC},bibtex_show={true},publisher={Elsevier},tag={peak},code={http://doi.org/10.5905/ethz-1007-711}}
TAC
Bounding the Distance to Unsafe Sets with Convex Optimization
This work proposes an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance estimation problem is relaxed to a Monge-Kantorovich type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion). The distance estimation problem will be correlatively sparse when the distance objective is separable.
@article{miller2023distance,title={{Bounding the Distance to Unsafe Sets with Convex Optimization}},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2110.14047},archiveprefix={arXiv},primaryclass={math.OC},tag={peak},note={arXiv: 2110.14047},url={https://ieeexplore.ieee.org/document/10149398},pdf={distance_arxiv.pdf},pages={1-15},journal={IEEE Transactions on Automatic Control},abbr={TAC},doi={10.1109/TAC.2023.3285862},code={https://github.com/Jarmill/distance},bibtex_show={true},slides={Distance_CDC_Presentation.pdf},arxiv={2110.14047},selected={true}}
Peak Estimation aims to find the maximum value of a state function achieved by a dynamical system. This problem has been previously cast as a convex infinite-dimensional linear program on occupation measures, which can be approximately solved by a converging hierarchy of moment relaxations. In this letter, we present an algorithm to approximate optimal trajectories if the solutions to these relaxations satisfy rank constraints. We also extend peak estimation to maximin and safety analysis problems, providing a certificate that trajectories are bounded away from an unsafe set.
@article{miller2020recovery,author={Miller, Jared and Henrion, Didier and Sznaier, Mario},journal={IEEE Control Systems Letters},title={{Peak Estimation Recovery and Safety Analysis}},year={2021},volume={5},number={6},tag={peak},pages={1982-1987},doi={10.1109/LCSYS.2020.3047591},abbr={LCSS},url={https://ieeexplore.ieee.org/document/9308943},html={https://ieeexplore.ieee.org/document/9308943},pdf={peak_recovery_arxiv.pdf},code={https://github.com/jarmill/peak/},bibtex_show={true},slides={CDC_peak_recovery.pdf}}
Conference Articles
CDC
Peak Estimation of Time Delay Systems using Occupation Measures
This work proposes a method to compute the maximum value obtained by a state function along trajectories of a Delay Differential Equation (DDE). An example of this task is finding the maximum number of infected people in an epidemic model with a nonzero incubation period. The variables of this peak estimation problem include the stopping time and the original history (restricted to a class of admissible histories). The original nonconvex DDE peak estimation problem is approximated by an infinite-dimensional Linear Program (LP) in occupation measures, inspired by existing measure-based methods in peak estimation and optimal control. This LP is approximated from above by a sequence of Semidefinite Programs (SDPs) through the moment-Sum of Squares (SOS) hierarchy. Effectiveness of this scheme in providing peak estimates for DDEs is demonstrated with provided examples.
@inproceedings{miller2023delay,title={Peak Estimation of Time Delay Systems using Occupation Measures},author={Miller, Jared and Korda, Milan and Magron, Victor and Sznaier, Mario},year={2023},tag={peak},abbr={CDC},slides={Time_Delay_Presentation__NYU.pdf},eprint={2303.12863},archiveprefix={arXiv},primaryclass={math.OC},code={https://github.com/Jarmill/timedelay},booktitle={2023 62nd IEEE Conference on Decision and Control (CDC)},bibtex_show={true},url={https://ieeexplore.ieee.org/document/10384165},html={https://ieeexplore.ieee.org/document/10384165},arxiv={2303.12863}}
CDC
Peak Value-at-Risk Estimation for Stochastic Differential Equations using Occupation Measures
This paper proposes an algorithm to upper-bound maximal quantile statistics of a state function over the course of a Stochastic Differential Equation (SDE) system execution. This chance-peak problem is posed as a nonconvex program aiming to maximize the Value-at-Risk (VaR) of a state function along SDE state distributions. The VaR problem is upper-bounded by an infinite-dimensional Second-Order Cone Program in occupation measures through the use of one-sided Cantelli or Vysochanskii-Petunin inequalities. These upper bounds on the true quantile statistics may be approximated from above by a sequence of Semidefinite Programs in increasing size using the moment-Sum-of-Squares hierarchy when all data is polynomial. Effectiveness of this approach is demonstrated on example stochastic polynomial dynamical systems.
@inproceedings{miller2023chancepeak,title={Peak Value-at-Risk Estimation for Stochastic Differential Equations using Occupation Measures},author={Miller, Jared and Tacchi, Matteo and Sznaier, Mario and Jasour, Ashkan},year={2023},tag={peak},abbr={CDC},booktitle={2023 62nd IEEE Conference on Decision and Control (CDC)},eprint={2303.16064},code={https://github.com/Jarmill/chance_peak},show_bibtex={true},html={https://ieeexplore.ieee.org/document/10383958},url={https://ieeexplore.ieee.org/document/10383958},slides={Chance_Peak_CDC_2023.pdf},bibtex_show={true},doi={10.1109/CDC49753.2023.10383958},primaryclass={math.OC}}
CDC
Bounding the Distance of Closest Approach to Unsafe Sets with Occupation Measures
This paper presents a method to lower-bound the distance of closest approach between points on an unsafe set and points along system trajectories. Such a minimal distance is a quantifiable and interpretable certificate of safety of trajectories, as compared to prior art in barrier and density methods which offers a binary indication of safety/unsafety. The distance estimation problem is converted into a infinite-dimensional linear program in occupation measures based on existing work in peak estimation and optimal transport. The moment-SOS hierarchy is used to obtain a sequence of lower bounds obtained through solving Linear Matrix Inequalities in increasing size, and these lower bounds will converge to the true minimal distance as the degree approaches infinity under mild conditions (e.g. Lipschitz dynamics, compact sets)
ROCOND
Facial Input Decompositions for Robust Peak Estimation under Polyhedral Uncertainty
This work bounds extreme values of state functions for a class of input-affine continuous-time systems that are affected by polyhedral-bounded uncertainty. Instances of these systems may arise in data-driven peak estimation, in which the state function must be bounded for all systems that are consistent with a set of state-derivative data records corrupted under L-infinity bounded noise. Existing occupation measure-based methods form a convergent sequence of outer approximations to the true peak value, given an initial set, by solving a hierarchy of semidefinite programs in increasing size. These techniques scale combinatorially in the number of state variables and uncertain parameters. We present tractable algorithms for peak estimation that scale linearly in the number of faces of the uncertainty-bounding polytope rather than combinatorially in the number of uncertain parameters by leveraging convex duality and a theorem of alternatives (facial decomposition). The sequence of decomposed semidefinite programs will converge to the true peak value under mild assumptions (convergence and smoothness of dynamics).
@inproceedings{miller2022facial_short,title={{Facial Input Decompositions for Robust Peak Estimation under Polyhedral Uncertainty}},journal={IFAC-PapersOnLine},volume={55},number={25},pages={55-60},year={2022},tag={peakddc},slides={ROCOND_Data_Driven_Presentation.pdf},booktitle={10th IFAC Symposium on Robust Control Design (ROCOND)},issn={2405-8963},doi={https://doi.org/10.1016/j.ifacol.2022.09.323},url={https://www.sciencedirect.com/science/article/pii/S2405896322015750},html={https://www.sciencedirect.com/science/article/pii/S2405896322015750},author={Miller, Jared and Sznaier, Mario},keywords={Robust Optimization in Control, Uncertain Systems, Sum-of-Squares, Computational Methods in Control, Safety Certificates},abbr={ROCOND},code={https://github.com/Jarmill/data_driven_occ},bibtex_show={true}}
CDC
Peak Estimation for Uncertain and Switched Systems
Peak estimation bounds extreme values of a function of state along trajectories of a dynamical system. This paper focuses on extending peak estimation to continuous and discrete settings with time-independent and time-dependent uncertainty. Techniques from optimal control are used to incorporate uncertainty into an existing occupation measure-based peak estimation framework, which includes special consideration for handling switching uncertainties. The resulting infinite-dimensional linear programs can be solved approximately with Linear Matrix Inequalities arising from the moment-SOS hierarchy.
@inproceedings{miller2021uncertain,author={Miller, Jared and Henrion, Didier and Sznaier, Mario and Korda, Milan},booktitle={60th IEEE Conference on Decision and Control (CDC)},title={{Peak Estimation for Uncertain and Switched Systems}},year={2021},volume={},number={},tag={peak},pages={3222-3228},doi={10.1109/CDC45484.2021.9683778},slides={CDC_uncertain.pdf},abbr={CDC},url={https://ieeexplore.ieee.org/document/9683778},html={https://ieeexplore.ieee.org/document/9683778},pdf={peak_uncertain_arxiv.pdf},code={https://github.com/jarmill/peak/},selected={true},bibtex_show={true}}
Preprints
Unsafe Probabilities and Risk Contours for Stochastic Processes using Convex Optimization
This paper proposes an algorithm to calculate the maximal probability of unsafety with respect to trajectories of a stochastic process and a hazard set. The unsafe probability estimation problem is cast as a primal-dual pair of infinite-dimensional linear programs in occupation measures and continuous functions. This convex relaxation is nonconservative (to the true probability of unsafety) under compactness and regularity conditions in dynamics. The continuous-function linear program is linked to existing probability-certifying barrier certificates of safety. Risk contours for initial conditions of the stochastic process may be generated by suitably modifying the objective of the continuous-function program, forming an interpretable and visual representation of stochastic safety for test initial conditions. All infinite-dimensional linear programs are truncated to finite dimension by the Moment-Sum-of-Squares hierarchy of semidefinite programs. Unsafe-probability estimation and risk contours are generated for example stochastic processes.
@preprint{miller2024unsafe,title={{Unsafe Probabilities and Risk Contours for Stochastic Processes using Convex Optimization}},author={Miller, Jared and Tacchi, Matteo and Henrion, Didier and Sznaier, Mario},year={2024},eprint={2401.00815},archiveprefix={arXiv},arxiv={2401.00815},tag={peak},bibtex_show={true},code={https://github.com/jarmill/prob_unsafe/},primaryclass={math.OC},note={\href{https://arxiv.org/abs/2401.00815}{[link]}}}
Peak Value-at-Risk Estimation of Stochastic Processes using Occupation Measures
This paper formulates algorithms to upper-bound the maximum Value-at-Risk (VaR) of a state function along trajectories of stochastic processes. The VaR is upper bounded by two methods: minimax tail-bounds (Cantelli/Vysochanskij-Petunin) and Expected Shortfall/Conditional Value-at-Risk (ES). Tail-bounds lead to a infinite-dimensional Second Order Cone Program (SOCP) in occupation measures, while the ES approach creates a Linear Program (LP) in occupation measures. Under compactness and regularity conditions, there is no relaxation gap between the infinite-dimensional convex programs and their nonconvex optimal-stopping stochastic problems. Upper-bounds on the SOCP and LP are obtained by a sequence of semidefinite programs through the moment-Sum-of-Squares hierarchy. The VaR-upper-bounds are demonstrated on example continuous-time and discrete-time polynomial stochastic processes.
@preprint{miller2023chancepeak_long,title={Peak Value-at-Risk Estimation of Stochastic Processes using Occupation Measures},author={Miller, Jared and Tacchi, Matteo and Sznaier, Mario and Jasour, Ashkan},year={2023},tag={peak},archiveprefix={arXiv},code={https://github.com/Jarmill/chance_peak},show_bibtex={true},html={https://arxiv.org/abs/2303.16064},url={https://arxiv.org/abs/2303.16064},slides={Chance_Peak__INFORMS.pdf},bibtex_show={true},primaryclass={math.OC}}
Peak Estimation of Hybrid Systems with Convex Optimization
Peak estimation of hybrid systems aims to upper bound extreme values of a state function along trajectories, where this state function could be different in each subsystem. This finite-dimensional but nonconvex problem may be lifted into an infinite-dimensional linear program (LP) in occupation measures with an equal objective under mild finiteness/compactness and smoothness assumptions. This LP may in turn be approximated by a convergent sequence of upper bounds attained from solutions of Linear Matrix Inequalities (LMIs) using the Moment-Sum-of-Squares hierarchy. The peak estimation problem is extended to problems with uncertainty and safety settings, such as measuring the distance of closest approach between points along hybrid system trajectories and unsafe sets.
@preprint{miller2023hybrid,title={{Peak Estimation of Hybrid Systems with Convex Optimization}},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2303.11490},archiveprefix={arXiv},url={https://arxiv.org/abs/2303.11490},html={https://arxiv.org/abs/2303.11490},arxiv={2303.11490},tag={peak},primaryclass={math.OC},code={https://github.com/Jarmill/hybrid_peak_est},bibtex_show={true}}
Quantifying the Safety of Trajectories using Peak-Minimizing Control
This work quantifies the safety of trajectories of a dynamical system by the perturbation intensity required to render a system unsafe (crash into the unsafe set). Computation of this measure of safety is posed as a peak-minimizing optimal control problem. Convergent lower bounds on the minimal peak value of controller effort are computed using polynomial optimization and the moment-Sum-of-Squares hierarchy. The crash-safety framework is extended towards data-driven safety analysis by measuring safety as the maximum amount of data corruption required to crash into the unsafe set.
@preprint{miller2023crash,title={{Quantifying the Safety of Trajectories using Peak-Minimizing Control}},author={Miller, Jared and Sznaier, Mario},year={2023},arxiv={2303.11896},archiveprefix={arXiv},tag={peakddc},primaryclass={math.OC},bibtex_show={true},url={https://arxiv.org/abs/2303.11896},html={https://arxiv.org/abs/2303.11896},code={https://github.com/Jarmill/crash-safety}}
Analysis and Control of Input-Affine Dynamical Systems using Infinite-Dimensional Robust Counterparts
Input-affine dynamical systems often arise in control and modeling scenarios, such as the data-driven case when state-derivative observations are recorded under bounded noise.
Common tasks in system analysis and control include optimal control, peak estimation, reachable set estimation, and maximum control invariant set estimation. Existing work poses these types of problems as infinite-dimensional linear programs in auxiliary functions with sum-of-squares tightenings. The bottleneck in most of these programs is the Lie derivative nonnegativity constraint posed over the time-state-control set. Decomposition techniques to improve tractability by eliminating the control variables include vertex decompositions (switching), or facial decompositions in the case where the polytopic set is a scaled box. This work extends the box-facial decomposition technique to allow for a robust-counterpart decomposition of semidefinite representable sets (e.g. polytopes, ellipsoids, and projections of spectahedra). These robust counterparts are proven to be equivalent to the original Lie constraint under mild compactness and regularity constraints. Efficacy is demonstrated under peak/distance/reachable set data-driven analysis problems and Region of Attraction maximizing control.
@preprint{miller2023robustcounterpart,title={Analysis and Control of Input-Affine Dynamical Systems using Infinite-Dimensional Robust Counterparts},author={Miller, Jared and Sznaier, Mario},year={2023},eprint={2112.14838},url={https://arxiv.org/abs/2112.14838},html={https://arxiv.org/abs/2112.14838},archiveprefix={arXiv},primaryclass={math.OC},tag={peakddc},bibtex_show={true},slides={MTNS_Robust_Counterpart.pdf},code={https://github.com/Jarmill/data_driven_occ},selected={true}}
