《动态规划法》PPT课件.ppt

《《动态规划法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《动态规划法》PPT课件.ppt（45页珍藏版）》请在装配图网上搜索。

1、第九章 动态规划法 动态规划法是求解控制变量限制在一定闭集内的最优控制问题 的又一种重要方法，它是由美国学者贝尔曼于 1957年提出来的。 动态规划法把复杂的最优控制问题变成多级决策过程的递推函数关 系，它的基础及核心是最优性原理。本章首先介绍动态规划法的基 本概念，然后讨论如何用动态规划法求解离散及连续系统的最优控 制问题。 第一节 动态规划法的基本概念 一、多级决策过程 所谓多级决策过程是指把一个过程分成若干级，而每一级都需作 出决策，以便使整个过程达到最佳效果。为了说明这个概念，首先 讨论一个最短路线问题的例子。 设有路线图如图 7-1所示。现在要从 地出发，选择一条最短路 线最终到达

2、地，其间要通过 等中间站，各站又有若干 个可供选择的通过点，各地之间的距离已用数字标注在图中。由此 可见，通过这些中间站时，有多个方案可供选择。 A F B C D E、 、 、 解决这类问题有两种方法： 1.探索法（穷举法） 将至的所有可能的路线方案都列举出来，算出每条路线的路程， 进行比较，找出最短路线。直观可知，这种方法是很费时的，如 本例共有 38条路线可供选择。如果中间站及各站可供选择的通过 点都增为 10个，则可供选择的路线将急剧增至 1010条，显然计算 工作量将急剧增加。 2. 分级决策法 将整个过程分成若干级，逐级进行决策。具体过程如下： 将 至 全程分为五级：第一级由 至

3、；第二级由 至 ；第三级由 至 ；第四 级由 至 ；第五级由 至 。让我们由后 向前逐级分析，先从第五级开始，其起点为 ，终点为 。 至 各只有一条路线，并无选择余地。 至 路程为 1， 至 路程为 2。第四级起点为 ，终点为 ，其间有六条 路线，由 至 的各种可能路线为 : A F A 1 2 3,B B B B B 1 2 3,B B B 1 2 3,C C C C 1 2 3,C C C C 1 2 3,D D D D 1 2 3,D D D D 12,E E E 12,E E E F 12,E E E F 12,EE F 1E F 2E F 1 2 3,D D D D 12,E E E

4、 FD 11 12 21 22 31 32 4 1 5 2 2 4 6 1 7 9 2 1 1 7 1 8 5 2 7 D E F D E F D E F D E F D E F D E F 可以发现，如果从 出发，则走 为最短，因此 至 应选 这段路线，称为决策。同理，如果从 出发，应决策 ；从 出发，应决策 。可见作此决策时不能只从本 级路程长短出发，应考虑两级路程之和为最短。在整个路线问题 中，究竟 哪一点作为起点，则取决于第三级的决策，不 过提出的三条可能的最短路线为第三级的决策积累了数据资料。 1D 12D E F 1D E 12DE 2D 21DE 3D 32DE 1 2 3D D

5、 D， ， 可见同样方法来分析第三级，其起点为 ，终点为 ，按题意共有八条路线。但是， 至 的最短路 线已在第四级讨论中确定，因此 的路线选择问题，实际 上只是选定级 的路线问题（即本级决策问题）。因此， 至 只有八条路线，分别为 1 2 3,C C C C D 1 2 3,D D D 1 2 3D D D， ， F C D F CD C F 2 1 2 1 2 2 1 2 11 12 21 22 23 31 32 33 1 4 5 5 7 12 8 4 12 4 7 11 6 7 13 4 4 8 4 7 11 2 7 9 E E E E E E E E C D F C D F C D F

6、C D F C D F C D F C D F C D F 比较可得分别从 出发时的三条最短路线，它们为： ； ； 。 1 2 3,C C C 2 11 EC D F ； 1 22 EC D F 2 31 EC D F 用同样方法，依次对 级及 级进行讨论，其结果列于 表 7-1。最后得到最短路线为 BC AB 2 1 1 2A B C D E F 相应最短路程为： 。 * 14J 通过上例的讨论，可以看到多级决策过程具有以下特点： 把整个过程看成（或人为地分成） 级的多级过程。 采取逐级分析的方法，一般由最后一级开始倒向进行。 n 在每一级决策时，不只考虑本级的性能指标的最优，而是同 时考虑

7、本级及以后的总性能指标最优，因此它是根据“全局”最优 来作出本级决策的。 从数学观点，分级决策法与穷举法进行比较： 穷举法：全程五级线路，每一级都可任选，因此全部路程相当于 一个“五变量函数”，求全程最短实质上是求这个“五变量函数” 的极小值。 分级决策法： 分成五级，从最后一级开始进行分级决策时，每级 都是一个“单变量函数”，因此进行每一级决策时，实际上是求一 个“单变量函数”的极小值。因此多级决策法把一个求“五变量函 数”的极值问题转化成为一个五组求“单变量函数”的极值问题。 这组实际解题带来极大好处，使计算工作量在为减少。以前面举的 十级中间站并各站具有十个通过点的路线问题为例，用多级决

8、策法 只需 920次计算，这与 1010次相比要少得多。 在最后一级开始倒向逐级分析中，我们发现，由于各站的起 始点并未确定，因此需要把各中间站的所有通过点作为出发点进 行计算，并将所有对应的最佳决策存进计算机，建立起一个完整 的“档案库”，因此要求计算机有相当大的容量。 (6)第一级起始条件（地）是确定的，因此只有逐级倒向分析到第 一级时，才能作出确定的第一级决策，然后再根据第一级决策顺向 确定各级的起始条件（各站的通过点），这时由于“档案库”中存 有全部“资料”，因此用“查档”的方法就可逐级确定决策。由此 可见，一般情况下，多级决策过程包括两个过程：倒向“建档”及 顺向“查档”，而大量的计

9、算工作是花费在建立“档案库”上。 二、最优性原理 在前例的分级决策过程中，实际上已应用了这样一个基本原理： 设一个过程由 点开始，经 点到达 点，如图 9-2所示，如果 为最优过程，则 段也必定是一个最优过程。我们把这 原理叙述如下： a b c a b c bc 一个最优决策具有这样的性质，不论初始状态和初始决策怎样 ，其余的决策对于第一次决策所造成的状态来说，必需构成一个 最优决策。称此为最优性原理。它也可简单地叙述为：最优轨迹 的第二段，本身亦是最优轨迹。 最优性原理是动态规划法的基础和核心。动态规划法就是对一个 多级过程，应用最优性原理，进行分级决策，求出最优控制的一种 数学方法。 3

10、、 多级决策过程的函数方程 应用动态规划法求解过程的最优决策时，首先要根据最优性原 理将多级决策过程表示成如下数学表达式： 级决策过程始点 处所采取的控制决策，从而使 状态转移到下一步 。 式中 级决策过程的始点 至终点 的最小消耗； kkwx k kx ix 由 级决策过程始点 至下一步到达点 的一步 消耗； 1,k k id x x k kx 1,kix k kx 1,kix kiu 1 , 1 1 ,m i n ,kik k k k i k k iuw x d x x w x (9-1) 上式表明，为使 级决策过程达到最小消耗，第一级决策应根据 两部分消耗之和最小的原则作出。第一部分 是

11、第一级决 策的一步消耗，第二部分 为由下一步到达点 作起点 至终点的最小消耗。式 (7-1)称为多级决策过程的函数方程，它是 最优性原理的数学表达形式。在上述路线问题中， 至 的四级 决策过程的函数方程可表示成： k 1,k k id x x 1 1,k k iwx 1,kix 2B F 式中 : 四级过程的起点； 由 出发到达下一步 站的某个可能通过点，它 可能为 或 ； 由 至 站的路线选择（本级决策）； 2B iC 4iu 2B C 12CC、 3C 2B C 44 2 2 3m i n ,i iiuw B d B C w C(9-2) 由 至 之间的路程； 从 至 终点的最短路程。 2

12、 , id B C 2B iC 3 iwC iC F 由表 7-1可知 2 1 3 1 2 2 3 2 2 3 3 3 4 5 9 3 11 14 5 8 13 d B C w C d B C w C d B C w C ， ， ， 三者进行比较，由此作出第一级决策为 即应选 路线。这 时 最小路程为 。 4,1u 21BC 2BF 42 9wB 函数方程是一个递推方程，一般说来，难于获得解析解，需要用 数 字计算机求解。 第二节 动态规划法解离散系统的 最优控制问题 设系统状态方程为 式中， 为 维状态向量， 为 维控制向量，设 为每一步转移中的性能指标。 kx n ku m kkJ x u

13、， 1 0 ,1 , , 1k k k k N x f x u，(9-3) 第一步，系统初始状态 在 作用下转移至 ，即 0 x 0u 1x 要求选择控制 ，使 达最小。这是一个一级决 策过程。 0u 00J x u， 1 0 0 x f x u， (9-4) 这时，第一步的性能指标为： 1 00J J x u， (9-5) 2 0 0 1 1JJ J x u x u， ，(9-6) 第二步，系统在 作用下由 转移到 ，转 移中的性能指标为 ，则两步转移的总性能指标为： 1u 1x 2 1 1 x f x u， 11J xu， 这里，因为 已知，而 ，因此在上述两步转 移的总性能指标中，只有

14、及 未知。现在要求选择 及 ，使两步性能指标达极小。这就是二级决策问题。 0 x 1 0 0 x f x u， 0u 1u 0u 1u 依次类推，系统状态由 作起点进行 步转移，则 步转移 的总性能指标为： 0 x N N 现在要求选择 使性能指标 达最小，这就 是 级决策问题。我们可以应用动态规划法来求解。根据最优性原 理，对 级最优决策过程来说，不论第一级控制向量 怎样选 定，余下的 级过程，从 产生的状态 作为 起点，必须构成 级最优过程。 0 1 1k u u u， ， ，NJ N N 0u 0u 1N 1 0 0 x f x u， 1N 1 0 0 0 1 1 1 1N N k J

15、J J N N J k k J x u x u x u xu ， ， ， ，(9-7) 如果我们用 表示 级过程的性能指标的极小值， 表示 级过程性能指标的极小值，则我们就可以列写出级决策过 程的函数方程为： 0Nw x N 1 1Nw x 1N 由此可见，第一级决策实质上是函数 10 0 0 0Nw J x u f x u， ， 对第一级的控制决策 求极值的问题。求解递推方程 (9-8)，就 可解得最优控制决策 。 0u 0 1 1k u u u， ， ， 100 m i n 0 0 0 0Nww ux J x u f x u， ，(9-8) 例 9-1 设离散系统状态方程为： 1 0 ,

16、1 , , 1k k k k N x x u 初始条件为 ，控制变量 不受限制，性能指标为 0 x u 1112222 0NNkN k J c x u 求最优控制 ，使 达最小。 * ku J 解 : 为简单起见，设 ，则这是一个二步控制问题，性能指标 可表示成： 2N 2 2 22 1 1 12 0 12 2 2 J cx u u 首先考虑最后一步，即由某状态 出发到达 的一步，如采 用控制 ，则有 1x 2x 1u 221 2 1 1 1121 22 x x u J c x u 或 2 21111J c x 1 u 1 u (1 ) J x 1 u 122 求最优控制使 为极小 ，则有 1

17、u 1J 1 1 1 1 01 J c x u uu 解得： 11 1 cxu c 可见 为 的函数。相应的最优性能指标及 为 1u 1x 2x 2 1 m in x1cJ 2 1 c 12 1 xx c 再考虑倒数第二步，即由初始状态 出发到达 的一步， 如采用控制 ，则有 0 x 1x 0u 100 x x u 2 2 m i n 1 m i n 0 2 2 0 2 2 0 1 m i n 0 2 11 m i n 0 2 2 1 1 m i n 0 0 0 2 2 1 c c c c u u u J u J x u u x u 令 221 0 0 0 0 0 2 2 1 c c u x

18、uu 有 0 0 12c c xu 相应的最优性能指标及 为： 1x 2 2 m in 0 2 1 2 c cxJ 11012 cc xx 最后得最优控制为： * 0001 1 2 1 2 cc cc xxuu ， 最优轨线为： * * * 010 0 1 0 2 1 2 1 2 c cc xx x x x x， ， 最优性能指标为： 2* 02 1 2c cxJ 上述离散型动态规划可近似地用来求解连续系统的最优控制问 题。 设连续系统状态方程为： 00t t tx f x u t x t x， ， ，(9-9) ft 给定，性能指标为： u t U (9-10) 0 fff F ttJ x

19、t t x t u t t d t， ， ，(9-11) 求最优控制 ，使 为最小。 *ut J 由于函数方程是一个递推方程，故特别适合于求解离散系 统的最优控制问题。为此要把连续过程问题转化成一个多级决 策过程。首先将时间间隔 分成 段，每段为 ，为使尽量 符合连续过程的实际情况， 应取足够大， 取足够小。接着应 将连续状态方程进行离散化，使之用下列有限差分方程来近似 表示： 0 ftt， N N 1kk k k k xx f x u， ，(9-12) 故 1k k k k k x x f x u， ，(9-13) 这样，就把研究连续过程问题近似转化成了 级决策过程。 下面就可按离散过程一样

20、建立函数方程，用递推求解方法逐级 进行最优决策，求出最优控制序列来。 N 1 0 N k N N F k k k J x x u， ， ， (9-14) 这里，假设在每段时间 内， 及 保持常值。同时，将积分 型的性能指标用以下序列和的形式来近似 kx ku 第三节 动态规划法解离散线性二次型问题 设离散线性系统状态方程为： 1k k k k k x A x B u(9-15) 性能指标为二次型 1 0 NT T T i NN J x S x x i Q i x i u i R i u i (9-16) 式中， 均为对称矩阵， 为正定矩阵， 为正半定矩阵。 求最优控制序列 使 为最小。 S Q

21、 R、 、 R QS、 * * *0 1 1N u u u， ， ，J 现在我们用动态规划法来求解。从初始端开始，经过 级 决策得到的最优性能指标可表示为 N 1 0 0 0 m in NT T TN u i w N N x x S x x i Q i x i u i R i u i， (9-17) 1 0 m in NT T TNk u i w k k N N x x Sx x i Q i x i u i R i u i， (9-18) 根据最优性原理，可以建立函数方程如下： 如果过程是从第 级开始至终产端，则这一段的最优性能指 标可表示为： k 1m i n 1 1TTN k N kukw

22、 k k k k k k k k w k k x x Q x u R u x， ， 假设二次型问题的最优性能指标为状态的二次函数： TNkw k k k k k x x P x， (9-20) 上式对 成立，代入式 (9-19)得： 0 , 1 , , 1kN m i n ( ) ( ) ( ) ( 1 ) ( 1 ) ( 1 ) TT Nk uk TT w k k k k k k k k u k R k u k x k P k x k x x Q x u R u， (9-21) 将系统状态方程代入，得： m i n 1 TT Nk uk T T T T w k k k k k k k k k

23、 k k k k k k k kk x x Q x u R u x A u B P A x B Bu ， (9-22) u设 不受约束，则令 2 1 2 1 0TTk k k k k k k k k R B P B B P A xu (9-23) 可得： 1* 1 1TTk k k k k k k k k kk u B P B R B P A x Gx (9-24) 式中 111TTk k k k k k k k G B P B R B P A 现在需要确定，将 式 (9-24)代入式 (9-22)，并利用 的假设，则式 (9-22)可写成： kP TNkw k k k k k x x P x

24、， 1 1 TTT TT T TT k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k x P x x Q x G x R G x x A B G P A B G x x Q G R G A B G P A B G x (9-26) 上式对任意状态变量都满足，由此可得离散系统的黎卡提方程 1TTk k k k k k k k k k k k P Q G R G A B G P A B G (9-27) 第四节 动态规划法解连续系统的最优控制问题 用离散动态规划法求解连续系统最优控制问题时，可能会 由于离散化过程而造

25、成一定误差。应用最优性原理，对连续系 统也可建立起相应的函数方程，经过变换，最后得到一个一阶 非线性偏微分方程，解之可得连续形式的最优控制即最优决策。 设连续系统状态方程为 00t t tx f x u t x t x， ， ， u t U (9-28) (9-29) 性能指标为 0 fffJ F dt ttx t t x t u t t， ， ， (9-30) 求最优控制 ，使为最小。 *ut 我们知道，对应最优控制 及最优轨线 ，性能指标将取 极小值，且为系统初始状态 及初始时刻 的函数，以表示， 则可写成： *ut *xt 0 x 0t *00 m i nw J J uUx t x u

26、x u， ， ，(9-31) 000 m in fffw F d ttuUx t x t t x u t t， ， ， ，(9-32) 这里， 与 的关系受系统动态方程约束。将指标函数的表 示式代入，则 *u *x 显然 f f f fw x t t x t t， ，(9-33) 设时刻 在区间 内，则根据最优性原理，从 到 这一 段过程必须构成最优过程，这一段过程的性能指标极小值可表 示为 t 0 ftt， t ft 将 这段最优过程分成二步，第一步 由 到， 是一很 小的时间间隔，第二步由 至 ，于是有 0 ftt， t t t ft 0 m in fffw F d ttuUx t t x

27、 t t x u， ， ， ，(9-34) m in ffw F d F d ttuUx t t x t t x u x u， ， ， ， ， ，(9-35) 根据最优性原理，从 到 这一段过程也应当构成最优过程， 其性能指标极小值可表示为： t ft 这样，式 (9-35)就变成： m in fffw F d ttuUx t t x t t x u， ， ， ，(9-36) m inw F d w ttuUx t t x u x t t， ， ， ，(9-37) 因为 很小，上式可写成： m inw F t w uUx t t x u x t t， ， ， ，(9-38) 将 用台劳级数展开

28、 w x t t， 2Twwww x t t x t t xxt， ， (9-39) 式中， 为二次及二次以上各项，代入式 (9-38)得： 2 2m in Twww F w uUx t t x u t x t t xxt， ， ， ，(9-40) 由于 不是 的函数，从而 亦不是 的函数，因此不 受最小化运算的影响，可从最小化运算符号析出，于是有 w x t t， u wt u 2m in Twww F w uUx t t x u t x x t txt， ， ， ，(9-41) 0简化上式，并以 除之，再取 ，则 m in TuUwwFf x u t x u ttx ， ， ， ，(9-4

29、2) 定义下列函数 TwwH F f x u t x u t x u txx， ， ， ， ， ， ，(9-43) 则 m inwwH uU x u ttx， ， ， (9-44) 如求出最优控制 ，则下式成立 *ut *wwH x u ttx， ， ， (9-45) 式 (9-45)称为哈密尔顿 -雅可比方程。当 不受限制时，可由 u 0Hu (9-46) 即 0TFf w x u t x u tu u x， ， ， ， (9-47) 解得 ，显然它是 的函数，记作 /wx x t， ，*u * w u t u x tx， ， (9-48) 将式 (9-48)代入哈密尔顿 -雅可比方程，并根

30、据如下边界条件 f f f fw x t t x t t， ，(9-49) 可以解出 来。再将 代回式 (9-48)，就可获得最优 控制 。这是一个状态反馈控制规律，由此可以实现闭 环最优控制。最后同 代入系统状态方程，就可解得 。 wx t t， wx t t， * u x t t， *u *xt 例 9-2 设系统状态方程为 12xx 2 xu 初始状态为 ， 不受约束，性能指标为 120 1 0 0 xx， u 221 0 12 2J x dt u 试求 ，使 为最小。 *ut J 解 根据式（ 9-45）、式 (9-43)有 222 1 u 12 22 12 u 12 1 m in 2

31、 2 1 m in 2 2 xw xu uxx x u x u xx t ， 由于 不受约束，可以根据 来求 ，得： u 0Hu *u 2 2 12 12 120 2xxxx 为解此偏微分方程，设： ，代入上 式，得： 221 1 2 1 2 3 22w x a x a x x a x 2 2 2 22 1 1 2 3 1 2 2 3 21 2 0a x a a a x x a a x 因而 222 1 2 3 2 31 0 2 0 0a a a a a a ， ， 联立解得： 2 3 11 1 2a a a ， ， 221 1 2 222w x x x x x 12 2 22w xxx * 1222xx u 从而可很方便地实现闭环状态反馈最优控制。