Partially Observable Monte-Carlo Graph Search
This addresses the need for pre-computed offline policies in POMDP applications with time or energy constraints, offering a scalable solution for domains where online methods are impractical.
The paper tackles the problem of scaling offline policies for large partially observable Markov decision processes (POMDPs) by proposing POMCGS, which folds search trees into policy graphs to reduce computations and handle continuous cases, achieving competitive values with state-of-the-art online algorithms on previously unsolvable POMDPs.
Currently, large partially observable Markov decision processes (POMDPs) are often solved by sampling-based online methods which interleave planning and execution phases. However, a pre-computed offline policy is more desirable in POMDP applications with time or energy constraints. But previous offline algorithms are not able to scale up to large POMDPs. In this article, we propose a new sampling-based algorithm, the partially observable Monte-Carlo graph search (POMCGS) to solve large POMDPs offline. Different from many online POMDP methods, which progressively develop a tree while performing (Monte-Carlo) simulations, POMCGS folds this search tree on the fly to construct a policy graph, so that computations can be drastically reduced, and users can analyze and validate the policy prior to embedding and executing it. Moreover, POMCGS, together with action progressive widening and observation clustering methods provided in this article, is able to address certain continuous POMDPs. Through experiments, we demonstrate that POMCGS can generate policies on the most challenging POMDPs, which cannot be computed by previous offline algorithms, and these policies' values are competitive compared with the state-of-the-art online POMDP algorithms.