最优控制课程课件II-4.动态规划-

........................................第⼋讲：动态规划最优控制的数学理论之四张杰⼈⼯智能学院中国科学院⼤学复杂系统管理与控制国家重点实验室中国科学院自动化研究所2017年10月12日Jie,Zhang(CASIA)OptimalControl最优控制的数学理论1/68........................................TableofContents1回顾：变分法、极值原理求解最优控制2动态规划⽅法3动态规划求解离散最优控制4离散时间线性⼆次性最优控制Jie,Zhang(CASIA)OptimalControl最优控制的数学理论2/68........................................下周四，10月19日随堂考试开卷考试，禁⽌电⼦设备，自带纸笔计算题、证明题、问答题包括截⽌考试当日的所有内容折算占平时成绩中的10分考试时间，10月19日课上后半节Jie,Zhang(CASIA)OptimalControl最优控制的数学理论3/68........................................回顾：变分法、极值原理求解最优控制TableofContents1回顾：变分法、极值原理求解最优控制2动态规划⽅法3动态规划求解离散最优控制4离散时间线性⼆次性最优控制Jie,Zhang(CASIA)OptimalControl最优控制的数学理论4/68........................................回顾：变分法、极值原理求解最优控制最优控制问题最优控制问题问题1(最优控制问题)1被控对的状态⽅程为_x(t)=f(x(t);u(t);t);x(t0)=x0:2容许控制,u2U;x2X:3标集,x(tf)2SS=[t0;1)fx(tf)2Rn:m(x(tf);tf)=0g4求分连续的u，以最小化性能指标J(u)=h(x(tf);tf)+∫tft0g(x(t);u(t);t)dt:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论5/68........................................回顾：变分法、极值原理求解最优控制庞特里亚⾦极小值原理Pontryagin极小值原理定理1(庞特里亚⾦极小值原理)上问题得到最优控制u(t)的要条件为（TPBVP）极值条件：对任意容许控制u′(t)H(x(t);u(t);p(t);t)H(x(t);u′(t);p(t);t):规范⽅程：状态(state)⽅程:_x(t)=+@H@p(x(t);u(t);p(t);t);协态(costate)⽅程:_p(t)=@H@x(x(t);u(t);p(t);t):边界条件(用于理标集)：[@h@x(x(tf);tf)p(tf)]
xf+[H(x(tf);u(tf);p(tf);tf)+@h@t(x(tf);tf)]tf=0:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论6/68........................................回顾：变分法、极值原理求解最优控制庞特里亚⾦极小值原理极值原理求解最优控制的过程构造Hamiltonian，求容许控制的极值条件，以协态和状态表示最优控制最优控制代⼊规范⽅程，得到关于最优状态、协态的常微分⽅程组根据边界条件和初值获得微分⽅程组的边界条件直接求解或使用数值⽅法求解两点边值问题开环控制Jie,Zhang(CASIA)OptimalControl最优控制的数学理论7/68........................................回顾：变分法、极值原理求解最优控制开环控制与闭环控制控制的形式：开环控制定义1(开环控制)若控制律形如u(t)=ϕ(x(t0);t);(1)称之为开环控制时刻打开控制器被控对象0(())(),xtutt0t()xtJie,Zhang(CASIA)OptimalControl最优控制的数学理论8/68........................................回顾：变分法、极值原理求解最优控制开环控制与闭环控制控制的形式：闭环控制定义2(闭环控制)若控制律形如u(t)=ϕ(x(t);t);(2)称之为闭环控制控制器被控对象()xt(())(),xutttJie,Zhang(CASIA)OptimalControl最优控制的数学理论9/68........................................回顾：变分法、极值原理求解最优控制开环控制与闭环控制课程内容最优控制的数学理论-经典变分法-庞特里亚⾦极值原理-动态规划⽅法-微分博弈最优控制的智能⽅法-强化学习与自适应动态规划-模型预测控制-模糊控制-平⾏控制与平⾏学习Jie,Zhang(CASIA)OptimalControl最优控制的数学理论10/68........................................回顾：变分法、极值原理求解最优控制开环控制与闭环控制变分法和最优控制的重要⼈物雅各布伯努利约翰伯努利莱布尼茨牛顿伽利略费马洛必达欧拉拉格朗日哈密尔顿雅可比高斯利普西茨克莱因维尔斯特拉斯Bolza卡拉西奥多里Bliss希尔伯特Hamel庞特里亚金HesteneIsaacsBellmanGamkrelidzeBoltyanskii变分问题变分法早期工作最优控制--美国团队最优控制苏联团队师生影响师生(隔代)互相影响Jie,Zhang(CASIA)OptimalControl最优控制的数学理论11/68........................................回顾：变分法、极值原理求解最优控制开环控制与闭环控制庞特里亚⾦极小值原理第三讲，提出庞特里亚⾦极小值原理（PMP）第五讲，p47-50，化欧拉⽅程为没有控制的PMP第六讲，利用变分法求得开集上的PMP（⼀阶条件）第七讲，简要证明了非连续、非开集上的PMP（极值条件）动态规划⽅法也可在特殊情况下得到庞特里亚⾦极小值原理！Jie,Zhang(CASIA)OptimalControl最优控制的数学理论12/68........................................动态规划⽅法TableofContents1回顾：变分法、极值原理求解最优控制2动态规划⽅法3动态规划求解离散最优控制4离散时间线性⼆次性最优控制Jie,Zhang(CASIA)OptimalControl最优控制的数学理论13/68........................................动态规划⽅法动态规划⽅法的发展1944年，冯诺依曼在名著TheoryofGamesandEconomicBehavior中使用倒推法(backwardinduction)解决博弈问题，其与Wald,Arrow的序贯分析法被认为是动态规划⽅法的前身1951年，RufusIsaacs首次使用动态规划类似的⽅法求解微分博弈问题，但当时并未受到重视自1952年起，RichardBellman等提出可用于离散最优控制的动态规划⽅法，60年代得到连续情况下的Hamilton-Jacobi-Bellman⽅程1983年，Crandall和Lions给出粘性解的概念，完善了HJB⽅程值函数非光滑情况的数学基础Jie,Zhang(CASIA)OptimalControl最优控制的数学理论14/68........................................动态规划⽅法动态规划的最优性原理定理2(最优性原理,Bellman1954)决过程的最优有如下性：不论初状态和初决如，其余的决对于由初决所形成的状态来，定也是⼀个最优上海南京天津北京[,]J上海南京[,]J南京北京[,]J南京天津,北京如果南京-天津-北京是南京到北京的最短路，上海-南京-北京会是最短路吗Jie,Zhang(CASIA)OptimalControl最优控制的数学理论15/68........................................动态规划⽅法⼀个例⼦：动态规划求解最短路例1(动态规划求解最短路)求从图中A点到H的最短路V(x)表示从x出发到H的最短距离——值函数ϕ(x)表示位于x应⾛到哪个点——闭环形式最优控制Jie,Zhang(CASIA)OptimalControl最优控制的数学理论16/68........................................动态规划⽅法1/7G!H此时已知V(H)=0。E;F;G能直达HG可选控制HV(G)=J[GH]+V[H]=2+0=2;ϕ(G)=H:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论17/68........................................动态规划⽅法2/7F!H此时已知V(H)=0;V(G)=2F可选控制G;HV(F)=minfJ[FG]+V[G];J[FH]+V[H]g=minf3+2;4+0g=4:ϕ(F)=H:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论18/68........................................动态规划⽅法3/7E!H此时已知V(H)=0;V(G)=2;V(F)=4E可选控制F;HV(E)=minfJ[EF]+V[F];J[EH]+V[H]g=minf1+4;7+0g=5:ϕ(E)=F:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论19/68........................................动态规划⽅法4/7D!H;C!HV(H)=0;V(G)=2;V(F)=4;V(E)=5。C;D直达D可选控制C;F，但V(C)未知，暂存C可选控制EV(C)=J[CE]+V(E)=3+5=8:ϕ(C)=E:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论20/68........................................动态规划⽅法5/7D!HV(H)=0;V(G)=2;V(F)=4;V(E)=5;V(C)=8。A;D直达D可选控制C;FV(D)=minfJ[DC]+V(C);J[DF]+V[F]g=minf5+8;3+4g=7:ϕ(D)=F:A可选控制B;C;D，但V(B)未知，暂存Jie,Zhang(CASIA)OptimalControl最优控制的数学理论21/68........................................动态规划⽅法6/7B!HV(H)=0;V(G)=2;V(F)=4;V(E)=5;V(D)=7;V(C)=8。A;B直达B可选控制DV(B)=J[BD]+V(D)=3+7=10:ϕ(B)=D:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论22/68........................................动态规划⽅法7/7B!HV(H)=0;V(G)=2;V(F)=4;V(E)=5;V(D)=7;V(C)=8;V(B)=10A可选控制B;C;DV(A)=minfJ[AB]+V(B);J[AC]+V(C);J[AD]+V(D)g=minf2+10;5+8;7+7g=12:ϕ(A)=B:Jie,Zhang(CASIA)OptimalControl最优控制的数学理论23/68........................................动态规划求解离散最优控制TableofContents1回顾：变分法、极