Using Caching to Solve Larger Probabilistic Planning Problems

Probabilistic planningalgorithmsseek effective plans for large, stochastic domains. MAXPLAN is a recently developed algorithm that converts a planning problem into an E-MAJSAT problem, an NPPP-complete problemthat is essentially a probabilistic version of SAT, anddrawson techniquesfromBoolean satisfiability and dynamicprogramming to solve the E-MAJSAT problem. This solution methodis able to solve planningproblems at state-of-the-art speeds, but it depends on the ability to store a valuefor each CNF subformula encounteredin the solution process and is therefore quite memory intensive; searching for moderate-size plans even on simple problems can exhaust memory. This paper presents twotechniques, basedon caching, that overcome this problem withoutsignificant performancedegradation. Thefirst technique uses an LRU cacheto store a fixed number of subformulavalues. Thesecondtechniqueuses a heuristic basedon a measureof subformula difficulty to selectivelysavethe values of onlythose subformulaswhosevalues are sufficiently difficult to compute andare likely to be reused later in the solutionprocess. We report results for both techniqueson a stochastic test problem.

Authors

• Stephen M. Majercik Byron Boots

Keywords

No keywords are indexed for this paper.