Transcription of Hamilton-Jacobi-Bellman Equation
1 Hamilton-Jacobi-Bellman EquationFeb 25, 2008 What is it?The Hamilton-Jacobi-Bellman (HJB) Equation is the continuous-time analog to the discrete deterministic dynamic programming algorithm Discrete VS Continuous xk 1=f xk,uk x t =f x t ,u t k 0,..,N0 t TJN xN =gN xN V T,x =h x Jk xk =minuk Uk{gk xk,uk +Jk 1 xk,uk }0=minu U{g x,u tV t,x + xV t,x 'f x,u }h x T 0Tg x t ,u t dtgN xN k=0N 1gk xk,uk HJB Equation Extension of hamilton -Jacobi Equation (classical mechanics) Solution is the optimal cost-to-go function Applications path planning medical financialDerivation Start with continuous time intervalt [0,T] Discretize into N pieces so that =TN Denotexk=x k , k=0,..,Nuk=u k , k=0,..,NDerivation Remember x t =f x t ,u t Approximate the continuous time by xk 1=xk f xk,uk h xN k=0N 1 g xk,uk h x T 0Tg x t ,u t dtDerivationJ* t,x J* t,x : Optimal cost-to-go function for continuous time problem: Optimal cost-to-go function for discrete time approximationDerivation From discrete time DPJN xN =gN xN Jk xk =minuk Uk{gk xk,uk +Jk 1 xk,uk } For the discrete time approximation J* N ,x =h x J* k ,x =minuk Uk{ g x,u J* k 1 ,x f x,u }Derivation Assume that the Taylor series expansion exists Reminder: Taylor series expansion for f x,y f x x,y y = i=0 {1i!}
2 [ x x y y]if x,y } J* k ,x f x,u = i=0 {1i![ t f x,u x]i J* k ,x } Ignoring all higher order terms J* k ,x f x,u = J* k ,x t J* k ,x f x,u x J* k ,x ' o o Derivation Combine J* k ,x =minuk Uk{ g x,u J* k 1 ,x f x,u } J* k ,x f x,u = J* k ,x t J* k ,x f x,u x J* k ,x ' o We get J* k ,x =minu U{ g x,u J* k ,x t J* k ,x + f x,u x J* k ,x ' o }Derivation0=minu U{ g x,u t J* k ,x f x,u x J* k ,x ' o }0=minu U{g x,u t J* k ,x f x,u x J* k ,x ' o } J* k ,x =minu U{ g x,u J* k ,x t J* k ,x + f x,u x J* k ,x ' o }Derivation Take the limit0=minu U{g x,u t J* k ,x f x,u x J* k ,x ' o } 0k k =tlim 0,k ,k =t J* k ,x =J* t,x Assume that0=minu U{g x,u tJ* t,x f x,u xJ* t,x '}J* T,x =h x ClaimIf V(t,x) is a solution to the HJB Equation , V(t,x) equals the optimal cost-to-go function for all t and xProof From0=minu U{g x,u tV t,x f x,u xV t,x '} With any control and state trajectory0 g x t , u t tV t, x t f x t , u t xV t, x t '{ u t |t [0,T]}{ x t |t [0,T]}Proof Substitute in x t =f x t , u t 0 g x t , u t tV t, x t x t xV t, x t '0 g x t , u t dV t, x t dt0 0Tg x t , u t dt 0 TdV t, x t dtdtProof Evaluate0 0Tg x t , u t dt 0 TdV t, x t dtdt0 0Tg x t , u t dt V T, x T V 0, x 0 V 0,x 0 h x T 0Tg x t , u t dt For any state and control trajectoryProof For optimal state and control trajectoryV 0,x 0 =h x* T 0Tg x* t ,u* t dt=J* 0,x 0 {u* t |t [0,T]}{x* t |t [0,T]}V 0,x 0 =J* 0,x 0 HJB Example Consider the simple scalar system x t =u t u t 1 t [0,T]
3 The terminal costV T,x =12x2 HJB Equation0=min u 1{ tV t,x u xV t,x }HJB Example Candidate control policyu* t,x = sgn x Optimal cost-to-go functionJ* t,x =12 max{0, x T t } 2 Check to see if it solves the HJB equationHJB ExampleJ* t,x =12 max{0, x T t } 2 tJ* t,x =max{0, x T t } xJ* t,x =sgn x max{0, x T t }0=min u 1{ tV t,x u xV t,x }=min u 1{1 usgn x }max{0, x T t }LQR and HJB Remember the continuous time LQR x t =Ax t Bu t J=x T 'QTx T 0T x t 'Qx t u t 'Ru t dtg x,u =x'Qx u'Ruh x =x'QTxLQR and HJB The HJB Equation0=minu{x'Qx u'Ru tV t,x Ax Bu xV t,x '} Try a solution of the formV t,x =x'K t xV T,x =x'QTx xV t,x =2K t x tV t,x =x' K t xLQR and HJB Substitute in the HJB equation0=minu{x'Qx u'Ru x' K t x 2x'K t Ax 2x'K t Bu} Differentiate to find minimum0= u{x'Qx u'Ru x' K t x 2x'K t Ax 2x'K t Bu}2B'K t x 2Ru=0 u= R 1B'K t xLQR and HJB Therefore, at minimum u0=x' K t K t A A'K t K t BR 1B'K t Q x0= K t K t A A'K t K t BR 1B'K t Q K t = K t A A'K t K t BR 1B'K t QContinuous-time Riccati EquationLQR and HJB Given that K(t) satisfies the Riccati equationJ* t,x =V t,x =x'K t x And the optimal control policy isu* t,x = R 1B'K t x
