工笔画线描花鸟画谱 金鱼篇_部分7.pdf

文档介绍：动态规划
讲座16
概要
•更多的滚动算法
•基于仿真的方法
•滚动算法的逼近
•区间滚动逼近
•离散化问题
•其它的次最优化方法
滚动算法
•滚动策略:在每个时刻k和状态,利用控制量
有
其中
以及为启发式余留代价。
•称为的Q-因子,对于随机问题,其计算
可以用Monte Carlo来仿真。
•潜在的难题:为了使Q-因子对达到最小,我们必须构
造Q-因子的偏差。在Q-因子计算中,这
种偏差常常导致仿真误差变大。
•潜在的补偿:通过直接仿真,比较任
意两个控制量u和。
Q-因子逼近
•这里,不是仿真Q-因子,而是逼近余留代价。
•确定性等价方法:给定,将今后的干扰固定在典型值
上,用下式逼近Q-因子:
式中是启发式算法的代价在干扰为典型情
况下的取值。
•这是用“单一样本仿真”来逼近。
•确定性等价方法中的变形:可以通过对少量“典型样本”的仿
真来逼近。
•替代方法:在有限的时间和状态对上,计算(精确或近似
的)基本策略余留代价的值,然后用近似结构和“最小平方”
来逼近。
区间滚动方法
•这是一个l步前瞻策略,它的近似余留代价刚好为0。
•等价地,近似余留代价是终端代价泛函。
•短的区间滚动节省计算量。
•“反论”:通过更长的区间滚动计算来改善性能并不总
是正确的。
•例:在起始状态,有两个控制起作用(1和2),在其
它的状态仅仅有一个控制作用。
滚动算法与区间滚动算法的组合
•在计算基本启发式余留代价时,我们可以用区间滚动逼近的方法。
•由于启发式算法是次最优的,区间滚动算法运行越长其作用就变得越
不可靠。
•例:N-步停止问题:停止代价为0,继续代价为-ε或1,0< ε<1/N ,
将继续代价为1时的第一个状态定义为状态m,最优策略是停在状态
m,并且最优代价是-mε。
•考虑启发式算法在每个状态的连续性,以及基于该启发式算法的滚动
策略,该策略具有l≤m的区间滚动步数。
•系统将延续最初m-l+1步,从而构成了一个为-(m-l+1)ε的代价。
当 l 变短的时候,滚动算法运行便得到了改善。
离散化
•若状态空间或/和控制空间是连续/无限的,必须用一个有限
的离散空间来替代。
•从连续性的要求上讲,随着离散化做得越来越好,离散问
题的余留代价泛函便收敛到连续性问题的泛函上。
•连续时间离散化后的缺陷。
•当涉及离散时间逼近时,控制器的约束集发生很大变化。
•例:
控制约束为,i=1,2。与离散化系统相比
较有
这里。
•连续时间的“凸化效果”。
常用离散化方法I
•给定一个状态空间为S的离散时间系统,考虑其一个有限子
集。例如,在连续状态空间S内, 可能是有限网格。从
方便考虑,可假定不变性,即在任何时间,每个阶段的系
统方程和代价是不变的。
•在状态空间内,我们定义一个原