Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction - Robotics Institute Carnegie Mellon University

Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction

Conference Paper, Proceedings of 17th International Conference on Applied Planning and Scheduling (ICAPS '07), pp. 304 - 311, September, 2007

Abstract

The state of a POMDP can often be factored into a tuple of n state variables. The corresponding flat model, with size exponential in n, may be intractably large. We present a novel method called conditionally irrelevant variable abstraction (CIVA) for losslessly compressing the factored model, which is then expanded into an exponentially smaller flat model in a representation compatible with many existing POMDP solvers. We applied CIVA to previously intractable problems from a robotic exploration domain. We were able to abstract, expand, and approximately solve POMDPs that had up to 10^24 states in the uncompressed flat representation.

BibTeX

@conference{Smith-2007-17043,
author = {Trey Smith and David R. Thompson and David Wettergreen},
title = {Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction},
booktitle = {Proceedings of 17th International Conference on Applied Planning and Scheduling (ICAPS '07)},
year = {2007},
month = {September},
pages = {304 - 311},
}