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},
}
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.