| 摘要: |
| 基于点的算法是部分可观察马尔可夫决策过程(partially observable Markov decision processes,简称POMDP)的一类近似算法.它们只在一个信念点集上进行Backup操作,避免了线性规划并使用了更少的中间变量,从而将计算瓶颈由选择向量转向了生成向量.但这类算法在生成向量时含有大量重复和无意义计算,针对于此,提出了基于点的POMDP算法的预处理方法(preprocessing method for point-based algorithms,简称PPBA).该方法对每个样本信念点作预处理,并且在生成α-向量之前首先计算出该选取哪个动作和哪些α-向量,从而消除了重复计算.PPBA还提出了基向量的概念,利用问题的稀疏性避免了无意义计算.通过在Perseus上的实验,表明PPBA很大地提高了算法的执行速度. |
| 关键词: POMDP 值迭代 基于点的算法 预处理 基向量 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60503021 (国家自然科学基金); the High-Tech Research Program of Jiangsu Province of China under Grant No.BG2006027 (江苏省高技术研究计划) |
|
| Preprocessing for Point-Based Algorithms of POMDP |
|
BIAN Ai-Hua,WANG Chong-Jun,CHEN Shi-Fu
|
| Abstract: |
| Point-Based algorithms are a class of approximation methods for partially observable Markov decision processes (POMDP). They do backup operators on a belief set only, so linear programming is avoided and fewer intermediate variables are needed, and the bottleneck turns from selecting vectors to generating vectors. But when generate vectors, there will be a great deal of repeated and meaningless computing. This paper will propose a preprocessing method for point-based algorithms (PPBA). This method preprocesses each sampled belief point, and before generating α-vectors it estimates which action and α-vectors to be selected first, in so doing repeated computing is eliminated. Base-vector is also defined in this paper, which cancels meaningless computing with sparseness of problem. Experiments on Perseus show that, PPBA accelerates the performance greatly. |
| Key words: POMDP value iteration point-based algorithm preprocessing base-vector |
