基于后验信念聚类的在线规划算法  

Online Planning Algorithm Based on Posterior Belief Clustering

作　　者：仵博[1,2,3] 吴敏[2,3] 

机构地区：[1]深圳职业技术学院教育技术与信息中心,广东深圳518055 [2]中南大学信息科学与工程学院,长沙410083 [3]先进控制与智能自动化湖南省工程实验室,长沙410083

出　　处：《计算机工程》2013年第4期214-218,共5页Computer Engineering

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

摘　　要：在连续状态的部分可观察马尔可夫决策过程中,在线规划无法同时满足高实时性与低误差的要求。为此,提出一种基于后验信念聚类的在线规划算法。使用KL散度分析连续状态下后验信念之间的误差,根据误差分析结果对后验信念进行聚类,利用聚类后验信念计算报酬值,并采用分支界限裁剪方法裁剪后验信念与或树。实验结果表明,该算法能够有效降低求解问题的规模,消除重复计算,具有较好的实时性和较低的误差。Aiming at the problem that online planning can not meet the requirement of high real-time and low error at the same time in continuous states Partially Observable Markov Decision Processes（POMDPs）, a forward-search algorithm called the Posterior Belief Clustering（PBC） is proposed in this paper. PBC analyzes the errors of a class of continuous posterior beliefs by KL divergence, and clusters these posterior beliefs into one based on errors of KL divergence. PBC calculates the posterior reward value only once for each cluster. The algorithm exploits branch-and-bound pruning approach to prune the posterior beliefs and/or tree online. Experimental results show that this algorithm can effectively reduce the size of the solving problem, eliminates repeated computation, and has good performance on real-time and low errors.

关 键 词：部分可观察马尔可夫决策过程 后验信念聚类 在线规划 KL散度 分支界限 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]