·14 智能系统学报 第3卷 和深度优先搜索算法进行求解.在每次迭代中，如 效.而FPG借鉴了策略梯度增强学习的算法思想 果存在一个不超过最优代价的解，那么找到解，否 这类算法不需要估计规划状态-动作对的值，而是 则，更新评价函数，求解过程重新开始.LDFS用 估计整个搜索过程长期平均回报的梯度.FPG使用 统一的符号元素为不同的模型定义，如确定的、非 的是OL POMDP(在线部分可观察马尔可夫决策过程) 确定的MDP、GT模型等，并给出针对这些模型的 策略梯度强化算法3).梯度的计算与控制与在决 贝尔曼方程.在此基础上，给出一个一般化的算 策点选择动作的参数有关，这些参数决定了策略、 法，即Find-and-Revise.对于任何一个可采纳的评 规划及系统.在梯度的影响下，调节参数的值使得 估函数，算法在策略π下找到一个从初始状态s0出 期望回报增加或初始状态的值增加. 发能够到达的状态s,在保证Res,(s>e情况下更 FPG的分解参数策略通过对每个动作应用参 新状态的评价值，最后返回评价函数.LDFS作为 数函数生成，此函数输入规划状态的描述，返回每 这一算法框架的一个实例，主要通过2个循环来实 个可取动作的概率分布.FPG的输入语言是mdp~ 现算法：一个循环位于状态s中的贪婪动作a上， sim可处理的全部语言，即在PDDL上进行了微小 a∈A(:另一个循环位于s的可能后继s’上.搜 的扩展36).FPG使用了mdpsim的数据结构和函 索中的端ip)节点是不一致的状态s、终止状态和 数实现了一个规划域的模拟器.文中算法1完整的 被标记为可解(solved)的状态.一个状态被标记为描述了FPG是怎样利用OL POMDE分解动作策略实 可解的，即在s下的搜索没有找到不一致的状态.现规划的.算法的目的是从状态空间中抽取一条路 如果s是一致的且在对s的后继状态s'搜索后标记 径：1)第1个状态作为规划的第0时间步的初始状 位为真，则s被标记为可解的，并记录动作a,s上 态；2)与可取动作相连的感知机输入当前状态s 的其他动作将不再被搜索.否则，对下一贪婪动作 的观察向量0：；3)每个感知机的网络计算其相对 进行试验，一直到没有这样的动作存在时为止，更 应动作的可取程度；4)选择一个规划动作；5)选 新s值.算法结束时返回评估函数和贪婪策略 择一个状态转移；6)规划器接收新的状态动作的 试验结果表明，在某些模型问题中，如Max、 全局回报同时生成即时梯度g=ne,;7)所有参数 AND/OR图中，LDFS并不比其他的一些算法表现 在梯度g的导向下立即更新. 差，事实上，在某些方面LDFS的性能还略胜一筹. FPG规划器能对较大问题域生成好的策略，它 2.3FPG方法 的缺点是其局部最优性、参数简化、观察范围减少导 分解策略梯度规划器(factored policy gradient 致可能生成次优规划.梯度的变化次数是关于 planner,.FPGB]是为解决较大规划问题域而设计 POMDP混合时间(mixing time)的函数，随着状态 的概率时序规划器，FPG与传统规划方法的区别主 的增多会成指数级增长，怎样计算任意MDP的 要有2点，首先，FPG是有导向的进行规划搜索， mixing time仍是一个开放问题 利用在线梯度下降法寻找最优的参数规划.其次， 2.4基于LA0的方法 策略被分解到每个动作中，从部分观察值映射到动 经典的启发式搜索算法可找到以简单路径 作可能执行的概率，反映出每个动作可取的程度 (A)、树或非循环图(AO`)形式的解.EicA. 与其他概率时序规划器不同，FPG在保证总 Hansen和Shlomo Zilberstein提出了一个新的一般 makespan最小的同时使成功到达目标的概率最大. 化的启发式搜索算法LAO`(generalization of FPG的目标是处理现实世界问题域并生成好 A0)2,列)，它是目前求解决策理论规划问题最为 的策略，它通过以下几点能实现目标：1)使用梯度 高效的算法之一.该算法结合了启发式搜索和动态 下降法导向策略搜索：2)将策略分解成针对每个 规划的优点，可以在不需评估整个状态空间的基础 动作简单的近似策略；3)利用临界观察提取出每 上寻找一条带有循环(1oop)的最优解.在2004年 个策略：4)使用蒙特卡罗(Monte-Carlo)算法的思 举办的第1届国际不确定智能规划比赛中，它取得 想，存储器需求独立于状态空间的大小.而前面所 了“overall,nomblocks/box”组的冠军 介绍的规划算法将概率规划问题描述成为一个状态 AO'是AI中应用于状态空间搜索的一个著名 空间，对长期价值效用和选择每个动作的代价进行 启发式算法.AO算法找到的解是解图，形式化为 评估4).它们的缺点是需要估计大量的状态·动 树或更一般化的是一个非循环的图.AO'算法通过 作对的值，即使算法修剪了大部分状态，但当问题 从初始状态出发，逐渐构造一个解图的方法来解决 域扩大时，相关状态会成指数级增长，使得算法失 状态空间搜索问题.它可以理解为下列2个主要运 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net和深度优先搜索算法进行求解. 在每次迭代中 , 如 果存在一个不超过最优代价的解 , 那么找到解 , 否 则 , 更新评价函数 , 求解过程重新开始. LDFS 用 统一的符号元素为不同的模型定义 , 如确定的、非 确定的、MDP、GT 模型等 , 并给出针对这些模型的 贝尔曼方程. 在此基础上 , 给出一个一般化的算 法 , 即 Find2and2Revise. 对于任何一个可采纳的评 估函数 , 算法在策略π下找到一个从初始状态 s0 出 发能够到达的状态 s, 在保证 Res v (s) >ε情况下更 新状态的评价值 , 最后返回评价函数. LDFS 作为 这一算法框架的一个实例 , 主要通过 2 个循环来实 现算法 : 一个循环位于状态 s 中的贪婪动作 a 上 , a ∈A (s) ; 另一个循环位于 s 的可能后继 s’上. 搜 索中的端(tip) 节点是不一致的状态 s、终止状态和 被标记为可解(solved) 的状态. 一个状态被标记为 可解的 ,即在 s 下的搜索没有找到不一致的状态. 如果 s 是一致的且在对 s 的后继状态 s’搜索后标记 位为真 , 则 s 被标记为可解的 , 并记录动作 a , s 上 的其他动作将不再被搜索. 否则 , 对下一贪婪动作 进行试验 , 一直到没有这样的动作存在时为止 , 更 新 s 值. 算法结束时返回评估函数和贪婪策略. 试验结果表明, 在某些模型问题中, 如 Max、 AND/ OR 图中 , LDFS 并不比其他的一些算法表现 差 , 事实上 , 在某些方面 LDFS 的性能还略胜一筹. 2. 3 F PG方法 分解策略梯度规划器 (factored policy gradient planner , FPG) [33 ]是为解决较大规划问题域而设计 的概率时序规划器 , FPG与传统规划方法的区别主 要有 2 点 , 首先 , FPG 是有导向的进行规划搜索 , 利用在线梯度下降法寻找最优的参数规划. 其次 , 策略被分解到每个动作中 , 从部分观察值映射到动 作可能执行的概率 , 反映出每个动作可取的程度. 与其他 概 率 时 序 规 划 器 不 同 , FPG 在 保 证 总 makespan 最小的同时使成功到达目标的概率最大. FPG的目标是处理现实世界问题域并生成好 的策略 , 它通过以下几点能实现目标 : 1) 使用梯度 下降法导向策略搜索 ; 2) 将策略分解成针对每个 动作简单的近似策略 ; 3) 利用临界观察提取出每 个策略 ; 4) 使用蒙特卡罗 (Monte2Carlo) 算法的思 想 , 存储器需求独立于状态空间的大小. 而前面所 介绍的规划算法将概率规划问题描述成为一个状态 空间 , 对长期价值效用和选择每个动作的代价进行 评估[ 34 ] . 它们的缺点是需要估计大量的状态 - 动 作对的值 , 即使算法修剪了大部分状态 ,但当问题 域扩大时 ,相关状态会成指数级增长 ,使得算法失 效. 而 FPG借鉴了策略梯度增强学习的算法思想 , 这类算法不需要估计规划状态 - 动作对的值 , 而是 估计整个搜索过程长期平均回报的梯度. FPG使用 的是 OL POMDP (在线部分可观察马尔可夫决策过程) 策略梯度强化算法[35 ] . 梯度的计算与控制与在决 策点选择动作的参数有关 , 这些参数决定了策略、 规划及系统. 在梯度的影响下 , 调节参数的值使得 期望回报增加或初始状态的值增加. FPG的分解参数策略通过对每个动作应用参 数函数生成 , 此函数输入规划状态的描述 , 返回每 个可取动作的概率分布. FPG 的输入语言是 mdp2 sim 可处理的全部语言 ,即在 PDDL 上进行了微小 的扩展[ 36 ] . FPG 使用了 mdp sim 的数据结构和函 数实现了一个规划域的模拟器. 文中算法 1 完整的 描述了 FPG 是怎样利用 OL POMDP分解动作策略实 现规划的. 算法的目的是从状态空间中抽取一条路 径 : 1) 第 1 个状态作为规划的第 0 时间步的初始状 态 ; 2) 与可取动作相连的感知机输入当前状态 st 的观察向量 ot ; 3) 每个感知机的网络计算其相对 应动作的可取程度 ; 4) 选择一个规划动作 ; 5) 选 择一个状态转移 ; 6) 规划器接收新的状态动作的 全局回报同时生成即时梯度 gt = rt et ; 7) 所有参数 在梯度 gt 的导向下立即更新. FPG规划器能对较大问题域生成好的策略 ,它 的缺点是其局部最优性、参数简化、观察范围减少导 致可能生成次优规划. 梯度的变化次数是关于 POMDP 混合时间(mixing time) 的函数 , 随着状态 的增多会成指数级增长 , 怎样计算任意 MDP 的 mixing time 仍是一个开放问题. 2. 4 基于 LAO 3 的方法 经典的启发式搜索算法可找到以简单路径 (A 3 ) 、树或非循环图 ( AO 3 ) 形式的解. Eric A. Hansen 和 Shlomo Zilberstein 提出了一个新的一般 化的 启 发 式 搜 索 算 法 LAO 3 ( generalization of AO 3 ) [ 12 ,37 ] , 它是目前求解决策理论规划问题最为 高效的算法之一. 该算法结合了启发式搜索和动态 规划的优点 , 可以在不需评估整个状态空间的基础 上寻找一条带有循环 (loop) 的最优解. 在 2004 年 举办的第 1 届国际不确定智能规划比赛中 , 它取得 了“overall , non2blocks/ box”组的冠军[ 14 ] . AO 3 是 AI 中应用于状态空间搜索的一个著名 启发式算法. AO 3 算法找到的解是解图 , 形式化为 树或更一般化的是一个非循环的图. AO 3 算法通过 从初始状态出发 , 逐渐构造一个解图的方法来解决 状态空间搜索问题. 它可以理解为下列 2 个主要运 · 41 · 智 能 系 统 学 报 第 3 卷