A point-reduced POMDP value iteration algorithm with application to robot navigation

摘要

The exact value iteration for POMDP planning is so complex that we use approximation to solve the problems in practice. In recent years, point-based algorithm has become a research hotspot. PBVI algorithm selects successors that improve the worst case density as rapidly as possible. The smaller the gaps between all belief points, the faster the value function converges to the optimal solutions. PBVI doubles the size of the belief set after each expansion. The exponential increase makes this algorithm incapable to solve problems with long horizons. However, there are some points in the set which have little contribution to the density. These points can be reduced to decrease the size of the set. Meanwhile, fewer points are expanded and more backups can be executed during each iteration. Based on this, this paper introduces a point-reduced POMDP value iteration algorithm and applied it to robot navigation problems. PRVI improves the original PBVI and is superior to other POMDP algorithms. Experiments supported that PRVI significantly improved the efficiency.