Reducing the Computational Cost of a Monte Carlo Based Planning Algorithm

Abstract

To travel effectively in an uncertain environment, a robot should use a path-planning algorithm which takes the impact of this uncertainty into account. In previous work, we developed the Path Distribution (PD) Planner which uses a Monte Carlo approach to sample the environment, generate the distribution of optimal paths, and plan a path using this distribution. We have shown that this approach outperforms other approaches to planning with uncertainty. However, Monte Carlo sampling can become extremely computationally expensive. In this paper, we develop two strategies to reduce the computational cost of the algorithm. The first, called Sampling in Planning Process (SiPP), performs lazy sampling within the planning algorithm itself. The second, which we call the Hierarchal PD Planner, performs dimensionality reduction by decomposing the environment into homogeneous regions. We show that these approaches can reduce computational costs by more than a factor of two with minimal loss of performance.