Automated Reasoning in Artificial Intelligence

My research is focused on automated reasoning in Artificial Intelligence, particularly in the areas of search, constraint-based reasoning and reasoning under uncertainty.

My ongoing focus is on constraint processing, a field which unifies themes cutting across many traditional areas in Artificial Intelligence. A variety of techniques have been developed for processing different kinds of constraint expressions and are being applied to diverse tasks such as vision, design, diagnosis, truth maintenance, scheduling, spatio-temporal reasoning, logic programming, and user interface. Many of these methods were incorporated into constraint programming languages which enhance practical applications substantially.

Since most reasoning tasks are computationally intractable, my primary approach is to devise methods through the understanding and exploitation of tractable reasoning tasks. My previous works on greedy problems, the mechanical generation of heuristics, the identification of tractable constraint models via topological decompositions, and the establishment of boundaries of local computations have been driven by this principal concern. With my students, I analyze algorithms both analytically and empirically using real life applications such as scheduling, planning, and diagnosis.

In the past decade I extended my research to general graphical models and especially to reasoning under uncertainty using Bayesian networks. We introduced the two unifying algorithmic frameworks of bucket-elimination and AND/OR search which capture the most common styles of human reasoning (e.g., Inference, and conditioning). Bucket elimination unifies dynamic programming for combinatorial optimization with algorithms for theorem proving, logic programs, temporal reasoning, probabilistic reasoning and planning under uncertainty. AND/OR search allows exploiting problem decomposition during search and is the basis to many recent algorithmic advances in graphical models. Within these two frameworks we develop efficient exact and approximate algorithms with potential impact across many computational disciplines.

Selected Work
R. Dechter and J. Pearl, "Tree-clustering schemes for constraint-processing" Artificial Intelligence, Vol. 38(3), April 1989, pp.353-366.

R. Dechter and J. Pearl, "Network-based heuristics for constraint-satisfaction problems" Artficial Intelligence, Vol 34(1), December 1987 pp. 1-38.

R. Dechter. "Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition" Artificial Intelligence, Vol. 41(3), 1990, pp. 273-312.

R. Dechter, and J. Pearl, "Structure identification in relational data." In Artificial Intelligence, Vol. 58, 1992, pp. 237-270.

Pinkas, G., and Dechter, R., "On Improving Connectionist Energy Minimization" In Journal of 157 Artificial Intelligence Research (JAIR), Vol. 3, 1995, pp. 223-248.

Ben-Eliyahu, R., and Dechter, R., "Default reasoning using classical logic" In Artificial Intelligence, Vol. 84, 1996, pp. 113-150.

van Beek, P., and Dechter, R., "On the minimality and decomposability of row-convex constraint networks" Journal of the ACM, Vol. 42, No. 3, May 1995, pp. 543-561.

van Beek, P., and Dechter, R., "Constraint restrictiveness versus local and global consistency" In Journal of the Association of Computing Memory.

Dechter, R., and van Beek, P., "Local and global relational consistency" In Journal of Theoretical Computer Science, 1996

Schwalb, E., and Dechter, R., "Processing Disjunctions in Temporal Constraint Networks" In Artificial Intelligence, volume 93, pp. 29-61, 1997.

Dechter, R., "Bucket Elimination: A unifying framework for probabilistic inference" In Uncertainty in Artificial Intelligence, UA196, 1996, pp. 211-219.

Dechter, R., and Rish, I., " A scheme for approximating probabilistic inference" In Uncertainty in Artificial Intelligence (UAI97), August 1997.

Frost, D., and Dechter, R. "Maintenance scheduling problems as benchmarks for constraint algorithms" in Annals of Math and AI, 1999

I Rish, and R. Dechter., "Resolution versus Search: Two Strategies for SAT" in Journal of Automated Reasoning, Volume 24, Issue 1/2, pp. 225-275, January, 2000.

K. Kask, R. Dechter, "A General Scheme for Automatic Generation of Search Heuristics from Specification Dependencies", in Artificial Intelligence, 129:91-131, 2001.

R. Dechter, I. Rish "Mini-Buckets: A General Scheme For Approximating Inferance" In the journal of ACM, 2003.

K. Kask, Rina Dechter, Javier Larrosa and Avi Dechter. "Unifying Cluster-Tree Decompositions for Reasoning in Graphical Models" in Artificial Intelligence Journal, 2005.

Bozhena Bidyuk and Rina Dechter. "Cutset Sampling for Bayesian Networks". in JAIR, 2006.

Rina Dechter and Robert Mateescu. "AND/OR Search Spaces for Graphical Models", in Artificial Intelligence 171 (2-3), pp. 73-106, 2007.