Approximate solution techniques for factored first-order MDPs
Scott Sanner, Craig E. Boutilier · 2007
Most traditional approaches to probabilistic planning in relationally specified MDPs rely on grounding the prob-lem w.r.t. specific domain instantiations, thereby incur-ring a combinatorial blowup in the representation. An alternative approach is to lift a relational MDP to a first-order MDP (FOMDP) specification and develop solu-tion approaches that avoid grounding. Unfortunately, state-of-the-art FOMDPs are inadequate for specify-ing factored transition models or additive rewards that scale with the domain size—structure that is very natu-ral 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 struc-ture. 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 em-pirical results to demonstrate that we can obtain solu-tions whose complexity scales polynomially in the log-arithm of the domain size—results that are impossible to obtain with any previously proposed solution method.