Approximate Solution Techniques for Factored First-order MDPs
Speaker: Scott Sanner (NICTA, Australia)
Most traditional approaches to probabilistic
planning in relationally specified MDPs rely on grounding the problem
w.r.t. specific domain instantiations, thereby incurring a
combinatorial blowup in the representation. An alternative approach
is to lift a relational MDP to a first-order MDP (FOMDP) specification
and develop solution approaches that avoid grounding. Unfortunately,
state-of-the-art FOMDPs are inadequate for specifying factored
transition models or additive rewards that scale with the domain size
-- structure that is very natural in probabilistic planning problems.
To remedy these deficiencies, we propose an extension of the FOMDP
formalism known as a factored FOMDP and present generalizations of
symbolic dynamic programming and linear-value approximation solutions
to exploit its structure. Along the way, we also make contributions
to the field of first-order probabilistic inference (FOPI) by
demonstrating novel first-order structures that can be exploited
without domain grounding. We present empirical results to demonstrate
that we can obtain solutions whose complexity scales polynomially in
the logarithm of the domain size -- results that are impossible to
obtain with any previously proposed solution method.
This is joint work with Craig Boutilier.