Rational Deployment of CSP Heuristics

1 Introduction

Large search spaces are common in artificial intelligence, heuristics being of major importance in limiting search efforts. The role of a heuristic, depending on type of search algorithm, is to decrease the number of nodes expanded (e.g. in A* search), the number of candidate actions considered (planning), or the number of backtracks in constraint satisfaction problem (CSP) solvers. Nevertheless, some sophisticated heuristics have considerable computational overhead, significantly decreasing their overall effect [Horsch and Havens, 2000; Kask et al., 2004], even causing increased total runtime in pathological cases. It has been recognized that control of this overhead can be essential to improve search performance; e.g. by selecting which heuristics to evaluate in a manner dependent on the state of the search [Wallace and Freuder, 1992; Domshlak et al., 2010].

We propose a rational metareasoning approach [Russell and Wefald, 1991] to decide when and how to deploy heuristics, using CSP backtracking search as a case study. The heuristics examined are various solution count estimate heuristics for value ordering [Meisels et al., 1997; Horsch and Havens, 2000], which are expensive to compute, but can significantly decrease the number of backtracks. These heuristics make a good case study, as their overall utility, taking computational overhead into account, is sometimes detrimental; and yet, by employing these heuristics adaptively, it may still be possible to achieve an overall runtime improvement, even in these pathological cases. Following the metareasoning approach, the value of information (VOI) of a heuristic is defined in terms of total search time saved, and the heuristic is computed such that the expected net VOI is positive.

We begin with background on metareasoning and CSP (Section 2), followed by a re-statement of value ordering in terms of rational metareasoning (Section 3), allowing a definition of VOI of a value-ordering heuristics - a contribution of this paper. This scheme is then instantiated to handle our case-study of backtracking search in CSP (Section 4), with parameters specific to value-ordering heuristics based on solution-count estimates, the main contribution of this paper. Empirical results (Section 5) show that the proposed mechanism successfully balances the tradeoff between decreasing backtracking and heuristic computational overhead, resulting in a significant overall search time reduction. Other aspects of such tradeoffs are also analyzed empirically. Finally, related work is examined (Section 6), and possible future extensions of the proposed mechanism are discussed (Section 7).

2 Background

2.1 Rational metareasoning

In rational metareasoning [Russell and Wefald, 1991], a problem-solving agent can perform base-level actions from a known set {Ai}. Before committing to an action, the agent may perform a sequence of meta-level "deliberation" actions from a set {Sj}. At any given time there is an "optimal" baselevel action, Aα, that maximizes the agent's expected utility:

where {Wk} is the set of possible world states, U(Ai,Wk) is the utility of performing action Ai in state Wk, and P(Wk) is the probability that the current world state is Wk.

A meta-level action provides information and affects the choice of the base-level action Aα. The value of information (VOI) of a meta-level action Sj is the expected difference between the expected utility of Sj and the expected utility of the current Aα, where P is the current belief distribution about the state of world, and P j is the belief-state distribution of the agent after the computational action Sj is performed, given the outcome of Sj :

Under certain assumptions, it is possible to capture the dependence of utility on time in a separate notion of time cost C. Then, Equation (2) can be rewritten as:

where the intrinsic value of information

is the expected difference between the intrinsic expected utilities of the new and the old selected base-level action, computed after the meta-level action is taken.

2.2 Constraint satisfaction

A constraint satisfaction problem (CSP) is defined by a set of variables X = {X1,X2, ...}, and a set of constraints C = {C1, C2, ...}. Each variable Xi has a non-empty domain Di of possible values. Each constraint Ci involves some subset of the variables-the scope of the constraint- and specifies the allowable combinations of values for that subset. An assignment that does not violate any constraints is called consistent (or a solution). There are numerous variants of CSP settings and algorithmic paradigms. This paper focuses on binary CSPs over discrete-values variables, and backtracking search algorithms [Tsang, 1993].

A basic method used in numerous CSP search algorithm is that of maintaining arc consistency (MAC) [Sabin and Freuder, 1997]. There are several versions of MAC; all share the common notion of arc consistency. A variable Xi is arcconsistent with Xj if for every value a of Xi from the domain Di there is a value b of Xj from the domain Dj satisfying the constraint between Xi and Xj. MAC maintains arc consistency for all pairs of variables, and speeds up backtracking search by pruning many inconsistent branches.

CSP backtracking search algorithms typically employ both variable-ordering [Tsang, 1993] and value-ordering heuristics. The latter type include minimum conflicts [Tsang, 1993], which orders values by the number of conflicts they cause with unassigned variables, Geelen's promise [Geelen, 1992] - by the product of domain sizes, and minimum impact [Refalo, 2004] orders values by relative impact of the value assignment on the product of the domain sizes.

Some value-ordering heuristics are based on solution count estimates [Meisels et al., 1997; Horsch and Havens, 2000; Kask et al., 2004]: solution counts for each value assignment of the current variable are estimated, and assignments (branches) with the greatest solution count are searched first. The heuristics are based on the assumption that the estimates are correlated with the true number of solutions, and thus a greater solution count estimate means a higher probability that a solution be found in a branch, as well as a shorter search time to find the first solution if one exists in that branch. [Meisels et al., 1997] estimate solution counts by approximating marginal probabilities in a Bayesian network derived from the constraint graph; [Horsch and Havens, 2000] propose the probabilistic arc consistency heuristic (pAC) based on iterative belief propagation for a better accuracy of relative solution count estimates; [Kask et al., 2004] adapt Iterative Join-Graph Propagation to solution counting, allowing a tradeoff between accuracy and complexity. These methods vary by computation time and precision, although all are rather computationally heavy. Principles of rational metareasoning can be applied independently of the choice of implementation, to decide when to deploy these heuristics.

3 Rational Value-Ordering

The role of (dynamic) value ordering is to determine the order of values to assign to a variable Xk from its domain Dk, at a search state where values have already been assigned to (X1, ...,Xk-1). We make the standard assumption that the ordering may depend on the search state, but is not recomputed as a result of backtracking from the initial value assignments to Xk: a new ordering is considered only after backtracking up the search tree above Xk.

Value ordering heuristics provide information on future search efforts, which can be summarized by 2 parameters:

• Ti-the expected time to find a solution containing assignment Xk = yki or verify that there are no such solutions;
• pi-the "backtracking probability", that there will be no solution consistent with Xk = yki.

These are treated as the algorithm's subjective probabilities about future search in the current problem instance, rather than actual distributions over problem instances. Assuming correct values of these parameters, and independence of backtracks, the expected remaining search time in the subtree under Xk for ordering ω is given by:

In terms of rational metareasoning, the "current" optimal base-level action is picking the ω which optimizes T s|ω . Based on a general property of functions on sequences [Monma and Sidney, 1979], it can be shown that T s|ω is minimal if the values are sorted by increasing order of Ti 1-pi .

A candidate heuristic H (with computation time T H ) generates an ordering by providing an updated (hopefully more precise) value of the parameters Ti, pi for value assignments Xk = yki, which may lead to a new optimal ordering ωH, corresponding to a new base-level action. The total expected remaining search time is given by:

Since both T H (the "time cost" of H in metareasoning terms) and T s|ωH contribute to T, even a heuristic that improves the estimates and ordering may not be useful. It may be better not to deploy H at all, or to update Ti, pi only for some of the assignments. According to the rational metareasoning approach (Section 2.1), the intrinsic VOI Λi of estimating Ti, pi for the ith assignment is the expected decrease in the expected search time:

where ω- is the optimal ordering based on priors, and ω+i on values after updating Ti, pi. Computing new estimates (with overhead T c ) for values Ti, pi is beneficial just when the net VOI is positive:

To simplify estimation of Λi, the expected search time of an ordering is estimated as though the parameters are computed only for ω-(1), i.e. for the first value in the ordering; essentially, this is the metareasoning subtree independence assumption. Other value assignments are assumed to have the prior ("default") parameters Tdef , pdef . Assuming w.l.o.g. that ω-(1) = 1:

and the intrinsic VOI of the ith deliberation action is:

where G(Ti, pi) is the search time gain given the heuristically computed values Ti, pi:

In some cases, H provides estimates only for the expected search time Ti. In such cases, the backtracking probability pi can be bounded by the Markov inequality as the probability for the given assignment that the time t to find a solution or to verify that no solution exists is at least the time T all i to find all solutions: pi = P (t ≥ T all i ) ≤ Ti T all i , and the bound can be used to estimate the probability:

Furthermore, note that in harder problems the probability of backtracking from variable Xk is proportional to p(|Dk|-1) def , and it is reasonable to assume that backtracking probabilities above Xk (trying values for X1, ...,Xk-1) are still significantly greater than 0. Thus, the "default" backtracking probability pdef is close to 1, and consequently:

By substituting (12), (13) into (11), estimate (14) for G(Ti, pi) is obtained:

Finally, since (12), (13) imply that Ti < T1 ⇔ Ti 1-pi < T1 1-p1 ,

4 VOI of Solution Count Estimates

The estimated solution count for an assignment may be used to estimate the expected time to find a solution for the assignment under the following assumptions 1 :

1. Solutions are roughly evenly distributed in the search space, that is, the distribution of time to find a solution can be modeled by a Poisson process.
2. Finding all solutions for an assignment Xk = yki takes roughly the same time for all assignments to the variable Xk. Prior work [Meisels et al., 1997; Kask et al., 2004] demonstrates that ignoring the differences in subproblem sizes is justified.
3. The expected time to find all solutions for an assignment divided by its solution count estimate is a reasonable estimate for the expected time to find a single solution.

Based on these assumptions, Ti can be estimated as T all |Dk |ni where T all is the expected time to find all solutions for all values of Xk, and ni is the solution count estimate for yki; likewise, T1 = T all |Dk |nmax , where nmax is the currently greatest ni. By substituting the expressions for Ti, T1 into (15), obtain as the intrinsic VOI of computing ni:

where P(n, ν) = e-ν ν n n! is the probability, according to the Poisson distribution, to find n solutions for a particular assignment when the mean number of solutions per assignment is ν = N |Dk| , and N is the estimated solution count for all values of Xk, computed at an earlier stage of the algorithm.

Neither T all nor T c , the time to estimate the solution count for an assignment, are known. However, for relatively low solution counts, when an invocation of the heuristic has high intrinsic VOI, both T all and T c are mostly determined by the time spent eliminating non-solutions. Therefore, T c can be assumed approximately proportional to T all |Dk| , the average time to find all solutions for a single assignment, with an unknown factor γ < 1:

Then, T all can be eliminated from both T c and Λ. Following Equation (8), the solution count should be estimated whenever the net VOI is positive:

The infinite series in (18) rapidly converges, and an approximation of the sum can be computed efficiently. As done in Section 5, γ can be learned offline from a set of problem instances of a certain kind for the given implementation of the search algorithm and the solution counting heuristic.

1 We do not claim that this is a valid model of CSP search; rather, we argue that even with such a crude model one can get significant runtime improvements.

Algorithm 1 implements rational value ordering. The procedure receives problem instance csp with assigned values for variables X1, ...,Xk-1, variable Xk to be ordered, and estimate N of the number of solutions of the problem instance (line 1); N is computed at the previous step of the backtracking algorithm as the solution count estimate for the chosen assignment for Xk-1, or, if k = 1, at the beginning of the search as the total solution count estimate for the instance. Solution counts ni for some of the assignments are estimated (lines 4-9) by selectively invoking the heuristic computation ESTIMATESOLUTIONCOUNT (line 8), and then the domain of Xk, ordered by non-increasing solution count estimates of value assignments, is returned (lines 11-12).

5 Empirical Evaluation

Specifying the algorithm parameter γ is the first issue. γ should be a characteristic of the implementation of the search algorithm, rather than of the problem instance; it is also desirable that the performance of the algorithm not be too sensitive to fine tuning of this parameter.

Most of the experiments were conducted on sets of random problem instances generated according to Model RB [Xu and Li, 2000]. The empirical evaluation was performed in two stages. In the first stage, several benchmarks were solved for a wide range of values of γ, and an appropriate value for γ was chosen. In the second stage, the search was run on two sets of problem instances with the chosen γ, as well as with exhaustive deployment, and with the minimum conflicts heuristic, and the search time distributions were compared for each of the value-ordering heuristics.

The AC-3 version of MAC was used for the experiments, with some modifications [Sabin and Freuder, 1997]. Variables were ordered using the maximum degree variable ordering heuristic. 2 The value-ordering heuristic was based on a version of the solution count estimate proposed in [Meisels et al., 1997]. The version used in this paper was optimized for better computation time for overconstrained problem instances. As a result, Equation (17) is a reasonable approximation for this implementation. The source code is available from http://ftp.davidashen.net/vsc.tar.gz.

2 A dynamic variable ordering heuristic, such as dom/deg, may result in shorter search times in general, but gave no significant improvement in our experiments; on the other hand, static variable ordering simplifies the analysis.

5.1 Benchmarks

CSP benchmarks from CSP Solver Competition 2005 [Boussemart et al., 2005] were used. 14 out of 26 benchmarks solved by at least one of the solvers submitted for the competition could be solved with 30 minutes timeout by the solver used for this empirical study for all values of γ: γ = 0 and the exponential range γ ∈ {10-7 , 10-6 , ..., 1}, as well as with the minimum-conflicts heuristic and the pAC heuristic.

Figure 1.a shows the mean search time of VOI-driven solution count estimate deployment TV SC normalized by the search time of exhaustive deployment TSC (γ = 0), for the minimum conflicts heuristic TMC, and for the pAC heuristic TPAC. The shortest search time on average is achieved by VSC for γ ∈ [10-4 , 3 · 10-3 ] (shaded in the figure) and is much shorter than for SC (mean ( TVSC(10-3 ) TSC ) ≈ 0.45); the improvement was actually close to the "ideal" of getting all the information provided by the heuristic without paying the overhead at all. For all but one of the 14 benchmarks the search time for VSC with γ = 3 · 10-3 is shorter than for MC. For most values of γ, VSC gives better results than MC ( TV SC TMC < 1). pAC always results in the longest search time due to the computational overhead.

Figure 1.b shows the mean number of backtracks of VOIdriven deployment NV SC normalized by the number of backtracks of exhaustive deployment NSC, the minimum conflicts heuristic NMC , and for the pAC heuristic NpAC . VSC causes less backtracking than MC for γ ≤ 3·10-3 ( NV SC NMC < 1). pAC always causes less backtracking than other heuristics, but has overwhelming computational overhead.

Figure 1.c shows CV SC, the number of estimated solution counts of VOI-driven deployment, normalized by the number of estimated solution counts of exhaustive deployment CSC. When γ = 10-3 and the best search time is achieved, the solution counts are estimated only in a relatively small number of search states: the average number of estimations is ten times smaller than in the exhaustive case (mean ( CV SC (10-3 ) CSC ) ≈ 0.099, median ( CVSC(10-3 ) CSC ) ≈ 0.048).

The results show that although the solution counting heuristic may provide significant improvement in the search time, further improvement is achieved when the solution count is estimated only in a small fraction of occasions selected using rational metareasoning.

5.2 Random instances

Based on the results on benchmarks, we chose γ = 10-3 , and applied it to two sets of 100 problem instances. Exhaustive deployment, rational deployment, the minimum conflicts heuristic, and probabilistic arc consistency were compared.

The first, easier, set was generated with 30 variables, 30 values per domain, 280 constraints, and 220 nogood pairs per constraint (p = 0.24, pcrit = 0.30). Search time distributions are presented in Figure 2.a. The shortest mean search time is achieved for rational deployment, with exhaustive deployment next ( TSC T V SC ≈ 1.75), followed by the minimum conflicts heuristic ( TMC T V SC ≈ 2.16) and probabilistic arc consistency ( TpAC T V SC ≈ 3.42). Additionally, while the search time distributions for solution counting are sharp ( max TSC T SC ≈ 1.08, maxTVSC T V SC ≈ 1.73), the distribution for the minimum conflicts heuristic has a long tail with a much longer worst case time ( maxTVSC T V SC ≈ 5.67).

The second, harder, set was generated with 40 variables, 19 values, 410 constraints, 90 nogood pairs per constraint (exactly at the phase transition: p = pcrit = 0.25). Search time distributions are presented in Figure 2.b. As with the first set, the shortest mean search time is achieved for rational deployment: TSC T V SC ≈ 1.43, while the relative mean search time for the minimum conflicts heuristic is much longer: T MC T V SC ≈ 3.45. The probabilistic arc consistency heuristic resulted again in the longest search time due to the overhead of computing relative solution count estimates by loopy belief propagation: maxTVSC T V SC ≈ 3.91.

Thus, the value of γ chosen based on a small set of hard instances gives good results on a set of instances with different parameters and of varying hardness.

5.3 Generalized Sudoku

Randomly generated problem instances have played a key role in the design and study of heuristics for CSP. However, one might argue that the benefits of our scheme are specific to model RB. Indeed, real-world problem instances often have much more structure than random instances generated according to Model RB. Hence, we repeated the experiments on randomly generated Generalized Sudoku instances [Ans´otegui et al., 2006], since this domain is highly structured, and thus a better source of realistic problems with a controlled measure of hardness.

The search was run on two sets of 100 Generalized Sudoku instances, with 4x3 tiles and 90 holes and with 7x4 tiles and 357 holes, with holes punched using the doubly balanced method [Ans´otegui et al., 2006]. The search was repeated on each instance with the exhaustive solution-counting, VOIdriven solution counting (with the same value of γ = 10-3 as for the RB model problems), minimum conflicts, and probabilistic arc consistency value ordering heuristics. Results are summarized in Table 1 and show that relative performance of the methods on Generalized Sudoku is similar to the performance on Model RB.

5.4 Deployment patterns

One might ask whether trivial methods for selective deployment would work, such as estimating solution counts for a certain number of assignments in the beginning of the search. We examined deployment patterns of VOI-driven SC with (γ = 10-3 ) on several instances of different hardness. For all instances, the solution counts were estimated at varying rates during all stages of the search, and the deployment patterns differed between the instances, so a simple deployment scheme seems unlikely.

VOI-driven deployment also compares favorably to random deployment. Table 2 shows performance of VOI-driven deployment for γ = 10-3 and of uniform random deployment, with total number of solution count estimations equal to that of the VOI-driven deployment. For both schemes, the values for which solution counts were not estimated were ordered randomly, and the search was repeated 20 times. The mean search time for the random deployment is ≈ 1.6 times longer than for the VOI-driven deployment, and has ≈ 100 times greater standard deviation.

6 Discussion and RelatedWork

The principles of bounded rationality appear in [Horvitz, 1987]. [Russell and Wefald, 1991] provided a formal description of rational metareasoning and case studies of applications in several problem domains. A typical use of rational metareasoning in search is in finding which node to expand, or in a CSP context determining a variable or value assignment. The approach taken in this paper adapts these methods to whether to spend the time to compute a heuristic.

Runtime selection of heuristics has lately been of interest, e.g. deploying heuristics for planning [Domshlak et al., 2010]. The approach taken is usually that of learning which heuristics to deploy based on features of the search state. Although our approach can also benefit from learning, since we have a parameter that needs to be tuned, its value is mostly algorithm dependent, rather than problem-instance dependent. This simplifies learning considerably, as opposed to having to learn a classifier from scratch. Comparing metareasoning techniques to learning techniques (or possibly a combination of both, e.g. by learning more precise distribution models) is an interesting issue for future research.

Although rational metareasoning is applicable to other types of heuristics, solution-count estimation heuristics are natural candidates for the type of optimization suggested in this paper. [Dechter and Pearl, 1987] first suggested solution count estimates as a value-ordering heuristic (using propagation on trees) for constraint satisfaction problems, refined in [Meisels et al., 1997] to multi-path propagation.

[Horsch and Havens, 2000] used a value-ordering heuristic that estimated relative solution counts to solve constraint satisfaction problems and demonstrated efficiency of their algorithm (called pAC, probabilistic Arc Consistency). However, the computational overhead of the heuristic was large, and the relative solution counts were computed offline. [Kask et al., 2004] introduced a CSP algorithm with a solution counting heuristic based on the Iterative Join-Graph Propagation

(IJGP-SC), and empirically showed performance advances over MAC in most cases. In several cases IJGP-SC was still slower than MAC due to the computational overhead. [Kask et al., 2004] also used the IJGP-SC heuristic as the value ordering heuristic for MAC.

Impact-based value ordering [Refalo, 2004] is another heavy informative heuristic. One way to decrease its overhead, suggested in [Refalo, 2004], is to learn the impact of an assignment by averaging the impact of earlier assignments of the same value to the same variable. Rational deployment of this heuristic by estimating the probability of backtracking based on the impact may be possible, an issue for future research. [Gomes et al., 2007] propose a technique that adds random generalized XOR constraints and counts solutions with high precision, but at present requires solving CSPs, thus seems not to be immediately applicable as a search heuristic.

The work presented in this paper differs from the above related schemes in that it does not attempt to introduce new heuristics or solution-count estimates. Rather, an "off the shelf" heuristic is deployed selectively based on value of information, thereby significantly reducing the heuristic's "effective" computational overhead, with an improvement in performance for problems of different size and hardness.

7 Summary and Future Research

This paper suggests a model for adaptive deployment of value ordering heuristics in algorithms for constraint satisfaction problems. As a case study, the model was applied to a valueordering heuristic based on solution count estimates, and a steady improvement in the overall algorithm performance was achieved compared to always computing the estimates, as well as to other simple deployment tactics. The experiments showed that for many problem instances the optimum performance is achieved when solution counts are estimated only in a relatively small number of search states.

The methods introduced in this paper can be extended in numerous ways. First, generalization of the VOI to deploy different types of heuristics for CSP, such as variable ordering heuristics, as well as reasoning about deployment of more than one heuristic at a time, are natural non-trivial extensions. Second, an explicit evaluation of the quality of the distribution model is an interesting issue, coupled with a better candidate model of the distribution. Such distribution models can also employ more disciplined statistical learning methods in tandem, as suggested above. Finally, applying the methods suggested in this paper to search in other domains can be attempted, especially to heuristics for planning. In particular, examining whether the meta-reasoning scheme can improve reasoning over deployment of heuristics based solely on learning methods is an interesting future research issue.

Acknowledgments

The research is partially supported by the IMG4 Consortium under the MAGNET program of the Israeli Ministry of Trade and Industry, by Israel Science Foundation grant 305/09, by the Lynne and William Frankel Center for Computer Sciences, and by the Paul Ivanier Center for Robotics Research and Production Management.