Search is one of the most pervasive techniques in artificial intelligence. Problem solving, diagnosis, design and planning, for example, can all be cast as a search through some space of alternatives. These search problems are often conceptually simple but computationally difficult since the solution time can grow exponentially with the size of the problem [12]. Given its central importance to the field, considerable work has been devoted to developing a variety of search methods and determining the situations for which they are best suited. In particular, heuristics [44] are often used to guide the series of choices or steps made during the search. Typically, at each decision point a heuristic evaluates a small number of potential choices, based on easily computed local properties of the search problem.
In a fundamental sense, the effectiveness of a search heuristic is determined by how the many repeated local decisions at the search steps combine to determine the global performance, e.g., the overall search cost or quality of the solution. In detail this depends on the specific problem and heuristic used. Fortunately, however, it is possible to study regularities in the typical behavior of general search methods for various classes of problems. This contrasts with the usual emphasis in computer science theory on a worst case analysis [12]. Focusing on typical behavior is particularly appropriate for evaluating search methods in practice since one usually is not interested in how well they work for a single given problem but rather for a variety of problems likely to be encountered in the future. In such cases, there may be only limited information available about the nature of the problems to be solved so the remaining details act as unspecified degrees of freedom. It is therefore useful to treat these unspecified degrees of freedom as randomly generated by some probability distribution. In this context, one might expect that statistical techniques, which have been so successful in describing physical systems, will provide a useful framework for understanding the global behavior of these computational problems, particularly when moving beyond idiosyncratic small systems [17]. This outlook becomes even more relevant when there is uncertain information as part of the problem [45].
Statistical mechanics, based on the law of large numbers, has taught us that many universal and generic features of large systems can be quantitatively understood as approximations to the average behavior of infinite systems. Although such infinite models can be difficult to solve in detail, their overall qualitative features can be determined with a surprising degree of accuracy. Since these features are universal in character and depend only on a few general properties of the system, they can be expected to apply to a wide range of actual configurations.
The first step in the statistical approach to search is to pick a suitable ensemble of problem instances. An ensemble consists of a class of problems and an associated probability for each one to appear. Often there will be a number of plausible choices with the same basic set of parameters and the same behaviors in the limit of large problems. In such cases one is free to select that ensemble that is most easily analyzed or most readily evaluated numerically [55]. Ideally these ensembles would have the broad range of applicability as those used in statistical physics (which generally treat each microscopic state consistent with the small number of known parameters as being equally likely). Unfortunately, in spite of some work along these lines [37], the nature of realistic search problems is not yet well enough understood to make this possible. Instead, most work in this area uses simple random classes of problems such as a variety of closely related ensembles of random constraint satisfaction problems [56, section 6.1,]. Comparing the predictions of these models to real problems should help identify more realistic ensembles, in much the same way that the need to incorporate quantum mechanical effects required a revision of the ensembles used in statistical physics.
The second step of a statistical analysis is to identify suitable global properties, such as the average search cost, in terms of the model parameters. Finally, one quantitatively relates the global behaviors to the local parameters describing the model. As in the statistical physics of anything more complex than ideal gases or solids, determining the exact form of this relation is often extremely difficult due to the many conditional probabilities involved. However, an approximate theory that assumes independent probabilities generally gives a good qualitative understanding of the global behaviors likely to be observed, and often fairly accurate quantitative values as well. These approximations give rise to so-called ``mean-field'' theories of physics since they correspond to assuming each component of the system interacts only with the mean behavior of the remaining components.
This technique provides a relatively simple way to identify those phenomena that are common to many statistical systems and arise mainly from the properties of large numbers rather than the details of particular systems. This is in contrast with the usual computer science theory with its focus on precise theorems. Moreover, examining the errors made by this approximation can also form the basis for more complex analyses using more detailed ensembles (indeed, the approximate theory can often be viewed as the exact behavior of some other, perhaps less realistic, ensemble of problems). Finally, one should note that the ensembles selected for empirical or theoretical work do not correspond precisely to those encountered in practice. The errors due to the choice of ensemble are likely to dominate those due to the approximations of the theory, giving another reason to focus on simple, robust phenomena rather than a complex, detailed analysis. This is a powerful advantage of the statistical mechanics approach since many behaviors are at least qualitatively similar in large size limit when detailed dependencies are ignored.