现代控制理论-第九章-动态规划法

第九章动态规划法动态规划法是求解控制变量限制在一定闭集内的最优控制问题的又一种重要方法，它是由美国学者贝尔曼于1957年提出来的。动态规划法把复杂的最优控制问题变成多级决策过程的递推函数关系，它的基础及核心是最优性原理。本章首先介绍动态规划法的基本概念，然后讨论如何用动态规划法求解离散及连续系统的最优控制问题。第一节动态规划法的基本概念一、多级决策过程所谓多级决策过程是指把一个过程分成若干级，而每一级都需作出决策，以便使整个过程达到最佳效果。为了说明这个概念，首先讨论一个最短路线问题的例子。设有路线图如图7-1所示。现在要从地出发，选择一条最短路线最终到达地，其间要通过等中间站，各站又有若干个可供选择的通过点，各地之间的距离已用数字标注在图中。由此可见，通过这些中间站时，有多个方案可供选择。AFBCDE、、、解决这类问题有两种方法：1.探索法（穷举法）将至的所有可能的路线方案都列举出来，算出每条路线的路程，进行比较，找出最短路线。直观可知，这种方法是很费时的，如本例共有38条路线可供选择。如果中间站及各站可供选择的通过点都增为10个，则可供选择的路线将急剧增至1010条，显然计算工作量将急剧增加。2.分级决策法将整个过程分成若干级，逐级进行决策。具体过程如下：将至全程分为五级：第一级由至；第二级由至；第三级由至；第四级由至；第五级由至。让我们由后向前逐级分析，先从第五级开始，其起点为，终点为。至各只有一条路线，并无选择余地。至路程为1，至路程为2。第四级起点为，终点为，其间有六条路线，由至的各种可能路线为:AFA123,,BBBBB123,,BBB123,,CCCC123,,CCCC123,,DDDD123,,DDDD12,EEE12,EEEF12,EEEF12,EEF1EF2EF123,,DDDD12,EEEFD1112212231324152246179211718527DEFDEFDEFDEFDEFDEF可以发现，如果从出发，则走为最短，因此至应选这段路线，称为决策。同理，如果从出发，应决策；从出发，应决策。可见作此决策时不能只从本级路程长短出发，应考虑两级路程之和为最短。在整个路线问题中，究竟哪一点作为起点，则取决于第三级的决策，不过提出的三条可能的最短路线为第三级的决策积累了数据资料。1D12DEF1DE12DE2D21DE3D32DE123DDD，，可见同样方法来分析第三级，其起点为，终点为，按题意共有八条路线。但是，至的最短路线已在第四级讨论中确定，因此的路线选择问题，实际上只是选定级的路线问题（即本级决策问题）。因此，至只有八条路线，分别为123,,CCCCD123,,DDD123DDD，，FCDFCDCF21212212111221222331323314557128412471167134484711279EEEEEEEECDFCDFCDFCDFCDFCDFCDFCDF比较可得分别从出发时的三条最短路线，它们为：；；。123,,CCC211ECDF；122ECDF231ECDF用同样方法，依次对级及级进行讨论，其结果列于表7-1。最后得到最短路线为BCAB2112ABCDEF相应最短路程为：。*14J通过上例的讨论，可以看到多级决策过程具有以下特点：⑴把整个过程看成（或人为地分成）级的多级过程。⑵采取逐级分析的方法，一般由最后一级开始倒向进行。n⑶在每一级决策时，不只考虑本级的性能指标的最优，而是同时考虑本级及以后的总性能指标最优，因此它是根据“全局”最优来作出本级决策的。⑷从数学观点，分级决策法与穷举法进行比较：穷举法：全程五级线路，每一级都可任选，因此全部路程相当于一个“五变量函数”，求全程最短实质上是求这个“五变量函数”的极小值。分级决策法：分成五级，从最后一级开始进行分级决策时，每级都是一个“单变量函数”，因此进行每一级决策时，实际上是求一个“单变量函数”的极小值。因此多级决策法把一个求“五变量函数”的极值问题转化成为一个五组求“单变量函数”的极值问题。这组实际解题带来极大好处，使计算工作量在为减少。以前面举的十级中间站并各站具有十个通过点的路线问题为例，用多级决策法只需920次计算，这与1010次相比要少得多。⑸在最后一级开始倒向逐级分析中，我们发现，由于各站的起始点并未确定，因此需要把各中间站的所有通过点作为出发点进行计算，并将所有对应的最佳决策存进计算机，建立起一个完整的“档案库”，因此要求计算机有相当大的容量。(6)第一级起始条件（地）是确定的，因此只有逐级倒向分析到第一级时，才能作出确定的第一级决策，然后再根据第一级决策顺向确定各级的起始条件（各站的通过点），这时由于“档案库”中存有全部“资料”，因此用“查档”的方法就可逐级确定决策。由此可见，一般情况下，多级决策过程包括两个过程：倒向“建档”及顺向“查档”，而大量的计算工作是花费在建立“档案库”上。二、最优性原理在前例的分级决策过程中，实际上已应用了这样一个基本原理：设一个过程由点开始，经点到达点，如图9-2所示，如果为最优过程，则段也必定是一个最优过程。我们把这原理叙述如下：abcabcbc一个最优决策具有这样的性质，不论初始状态和初始决策怎样，其余的决策对于第一次决策所造成的状态来说，必需构成一个最优决策。称此为最优性原理。它也可简单地叙述为：最优轨迹的第二段，本身亦是最优轨迹。最优性原理是动态规划法的基础和核心。动态规划法就是对一个多级过程，应用最优性原理，进行分级决策，求出最优控制的一种数学方法。3、多级决策过程的函数方程应用动态规划法求解过程的最优决策时，首先要根据最优性原理将多级决策过程表示成如下数学表达式：――级决策过程始点处所采取的控制决策，从而使状态转移到下一步。式中――级决策过程的始点至终点的最小消耗；kkwxkkxix――由级决策过程始点至下一步到达点的一步消耗；1,,kkidxxkkx1,kixkkx1,kixkiu1,11,min,kikkkkikkiuwxdxxwx(9-1)上式表明，为使级决策过程达到最小消耗，第一级决策应根据两部分消耗之和最小的原则作出。第一部分是第一级决策的一步消耗，第二部分为由下一步到达点作起点至终点的最小消耗。式(7-1)称为多级决策过程的函数方程，它是最优性原理的数学表达形式。在上述路线问题中，至的四级决策过程的函数方程可表示成：k1,,kkidxx11,kkiwx1,kix2BF式中:――四级过程的起点；――由出发到达下一步站的某个可能通过点，它可能为或；――由至站的路线选择（本级决策）；2BiC4iu2BC12CC、3C2BC44223min,iiiuwBdBCwC(9-2)――由至之间的路程；――从至终点的最短路程。2,idBC2BiC3iwCiCF由表7-1可知213122322333459311145813dBCwCdBCwCdBCwC，，，三者进行比较，由此作出第一级决策为即应选路线。这时最小路程为。4,1u21BC2BF429wB函数方程是一个递推方程，一般说来，难于获得解析解，需要用数字计算机求解。第二节动态规划法解离散系统的最优控制问题设系统状态方程为式中，为维状态向量，为维控制向量，设为每一步转移中的性能指标。kxnkumkkJxu，10,1,,1kkkkNxfxu，(9-3)第一步，系统初始状态在作用下转移至，即0x0u1x要求选择控制，使达最小。这是一个一级决策过程。0u00Jxu，100xfxu，(9-4)这时，第一步的性能指标为：100JJxu，(9-5)20011JJJxuxu，，(9-6)第二步，系统在作用下由转移到，转移中的性能指标为，则两步转移的总性能指标为：1u1x211xfxu，11Jxu，11Jxu，这里，因为已知，而，因此在上述两步转移的总性能指标中，只有及未知。现在要求选择及，使两步性能指标达极小。这就是二级决策问题。0x100xfxu，0u1u0u1u依次类推，系统状态由作起点进行步转移，则步转移的总性能指标为：0xNN现在要求选择使性能指标达最小，这就是级决策问题。我们可以应用动态规划法来求解。根据最优性原理，对级最优决策过程来说，不论第一级控制向量怎样选定，余下的级过程，从产生的状态作为起点，必须构成级最优过程。011kuuu，，，NJNN0u0u1N100xfxu，1N10001111NNkJJJNNJkkJxuxuxuxu，，，，(9-7)如果我们用表示级过程的性能指标的极小值，表示级过程性能指标的极小值，则我们就可以列写出级决策过程的函数方程为：0NwxN11Nwx1N由此可见，第一级决策实质上是函数10000NwJxufxu，，对第一级的控制决策求极值的问题。求解递推方程(9-8)，就可解得最优控制决策。0u011kuuu，，，100min0000NwwuxJxufxu，，(9-8)例9-1设离散系统状态方程为：10,1,,1kkkkNxxu初始条件为，控制变量不受限制，性能指标为0xu11122220NNkNkJcxu求最优控制，使达最小。*kuJ解:为简单起见，设，则这是一个二步控制问题，性能指标可表示成：2N2222111201222Jcxuu首先考虑最后一步，即由某状态出发到达的一步，如采用控制，则有1x2x1u221211112122xxuJcxu或221111Jcx1u1u(1)Jx1u122求最优控制使为极小，则有1u1J111101Jcxuuu＝解得：111cxuc可见为的函数。相应的最优性能指标及为1u1x2x21minx1cJ21c121xxc再考虑倒数第二步，即由初始状态出发到达的一步，如采用控制，则有0x1x0u100xxu22min1min02202201min0211min02211min000221ccccuuuJuJxuuxu令22100000221ccuxuu有0012ccxu相应的最优性能指标及为：1x22min0212ccxJ11012ccxx最后得最优控制为：**00011212ccccxxuu，最优轨线为：***01001021212cccxxxxxx，，最优性能指标为：2*0212ccxJ上述离散型动态规划可近似地用来求解连续系统的最优控制问题。设连续系统状态方程为：00tttx