Trey Smith, David R. Thompson, David S. Wettergreen
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 1024 states in the uncompressed flat representation.
Subjects: 3.4 Probabilistic Reasoning; 1.11 Planning
Submitted: Jun 26, 2007