Planning for Markov Decision Processes with Sparse Stochasticity

December 2004

Planning for Markov Decision Processes with Sparse Stochasticity

Authors:

Maxim Likhachev, Geoff Gordon, and Sebastian Thrun
Conference Paper
Proceedings of (NeurIPS) Neural Information Processing Systems

Abstract:

Planning algorithms designed for deterministic worlds, such as A* search, usually run much faster than algorithms designed for worlds with uncertain action outcomes, such as value iteration. Real-world planning problems often exhibit uncertainty, which forces us to use the slower algorithms to solve them. Many real-world planning problems exhibit sparseuncertainty: there are long sequences of deterministic actions which accomplish tasks like moving sensor platforms into place, interspersed with a small number of sensing actions which have uncertain outcomes. In this paper we describe a new planning algorithm, called MCP (short for MDP Compression Planning), which combines A* search with value iteration for solving Stochastic Shortest Path problem in MDPs with sparse stochasticity. We present experiments which show that MCP can run substantially faster than competing planners in domains with sparse uncertainty; these experiments are based on a simulation of a ground robot cooperating with a helicopter to fill in a partial map and move to a goal location.
@conference{Likhachev-2004-109737,
author = {Maxim Likhachev And Geoff Gordon And Sebastian Thrun},
title = {Planning for Markov Decision Processes with Sparse Stochasticity},
booktitle = {Proceedings of (NeurIPS) Neural Information Processing Systems},
year = {2004},
month = {December},
pages = {785 - 792},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.