0引言部分可观察马尔可夫决策过程 (partially observable Markov decision processes , POMDP 描述的是当前世界模型部分可知的情况下,智能体 Agent Agent 的例如, 足球运动员在球场上踢足球, 每个球员并不完全清楚他周围的所有状态, 当他向前带球的过程中, 他可能知道在他前面人的位置和状态, 但是可能不知道在他后面的其他队友的位置和状态, 此时他观察到的信息是不完整的, 但是一个优秀的足球运动员往往靠着一种感觉传给他身后的最有利的队员, 使其进行最有利的进攻,过程就是部分可观察马尔可夫决策过程。
在部分可感知模型中, 不仅要考虑到状态的不确定性, 同时还要考虑到动作的不确定性,这种世界模型更加能够客观的描述真实世界, 因此应用十分广泛。
本文综述了目前在 POMDP 领域的研究情况, 介绍了 MDP 的数学理论基础和决策模型, 以及一种典型的 POMDP 决策算法-值迭代算法, 介绍了目前现有的几种经典的决策算法, 并分析它们之间的优点和不足, 列举了一些 POMDP 常见的应用领域, 并进行了总结和展望。
1马尔可夫决策过程Agent 每一个时刻都要做一些决策, 做决策时不仅要考虑甚至是其它 Agents (Markov decision process , MDP 的最优解, MDP 可以用一个四元组<, >来描述 [1]::Agent的行为集;, :×:当 Agent在状态 ,可能转移到状态的概率,使用 |:→ 情况下采用动作-2116--2117-, Agent 使 Agent 选择的动作能够获得在 MDP 模型中, Agent在为折扣因子,其目标是让期望值有界(1由于 MDP 决策过程中, 要同时考虑世界模型的不确定性和目标的长远性,需要在策略时刻,状态的情况下,值函数构造如下=,=,*,也就是 Agent 每个时刻都能做到的最优决策, 根据 Bellman最优策略公式可以得到。
根据贪婪策略*=argmax ,*1(4=max,*(5最优策略的通常使用值迭代算法 [2], 具体的算法步骤如下步骤 1 初始化 V 1(s =0,假定一个任意小的数值=max,1得到 V t (S ; 步骤 3判断下式, 如果结果为真, 则进入步骤 4; 否则返回步骤 2;‖1‖<步骤 4对于每个 s ∈ S ,取 =argmax,1由于下式可以知道, 值迭代算法所求出来的策略将是最优策略max*(62POMDPs在 POMDP 模型中, Agent 必须利用随机环境中部分观察在每个时间点上, Agent 都可能是众多可能状态中的某一状态, 它必须利用现有的部分信息、 [1,3]。
一般情况下, POMDP 可以用一个六元组 <,, >来描述,其中、与 MDP一样。
,:×£ºA gent 它可计算出采用动作:Agent使用来描述 Agent处在用以下的形式来进行描述 [4,5]:×→;→、行为得到,具体的过程根据贝叶斯计算如下,,,,,Pr , =Pr ,Pr ,,策略Agent 世界模型sa图2MDP 决策t 时刻状态 S tt+1时刻状态 S t+1 T函数R选取动作报酬值选取动作报酬值图 3POMDP 模型状态评估 (SE图 4决策行动信念观察状态abosa'b'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 的行动上, 根据当前的信念状态和行为就可以决定下一个周期的信念状态和行为,具体描述如下,=Pr(b' ∣ a,b=a,b,o(b,a :信念状态报酬函数,其定义如下*=argmax**=max*1-策略树 (如图 5所示和值函数, 通过求解值函数来进行最优策略的选取。
令-策略树,-策略树的集合, 为策略树的节点,则值函数的构造如下=+,,=(14为了简化表达,令=<,=µÄ×îÓÅÖµ£¬Í¼6描述了在不同区域的最优值=max(15 对于以上策略树, 其最大的节点数为 (||-1 , 其中|1(16策略树的时间复杂度是一个指数函数,随着,然后将所有节点的策略集合求或, 得到值函数[4,5]。
由于 ||、 |1|的时间复杂度是多项式的,因此1(18(19W i t n e s s算法不去关注所有时间的所有动作, 它将每个节点进行分解, 取获取每个节点的最优动作, 然后在将所有的最优动作转换为最终的值函数。
这种算法在某些情况下可以降低计算的复杂度, 但对世界模型的建模不够完整, 难以保证所求得的解一定是有效的, 算法如图 7所示。
3.2Incremental Pruning 算法Witness 算法对于小规模的计算时效果比较好, 但是当问题规模变大后,使用 Witness 算法就很难求得近似最优解。
Zhang and Liu (1996 提出一种 Incremental Pruning 算法 (如图 8所示可以较好的解决较大规模问题。
该算法的基本思想是使用动态规划方法根据给定的值函数,t =t +1;}whi l e (‖ 1 ‖< 1 2O -2119-数=max+(20=max=(22表示成向量集合表示成向量集合 ,将=max表示成向量集合=max表示成向量集合(2412(25={,},, Pr,3.3基于点的值迭代算法以上两种算法都是通过降低信念状态空间的维数来降低求解的规模, 但是在实际的求解过程中历史观察-动作集合也是一个指数函数, 如何降低历史观察-动作函数的求解复杂度也是衡量一种算法优劣的重要尺度。
基于点的值迭代算法 [Jolle Pineau,Geoff Gordon and Sebastian Thrun,2003]主要是通过降低历史观察-动作值函数的求解规模来近似求解 POMDP 问题 [7]。
基于值迭代的算法都是 PWLC 的,可以表示为可以看成 Backup 操作,每个动作都对应一个+, ,,=, 实现精确更新,首先引入中间变量, *=,0=,,,1=||O| , 也就是所谓的“维数灾” 问题, 使得问题无法求解。
为了解决这个问题, Witness 算法、 Incremental Pruning 算法和基于点的值迭代算法都是将整个问题进行分解,构造,|, |。
4POMDP 应用领域20世纪末,由于看到 POMDP 模型可以更加真实的反应客观世界模型, 人们开始对 POMDP 进行大量的研究和应用 [9]。
在科学应用领域, 科学家主要将其应用到自主机器人控制上。
例如:在太空中的漫步机器人; 机器人导航; 炸弹拆除; 放射性废物回收; 深海探矿; 管道网络的检修和维护等, 在这些领域中, 人们不可能直接操作, 只能依靠机器人来进行, 同时这些领域的环境条件非常符合 POMDP 模型。
在工业应用领域, 例如机器生产和维护, 人们可以建立一个 POMDP 模型, 使得最小化机器使用费用, 最大化生产能力。
例如道路检测管理,美国高速公路就是一个成功案例, Woodward-Clycde 公司开发了一个基于马氏决策过程的公路管理系统, 使用有限的资金来维护公路, 这个系统 4年内就节省了 1亿多美元。
在养鱼行业中,也需要在短期目标和长期目标之间作平衡, 使用 POMDP 模型决策可以达到这一目的。
在商业应用领域, 例如网络故障查找和排除, 假如电网出现故障, 需要快速地找到故障处并排除它。
在市场管理领域, 人们可以开发基于 POMDP 的软件来解决库存问题, 使得利润最大化。
POMDP 还可以应用到医疗诊断问题上, 尽早查处病因。
在军事领域, POMDP 的应用也很广泛, 例如:移动目标的查找、跟踪和拯救; 目标的辨认; 武器的使用分配等。
5结束语解决 POMDP 问题的算法有很多种, 但是从本质上都是基于动态规划和线性规划思想, 对所求问题进行分解, 降低“维数灾” 问题, 然后采用值迭代算法进行求解。
本文重点介绍和分析了 Witness 算法、 IncrementalPruning 算法和基于点的值迭代算法, 这 3种算法虽然表达方式不同, 但是一个本质思想就是降低所求问题的规模, 求出近似解。
(下转第 2126页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=F\{w }; while (F ≠+1=({a }1+1+{1++|<|++;W=W∪ {w }; F=F\{w }; retrun W;}图 8Incremental Pruning 算法表 13种算法分析比较算法指标最坏最好 Witness 算法 O (ZMQ 2 O (ZMQ 2 Incremental Pruning 算法O (ZMQ 2 O (ZQ 2 基于点的值迭代算法O (Z 2M 2QO (ZMQ3系统实现在上述研究和分析的基础上, 以全国高校仪器设备和优质资源共享项目为契机, 设计实现了基于 Web 贵重仪器设备共享系统。
系统采用 J2EE 技术, 设计为典型的B/S结构:表示层是浏览器, 显示用户界面; 应用层为服务器和应用程序, 应用程序由 JSP 、 Servlet 、 Javabean 、 Applet 和 EJB 构成; 数据层存储了仪器设备的相关信息。
通过该系统, 各高校之间可以通过 Internet 便捷的共享贵重仪器设备资源, 提高贵重仪器的使用率, 实现高校之间优势资源互补, 提高国内高校综合实力和竞争能力。
4结束语基于 Web 贵重仪器设备共享系统充分体现了贵重仪器设备远程操作和共享的特点。