·12 智能系统学报 第3卷 由此，可得到贝尔曼方程的一个简化版本2 状态空间. f9=c(g,9+y7s,,ss1. Kof等人以模拟自动车辆行驶路径的路径追 踪问题为例26)，比较了几种不同算法2)，得出 (4) RTDP能够快速收敛于一种次优策略，其后，其他 在求解规划的过程中，由于策略迭代要更新每 研究人员也以实验结果证明了较大状态空间问题中 个状态的策略，其求解速度也是相对缓慢的 该算法的快速收敛性.因而RTDP的最大优点是可 2.2启发式动态规划算法 以在较短的时间内得到一个较好的策略.但由于很 用动态规划方法求解规划问题起到了良好的效 多状态被频繁地更新，所以在每个状态上完全收敛 果.但是，这些算法在更新状态的评估值时，均考 的速度是非常慢的，这是其缺点之一.另外，RT 虑了所有状态的评估值或策略，对于大的状态空间 DP算法要求系统的状态是完全可观察的，但在现 问题，其复杂度是让人望而却步的.鉴于此，研究 实中却很难满足，因此，还需要改进算法，以提高 者将启发式技术引入到动态规划算法中，以提高求 效率或者解决更复杂的问题 解规划的效率.下面重点介绍几种启发式动态规划 2.2.2基于Labeled RTDP的方法 (heuristic search dynamic programming algo- 由于RTDP的收敛速度比较缓慢，Labeled rithms.HS/DP) RTDP(LRTDP)算法I引入一个标记方案，提高 2.2.1基于RTDP的方法 了RTDP的收敛速度，同时保留了RTDP的其他 1995年Barto等人提出了实时动态规划算法 优点 (real-time dynamic programming,RTDP)241, Labeled RTDP算法的标记功能由一个被称为 里的“实时”指的是动作必须在严格的时间约束下执 Checksolved的标记程序完成.它的主要思想是： 行，其实质是通过对Kof提出的LRTA*2)算法 当贪婪策略定义在状态s上的启发式值和从s出发 进行扩展，来解决随机最短路径问题.在RTDP算 利用贪婪选择策略可达的那些状态上的启发式值都 法中，并不对所有状态的评估函数进行更新，因而 收敛时，标记状态为可解状态(solved).状态s及 减少了状态空间，在一定的假设前提条件下，RT- 由s出发利用贪婪策略可达的那些状态组成的图称 DP收敛于一种最优策略， 为状态s的贪婪图(greedy graph),贪婪图中的状 RTDP在一个单一的执行路迹(trace)上模拟 态构成的集合成为状态s的贪婪封装集(greedy en- 贪婪策略，并使用贝尔曼更新方程更新它们访问到 velope).状态s被激活时，Checksolved程序开始 的状态的评估值.这里主要介绍tria-based RTDP 搜索以s为根结点的贪婪图，寻找是否存在误差大 算法.该算法通过将状态上的计算组织为Sequem- 于E的状态s',如果不存在误差大于e的状态，则 tial trials而求解规划问题.Sequential trials是一 标记s为可解状态且Checksolved(s)返回true,即 种一边试验一边修正试验方案的试验方法.一个 当值函数在状态s上收敛时，标记s为可解.如果 RTDP试验是一个路径，每一个试验包含一系列步 在状态s的贪婪封装集中出现误差大于ε的一个状 骤(steps)).在每一步骤中，根据前向一步或多步深 态s'时，状态s和与其相关的状态都要被更新 度搜索而选择动作，基于动作的结果，选择当前的 Checksolved(s)返▣false.Checksolved的代码在 状态.包含当前状态的一个状态子集的代价函数被 文献[13]中的算法3中给出，状态s的标记在程序 更新，也即控制器总是遵循与最近更新的最优评估 中用哈希表的1个比特位表示，记为s.solved,一 函数相对应的贪婪策略，通过这个策略来选择将要 个状态s被标记为可解当且仅当s.solved=true 执行的动作，基于被选择的这个动作来更新当前状 LRTDP算法通过模拟试验实现，除了终止条件不 态.在每一个试验的开始，当前状态被设置为开始 同，它与RTDP的试验非常相似.实验从初始状态 状态，当到达目标状态或经过一定的步骤数之后，开始，以贪婪策略π，选择动作，以相应的转移概率 试验结束.RTDP反复执行这样的试验，直至收 选择后继状态，直到到达一个可解状态时实验结束 敛.RTDP的一个重要特性是，它只更新从初始状 (初始时只有目标状态是可解状态).每次实验结 态能够到达的那些状态的评估值，可能忽略了状态 束，调用标记程序Checksolved,反向核对状态的 空间中的许多状态，因而可以相对比较快地产生一 值函数的值，从最后一个不可解状态(unsolved)开 个相对比较好的策略.文献[24]证明在确定性合理 始回溯遍历到%，直到程序在一些状态上返回 条件下，RTDP逐渐收敛于最优解而不用估计整个 false.当初始状态so被标记为可解时，Labeled 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net由此 , 可得到贝尔曼方程的一个简化版本[22 ] : f i (s) = c(πi (s) ,s) +γ s′∑∈S T (s,πi (s) ,s′) f i (s′) . (4) 在求解规划的过程中 , 由于策略迭代要更新每 个状态的策略 , 其求解速度也是相对缓慢的. 2. 2 启发式动态规划算法 用动态规划方法求解规划问题起到了良好的效 果. 但是 , 这些算法在更新状态的评估值时 , 均考 虑了所有状态的评估值或策略 , 对于大的状态空间 问题 , 其复杂度是让人望而却步的. 鉴于此 ,研究 者将启发式技术引入到动态规划算法中 , 以提高求 解规划的效率. 下面重点介绍几种启发式动态规划 算法( heuristic search / dynamic programming algo2 rit hms , HS/ DP) . 2. 2. 1 基于 R TD P 的方法 1995 年 Barto 等人提出了实时动态规划算法 (real2time dynamic programming , RTDP) [24 ] , 这 里的“实时”指的是动作必须在严格的时间约束下执 行 , 其实质是通过对 Korf 提出的 LRTA 3 [25 ] 算法 进行扩展 , 来解决随机最短路径问题. 在 RTDP 算 法中 , 并不对所有状态的评估函数进行更新 , 因而 减少了状态空间 , 在一定的假设前提条件下 , RT2 DP 收敛于一种最优策略. RTDP 在一个单一的执行路迹 (trace) 上模拟 贪婪策略 , 并使用贝尔曼更新方程更新它们访问到 的状态的评估值. 这里主要介绍 trial2based RTDP 算法. 该算法通过将状态上的计算组织为 Sequen2 tial trials 而求解规划问题. Sequential trials 是一 种一边试验一边修正试验方案的试验方法. 一个 RTDP 试验是一个路径 , 每一个试验包含一系列步 骤(step s) . 在每一步骤中 , 根据前向一步或多步深 度搜索而选择动作 , 基于动作的结果 , 选择当前的 状态. 包含当前状态的一个状态子集的代价函数被 更新 , 也即控制器总是遵循与最近更新的最优评估 函数相对应的贪婪策略 , 通过这个策略来选择将要 执行的动作 , 基于被选择的这个动作来更新当前状 态. 在每一个试验的开始 , 当前状态被设置为开始 状态 , 当到达目标状态或经过一定的步骤数之后 , 试验结束. RTDP 反复执行这样的试验 , 直至收 敛. RTDP 的一个重要特性是 , 它只更新从初始状 态能够到达的那些状态的评估值 , 可能忽略了状态 空间中的许多状态 , 因而可以相对比较快地产生一 个相对比较好的策略. 文献[24 ]证明在确定性合理 条件下 , RTDP 逐渐收敛于最优解而不用估计整个 状态空间. Korf 等人以模拟自动车辆行驶路径的路径追 踪问题为例[26 ] , 比较了几种不同算法[27 ] , 得出 RTDP 能够快速收敛于一种次优策略 ; 其后 , 其他 研究人员也以实验结果证明了较大状态空间问题中 该算法的快速收敛性. 因而 RTDP 的最大优点是可 以在较短的时间内得到一个较好的策略. 但由于很 多状态被频繁地更新 , 所以在每个状态上完全收敛 的速度是非常慢的 , 这是其缺点之一. 另外 , RT2 DP 算法要求系统的状态是完全可观察的 , 但在现 实中却很难满足. 因此 , 还需要改进算法 , 以提高 效率或者解决更复杂的问题. 2. 2. 2 基于 Labeled RTDP 的方法 由于 RTDP 的收敛速度比较缓慢 , Labeled RTDP(LRTDP) 算法[ 13 ] 引入一个标记方案 , 提高 了 RTDP 的收敛速度 , 同时保留了 RTDP 的其他 优点. Labeled RTDP 算法的标记功能由一个被称为 Checksolved 的标记程序完成. 它的主要思想是 : 当贪婪策略定义在状态 s 上的启发式值和从 s 出发 利用贪婪选择策略可达的那些状态上的启发式值都 收敛时 , 标记状态为可解状态 (solved) . 状态 s 及 由 s 出发利用贪婪策略可达的那些状态组成的图称 为状态 s 的贪婪图 (greedy grap h) , 贪婪图中的状 态构成的集合成为状态 s 的贪婪封装集(greedy en2 velope) . 状态 s 被激活时 , Checksolved 程序开始 搜索以 s 为根结点的贪婪图 , 寻找是否存在误差大 于ε的状态 s’, 如果不存在误差大于ε的状态 , 则 标记 s 为可解状态且 Checksolved (s) 返回 true , 即 当值函数在状态 s 上收敛时 , 标记 s 为可解. 如果 在状态 s 的贪婪封装集中出现误差大于ε的一个状 态 s’时 , 状态 s 和与其相关的状态都要被更新 , Checksolved (s) 返回 false. Checksolved 的代码在 文献[ 13 ]中的算法 3 中给出 , 状态 s 的标记在程序 中用哈希表的 1 个比特位表示 , 记为 s. solved , 一 个状态 s 被标记为可解当且仅当 s. solved = true. L RTDP 算法通过模拟试验实现 , 除了终止条件不 同 , 它与 RTDP 的试验非常相似. 实验从初始状态 开始 , 以贪婪策略πv 选择动作 , 以相应的转移概率 选择后继状态 , 直到到达一个可解状态时实验结束 (初始时只有目标状态是可解状态) . 每次实验结 束 , 调用标记程序 Checksolved , 反向核对状态的 值函数的值 , 从最后一个不可解状态 ( unsolved) 开 始回溯遍历到 s0 , 直到程序在一些状态上返回 false. 当初始状态 s0 被标记为可解时 , Labeled · 21 · 智 能 系 统 学 报 第 3 卷