Extending the Applicability of POMDP Solutions to Robotic Tasks

Partially observable Markov decision processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot and, then, uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large continuous-state robotic tasks.

I. Introduction

Partially observable Markov decision processes (POMDPs) [1] represent a planning problem in which an agent performs actions and obtains sensor observations with the goal of maximizing the total long-term reward. POMDPs can address noise in both the sensors and actuators of a robotic agent. Solving a POMDP is the process of computing an action policy that maximizes the total accumulated reward from an arbitrary reward function. The optimal action policy consists of the optimal action for any possible sequence of observations, such that the expected total reward is maximized under the POMDP model of sensing and action uncertainty. POMDPs have been established as a tool to solve a variety of tasks in robot soccer [2], household robotics [3], coastal survey [4] , and even nursing assistance [5].