AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT
Knot Pipatsrisawat, Adnan Darwiche

Last modified: 2009-06-25


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.


E-MAJSAT; Bound computation; Knowledge compilation

Full Text: PDF