部分可观察马尔可夫决策过程研究进展

1、0引 言部分可观察马尔可夫决策过程 (partially observable Markov decision processes , POMDP 描述的是当前世界模型部分可知的 情况下,智能体 Agent Agent 的 例如, 足球运动员在球场上踢 足球, 每个球员并不完全清楚他周围的所有状态, 当他向前 带球的过程中, 他可能知道在他前面人的位置和状态, 但是 可能不知道在他后面的其他队友的位置和状态, 此时他观察 到的信息是不完整的, 但是一个优秀的足球运动员往往靠着 一种感觉传给他身后的最有利的队员, 使其进行最有利的进 攻,过程就是部分可观察马尔可夫决策过程。在部分可感知模 型中,

2、 不仅要考虑到状态的不确定性, 同时还要考虑到动作 的不确定性,这种世界模型更加能够客观的描述真实世界, 因此应用十分广泛。本文综述了目前在 POMDP 领域的研究情况, 介绍了 MDP 的数学理论基础和决策模型, 以及一种典型的 POMDP 决策算 法-值迭代算法, 介绍了目前现有的几种经典的决策算法, 并 分析它们之间的优点和不足, 列举了一些 POMDP 常见的应用 领域, 并进行了总结和展望。1马尔可夫决策过程Agent 每一个时刻都要做一些决策, 做决策时不仅要考虑 甚至是其它 Agents (Markov decision process , MDP 的最优解, MDP 可以用一个

3、四元组 < , >来描述 1 :Agent 的行为集;, : ×:当 Agent 在状态 , 可能转移到状态 的概率, 使用 |: 情况下 采用动作-2116-2117 -, Agent 使 Agent 选择的动作能够获得在 MDP 模型中, Agent 在为折扣因子, 其目标是让期望值有界(1由于 MDP 决策过程中, 要同时考虑世界模型的不确定性 和目标的长远性, 需要在策略时刻, 状态的情况下, 值函数构造如下 = , = ,*,也就是 Agent 每个时刻都能做到的最优决策, 根据 Bellman 最优策略公式可以得到。根据贪婪策略 *=arg max ,*1(4

4、 = max,*(5最优策略的通常使用值迭代算法 2, 具体的算法步骤如下 步骤 1初始化 V 1(s =0, 假定一个任意小的数值= max,1得到 V t (S ; 步骤 3判断下式, 如果结果为真, 则进入步骤 4; 否则返回步骤 2; 1 <步骤 4对于每个 s S , 取 =arg max,1由于下式可以知道, 值迭代算法所求出来的策略将是最 优策略 max *(62POMDPs在 POMDP 模型中, Agent 必须利用随机环境中部分观察 在每个时间点上, Agent 都可能是众多可 能状态中的某一状态, 它必须利用现有的部分信 息、 1,3。 一般情况下, POMDP 可

5、以用一个六元组 < , , >来描述, 其中、 与 MDP 一样。 , : ×£ºA gent 它可计算出采 用动作:Agent 使用来描述 Agent 处在用以下的形式来进行描述 4,5 : × ;、 行 为得到, 具体的过程根据贝叶斯计算如下 , , , , ,Pr, = Pr, Pr , ,策略 Agent 世界模型 s a图 2MDP 决策t 时刻状态 S t t+1时刻状态 S t+1T 函数R选取 动作 报酬 值选取 动作 报酬 值图 3 POMDP 模型状态评估 (SE 图 4决策行动信念观察状态abosa'b'

6、o's' R (s, a O (s', a, o T (s, a, s' b (s -2118 -Pr , =Pr , , =Pr , Pr , = , , = , , = , ,(8以前的观点来解决 POMDP 问题时, 由于必须知道历史动 作才能决定当前的动作, 这种解决方案是非马尔可夫链, 然而 当引入信念状态空间后, POMDP 问题就可以转化为基于信念 状态空间的马尔可夫链来求解。通过信念状态空间的引入, POMDP 问题可以看成 Belief MDP 问题3。寻求一种最优策略将当前的信念状态映射到Agent 的行动上, 根据当前的信念状态和行为就可以

7、决定下一 个周期的信念状态和行为, 具体描述如下 ,=Pr(b' a,b =a,b,o(b,a :信念状态报酬函数, 其定义如下 *=arg max * *= max*1 -策略树 (如图 5所示 和值函数, 通过求解值函数来进行最优策略的选取。令 -策略树, - 策略树的集合, 为策略树的节点, 则值函数的构造如下 = + , , =(14为了简化表达, 令 =< , =µÄ×îÓÅÖµ£¬Í¼6 描述了在不同区域的最优值= max(15 对于以上策略树, 其

8、最大的节点数为 ( |-1 , 其中 |1(16策略树的时间复杂度是一个指数函数,随着,然后将所有节点的策略集合求或, 得到值函数4,5。 由于 |、 |1|的时间复杂度是多项式的, 因此1(18 (19W i t n e s s算法不去关注所有时间的所有动作, 它将每个节点进行分解, 取获取每个节点的最优动作, 然后在将所有的最 优动作转换为最终的值函数。 这种算法在某些情况下可以降 低计算的复杂度, 但对世界模型的建模不够完整, 难以保证所求得的解一定是有效的, 算法如图 7所示。3.2Incremental Pruning 算法Witness 算法对于小规模的计算时效果比较好, 但是当问

9、题规模变大后,使用 Witness 算法就很难求得近似最优解。 Zhang and Liu (1996 提出一种 Incremental Pruning 算法 (如图 8所示 可以较好的解决较大规模问题。该算法的基本思想是 使用动态规划方法根据给定的值函数 ,t =t +1;whi l e ( 1 <12 O-2119- 数 =max +(20 =max =(22 表示成向量集合 表示成向量集合 , 将 =max 表示成向量集合 =max 表示成向量集合(24 1 2(25 = , , , Pr ,3.3基于点的值迭代算法以上两种算法都是通过降低信念状态空间的维数来降低求解的规模, 但是

10、在实际的求解过程中历史观察-动作集合 也是一个指数函数, 如何降低历史观察-动作函数的求解复 杂度也是衡量一种算法优劣的重要尺度。 基于点的值迭代算 法 Jolle Pineau,Geoff Gordon and Sebastian Thrun,2003主要是通 过降低历史观察-动作值函数的求解规模来近似求解 POMDP 问题 7。 基于值迭代的算法都是 PWLC 的, 可以表示为可以看成 Backup 操作, 每个动作都对应一个 +, , ,=, 实现精确更新, 首先引入中间变量, * =,0 =, , 1 =|O| , 也就是所谓的 “维数灾” 问题, 使得问题无法求解。 为了解决这个问题

11、, Witness 算法、 Incremental Pruning 算法和基于点 的值迭代算法都是将整个问题进行分解,构造, |, |。4POMDP 应用领域20世纪末,由于看到 POMDP 模型可以更加真实的反应 客观世界模型, 人们开始对 POMDP 进行大量的研究和应用 9。 在科学应用领域, 科学家主要将其应用到自主机器人控制上。 例如:在太空中的漫步机器人; 机器人导航; 炸弹拆除; 放射性 废物回收; 深海探矿; 管道网络的检修和维护等, 在这些领域中, 人们不可能直接操作, 只能依靠机器人来进行, 同时这些 领域的环境条件非常符合 POMDP 模型。在工业应用领域, 例如机器生产

12、和维护, 人们可以建立一 个 POMDP 模型, 使得最小化机器使用费用, 最大化生产能力。 例 如 道 路 检 测 管 理,美 国 高 速 公 路 就 是 一 个 成 功 案 例, Woodward-Clycde 公司开发了一个基于马氏决策过程的公路 管理系统, 使用有限的资金来维护公路, 这个系统 4年内就节 省了 1亿多美元。在养鱼行业中,也需要在短期目标和长期 目标之间作平衡, 使用 POMDP 模型决策可以达到这一目的。 在商业应用领域, 例如网络故障查找和排除, 假如电网出现故 障, 需要快速地找到故障处并排除它。 在市场管理领域, 人们 可以开发基于 POMDP 的软件来解决库存

13、问题, 使得利润最大 化。 POMDP 还可以应用到医疗诊断问题上, 尽早查处病因。 在军事领域, POMDP 的应用也很广泛, 例如:移动目标的查找、 跟踪和拯救; 目标的辨认; 武器的使用分配等。5结束语解决 POMDP 问题的算法有很多种, 但是从本质上都是基于动态规划和线性规划思想, 对所求问题进行分解, 降低 “维 数灾” 问题, 然后采用值迭代算法进行求解。 本文重点介绍和 分析了 Witness 算法、 Incremental Pruning 算法和基于点的值迭 代算法, 这 3种算法虽然表达方式不同, 但是一个本质思想就 是降低所求问题的规模, 求出近似解。(下转第 2126页

14、 DP-Update (S For each a in A and o in O;S o a =Filter ( , S t-1 ;S a =IncPrune ( , ; =return S' IncPrune ( , W=RR (2; for (i=3;i<=k;i+ W=RR( W, ; retrun W; RR (A, B F=A;W=W w ; F=Fw ; while (F +1=(a 1+1+1+|<|+;W=W w ; F=Fw ; retrun W;图 8Incremental Pruning 算法表 13种算法分析比较算法指标最坏 最好 Witness 算

15、法 O (ZMQ 2 O (ZMQ 2 Incremental Pruning 算法O (ZMQ 2 O (ZQ 2 基于点的值迭代算法O (Z 2M 2Q O (ZMQ 3系统实现在上述研究和分析的基础上, 以全国高校仪器设备和优 质资源共享项目为契机, 设计实现了基于 Web 贵重仪器设备 共享系统。 系统采用 J2EE 技术, 设计为典型的 B/S结构:表示 层是浏览器, 显示用户界面; 应用层为服务器和应用程序, 应 用程序由 JSP 、 Servlet 、 Javabean 、 Applet 和 EJB 构成; 数据层存 储了仪器设备的相关信息。通过该系统, 各高校之间可以通 过 I

16、nternet 便捷的共享贵重仪器设备资源, 提高贵重仪器的使 用率, 实现高校之间优势资源互补, 提高国内高校综合实力和 竞争能力。4结束语基于 Web 贵重仪器设备共享系统充分体现了贵重仪器设 备远程操作和共享的特点。 系统采用基于 Web 的工作机制和 混合式共享模式有利于信息的动态更新和统一管理, 有利于 解决地理位置分布性和软硬件平台异构性的问题, 保证了系 统的鲁棒性、 通用性和可扩展性, 为贵重仪器设备的远程操作 和共享奠定了基础。系统采用基于角色的访问控制技术, 实 现了 “用户 -角色 -权限” 管理模式, 保证了数据和系统的安全 性, 降低了管理难度, 而且可以满足用户多样

17、化需求; 采用屏 幕共享技术开发了第三方共享软件, 实现了通过 Internet 对贵 重仪器设备的远程操作和共享, 保证了软件的通用性。系统 可以避免贵重仪器设备的重复购置, 提高现有资源的使用率, 为最终建立全国范围内共性的和跨地区、 跨高校的网上仪器 设备资源共享应用服务平台提供良好的基础。参考文献 :1范莉娅 , 王爱民 , 肖田元 , 等 . 基于 Web 的全生命周期项目管理 系统研究 J . 机械科学与技术 , 2005,24(5 :529-532.2杨志宝 , 罗亚波 , 肖田元 . 面向中小企业的 ASP 方案研究 J . 计 算机工程与应用 , 2003,39(22 :19

18、8-201.3孙笑庆 , 刘宝旭 , 姜力东 , 等 .FreeNet 中的密钥和索引机制综述 J . 计算机工程与应用 , 2003,39(11 :138-141.4张联峰 , 刘乃安 , 钱秀槟 , 等 . 综述 :对等网 (P2P 技术 J . 计算机工 程与应用 , 2003,39(12 :142-145.5毛科杰 . 网络化制造平台公共服务技术研究 D . 北京 :清华大 学 , 2005.6侯永涛 , 顾寄南 . 网络化制造环境下的软件工具共享技术的研 究综述 J . 中国制造业信息化 , 2004,33(9 :86-88.(上接第 2119页 目前 POMDP 面临两大问题, 其

19、一是 “维数灾” 问题, 涉及 的是时间复杂度; 另一种是 “应用建模难” 问题。对于 “维数 灾” 问题, 除了使用动态规划和线性规划思想外, 还需探讨其 它解决方案, 同时加入学习算法, 特别是增强学习、 分层学习。 对于 “应用建模难” 问题, 在许多应用领域中, 看起来很简单的 问题, 但是却需要很大的状态空间, 因此需要一些新的算法来 高效地解决这个问题。 以上两种问题的解决, 是 POMDP 的未 来研究的主要方向。参考文献 :1Stephen M Majercik, Michael L Littman. Contingent planning under uncertainty

20、via stochastic satisfiability J . Artificial Intel-ligence, 2003,147(1-2 :119-162.2刘克 . 实用马尔可夫决策过程 M . 北京 :清华大学出版社 , 2004. 20-52.3Alexander L Strehl, Michael L Littman. An empirical evaluation of interval estimation for Markov decision processes A . The 16th IEEE International on Tools with Artifici

21、al Intelligence Conference C . Seattle:The MIT Press, 2004. 531-539.4Poupart P . Exploiting structure to effciently solve large scale partially observable Markov decision processes D . Toronto: University of Toronto, 2005.5SébastienPaquet, Ludovic Tobin, Brahim Chaibdraa. An onlinePOMDP algorit

22、hm for complex multi-Agent environment A . The Proceedings of The fourth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS-05 C . Netherlands:Utrecht University,2005. 970-977.6Haakan L S Younes, Michael L Littman, David Weissman, et al. The first probabilistic track of the international planning compe-tition J . Journal of Artificial Intelligence Research, 2005, 24: 851-887.7Pineau J, Gordon G, Thrun S. Point-based value iteration:An anytime algorithm