Slide 1Uncertain ROA analysis:Lyapunov function depends on states and uncertaintyMultipliers depend on states and uncertaintySeveral SOS constraints (of differing polynomial degree)Task: FindYields relaxed problem, possibly easier to solve Keeping this V, resolve for original certificateExample impact of ad-hoc, quasi-sequential approach             nnnnxsxVFxsxVFxVxsxs,,,,,,,,,,,221121Development of Analysis Tools for Certification of Flight Control LawsFA9550-05-1-0266, UC Berkeley, Andrew Packard, Honeywell, Pete Seiler, U Minnesota, Gary Balashttp://jagger.me.berkeley.edu/~pack/certifyBest-case study: Nonlinear system with known ROAFacts: Cubic vector field, and if (pos.def.), then•Origin is exponentially stable•ROA is ellipsoid, Test: Apply methodology presented at 9/05 Review on randomly generated problems. Assess ability to compute correct answer, and time to do so…Derive analysis tools applicable to certification and validation of flight control laws.How: quantitative, provable, nonlinear robustness analysisRegion-of-attractionDisturbance attenuation1V1p2p3px0fdxdV1Vx.April 05-Sept 05:Reasonable results for several low-order (<4) nonlinear dynamical systems. Success in obtaining inner/outer bounds on disturbance attenuation levels, state reachability, and region-of-attraction.Sept 05-Feb 06 Accomplishments/Results2 papers accepted to 2006 Amer. Contr. Conf., PhD thesis completed (Weehong Tan), all at project website.Continued to focus on impact of unfavorable growth in computational requirements as a function of state order and uncertainties.Performed a “best-case” assessment of methods on a class of systems with cubic vector fields, and known region-of-attraction.Developed a hybrid “grid to get Lyapunov function, then certify” approach to handle uncertain systems. Showed its usefulness on a 3rd order systemDerived explicit formula (to 2006 CDC) for the parameter-dependent Lyapunov function that is implicitly constructed in a frequency-domain, μ-analysis for linear, uncertain systems. We hope to ultimately treat uncertainty in this “implicit” manner, rather than the explicit approach we currently take. xBxxxxT0B 1:  BxxRxTnApproach: Use non-smooth Lyapunov functions (eg., ptwise max), and verify set containments with SOS proof certificates. Optimizations are nonconvex.Results:Correct answer (within 0.1%) in 99.8% cases. But, compute time grows exponentially in # of states. On P4/2.8Ghz: 2 sec for 4 states, 100s for 8, 4400s for 12.Idea: Grid some variables in some constraints (reduce degree, but now several copies of constraints). high degree poly in x,δ               mknkknnmkkxsxVFxsxVFxVxsxs12211121,,,,,,,,,lower degree, in x only, but many    nnxsxVF,,,22 ,2xshigh degree, but linear in s2   322113232321915.01915.0145.0145.0xxxxxxxxxxxEnabled a fairly tight inner-bound estimate of the robust region-of-attracttion for uncertain, 3rd order system. Gives provable certificates. log(# of states)