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

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.