A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 590-594.
Abstract
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.Knot Pipatsrisawat, Adnan Darwiche
@inproceedings{ijcai2009p104,
title = {A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT},
author = {Pipatsrisawat, Knot and Darwiche, Adnan},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {590--594},
year = {2009},
url = {https://ijcai.org/proceedings/2009/104},
}
TY - CPAPER TI - A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT AU - Pipatsrisawat, Knot AU - Darwiche, Adnan T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 590 EP - 594 UR - https://ijcai.org/proceedings/2009/104 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
