Online algorithm based on Monte Carlo particle filtering in POMDPs
Bo Wu, Min Wu · Kongzhi yu juece · 2013
In order to solve the double exponential size problem of belief states space in partially observable Markov decision processes(POMDPs), an online algorithm based on Monte Carlo particle filtering(MCPF) is proposed. Firstly, the methods of particle filtering and particle projection are used to update and expand the belief states respectively, and the and-or tree of reachable belief states is built. Then, a branch-and-bound pruning method is proposed to prune the tree to reduce computation. Finally, the experiment and simulation results show that the proposed algorithm has the effectiveness in retaining the quality of the policies and reducing the cost of computing policies, so it can meet the requirement of a real-time system.