《最优控制动态规划（1）讲解课件》由会员分享，可在线阅读，更多相关《最优控制动态规划（1）讲解课件（55页珍藏版）》请在金锄头文库上搜索。
1、动态规划法,动态规划是解决多级决策过程最优化的一种数学方法。所谓多级决策过程，是指把一个过程分为若干个阶段，而每一个阶段都需作出决策，以便使整个过程取得最优的效果。,最短路线问题,问题: 要求从A地到F地，选择一条最短的线路。,为了便于分析，引入几个符号：,N：从某点到终点之间的级数；,x：表示在任一级所处的位置，称为状态变量；,SN (x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点；,WN(x)：表示从状态x到终点F的N级过程的最短距离；,d(x, SN)：表示从状态x到点SN的距离。,从最后一级开始计算：,从哪下手？,SN (x)：决策变量，表示当处于状态x，还有N级时，所
2、选取的下一个点；,WN(x)：表示从状态x到终点F的N级过程的最短距离；,同理,所以，最短路线为,最短距离为14,一个N级最优过程，不管第一级决策如何，其余N-1级，决策过程至少必须依据第一级决策所形成的状态组成一个N-1级最优过程，在此基础上，在选择第一级决策，使总的N级过程为最优。,这种递推关系可以用下列递推方程式来表达：,是不是穷举法？,再看一个例子,最短时间问题,问题：设有人要从 A 点开车到 E 站，中间要经过任意三个中间站，站名在图中圆圈内表示。站与站之间称为段，每段路程所需时间（小时）标在段上。现要问，这人应如何选择路线才能最快到达目的地？,什么是穷举法?,从 走到 一共有六条路
3、线，每条路线由四段组成。这六条路线和对应的行车时间如下,路 线 行车时间（小时）13111413129,显然最优路线是 ，它所花时间为9小时。,这里每条路线由四段组成，也可以说是四级决策。为了计算每条路线所花时间，要做三次加法运算，为了计算六条路线所花的时间要作36=18次运算。这种方法称为“穷举法”。显然当段数很多时，计算量是很大的。这种方法的特点是从起点站往前进行，而且把这四级决策一起考虑。应注意从到 下一站 所花的时间为1，而到 所花时间为3，但最优路线却不经过 。这说明只看下一步的“眼前利益”来作决策是没有意义的。,为将问题表达得清楚，引进下面的术语（写法并不完全一样）。,令 表示由某
4、点 到终点的段数（如 到 为2段， 。,令 表示当前所处点的位置（如 ），称为状态变量。,对比一下最开始的例子,令 为决策（控制）变量，它表示当处在 位置而还有 段要走时，所要选取的下一点。 例如，从 出发，下一点为 时，则表示为。,令 表示从点 到点 的时间。 例如，从 到 的时间为,有了这些术语后，就可用动态规划来解这个例子。从最后一段出发进行计算，并将计算出的最短时间 用括号表示在相应的点 处（见图6-1）。,n=1 （倒数第一段）,考虑从 和 到 的路线，由定义可知，最短时间分别为,n=2（倒数第二段）考虑从 到 的路线。,由 到 有两种路线： ， 。两种路线中的最短时间由下式确定：,
5、最优决策为 。,由 到 只有一种路线 ， 其时间为,n=3（倒数第三段）,从B2到E有两种路线： 和,最优决策,最短时间为：,n=4（倒数第四段）,从A到E的路线有两种： 和 。,最优决策为,至此求出了A到E的最短时间为9，最优路线为 。在图中用粗线表示。这里，为决定最优路线进行了10次加法，比穷举法的18次少了8次。当段数n更多时，节省计算将会更多。,以上面的最短时间问题为例，如把 当作初始状态，则余下的决策 对 来讲是最优策略；如把 当初始状态，则余下的决策 对 来讲也构成最优策略。一般来说，如果一个最优过程用状态 来表示，最优决策为 ，则对状态 来讲，必定是最优的，这可用图6-2来表示。
6、,图6-2 最优性原理示意图,动态规划的特点：,一是它从最后一级反向计算； 二是其将一个N级决策问题化为N个单级决策问题。,好处：将一个复杂问题化为多个简单问题加以求解。,最优性原理,贝尔曼的最优性原理可叙述如下： “一个多级决策问题的最优决策具有这样的性质：当把其中任何一级及其状态作为初始级和初始状态时，则不管初始状态是什么，达到这个初始状态的决策是什么，余下的决策对此初始状态必定构成最优策略。”,在多数实际问题中， 级决策的性能指标 取如下形式,是由某级状态和决策决定的性能函数，要求寻找决策 使J取极小值 。,最优性原理可表示为,根据上式就可证明最优性原理的正确性。若以 为初态时，余下的决
7、策 不是最优的，那么就存在另一决策序列 所决定的指标值 ，于是,这与 是极小值发生矛盾，所以余下的决策必须是最优的。,6-2 离散最优控制问题,设控制系统的状态方程为,式中x(k)是k时刻的几维状态向量，u(k)是k时刻的p维容许控制向量，设系统在每一步转移中的性能指标为Fx(k),u(k),如在u(0)的作用下,在u(1)的作用下,对N级决策过程,性能指标,要求选择控制序列,使性能指标达到极小,根据最优性原理,解上述递推方程，即可获得最优控制序列。,例6-1,设一阶离散系统的状态方程为,初始条件为x(0)，控制变量u不受约束，性能指标为,求最优控制u*(t)，使J达最小，为简便起见，设N2,
8、解,设在u(0)、u(1)作用下，系统状态为x(0)、x(1)、x(2),先考虑从x(1)到x(2)的情况，控制为u(1),再考虑从x(0)到x(1)的情况，控制为u(0),最优控制序列为,最优性能指标为,连续系统的动态规划,设系统的状态方程和性能指标为,受约束，可写成 为某一闭集。要寻找满足此约束且使 最小的最优控制 。,（6-21）,显然 满足终端条件,通常假定 对 及 的二阶偏导数存在且有界。,（6-23）,根据最优性原理，从 也应是最优过程。,因 故,这样，式（6-23）可写成,（6-24）,从上式两端消去 ，除以 ，再令 ，可得,（6-25）,引用以前使用过的哈密顿函数,（6-26）
9、,（6-27）,则（6-25）可写成,（6-28）,（6-25）或（6-28）称为哈密顿雅可比贝尔曼方程，边界条件是： 哈密顿雅可比贝尔曼方程在理论上很有价值，但它是 的一阶偏微分方程并带有取极小的运算，因此求解是非常困难的，一般情况得不到解析解，只能用计算机求数值解。对于线性二次问题，可以得到解析解，而且求解结果与用极小值原理或变分法所得结果相同。这时，哈密顿雅可比贝尔曼方程可归结为黎卡提方程。在实际计算线性二次问题时，一般用直接求解黎卡提方程来求最优控制。,例6-3,设系统状态方程为,初始状态,不受约束，性能指标为,求最优控制u*(t)，使性能指标J为最小。,解,由于,因为系统是时不变的，
10、并且性能指标的被积函数不是时间的显函数，故,解,由于,因为系统是时不变的，并且性能指标的被积函数不是时间的显函数，故,解得,引用以前使用过的哈密顿函数,（6-26）,（6-27）,则（6-25）可写成,（6-28）,思考题,HJB方程与极小值原理的区别和联系？,动态规划与极小值原理,动态规划和极小值原理是最优控制理论的两大基石，它们都可以解决有约束的最优控制问题，虽然在形式上和解题方法上不同，但却存在着内在的联系。下面我们从动态规划来推演极小值原理，不过要说明这种推演是基于最优指标对和两次连续可微这个条件的。,最优性能指标与状态方程为,（6-29）,要求确定U(t)使性能指标,（6-30）,极
11、小。其中， 固定， 自由， 可以有约束，也可以没有。,1、 （状态方程） （6-31）,2、 （协态方程） （6-32）,3、 （边界方程） （6-33）,4、 （横截条件） （6-34）,5、 （极值条件） （6-35）,用动态规划求解的结果已在上节中得到，现在归纳一下：在动态规划中协态变量 满足,哈密顿雅可比贝尔曼方程（6-28）本身说明了哈密顿函数在最优控制上取极值的条件，故等同于上面极小值原理所得的条件5，不过（6-28）还多给出了一点信息，即 。,下面由动态规划法来推出协态方程。,由,（6-27）,因假设对两次连续可微，因此上式成立，且可交换求导次序，得,即协态方程（因都是最优解条件
12、。故省去*号。,由（6-22）和（6-27）再来推横截条件,（6-27）,（6-22）,（横截条件）,6.7 小结,1. 动态规划是把多级决策问题化为多个单级决策问题来求解的，而单级问题比多级问题容易处理得多。这种把一个复杂的特定问题化为（又可称为嵌入）一系列性质相似的易于求解的问题的做法称为“不变嵌入”法。,2. 动态规划的基础是最优性原理。这个原理告诉我们：在多级最优决策中，不管初始状态是什么，余下的决策对此状态必定构成最优决策。根据这个原理，动态规划解决多级决策问题（包括离散系统最优控制）是从最后一级开始倒向计算的。,3. 连续系统的动态规划可导出哈密顿雅可比贝尔曼方程，这个方程一般只能
13、有数值解。从它可推演出极小值原理，不过要假定, 二次连续可微。,4. 动态规划比穷举法的计算量是少了不少，但对复杂问题（状态变量和控制变量的数目多，级数多），它的计算量和存储量仍旧非常大，有时用一般计算机也解决不了。这种情况称为“维数灾”。,Bellman最优性原理的精髓,总体最优 局部最优 关键是求解值函数V(x,t) V(x,t)满足著名的哈密顿雅可比贝尔曼方程，简称HJB方程。,HJB方程本身是一个偏微分方程，不一定有经典接，后来又引申出了粘性解的概念。,最优控制这样一个学科的不断发展，用到了ODE、PDE、变分、泛函、矩阵论、优化,目前为止，有什么特别难的地方吗？,或者什么地方用到了特别高深的数学了吗？,本质上只用了分部积分、泰勒展开,
