动态规划讲座

《动态规划讲座》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.231动态规划讲座16概要•更多的滚动算法•基于仿真的方法•滚动算法的逼近•区间滚动逼近•离散化问题•其它的次最优化方法滚动算法•滚动策略：在每个时刻k和状态，利用控制量有其中以及为启发式余留代价。•称为的Q-因子，对于随机问题，其计算可以用MonteCarlo来仿真。•潜在的难题：为了使Q-因子对达到最小，我们必须构造Q-因子的偏差。在Q-因子计算中，这种偏差常常导致仿真误差变大。•潜在的补偿：通过直接仿真，比较任意两个控制量u和。Q-因子逼近•这里，不是仿真Q-因子，而是逼近余留代价。•确定性等价方法：给定，将今后的干扰固定在典型值上，用下式逼近Q-因子：

2、式中是启发式算法的代价在干扰为典型情况下的取值。•这是用“单一样本仿真”来逼近。•确定性等价方法中的变形：可以通过对少量“典型样本”的仿真来逼近。•替代方法：在有限的时间和状态对上，计算（精确或近似的）基本策略余留代价的值，然后用近似结构和“最小平方”来逼近。区间滚动方法•这是一个l步前瞻策略，它的近似余留代价刚好为0。•等价地，近似余留代价是终端代价泛函。•短的区间滚动节省计算量。•“反论”：通过更长的区间滚动计算来改善性能并不总是正确的。•例：在起始状态，有两个控制起作用（1和2），在其它的状态仅仅有一个控制作用。滚动算法与区间滚动算法的组合•在计算基本启发式

3、余留代价时，我们可以用区间滚动逼近的方法。•由于启发式算法是次最优的，区间滚动算法运行越长其作用就变得越不可靠。•例：N-步停止问题：停止代价为0，继续代价为－ε或1，0<ε<1/N，将继续代价为1时的第一个状态定义为状态m，最优策略是停在状态m，并且最优代价是－mε。•考虑启发式算法在每个状态的连续性，以及基于该启发式算法的滚动策略，该策略具有l≤m的区间滚动步数。•系统将延续最初m－l＋1步，从而构成了一个为－(m－l＋1)ε的代价。当l变短的时候，滚动算法运行便得到了改善。离散化•若状态空间或/和控制空间是连续/无限的，必须用一个有限的离散空间来替代。•从连

4、续性的要求上讲，随着离散化做得越来越好，离散问题的余留代价泛函便收敛到连续性问题的泛函上。•连续时间离散化后的缺陷。•当涉及离散时间逼近时，控制器的约束集发生很大变化。•例：控制约束为，i＝1，2。与离散化系统相比较有这里。•连续时间的“凸化效果”。常用离散化方法I•给定一个状态空间为S的离散时间系统，考虑其一个有限子集。例如，在连续状态空间S内，可能是有限网格。从方便考虑，可假定不变性，即在任何时间，每个阶段的系统方程和代价是不变的。•在状态空间内，我们定义一个原始问题的逼近过程，即：•将每个表示为中状态的凸组合，也就是：其中，•在状态空间上定义一个“简化”的动

5、态系统，根据原始问题的系统方程，我们将每一个移动至，然后再以概率移动到。•类似地，定义简化系统每个阶段相应的转移代价。常用离散化方法II•令为“简化”问题的最优余留代价，其中k为时间，状态为。•对任意的，由下式逼近原始问题的最优余留代价：并基于应用一步前瞻方法。•系数的选择在理论上讲是任意的，但应以连续性为原则，即，当中状态数目增加时，应收敛于原始问题的最优余留代价。•有趣现象：原始问题可能是确定性的，而简化的问题总是随机的。•一般化：集合可以是任何有限集合（不是的子集），只要系数可以表示x与之间的连接程度。其它次最优控制方法•使动态规划方程误差最小：用泛函逼近最

6、优余留代价泛函J(x)，这里是一个未知参数向量，用来使动态规划kk方程的误差为最小。•直接逼近控制策略：对于状态的一个子集，寻找：然后求出，其中是由下述问题解出的参数向量:•策略空间的逼近：不要受最优余留代价逼近的影响。将策略参数化为，然后使问题的代价泛函对求最小。