4微分博弈介绍

........................................第四讲：微分博弈介绍最优控制介绍之四张杰复杂系统管理与控制国家重点实验室中国科学院自动化研究所计算机与控制学院中国科学院⼤学2016年9月22日Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍1/58........................................Contents1复习：最优控制问题的数学⽅法2博弈论基础3微分博弈4例⼦：零和追逃博弈Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍2/58........................................最优控制问题问题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最小化性能指标J(u)=h(x(tf);tf)+∫tft0g(x(t);u(t);t)dt:Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍3/58........................................⽆约束最优控制问题例(小车的能量最优控制)x1位置，x2速度，u加速度，则质量为1小车的状态⽅程为：_x1(t)=x2(t);(1)_x2(t)=u(t):(2)要将状态从初始的x(t0)=x0控制到x(tf)=xf，最小化能量：minJ(u)=∫tft012u2(t)dt:(3)Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍4/58........................................欧拉-拉格朗日⽅程@g@x(x(t);_x(t);t)ddt[@g@_x(x(t);_x(t);t)]=0:考察∆J=0的必要条件：驻值条件需假定g可微在最优解x连续可微时成立Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍5/58........................................Pontryagin’sMinimumPrinciple,PMP.定理1(庞特里亚⾦极值原理,1/2)1状态⽅程_x(t)=f(x(t);u(t);t);x(t0)=x0:(4)2容许控制u2U3最小化性能指标J(u)=h(x(tf);tf)+∫tft0g(x(t);u(t);t)dt:(5)定义HamiltonianH(x(t);u(t);p(t);t):=g(x(t);u(t);t)+pT(t)f(x(t);u(t);t);(6)则最优控制u2U的必要条件如下Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍6/58........................................Pontryagin’sMinimumPrinciple,PMP.定理1(庞特里亚⾦极值原理,cont.2/2)极值条件：u;u2U;8t2[t0;tf]H(x(t);u(t);p(t);t)H(x(t);u(t);p(t);t):规范⽅程：8t2[t0;tf]状态(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)]Txf+[H(x(tf);u(tf);p(tf);tf)+@h@t(x(tf);tf)]tf=0:Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍7/58........................................Bellman⽅程：求解离散最优控制2/2定理1(Bellman⽅程)最优控制下的性能指标为“值函数”V(x0;k0)=minu2UJ(u;x0;k0)(7)根据最优性原理，如下Bellman⽅程是最优控制的要条件V(x(k);k)=minu(k)2UfgD(x(k);u(k);k)+V(x(k+1);k+1)gk=k0;:::;N1(8)V(x(N);N)=hD(x(N);N):(9)Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍8/58........................................Hamilton-Jacobi-Bellman⽅程2/2定理1(Hamilton-Jacobi-Bellman⽅程)对于任意的x0;t0，最优控制u下的性能指标为“值函数”V(x0;t0)=minu2UJ(u;x0;t0)(10)最优控制的要条件是Hamilton-Jacobi-Bellman⽅程Vt(x(t);t)=minu2UH(x(t);u(t);VTx(x(t);t);t);t2[t0;tf](11)及其边界条件V(x(tf);tf)=h(x(tf);tf):(12)Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍9/58........................................HJB⽅程和PMP、经典变分的关系欧拉-拉格朗日⽅程⇕等价哈密尔顿⽅程组,哈密尔顿雅各比⽅程+发展+发展极值原理(V⼆次可导特况HJB⽅程Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍10/58........................................最优控制问题的数学⽅法变分法与庞特里亚⾦极小值原理：求解常微分⽅程动态规划：求解偏微分⽅程上述⽅法主要考察单被控对象的最优控制问题Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍11/58........................................例⼦：导弹攻击固定目标的最优控制例1(导弹攻击固定目标的最优控制)初始时刻导弹三维坐标x0，速度为v0，状态⽅程_x(t)=v(t);x(t0)=x0:(13)_v(t)=u(t);v(t0)=v0:(14)终⽌条件：tf时刻导弹击中目标的坐标xf，速度vf自由最小化性能指标，例如最小能量J(u)=∫tft012∥u∥2dt(15)Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍12/58........................................例⼦：导弹攻击移动目标的最优控制例2(导弹攻击移动目标的最优控制)导弹(M)状态⽅程和目标(T)状态⽅程分别为(uT已知)_xM(t)=vM(t);_vM(t)=uM(t):(16)_xT(t)=vT(t);_vT(t)=uT(t):(17)终⽌条件：tf时刻导弹击中目标，速度vf自由xM(tf)=xT(tf):(18)最小化性能指标，例如能量J(uM)=∫tft012∥uM∥2dt(19)Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍13/58........................................导弹攻击移动目标的最优控制解：(引⼊“相对位置”“相对速度”)x:=xMxT,v:=vMvT.状态⽅程变为_x=vMvT=v;(20)_v=uMuT:(21)终值条件x(tf)=0,v(tf)free。性能指标不变转化为和导弹攻击固定目标最优控制完相同形式的问题，可使用极值原理或动态规划求解Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍14/58........................................被攻击的目标也使用最优控制躲避？Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍15/58........................................求解最优控制的⽅法最优控制的数学理论经典变分法庞特里亚⾦极小值原理动态规划⽅法微分博弈最优控制的智能⽅法模型预测控制自适应动态规划模糊控制平⾏控制Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍16/58........................................Contents1复习：最优控制问题的数学⽅法2博弈论基础3微分博弈4例⼦：零和追逃博弈Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍17/58........................................微分博弈的发展1928年(OntheTheoryofGamesofStrategy)，1944年(Theoryofgamesandeconomicbehavior)两篇著作中，JohnVonNeumann和OskerMorgenstern创立博弈论1951年起，Rand公司在美国空军资助下，RufusIssacs研究对抗双⽅都能自由决策⾏动的追逃问题，形成了微分博弈的最初研究成果60-70年代，微分博弈理论逐渐完善，得到微分博弈值函数存在性等基础结果；1965年，Issacs整理出版了第⼀部微分博弈同名专著。也称动态博弈80年代起，微分博弈在经济学和管理学中获得应用，发展了非零和微分博弈、斯坦伯格平衡等2016年，Google公司的AlphaGo结合动态博弈和强化学习首次在围棋领域战胜⼈类世界冠军Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍18/58........................................从优化到博弈定义(函数极小值)ΩRN是开集。称函数F2C1(Ω)在x达到局部极小值，若存在ϵ0使得:F(x)F(x);if∥xx∥ϵ;x2Ω:定义1(纳什平衡NashEquilibrium,NE)F2C1(Ω1Ω2)，局中⼈i=1;2的性能指标分别为Fi(x1;x2),x12Ω1,x22Ω2。x1;x2是纳什平衡，若F1(x1;x2)F1(x1;x2);8x12Ω1(22)F2(x1;x2)F2(x1;x2);8x22Ω2(23)Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍19/58........................................例⼦：囚徒困境例3(囚徒困境)B招供(C)不招供(N)A招供(C)6/61/8不招供(N)8/12/2A和B两⼈均可采取⾏动N-不招供，或C-招供F1(C;C)=6;F1(N;C)=8;F1(C;N)=1;F1(N;N)=2;F2(C;C)=6;F2(N;C)=1;F2(C;N)=8;F2(N;N)=2:F1(C;C)F1(N;C);F2(C;C)F2(C;N):Fei-Yue,Wang(CASIA)OptimalControl最优控制介绍20/58........................................反应函数法求解博弈平衡定义2(反应函数)对于任意给定的x22Ω，映射R1(x2)=argminx12ΩF1(x1;x2)称为局中⼈-1的反应函数(reactionfunction,orbestresponse)Remark1(反应函数法求解纳什平衡)若x1=R1(x2);x2=R2(x1)，可知x1;x2为纳什平衡。可过联立博弈双⽅的反应函数求解博弈的纳什平衡；⽅法也可处理其他博弈平衡（如斯坦伯格平衡等）Fei-Yue,Wang(CASIA)