Rina Dechter
Information and Computer Sciende
University of California, Irvine
Research in UC-Irvine is focused on automated reasoning in Artificial Intelligence, particularly in the areas of search, constraint-based reasoning and reasoning under uncertainty. Constraint networks served in the last decades as a framework for studying the boundaries of efficient reasoning. In the past years theoretical studies in UC-Irvine have identified a variety of tractable classes and methods of exploiting those classes, to tackle general problems, while empirical studies provided new insights by evaluating average performance of large classes of problems.
In the past 10 years Research on constraint processing in UC-Irvine focused on identifying tractable classes and using those classes to suggest heuristics and approximation methods for solving the general constraint satisfaction problems.
Systematic methods were investigated using the framework of backtracking search on one hand and variable-elimination algorithms on the other. Approximation scheme ranging from local stochastic search (approximating search) to local constraint propagation and bounded consistency (approximating variable elimination ) were presented and analyzed. The special class of temporal constraints was studied. Many of these techniques exploit the topological structure of the knowledge base. Two parameters controlling the complexity of structure-based reasoning are the induced width and the cycle-cutset of the problem's graph [Dec92].
Research also focused on constraint-processing algorithms to temporal reasoning, developing general network-based frameworks capable of handling both qualitative and quantitative temporal information [dmp90,meiri91,eddie97]. These algorithms were also embedded in a temporal language and are summarized in [eddie-thesis98].
Currently, we expand constraint processing techniques to constraint optimization and to probabilistic inference, using the unifying framework of bucket elimination, which allow exploring the interplay between inference and search. that allows expressing combination of variable elimination (such as dynamic programming, resolution, Fourier linear elimination, adaptive consistency, and inferences in probabilistic networks) with conditioning algorithm ( such as backtracking search, DavisLovelenad-Longemann (DLL) algorithm, and Branch and bound) in a unified manner.
Below we elaborate on our recent activities:
Trading space for time Variable elimination algorithms are space and
time exponential in the induced-width, while search is linear space and exponential
time. We have developed hybrid schemes that use inference and search as its
two extremes and, using a single design parameter, permit the user to control
the storage-time tradeoff in accordance with available resources [EFD96,KD99,KD96].
Empirical evaluation of backtrack search We have conducted a large scale empirical evaluation of different styles of backtracking schemes for solving CSPs over randomly generated instances and several benchmarks [dfrost94a,frost-thesis]. In particular, we focused on the problem of scheduling maintenance of power generating units in a power plant. We modeled the problem as a constraint problem and provided an ``iterative learning'' algorithm which solves a series of CSPs with successively tighter cost-bound constraints. [FD99, Fro97].
Approximating variable-elimination We designed a new approach for approximating inference (e.g., bucket-elimination [dechter-bucket]) for constraint optimization and probabilistic inference, called mini-bucket elimination. The scheme permits a flexible adjustment of the three-dimensional storage-time-accuracy surface. The idea, inspired by successful constraint propagation algorithms, is to bound the dimensionality of dependencies created during inference. It yields a parameterized scheme controlled by a bound on the size of functions that are recorded during processing. Higher bounds result in more accurate solutions but require more computation. [DR97, RKD98]. We evaluated empirically the mini-bucket approach for the optimization task of finding the most probable explanation (MPE) in belief networks, demonstrating improved performance relative to other approaches [RKD98].
Stochastic local search schemes. We develop several variants of Stochastic Local Search (SLS) methods. In particular, we provided two schemes for combining local search with local inference (arc-consistency) for CSPs, showing improved performance [KD95,KD96]. We extended such algorithms for optimization showing that combining hill-climbing with stochastic steps outperform pure hill-climbing search, pure stochastic simulation search, as well as the well-known simulated annealing[KD99].
Temporal reasoning. We designed two temporal languages having practical inference procedures based on bounded constraint propagation. We designed our temporal languages within the framework of CLP (Constraint Logic Programming), using Datalog as the base language and including a temporal constraint domain and the temporal reification method for expressing the times at which predicate are true [Sch98].
Research also focused on constraint-processing algorithms to temporal reasoning, developing general network-based frameworks capable of handling both qualitative and quantitative temporal information [RDP90,Mei91,SD97]. These algorithms were also embedded in a temporal language and are summarized in [Sch98].
[Dec92] R.~Dechter. Constraints networks. In Encyclopedia of Artificial Intelligence, 2nd Ed., pages 276--285, 1992.
[Dec96a]R.Dechter. Bucket elimination: A unifying framework for probabilistic inference algorithms. In Uncertainty in Artificial Intelligence (UAI'96), pages 211--219, 1996.
[Dec96b] R.Dechter. Topological parameters for time-space tradeoffs. In Unc rtainty in Artificial Intelligence (UAI'96), pages 220--227, 1996.
[DR97] R.Dechter and I.~Rish. A scheme for approximating probabilistic inference. In Proceedings of Uncertainty in Artificial Intelligence (UAI'97), pages 132--141, 1997.
[EFD96] Y.El-Fattah and R.~Dechter. An evaluation of structural parameters for probabilistic reasoning: results on benchmark circuits. In Uncertainty in Artificial Intelligence (UAI'96), pages 244--251, 1996.
[FD94] D.~Frost and R.~Dechter. In search of best search: An empirical evaluation. In AAAI'94: Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 301--306, Seattle, 1994.
[FD99] D.~Frost and R.Dechter. Maintenance scheduling problems as benchmarks for constraint algorithms. Annals of Mathematics and Artificial Intelligence (to appear), 1999.
[Fro97] D.H. Frost. Algorithms and heuristics for constraint satisfaction problems. Technical report, Ph.D. thesis, Information and Computer Science, University of California, Irvine, California, 1997.
[KD95] K.~Kask and R.~Dechter. Gsat and local consistency. In International Joint Conference on Artificial Intelligence (IJCAI'95), pages 616--622, Montreal, Canada, August 1995.
[KD96] K.~Kask and R.~Dechter. A graph-based method for improving gsat. In National Conference on Artificial Intelligence (AAAI'96), pages 350--355, Portland Oregon, August 1996.
[KD99] K.~Kask and R.~Dechter. Stochastic local search for bayesian networks. In Workshop on AI and Statistics (AISTAT'99), 1999.
[Mei91] I.~Meiri. Combining qualitative and quantitative constraint satisfaction problems. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI'91), Anaheim, CA, July 1991.
[RD00] I.~Rish and R.~Dechter. Resolution vs. sat: two approaches to sat. Journal of Approximate Reasoning (to appear), 2000.
[RDP90] I.~Meiri R.~Dechter and J.~Pearl. Temporal constraint networks. In Artificial Intelligence, 49:61--95, 1990.
[RKD98]I.~Rish, K.~Kask, and R.~Dechter. Approximation algorithms for probabilistic decoding. In {\em Uncertainty in Artificial Intelligence (UAI'98), 1998.
[Sch98] E.~Schwalb. Temporal reasoning with constraints. Technical report, Ph.d. thesis, Information and Computer Science, Universiy of California, Irvine, 1998.
[SD97] E.~Schwalb and R.~Dechter Processing disjunctions in temporal constraint networks. Artificial Intelligence, pages 29--61, 1997.