Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction

Trey Smith, David R. Thompson, and David Wettergreen
Proc. Int. Conf. on Applied Planning and Scheduling (ICAPS), , 2007


Download
  • Adobe portable document format (pdf) (707KB)
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.

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.

Notes

Text Reference
Trey Smith, David R. Thompson, and David Wettergreen, "Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction," Proc. Int. Conf. on Applied Planning and Scheduling (ICAPS), , 2007

BibTeX Reference
@article{Smith_2007_5938,
   author = "Trey Smith and David R Thompson and David Wettergreen",
   title = "Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction",
   journal = "Proc. Int. Conf. on Applied Planning and Scheduling (ICAPS)",
   year = "2007",
}