Analytical Validation Tools for Safety Critical Systems NASA NRA

Analytical Validation Tools for Safety Critical Systems NASA NRA, 2008-11 (TM: Dr. Christine Belcastro) Participants Univ of Minnesota: Gary Balas UC Berkeley: Andy Packard Barron Associates: Alec Bateman

Our Perspective Linear analysis: provides a quick answer to a related, but different question: Q: How much gain and time-delay variation can be accommodated without undue performance degradation? A: (answers a different question) Here s a scatter plot of margins at 1000 trim conditions throughout envelope Why does linear analysis have impact in nonlinear problems? Domain-specific expertise exists to interpret linear analysis and assess relevance Speed, scalable: Fast, defensible answers on high-dimensional systems Here s a scatter plot of guaranteed region-of-attraction estimates, in the presence of 40% unmodeled dynamics at plant input, and 3 parametric variations, at 1000 trim conditions throughout the envelope Extend validity of the linearized analysis Infinitesimal local (with certified estimates) Address uncertainty

Overview Numerical tools to quantify/certify dynamic behavior Locally, near equilibrium points Analysis considered Region-of-attraction, input/output gain, reachability, establishing local IQCs Methodology Enforce Lyapunov/Dissipation inequalities locally, on sublevel sets Set containments via S-procedure and SOS constraints Bilinear semidefinite programs always feasible Simulation aids nonconvex proof/certificate search Address model uncertainty Parametric Uncertainty Parameter-independent Lyapunov/Storage Fcn Branch-&-Bound Dynamic Uncertainty Local small-gain theorems

Nonlinear Analysis = = ( ), ( ) 0 x f x f x Autonomous dynamics equilibrium point uncertain initial condition, Question: do all solutions converge to ) 0 ( x G x = = ( , ), ( ) 0 , x 0 x f x w f Driven dynamics equilibrium point uncertain inputs, , w w R 2 z = (x ) h Question: how large can get? = = or ( , ) ( , , ) x f x x f x w Uncertain dynamics Unknown, constant parameters, Unmodeled dynamics Same questions

Region-of-Attraction and Reachability V 1 p 2 3 By choice of positive-definite V, maximize so that: Dynamics, equilibrium point ( ), x f x = p = ( ) f x 0 p 1 : ( ) x p x : ( ) 1 is bounded x V x : , ( ) 1 x x x V x : ( ) 1 x V x p: Analyst-defined function whose (well-understood) sub- level sets are to be in region-of- attraction : ( ) x p x x dV dx : ( ) f x 0 x ROAx dVf dx 0 = Given a differential equation and a positive definite function p, how large can get, knowing ( ) e t ( , ) f x w x n n + R Conditions on w dVf x w dx 2 T on all ( , ) : ( ) x V x , w w R w = (0) w 0 R x 2 : ( ) x V x : ( ) x p x R 2 Conclusion on ODE = = ( , ) ( ) p x x e f x w = (0) w 0 R x e w for all solution exists and t , ( ) e t 2

Solution Approach 1. Sum-of-squares to (conservatively) enforce nonnegativity if i i = 2 for some f f g g i 2. Easy (semidefinite program) to check if a given polynomial is SOS 3. S-procedure to (conservatively) enforce set containment 4. Apply S-procedure to Analysis conditions. For (e.g.) reachability, minimize (by choice of si and V) such that ( ) ( ( 2 ( , ) R V s f x w w w dx ) 2 p s R V 1 , x w dV ) + 2 T , x w 5. SDP iteration: Initialize V, then a) Optimize objective by changing S-procedure multipliers b) Optimize objective by changing V c) Iterate on (a) and (b) 6. Initialization of V is important for the iteration to work a) Simulation of system dynamics yields convex constraints which contain all feasible Lyapunov function candidates. This set can be sampled to initialize V

Quantitative improvement on linearized analysis Consider dynamics x Ax = + These SOS/S-procedure formulations are always feasible using quadratic V 23( ) f x where matrix A is Hurwitz, and function f23 consists of 2nd and 3rd degree polynomials, f23(0)=0 A nonempty region-of-attraction is certified Consider dynamics Bw Ax x + = = + + + + ( , ) ( ) ( ) f x w f x g x w For some R>0, 2 3 2 ( ) z Cx h x 2 w R z w where matrix A is Hurwitz, and f2, g2, h2 quadratic, f3 cubic with f2(0,0)=f3(0)=h2(0)=0, and A sI C ) ( 2 2 2 B 1 Consider dynamics Ax x = = + + ( , ) b x x Ew For some R>0, 1 1 x 1 2 ( ) x q 2 1 remains bounded w R x where matrix A is Hurwitz, and functions b bilinear, q quadratic 2

Sum-of-Squares Sum-of-squares (SOS) decompositions (Parrilo) certify nonnegativity, and (with S-procedure) certify set containment conditions A polynomial f, in n real-variables is SOS if it can be expressed as a sum-of-squares of other polys, = j 1 p = 2 f g notate as f n j SDP decides SOS: For f with degree 2d q = i q + such that R 0 f M M 0 n i i 1 Each Mi is s s, where 2 1 + n + n + n + n 2 d d d d = = + s q 2 d d d d 2

(s,q) dependence on n and 2d 2 1 + n + n + n + n 2 d d d d = = + s q 2 d d d d 2 ( ( ) DIE ) ( ) DIE DIE ( ) DIE 2d SOS SOS SOS SOS 2 4 6 8 n 2 3 0 6 6 10 27 15 75 3 4 0 10 20 20 126 35 465 4 5 0 15 50 35 420 70 1990 6 7 0 28 196 84 2646 210 19152 8 9 0 45 540 165 10692 495 109890 10 11 ( 0 2 66 1210 286 33033 1001 = f ( ( ) w w w x f V + , 457743 = = = ) ( ) 4 V V ( ) 2 V ( ) 6 V + , n n n x x w ( V = ) s = 2 = = ( ) 2 1 ) 3 T z f f ( ) 3 ( ) 3 f T ( . .) : e g DIE R z + 1 SOS n n w

Region-of-atraction: 4-state aircraft example Aircraft: Short period longitudinal model, pitch axis, with 1-state linear controller q 2 = + + + Eliminate parameter uncertainty ( , ) ( , ) ( , ) ( , ) z f z u f z u f z u f z u = z 1 1 2 2 3 1 z u = c 1 = c + C A B c location CG , z 1 3 mass , 2 2 T = + ( : ) x p z z Simple form for shape factor: Different Lyapunov function structures Quadratic ( cert=8.6) Fully quartic (quadratic + cubic + quartic) cert=15.3 4000 simulations 3 minutes discover divergent Form LP/ConvexP 0.5 minutes trajectories Get a feasable point 1 minute Assess answer with V 0.5 minutes SDP Iterate from V 0.5 min/iteration, 10 iters Other approaches have deficiencies Directly use commercial BMI solver (PENBMI) cert=15.2, but 6 hours TOTAL 10 minutes (0= x ROA ) 16 1 . : ( ) 15 3 . p x p x Certified set of convergent initial conditions Divergent initial condition Disk in 4-d state space, centered at equilibrium point

4-state aircraft example w/uncertainty Aircraft: Short period longitudinal model, pitch axis, with 1-state linear controller q = z 2 1 = + + + ( , ) ( , ) ( , ) ( , ) z f z u f z u f z u f z u 1 1 2 2 3 CG , location 1 z u = c 1 = c + C A B mass , c z 2 3 Not-uncertain results Quadratic ( cert=8.6) Fully quartic ( cert=15.3) Divergent IC, 2 T = + ( : ) x p z z Same form for shape factor: 9-processor Branch-&-Bound Divide worst region into 9 (0= x ) 16 1 . p 1 15 0.5 2 10 upper bound 0 (V) = 4 lower bound 5 -0.5 (V) = 2 lower bound -1 -1 0 1 1 0 0 1 2 3 4 number of iterations

Unmodeled dynamics: Local small-gain theorem M Local induced gain constraint ( 1) on dVf x w w w h x h x dx x = : z w = = ( ) ( ) w t ( ( ), ( )) ( ( )) t t g k t z t 2 T T on ( , ) ( ) ( ) ( ) l x ( ) V x R z w Implies: Starting from x(0)=0, for all 2,T w M z 2, 2, T T R = = ( ) ( ) z t ( ( ), ( )) ( ( )) h x t x t f x t w t w x 1 causal, globally stable, also satisfies DIE = + : S dSF d V Q 2 2 l ( ) ( ) ( ) 2 on S R dQg d ( , ) ( ) T T ( ) k z ( ) k z z z z l This gives: { : ( ) 2 }invariant, ROA S R { : ( ) S 2 2 {( ,0): ( ) x } } V x R R

4-state aircraft example w/uncertainty 2 1 = + + + ( , ) ( , ) ( , ) ( , ) z f z u f z u f z u f z u 1 1 2 2 3 .75 z C = C P 1 u = c + 1.25 A B cu u c z c c 3 with M, CG 5.1 (7.5) 2.4 (4.1) Results Nominal with Nominal 8.6 (15.3) 4.2 (6.7) 2 T = + ( : ) x p z z 2 T = + + ( : ) x ( ) p z z Q x 2 2 angle-of-attack (x2) 1 1 pitch rate (x1) 0 0 -1 -1 -2 -2 0 5 10 0 5 10 time time

Adaptive System: reachability example analysis Model-reference adaptive systems ( ( + ) ) K = x x x PB x x x m r m Reference model K = r x x PB r r m = + + x A x B u Ed = + x A x B r T x T r = m m m m u K x K r - u Adaptive control plant e Quadratic vector field, marginally stable linearization d x Example: 2-state P, 2-state ref. model, 3 adaptive parameters Insert additional disturbance (d) Bound worst-case effect of external signals (r,d) on tracking error (e) Initial conditions: m x x = ) 0 ( , 0 ) 0 ( T x T r = + = = , 0 ) 0 ( , ) 0 ( A B K A B K B m m Reachability analysis certifies that for all (r,d) with then for all t, 95 . 0 2 2 ( ) 2 e t r 0.8 d r d 0.6 1 0.4 inputs There are particular r and d satisfying r 0 E2 0.2 -1 0 = . 0 95 d -0.2 2 0 5 10 time 15 20 -2 -1 0 1 2 E1 causing e to achieve at some time t. ( e 2= ) 5 . 1 t

Wrapup/Perspective Extensive simulation Proofs of behavior with certificates and linearized analysis Tools that handle (cubic, in x, vector field) 15 states, 3 parameters, unmodeled dynamics, analyze with (V)=2 7 states, 3 parameters, unmodeled dynamics, analyze with (V)=4 Certified answers, however, not clear that these are appropriate for design choices Sproc/SOS/DIE more quantitative than linearization Linearized analysis: quadratic storage functions, infinitesimal sublevel sets SOS/S-procedure always works Work to scale up to large, complex systems analysis (e.g., adaptive flight controls) where certificates are desired.