Recent trends pushing robots into unstructured environments with limited sensors have motivated considerable work on planning under uncertainty and stochastic optimal control, but these methods typically do not provide guaranteed performance. Here we consider the problem of bounding the probability of failure (defined as leaving a finite region of state space) over a finite time for stochastic non-linear systems with continuous state. Our approach searches for exponential barrier functions that provide bounds using a variant of the classical supermartingale result. We provide a relaxation of this search to a semidefinite program, yielding an efficient algorithm that provides rigorous upper bounds on the probability of failure for the original non-linear system. We give a number of numerical examples in both discrete and continuous time that demonstrate the effectiveness of the approach.
AbateAKatoenJ-PLygerosJPrandiniM (2010) Approximate model checking of stochastic hybrid systems. European Journal of Control16: 624–641.
2.
AbbeelPCoatesAQuigleyMNgAY (2006) An application of reinforcement learning to aerobatic helicopter flight. In Proceedings of the Neural Information Processing Systems (NIPS ’07), vol. 19.
3.
AubinJ-PBayenASaint-PierreP (2011) Viability Theory: New DirectionsNew York: Springer.
4.
BeutlerFJ (1973) On two discrete-time system stability concepts and supermartingales. Journal of Mathematical Analysis and Applications44: 464–471.
5.
BlanchiniFMianiS (2008) Set-theoretic Methods in Control. New York: Springer.
6.
BouadiHBouchouchaMTadjineM (2008) Sliding mode control based on backstepping approach for an UAV type-quadrotor. International Journal of Applied Mathematics and Computer Sciences4: 12–17.
7.
BoydSVandenbergheL (2004) Convex Optimization. Cambridge: Cambridge University Press.
8.
BylKTedrakeR (2008) Metastable walking on stochastically rough terrain. In Proceedings of Robotics: Science and Systems IV.
9.
BylKTedrakeR (2009) Metastable walking machines. The International Journal of Robotics Research28: 1040–1064.
CoryRTedrakeR (2008) Experiments in fixed-wing UAV perching. In Proceedings of the AIAA Guidance, Navigation, and Control Conference. AIAA.
12.
DynkinEB (1965) Markov Processes, vol. 1. New York: Academic Press.
13.
GrantMBoydS (2008) Graph implementations for nonsmooth convex programs. In BlondelVBoydSKimuraH (eds), Recent Advances in Learning and Control (tribute to M. Vidyasagar) (Lecture Notes in Control and Information Sciences, vol. XXX). New York: Springer, pp. 95–110.
14.
GrantMBoydS (2011) CVX: Matlab software for disciplined convex programming - version 1.1beta. http://cvxr.com/cvx.
15.
JamesMR (1992) Asymptotic analysis of nonlinear stochastic risk-sensitive control and differential games. Mathematics of Control, Signals, and Systems5: 401–417.
16.
KushnerHJ (1965) On the stability of stochastic dynamical systems. Proceedings of the National Academy of Sciences of the USA53: 8–12.
17.
KushnerHJ (1966) Finite time stochastic stability and the analysis of tracking systems. IEEE Transactions on Automatic Control11(2): 219–227.
18.
LofbergJ (2009) Pre- and post-processing sum-of-squares programs in practice. IEEE Transactions on Automatic Control54: 1007.
McGeerT (1990) Passive dynamic walking. The International Journal of Robotics Research9(2): 62–82.
21.
MegretskiA (2003) Positivity of trigonometric polynomials. In Proceedings of the 42nd IEEE Conference on Decision and Control.
22.
MellingerDMichaelNKumarV (2010) Trajectory generation and control for precise aggressive maneuvers with quadrotors. In Proceedings of the 12th International Symposium on Experimental Robotics (ISER 2010).
23.
PapachristodoulouAPrajnaS (2005) Analysis of non-polynomial systems using the sum of squares decomposition. Positive Polynomials in Control312: 23–43.
24.
PhamQ-CTabareauNSlotineJ-J (2009) A contraction theory approach to stochastic incremental stability. IEEE Transactions on Automatic Control54: 816–820.
25.
PrajnaSJadbabaieAPappasG (2004a). Stochastic safety verification using barrier certificates. In 43rd IEEE Conference on Decision and Control, pp. 929–934.
26.
PrajnaSPapachristodoulouASeilerPParriloPA (2004b) SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB User’s guide, 2.00 edition.
27.
PrajnaS.PapachristodoulouA.WuF. (2004c). Nonlinear control synthesis by sum of squares optimization: A Lyapunov-based approach. In Proceedings of the ASCC 2004.
28.
PrimbsJASungCH (2009) Stochastic receding horizon control of constrained linear systems with state and control multiplicative noise. IEEE Transactions on Automatic Control54(2): 221–230.
29.
RaibertMBlankespoorKNelsonGPlayterRand the BigDog Team (2008) Bigdog, the rough-terrain quadruped robot. In Proceedings of the 17th World Congress, The International Federation of Automatic Control.
30.
RawlingsJBMayneDQ (2009) Model Predictive Control: Theory and Design. Nob Hill Pub.
31.
ShkolnikALevashovMManchesterIRTedrakeR (2011) Bounding on rough terrain with the littledog robot. The International Journal of Robotics Research30: 192–215.
32.
SturmJF (1999) Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optimization Methods and Software11: 625–653.
33.
TanWPackardA (2008) Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming. IEEE Transactions on Automatic Control53: 565–571.
34.
TobenkinMMManchesterIRTedrakeR (2011) Invariant funnels around trajectories using sum-of-squares programming. In Proceedings of the 18th IFAC World Congress.
35.
WesterveltERGrizzleJWChevallereauCChoiJHMorrisB (2007) Feedback Control of Dynamic Bipedal Robot Locomotion. Boca Raton, FL: CRC Press.
36.
YangYLiJChenG (2009) Finite-time stability and stabilization of nonlinear stochastic hybrid systems. Journal of Mathematical Analysis and Applications356: 338–345.
37.
YeagerJC (1998) Implementation and testing of turbulence models for the F18-HARV simulation. Technical report.
