Using Caching to Solve Larger Probabilistic Planning Problems
Stephen M. Majercik and Michael L. Littman
Abstract: Probabilistic planning algorithms seek effective plans for large,
stochastic domains. MAXPLAN is a recently developed algorithm
that converts a planning problem into an E-MAJSAT problem, an
NP^PP-complete problem that is essentially a probabilistic version
of SAT, and draws on techniques from Boolean satisfiability and
dynamic programming to solve the E-MAJSAT problem. This solution
method is able to solve planning problems at state-of-the-art speeds,
but it depends on the ability to store a value for each CNF subformula
encountered in the solution process and is therefore quite memory
intensive; searching for moderate-size plans even on simple problems
can exhaust memory. This paper presents two techniques, based on
caching, that overcome this problem without significant performance
degradation. The first technique uses an LRU cache to store a fixed
number of subformula values. The second technique uses a heuristic
based on a measure of subformula difficulty to selectively save the
values of only those subformulas whose values are sufficiently
difficult to compute and are likely to be reused later in the solution
process. We report results for both techniques on a stochastic test
problem.