*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

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.* I*n 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 I*nternational
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.