A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT
A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT
复制标题
一种新的基于 d-DNNF 的功能 E-MAJSAT 边界计算算法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Adnan Darwiche
中科院分区：
文献类型：
--
作者：
Knot Pipatsrisawat;Adnan Darwiche
我们提出了一个新的算法计算上界的EMAJSAT问题的优化版本称为功能E-MAJSAT。该算法利用编译语言d-DNNF，它是解决相关问题的几个最先进算法的基础。该边界计算可以用于求解泛函E-MAJSAT的分支定界求解器中。然后，我们提出了一种技术，用于修剪值的分支定界搜索树的基础上，每个绑定计算后的信息。我们评估了所提出的技术在MAP求解器和概率一致的规划。在这两种情况下，我们的实验表明，新技术将最先进的求解器的效率提高了几个数量级。
We present a new algorithm for computing upper bounds for an optimization version of the EMAJSAT problem called functional E-MAJSAT. The algorithm utilizes the compilation language d-DNNF which underlies several state-of-the-art algorithms for solving related problems. This bound computation can be used in a branch-and-bound solver for solving functional E-MAJSAT. We then present a technique for pruning values from the branch-and-bound search tree based on the information available after each bound computation. We evaluated the proposed techniques in a MAP solver and a probabilistic conformant planner. In both cases, our experiments showed that the new techniques improved the efficiency of state-of-the-art solvers by orders of magnitude.