Sparse Sampling Action Values Initialized by a Compact Representation Technique

Abstract

Most of the techniques proposed for problems involving mobile robots are specified in terms of optimal control of Markov decision processes (MDPs). However, the state space dimension explosion makes such tabular MDP-based solutions unfeasible. As an alternative to this, a planning technique based on sparse sampling (SSA) of simulated instances of a MDP model has been suggested. Because the execution time of this algorithm is exponential on the level of an exploration tree and on the number of samplings to be generated, this paper proposes a technique where leaves null-values in the SSA algorithm are substitute by meaningful values, acquired from any of the following approaches: 1) a simple environment reward distribution; 2) a standard reinforcement learning algorithm, and 3) a compact representation on a coarse state discretization for generating initial estimates of the action values. The experiments carried out showed that such information-based variants of SSA lead quickly to better results than the original technique.