My research is in the field of Automated Reasoning in Artificial Intelligence and focused on Graphical Models. Graph based models (e.g., Bayesian and constraint networks, influence diagrams and Markov decision processes) are a central paradigm for knowledge representation and reasoning in both Artificial Intelligence and Computer Science in general. These models are used to accomplish many science and engineering tasks, such as scheduling, planning and learning, diagnosis and prediction, design, hardware and software verification and bioinformatics. They are also instrumental for learning schemes. These reasoning problems can be stated as the formal tasks of constraint satisfaction and satisfiability, combinatorial optimization and probabilistic inference.
Since most reasoning tasks are computationally intractable, my primary approach is to devise anytime approximations methods through the understanding and exploitation of tractable reasoning tasks. As their name implies, anytime methods provide a solution anytime during the processing, hopefully with error bounds, that are tightened if more time is available, eventually resulting in exact answers.
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 probabilistic graphical models 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. Our framework allows leveraging the strength variational methods yielding tractable-based heuristics to guide AND/OR search and Monte-Carlo schemes and facilitate their integrations.
In sum, my research interests are in the areas of Automated Reasoning, Knowledge-Representation, Planning and Learning.
Dechter, R., and Pearl, J., "Generalized best-first strategies and the optimality of A*", Journal of the ACM, Vol. 32(3), July 1985, pp. 505-536.
R. Dechter and J. Pearl, "Network-based heuristics for constraint-satisfaction problems", Artificial Intelligence, Vol 34(1), December 1987 pp. 1-38.
R. Dechter and J. Pearl, "Tree-clustering schemes for constraint-processing", Artificial Intelligence, Vol. 38(3), April 1989, pp.353-366.
R. Dechter, "Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition", Artificial Intelligence, Vol. 41(3), 1990, pp. 273-312.
Dechter, R., Meiri, I., and Pearl, J., “Temporal constraint networks”, Artificial Intelligence, Vol. 49, 1991, pp. 61{95}.
R. Dechter, and J. Pearl, "Structure identification in relational data,", Artificial Intelligence, Vol. 58, 1992, pp. 237-270.
Ben-Eliyahu, R., and Dechter, R., “Propositional semantics for disjunctive logic programs", In the Journal of Annals of Mathematics and Artificial Intelligence, Vol 12, 1994, pp. 53-87.
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.
Dechter R., "Bucket elimination: A unifying framework for reasoning," Artificial Intelligence, 113 (1999) 41-85.
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 Inference" In the journal of ACM, 2003.
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.
R. Marinescu and R. Dechter, "AND/OR Branch-and-Bound search for combinatorial optimization in graphical models," Artif. Intell., 173(16-17): 1457-1491 (2009).
V. Gogate and R. Dechter. "SampleSearch: Importance Sampling in presence of Determinism," Artif. Intell., 175(2): 694-729 (2011).
Lars Otten, Rina Dechter, "Anytime AND/OR depth-first search for combinatorial optimization," AI Commun., 25(3): 211-227 (2012).
Mark Silberstein, Omer Weissbrod, Lars Otten, Anna Tzemach, Andrei Anisenia, Oren Shtark, Dvir Tuberg, Eddie Galfrin, Irena Gannon, Adel Shalata, Zvi U. Borochowitz,
Rina Dechter, Elizabeth Thompson, Dan Geiger, "A system for exact and approximate genetic linkage analysis of SNP data in large pedigrees," Bioinformatics, 29(2): 197-205 (2013).
Natalia Flerova, Radu Marinescu and Rina Dechter, "Searching for m best solutions in graphical models," Journal of Artificial Intelligence Research", 2016. pp. 889-952.
William Lam, Kalev Kask, Javier Larrosa, and Rina Dechter. "Residual-Guided Look-Ahead in AND/OR Search for Graphical Models," Journal of Artificial Intelligence Research (JAIR), volume 60, 2017. pp. 287-346.
Radu Marinescu, Junkyu Lee, Rina Dechter and Alex Ihler. "AND/OR Search for Marginal Map," Journal of Artificial Intelligence Research(JAIR), Vol 63 2018.
