Rina Dechter
Distinguished Professor
Donald Bren School of Information and Computer Sciences
Donald Bren School of Information and Computer Sciences
PH.D., University of California, Los Angeles, 1985, Computer Science
University of California, Irvine
CS 424-E
Mail Code: 3425
Irvine, CA 92697
CS 424-E
Mail Code: 3425
Irvine, CA 92697
Research Interests
Problem Solving in Artificial Intelligence, Constraint Based Reasoning
Websites
Research Abstract
The overall aim of my research is to devise methods of automated reasoning via the understanding and exploitation of tractable classes of reasoning tasks. I believe that approximation methods based on tractable models cover a significant portion of intelligent activities and, hence, should serve as the cornerstone in automated reasoning systems. This principle has motivated my previous research on greedy problems, mechanical generation of heuristics, topological decompositions, and local computations in constraint networks.
Constraint networks have proven to be a useful language for modeling and solving computationally intensive tasks in Artificial Intelligence. The language of constraints expresses information in terms of the desired relationships among entities without specifying how such relationships are to be achieved. Constraint networks are used to model mundane cognitive tasks (e.g., vision, language comprehension, default reasoning, abduction) as well as applications such as scheduling, design, and diagnosis which require high levels of human expertise. In general, the tasks posed in this language are computationally intractable (NP-hard). A survey of constraint networks appears in "Constraint Networks," in the Encyclopedia of Artificial Intelligence, 1992.
In recent years, I have developed and analyzed a large number of techniques for finding partial and complete solutions to a variety of constraint classes, often accompanied by theoretical guarantees of worst-case performance. These techniques, including directional consistency, adaptive consistency, tree clustering, cycle cutset schemes, backjumping, and search-based learning, have become popular in many constraint-processing applications.
My current research interests focus on developing scalable techniques in constraint processing and on applying those techniques to broader areas in automated reasoning. The following is an outline of my research projects.
Empirical Evaluation Of Constraint Processing Algorithms:
An ongoing research goal is to close the gap between theory and practice in constraint processing. To that end, we perform a large-scale experimentation on both real-life and simulated systems. We plan to build an environment in which large scale constraint-based problems could be modeled, processed, evaluated, and analyzed. The project promises to yield a deeper understanding of those features in the domain that admit efficient processing. I hope that this understanding will lead to scalable algorithms, and to new software tools and languages for generic constraint-processing applications. My experimental work focuses both on comparing backtracking style algorithms as well as local search greedy algorithms.
Constraint networks have proven to be a useful language for modeling and solving computationally intensive tasks in Artificial Intelligence. The language of constraints expresses information in terms of the desired relationships among entities without specifying how such relationships are to be achieved. Constraint networks are used to model mundane cognitive tasks (e.g., vision, language comprehension, default reasoning, abduction) as well as applications such as scheduling, design, and diagnosis which require high levels of human expertise. In general, the tasks posed in this language are computationally intractable (NP-hard). A survey of constraint networks appears in "Constraint Networks," in the Encyclopedia of Artificial Intelligence, 1992.
In recent years, I have developed and analyzed a large number of techniques for finding partial and complete solutions to a variety of constraint classes, often accompanied by theoretical guarantees of worst-case performance. These techniques, including directional consistency, adaptive consistency, tree clustering, cycle cutset schemes, backjumping, and search-based learning, have become popular in many constraint-processing applications.
My current research interests focus on developing scalable techniques in constraint processing and on applying those techniques to broader areas in automated reasoning. The following is an outline of my research projects.
Empirical Evaluation Of Constraint Processing Algorithms:
An ongoing research goal is to close the gap between theory and practice in constraint processing. To that end, we perform a large-scale experimentation on both real-life and simulated systems. We plan to build an environment in which large scale constraint-based problems could be modeled, processed, evaluated, and analyzed. The project promises to yield a deeper understanding of those features in the domain that admit efficient processing. I hope that this understanding will lead to scalable algorithms, and to new software tools and languages for generic constraint-processing applications. My experimental work focuses both on comparing backtracking style algorithms as well as local search greedy algorithms.
Publications
R. Dechter and J. Pearl "Structure Identification in Relational Data," Artificial Intelligence, forthcoming.
R. Ben-Eliyahu and R. Dechter, "Propositional Semantics for Default Logic," Proceedings of Fourth International Workshop On Nonmonotonic Reasoning, Plymouth, Vermont, May 1992.
R. Dechter, "From Local to Global Consistency," Artificial Intelligence Journal, Vol 55, 1992, pp. 87-107.
Link to this profile
https://faculty.uci.edu/profile/?facultyId=2398
https://faculty.uci.edu/profile/?facultyId=2398
Last updated
09/15/2020
09/15/2020