SHP-VI:一种基于最短哈密顿通路的POMDP值迭代算法  

SHP-VI: A Shortest Hamiltonian Path-Based POMDP Value Iteration Algorithm

作　　者：冯奇[1] 周雪忠[1] 黄厚宽[1] 张小平[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044

出　　处：《计算机研究与发展》2011年第12期2343-2351,共9页Journal of Computer Research and Development

基　　金：国家科技重大专项基金项目(2009ZX10005-019);国家"九七三"重点基础研究发展计划基金项目(2006CB504601);国家科技支撑计划基金项目(2007BAI10B06-01);北京市科委科研攻关基金项目(D08050703020803;D08050703020804)

摘　　要：基于试探(trial-based)的值迭代算法是求解部分可观察Markov决策过程(partially observable Markov decision process,POMDP)模型的一类有效算法,其中FSVI算法是目前最快的算法之一.然而对于较大规模的POMDP问题,FSVI计算MDP值函数的时间是不容忽视的.提出一种基于最短哈密顿通路(shortest Hamiltonian path)的值迭代算法(shortest Hamiltonian path-based value iteration,SHP-VI).该方法用求解最短哈密顿通路问题的蚁群算法计算一条最优信念状态轨迹,然后在这些信念状态上反向更新值函数.通过与FSVI算法的实验比较,结果表明SHP-VI算法很大程度地提高了基于试探的算法计算信念状态轨迹的效率.Trial-based value iteration is a class of efficient algorithms to solve partially observable Markov decision process （POMDP）, among which FSVI is one of the fastest algorithms. But the overhead of computing MDP value function by FSVI is not negligible for large-scale POMDP problems. In this paper, we propose a new value iteration method based on the shortest Hamiltonian path （shortest Hamiltonian path-based value iteration, SHP-VI）. This method explores an optimal belief trajectory using the shortest Hamiltonian path resulting from ant colony optimization, and updates value function over the encountered belief states in reversed order. Compared with FSVI, the experimental results show that SHP-VI accelerates the computation of belief trajectory greatly in trial-based algorithms.

关 键 词：部分可观察Markov决策过程 值迭代 基于点的算法 基于试探的算法 哈密顿通路 

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