优控制第七章动态规划法.ppt

第七章动态规划法 动态规划是贝尔曼在50年代作为多段决策过程研究出来的 现已在许多技术领域中获得广泛应用 动态规划是一种分段最优化方法 它既可用来求解约束条件下的函数极值问题 也可用于求解约束条件下的泛函极值问题 它与极小值原理一样 是处理控制矢量被限制在一定闭集内 求解最优控制问题的有效数学方法之一 动态最优的核心是最优性原理 它首先将一个多段决策问题转化为一系列单段决策问题 然后从最后一段状态开始逆向递推到初始段状态为止的一套求解最优策略的完整方法 下面先介绍动态规划的基本概念 然后讨论连续型动态规划 一 多段决策问题动态规划是解决多段决策过程优化问题的一种强有力的工具 所谓多段决策过程 是指把一个过程按时间或空间顺序分为若干段 然后给每一步作出 决策 或控制 以使整个过程取得最优的效果 如图1所示 对于中间的任意一段 例如第k 1段作出相应的 决策 或控制 uk后 才能确定该段输入状态与输出状态间的关系 即从xk变化到xk 1的状态转移规律 在选择好每一段的 决策 或控制 uk以后 那么整个过程的状态转移规律从x0经xk一直到xN也就被完全确定 全部 决策 的总体 称为 策略 当然 如果对每一段的决策都是按照使某种性能指标为最优的原则作出的 那么这就是一个多段最优决策过程 图1多段决策过程示意图 容易理解 在多段决策过程中 每一段 如第k 1段 的输出状态 xk 1 都仅仅与该段的决策 uk 及该段的初始状态 xk 有关 而与其前面各段的决策及状态的转移规律无关 这种性质称为无后效性 下面以最优路线问题为例 来讨论动态规划求解多段决策问题 设汽车从A城出发到B城 途中需穿越三条河流 它们各有两座桥P Q可供选择通过 如图2所示 各段间的行车时间 或里程 费用等 已标注在相应段旁 问题是要确定一条最优行驶路线 使从A城出发到B城的行车时间最短 现将A到B分成四段 每一段都要作一最优决策 使总过程时间为最短 所以这是一个多段最优决策问题 由图2可知 所有可能的行车路线共有8条 如果将各条路线所需的时间都一一计算出来 并作一比较 便可求得最优路线是AQ1P2Q3B 历时12 这种一一计算的方法称为穷举算法 这种方法计算量大 如本例就要做3 23 24次加法和7次比较 如果决策一个n段过程 则共需 n 1 2n 1次加法和 2n 1 1 次比较 可见随着段数的增多 计算量将急剧增加 应用动态规划法可使计算量减少许多 动态规划法遵循一个最优化原则 即所选择的最优路线必须保证其后部子路线是最优的 例如在图2中 如果AQ1P2Q3B是最优路线 那么从这条路线上任一中间点到终点之间的一段路线必定也是最优的 否则AQ1P2Q3B就不能是最优路线了 根据这一原则 求解最优路线问题 最好的办法就是从终点开始 按时间最短为目标 逐段向前逆推 依次计算出各站至终点之间的时间最优值 并据此决策出每一站的最优路线 如在图2中 从终点B开始逆推 最后一段 第四段 终点B的前站是P3或Q3 不论汽车先从哪一站始发 行驶路线如何 在这最后一段 总不外乎是从P3到B 历时为4 或从Q3到B 历时为2 将其标明在图3中相应的圆圈内 比较P3与Q3这一最后一段最优决策为Q3B 最后一段 第四段 终点B的前站是P3或Q3 不论汽车先从哪一站始发 行驶路线如何 在这最后一段 总不外乎是从P3到B 历时为4 或从Q3到B 历时为2 将其标明在图3中相应的圆圈内 比较P3与Q3这一最后一段最优决策为Q3B 第三段 P3 Q3的前站是P2 Q2 在这一段也不论其先后的情况如何 只需对从P2或Q2到B进行最优决策 从P2到B有两条路线 P2P3B 历时为6 P2Q3B 历时为4 取最短历时4 标注在P2旁 从Q2到B也有两条路线 Q2P3B 历时为7 Q2Q3B 历时为5 取最短历时5 标注在Q2旁 比较P2与Q2的最优值 可知这一段的最优路线是P2Q3B 第二段 P2 Q2的前站是P1 Q1 同样不管汽车是如何到达的P1 Q1 重要的是保证从P1或Q1到B要构成最优路线 从P1到B的两条路线中 P1P2Q3B 历时为11 P1Q2Q3B 历时为11 取最短历时11 标注在P1旁 从Q1到B的也有两条路线中 Q1P2Q3B 历时为8 Q1Q2Q3B 历时为13 取最短历时8 标注在Q1旁 比较P1与Q1的最优值 可知这一段的最优路线是Q1P2Q3B 第一段 P1 Q1的前站是始发站A 显见从A到B的最优值为12 故得最优路线为AQ1P2Q3B 综上可见 动态规划法的特点是 1 与穷举算法相比 可使计算量大大减少 如上述最优路线问题 用动态规划法只须做10次加法和6次比较 如果过程为n段 则需做加法 以上例为例 用穷举法需作4608次加法 而后者只需做34次加法 2 最优路线的整体决策是从终点开始 采用逆推方法 通过计算 比较各段性能指标 逐段决策逐步延伸完成的 全部最优路线的形成过程已充分表达在图3中 从最后一段开始 通过比较P3 Q3 得到Q3B 倒数第二段 通过比较P2 Q2 得到P2Q3B 倒数第三段 通过比较P1 Q1 得到最优决策为Q1P2Q3B 直至最后形成最优路线AQ1P2Q3B 象这样将一个多段决策问题转化为多个单段决策的简单问题来处理 正是动态规划法的重要特点之一 3 动态规划法体现了多段最优决策的一个重要规律 即所谓最优性原理 它是动态规划的理论基础 对图4所示的N段决策过程 如果在第k 1段处把全过程看成前k段子过程和后N k段子过程两部分 对于后部子过程来说 xk可看作是由x0及前k段初始决策 或控制 u0 u1 uk 1所形成的初始状态 那么 多段决策的最优决策略具有这样的性质 不论初始状态和初始决策如何 其余 后段 决策 或控制 对于由初始决策所形成的状态来说 必定也是一个最优策略 这个性质称为最优性原理 图4N段决策过程 设图5中x t 是连续系统的一条最优轨线 x t1 是最优轨线上的一点 那么最优性原理说明 不管t t1 t0 t1 tf时 系统是怎样转移到状态x t1 的 但从x t1 到x tf 这段轨线必定是最优的 因为最优轨线的后一段从x t1 到x tf 如果还有另一条轨线是最优的话 那么原来从x t0 到x tf 的轨线就不是最优的 这与假设矛盾 因此 最优性原理成立 应用最优性原理可以将一个N段最优决策问题转化为N个一段最优决策问题 从而大大减少求解最优决策问题的计算量 图5连续系统的状态转移过程 图5连续系统的状态转移过程 二 连续系统的动态规划利用动态规划最优性原理 可以推导出性能泛函为极小应满足的条件 哈密尔顿 雅可比方程 它是动态规划的连续形式 解此方程可求得最优控制u t 现在来推导这一方程 设连续方程为 1 终端约束 使性能泛函 求最优控制u t 或u任意 初始状态 2 3 4 根据最优性原理 如果x t 是以x t0 为初始状态的最优轨线 如图6所示 图6连续系统最优轨线 5 设t t t0 t tf 时 状态为x t 它将轨线分成前后两半断 那么以x t 为初始状态的后半段也必是最优轨线 而与系统先前如何到达x t 无关 若取t0 t t t t 式 4 可写成 根据最优性原理 如果t到tf的过程是最优的 则从t t到tf的后部子过程也是最优的 其中t t t tf 因此可写成 6 7 当 t很小时 有 式 5 可近似表示为 8 5 将x t t 进行泰勒展开 取一次近似 有 9 10 11 将上式在 x t 领域展成泰勒级数 考虑到J x x t t 既是x的函数 也与t有关 所以 12 8 代入式 8 得 13 12 8 考察上式因为J x t 与u无关 故J x t 与 可提到min号外面 经整理可得 式 14 称为连续系统动态规划基本方程或贝尔曼方程 14 贝尔曼方程 它是一个关于J x t 的偏微分方程 解此方程可求得最优控制使J为极小 它的边界条件为 15 14 如果令哈密尔顿函数为 式中 则式 14 可写成 17 16 当控制矢量u t 不受限制时 则有 上两式称为哈密尔顿 雅可比方程 上式说明 在最优轨线上 最优控制必须使H达全局最小 实际上这就是极小值原理的另一种形式 18 由贝尔曼方程可推导出协态方程和横截条件 式 14 可写成 对x求偏导数 得 20 19 14 由于对t的全导数 为 22 21 代入式 20 可写成 20 令 则上式可写成 23 这就是所求的协态方程 与以前结果完全一致 22 在t tf时 在终端处性能泛函为 式中 与N同维的乘子矢量 24 对x tf 求偏导数 得 25 26 即 24 将式 24 对tf求偏导数 得 27 24 考虑式 17 式 20 得 上述结果与极小值原理中推导的完全一致 上述推导过程实际上等于用动态规划方法间接证明了极小值原理 28 17 20 27 应当指出 与极小值原理相比 动态规划法需要解偏微分方程式 14 它要求J x t 具有连续的偏导数 但在实际工程中 这一点常常不能满足 因而限制了动态规划法的使用范围 例1 设 求最优控制u t 使 解 构造哈密尔顿函数 根据哈密尔顿 雅可比方程 有 考虑控制u不受限制 得 故 边界条件 因 x tf tf 0 故J x tf 0如果令 则得 这正是应用极小值原理所得的结果 二者完全一致 例2 设受控系统状态方程为 初始状态为 性能泛函为 试求在u无限制情况下 使J取极小时的最优控制 解 构造哈密尔顿函数 由哈密尔顿 雅可比方程 因u无限制 可从 求得 代入上式 并注意到J 与t无关 因而 有 为求解此偏微分方程 设其解为 满足方程 得 各项系数为 可得 解为 最优控制 最优控制可由状态反馈实现 如图7所示 进一步考察系统的状态轨线 系统的状态方程 为齐次方程 它的解为 于是最优控制为 性能泛函最优值为 例3 设受控系统的微分方程为 使性能指标 即要求快速响应 求最优控制u 且满足 解 若选 可得系统的状态方程 根据哈密尔顿 贝尔曼方程 为使 取全局最小 可得 在所论情况下 因J 与t无关 故哈密尔顿 贝尔曼方程为 这是一个非线性偏微分方程 需借助电子计算机求解J 再求J 对x2的偏导数便可求得最优控制 综上所述