Bound extreme values of state functions 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 may be used to quantify the safety of trajectories. 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 (Miller & Sznaier, 2021).
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 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
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
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)
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
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={https://arxiv.org/abs/2303.11490},tag={peak},primaryclass={math.OC},code={https://github.com/Jarmill/hybrid_peak_est},bibtex_show={true}}
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.
@preprint{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},slides={Time_Delay_Presentation__NYU.pdf},eprint={2303.12863},archiveprefix={arXiv},primaryclass={math.OC},code={https://github.com/Jarmill/timedelay},bibtex_show={true},url={https://arxiv.org/abs/2303.12863},html={https://arxiv.org/abs/2303.12863},arxiv={https://arxiv.org/abs/2303.12863}}
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},eprint={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={SIAM_data_driven.pdf},code={https://github.com/Jarmill/data_driven_occ},selected={true}}
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.
@preprint{miller2021distance,title={{Bounding the Distance to Unsafe Sets with Convex Optimization}},author={Miller, Jared and Sznaier, Mario},year={2021},eprint={2110.14047},archiveprefix={arXiv},primaryclass={math.OC},tag={peak},note={arXiv: 2110.14047},url={https://arxiv.org/abs/2110.14047},pdf={distance_arxiv.pdf},code={https://github.com/Jarmill/distance},bibtex_show={true},slides={Distance_CDC_Presentation.pdf},arxiv={2110.14047},selected={true}}
