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

摘要

在连续状态的部分可观察马尔可夫决策过程中,在线规划无法同时满足高实时性与低误差的要求.为此,提出一种基于后验信念聚类的在线规划算法.使用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.