POMDP-lite for Robust Robot Planning under Uncertainty
This work addresses the problem of efficient planning under uncertainty for robotics, offering a novel subclass that enables scalable solutions, though it is incremental as it builds on existing POMDP frameworks.
The paper tackles the computational intractability of general POMDPs for robot planning under uncertainty by introducing POMDP-lite, a subclass with constant or deterministically changing hidden states, and develops a model-based Bayesian reinforcement learning algorithm that outperforms state-of-the-art general-purpose POMDP algorithms on large-scale models with up to 10^20 states.
The partially observable Markov decision process (POMDP) provides a principled general model for planning under uncertainty. However, solving a general POMDP is computationally intractable in the worst case. This paper introduces POMDP-lite, a subclass of POMDPs in which the hidden state variables are constant or only change deterministically. We show that a POMDP-lite is equivalent to a set of fully observable Markov decision processes indexed by a hidden parameter and is useful for modeling a variety of interesting robotic tasks. We develop a simple model-based Bayesian reinforcement learning algorithm to solve POMDP-lite models. The algorithm performs well on large-scale POMDP-lite models with up to $10^{20}$ states and outperforms the state-of-the-art general-purpose POMDP algorithms. We further show that the algorithm is near-Bayesian-optimal under suitable conditions.