Generating Exponentially Smaller POMDP Models Using Conditionally Irrelevant Variable Abstraction

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.