基于点的POMDP算法的预处理方法

• 作者: 卞爱华 王崇骏 陈世福
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: POMDP 值迭代 基于点的算法 预处理 基向量
• 年，卷（期）: 2008,（6）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1309-1316
• 页数: 8页
• 分类号: TP301
• 字数: 7922字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.01309

摘要

基于点的算法是部分可观察马尔可夫决策过程(partially observable Markov decision processes,简称POMDP)的一类近似算法.它们只在一个信念点集上进行Backup操作,避免了线性规划并使用了更少的中间变量,从而将计算瓶颈由选择向量转向了生成向量.但这类算法在生成向量时含有大量重复和无意义计算,针对于此,提出了基于点的POMDP算法的预处理方法(preprocessing method for point-based algorithms,简称PPBA).该方法对每个样本信念点作预处理,并且在生成α-向量之前首先计算出该选取哪个动作和哪些α-向量,从而消除了重复计算.PPBA还提出了基向量的概念,利用问题的稀疏性避免了无意义计算.通过在Perseus上的实验,表明PPBA很大地提高了算法的执行速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王崇骏	南京大学计算机科学与技术系	56	1131	15.0	32.0
2	陈世福	南京大学计算机科学与技术系	169	4351	32.0	60.0
3	卞爱华	南京大学计算机软件新技术国家重点实验室	1	11	1.0	1.0