Using Caching to Solve Larger Probabilistic Planning Problems
Using Caching to Solve Larger Probabilistic Planning Problems
复制标题
使用缓存解决更大的概率规划问题
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
M. Littman
中科院分区：
文献类型：
--
作者：
S. Majercik;M. Littman
概率规划算法寻求大的，随机域的有效计划。MAXSAT是最近开发的一种算法，它将规划问题转换为E-MAJSAT问题，这是一个NPP-complete问题，本质上是SAT的概率版本，并利用布尔可满足性和动态规划技术来解决E-MAJSAT问题。这种求解方法能够以最先进的速度解决规划问题，但它依赖于为求解过程中遇到的每个CNF子公式存储值的能力，因此非常占用内存;即使在简单的问题上搜索中等大小的计划也会耗尽内存。本文提出了两种技术，基于缓存，克服了这个问题，没有显着的性能下降。第一种技术使用LRU缓存来存储固定数量的子公式值。第二种技术使用一种基于子公式难度的启发式方法，选择性地保存那些子公式的值，这些子公式的值很难计算，并且很可能在以后的求解过程中被重用。我们报告的结果，这两种技术的随机测试问题。
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 NpPP-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.