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

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

基于试探(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.