×

zbMATH — the first resource for mathematics

AND/OR search spaces for graphical models. (English) Zbl 1168.68549
Summary: The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Indeed, most algorithmic advances in search-based constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, treewidth and pathwidth are shown to play a key role in characterizing the effect of AND/OR search graphs vs. the traditional OR search graphs. We compare memory intensive AND/OR graph search with inference methods, and place various existing algorithms within the AND/OR search space.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
AIS-BN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Nilsson, N.J., Principles of artificial intelligence, (1980), Tioga Palo Alto, CA · Zbl 0422.68039
[2] E.C. Freuder, M.J. Quinn, Taking advantage of stable sets of variables in constraint satisfaction problems, in: Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI’85), 1985, pp. 1076-1078
[3] E.C. Freuder, M.J. Quinn, The use of lineal spanning trees to represent constraint satisfaction problems, Tech. Rep. 87-41, University of New Hampshire, Durham (1987)
[4] Z. Collin, R. Dechter, S. Katz, On the feasibility of distributed constraint satisfaction, in: Proceedings of the Twelfth International Conference of Artificial Intelligence (IJCAI’91), 1991, pp. 318-324 · Zbl 0747.68065
[5] Collin, Z.; Dechter, R.; Katz, S., Self-stabilizing distributed constraint satisfaction, The Chicago journal of theoretical computer science, 3, 4, (1999), special issue on self-stabilization · Zbl 0940.68002
[6] Modi, P.J.; Shena, W.; Tambea, M.; Yokoo, M., Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial intelligence, 161, 149-180, (2005) · Zbl 1132.68706
[7] R. Dechter, Constraint networks, in: Encyclopedia of Artificial Intelligence, 1992, pp. 276-285
[8] R. Bayardo, D. Miranker, A complexity analysis of space-bound learning algorithms for the constraint satisfaction problem, in: Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI’96), 1996, pp. 298-304
[9] J. Larrosa, P. Meseguer, M. Sanchez, Pseudo-tree search with soft constraints, in: Proceedings of the European Conference on Artificial Intelligence (ECAI’02), 2002, pp. 131-135
[10] Terrioux, C.; Jégou, P., Hybrid backtracking bounded by tree-decomposition of constraint networks, Artificial intelligence, 146, 43-75, (2003) · Zbl 1082.68803
[11] C. Terrioux, P. Jégou, Bounded backtracking for the valued constraint satisfaction problems, in: Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP’03), 2003, pp. 709-723 · Zbl 1273.68363
[12] Darwiche, A., Recursive conditioning, Artificial intelligence, 125, 1-2, 5-41, (2001) · Zbl 0969.68150
[13] F. Bacchus, S. Dalmao, T. Pitassi, Value elimination: Bayesian inference via backtracking search, in: Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI’03), 2003, pp. 20-28
[14] F. Bacchus, S. Dalmao, T. Pitassi, Algorithms and complexity results for #sat and bayesian inference, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS’03), 2003, pp. 340-351
[15] T. Sang, F. Bacchus, P. Beam, H. Kautz, T. Pitassi, Combining component caching and clause learning for effective model counting, in: Proceedings of the Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT’04), 2004
[16] Dechter, R., Bucket elimination: A unifying framework for reasoning, Artificial intelligence, 113, 41-85, (1999) · Zbl 0939.68847
[17] Bryant, R.E., Graph-based algorithms for Boolean function manipulation, IEEE transaction on computers, 35, 677-691, (1986) · Zbl 0593.94022
[18] Darwiche, A.; Marquis, P., A knowledge compilation map, Journal of artificial intelligence research (JAIR), 17, 229-264, (2002) · Zbl 1045.68131
[19] Darwiche, A., A differential approach to inference in Bayesian networks, Journal of the ACM, 50, 3, 280-305, (2003) · Zbl 1325.68226
[20] D. McAllester, M. Collins, F. Pereira, Case-factor diagrams for structured probabilistic modeling, in: Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI’04), 2004, pp. 382-391 · Zbl 1161.68784
[21] Fargier, H.; Vilarem, M., Compiling csps into tree-driven automata for interactive solving, Constraints, 9, 4, 263-287, (2004) · Zbl 1101.68088
[22] V. Bertacco, M. Damiani, The disjunctive decomposition of logic functions, in: ICCAD, International Conference on Computer-Aided Design, 1997, pp. 78-82
[23] N. Wilson, Decision diagrams for the computation of semiring valuations, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05), 2005, pp. 331-336
[24] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artificial intelligence, 38, 353-366, (1989) · Zbl 0665.68084
[25] Arnborg, S.A., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[26] H.L. Bodlaender, J.R. Gilbert, Approximating treewidth, pathwidth and minimum elimination tree-height, Tech. rep., Utrecht University (1991) · Zbl 0768.68121
[27] H.L. Bodlaender, Treewidth: Algorithmic techniques and results, in: The Twenty Second International Symposium on Mathematical Foundations of Computer Science (MFCS’97), 1997, pp. 19-36 · Zbl 0941.05057
[28] R. Dechter, A new perspective on algorithms for optimizing policies under uncertainty, in: International Conference on Artificial Intelligence Planning Systems (AIPS-2000), 2000, pp. 72-81
[29] Shenoy, P., Valuation-based systems for Bayesian decision analysis, Operations research, 40, 463-484, (1992) · Zbl 0850.62131
[30] Pearl, J., Probabilistic reasoning in intelligent systems, (1988), Morgan Kaufmann
[31] R. Marinescu, R. Dechter, AND/OR branch-and-bound for graphical models, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05), 2005, pp. 224-229
[32] D. Allen, A. Darwiche, New advances in inference by recursive conditioning, in: Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI’03), 2003, pp. 2-10
[33] Kask, K.; Dechter, R.; Larrosa, J.; Dechter, A., Unifying cluster-tree decompositions for reasoning in graphical models, Artificial intelligence, 166, 1-2, 165-193, (2005) · Zbl 1132.68680
[34] Dechter, R., Constraint processing, (2003), Morgan Kaufmann
[35] Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artificial intelligence, 34, 1-38, (1987) · Zbl 0643.68156
[36] Rish, I.; Dechter, R., Resolution vs. search; two strategies for sat, Journal of automated reasoning, 24, 1/2, 225-275, (2000) · Zbl 0967.68147
[37] Dechter, R., Enhancement schemes for constraint processing: backjumping, learning and cutset decomposition, Artificial intelligence, 41, 273-312, (1990)
[38] R.J. Bayardo, R.C. Schrag, Using csp look-back techniques to solve real world sat instances, in: Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI’97), 1997, pp. 203-208
[39] Marques-Silva, J.P.; Sakalla, K.A., Grasp: A search algorithm for propositional satisfiability, IEEE transaction on computers, 48, 5, 506-521, (1999) · Zbl 1392.68388
[40] Robertson, N.; Seymour, P., Graph minors i. excluding a forest, J. combin. theory ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[41] Bienstock, D.; Robertson, N.; Seymour, P.; Thomas, R., Quickly excluding a forest, J. combin. theory ser. B, 52, 274-283, (1991) · Zbl 0763.05023
[42] R. Mateescu, R. Dechter, Compiling constraint networks into AND/OR multi-valued decision diagrams (AOMDDs), in: Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP’06), 2006, pp. 329-343 · Zbl 1160.68555
[43] D.H. Frost, Algorithms and heuristics for constraint satisfaction problems, Tech. rep., Ph.D. thesis, Information and Computer Science, University of California, Irvine (1997)
[44] R. Mateescu, R. Dechter, The relationship between AND/OR search and variable elimination, in: Proceedings of the Twenty First Conference on Uncertainty in Artificial Intelligence (UAI’05), 2005, pp. 380-387
[45] Dechter, R.; Frost, D., Backjump-based backtracking for constraint satisfaction problems, Artificial intelligence, 136, 2, 147-188, (2002) · Zbl 0995.68102
[46] J. Huang, A. Darwiche, Dpll with a trace: From sat to knowledge compilation, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05), 2005, pp. 156-162
[47] McMillan, K.L., Symbolic model checking, (1993), Kluwer Academic · Zbl 1132.68474
[48] K.L. McMillan, Hierarchical representation of discrete functions with application to model checking, in: Computer Aided Verification, 1994, pp. 41-54
[49] Gergov, J.; Meinel, C., Efficient Boolean manipulation with OBDDs can be extended to fbdds, IEEE trans. computers, 43, 1197-1209, (1994) · Zbl 1063.68573
[50] Sieling, D.; Wegner, I., Graph driven BDDs—a new data structure for Boolean functions, Theoretical computer science, 141, 283-310, (1994) · Zbl 0873.68036
[51] R. Brayton, C. McMullen, The decomposition and factorization of boolean expressions, in: ISCAS, Proceedings of the International Symposium on Circuits and Systems, 1982, pp. 49-54
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.