基于信念点裁剪策略树的POMDP求解算法  

Belief Point-based POMDP Solution for Policy Tree Pruning

作　　者：郑红燕[1] 仵博[1,2] 冯延蓬[1] 孟宪军[1] 

机构地区：[1]深圳职业技术学院,广东深圳518055 [2]中南大学,湖南长沙410083

出　　处：《信息与控制》2013年第1期53-57,共5页Information and Control

基　　金：国家自然科学基金资助项目(61074058);广东省自然科学基金资助项目(S2011040004769)

摘　　要：针对大规模部分可观察马尔可夫决策过程(POMDP)算法中策略树规模指数级增长、已证信念点(witness point,WP)求解困难的问题,根据策略树值函数是分段线性凸函数的特点,提出一种基于信念点的策略树增量裁剪和值迭代求解算法.在策略树生成过程中,利用边界点进行无损裁剪,利用中间点进行有损裁剪,并利用实时信念状态分布求取近似最优解.对比实验结果表明,该算法能快速收敛,以更少的时间获得相当精度的奖赏值.Large-scale partially observable Markov decision process （POMDP） suffers from the exponential growth of the policy tree and the difficulty of finding witness points （WPs）. Based on the piecewise linearity and convexity of the value function, a belief point-based algorithm is proposed for policy tree incremental pruning and value iteration solution. When policy trees are generating, the algorithm uses boundary points for non-destructive pruning, and exploits intermediate points for destructive pruning. It also makes use of realtime belief states to solve approximate optimal solution. Comparison experiment results show that the proposed algorithm converges quickly and achieve high reward within less time.

关 键 词：部分可观察马尔科夫决策过程(POMDP) 策略树 信念状态 基于点 增量裁剪 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]