A Wrinkle on Satisficing Search Problems

Introduction

Many investigators have examined problems of satisficing search : try the available methods one at a time until one of them satisfies the stated criteria, then stop. The objective is to find a method ordering with the least expected cost to solve the problem. Typically, only the probability of success and the ex­ pected cost are known for each method.

Method i is pairwise preferred to method j if, given only these two methods, it is less expensive to try i first. Pairwise preference is transitive. Therefore, if the optimal ordering of n methods is m 1 m 2 ... mn and mn+ 1 is added, it is merely inserted somewhere in the original ordering - all original methods stay in the same posi ­ tion relative to one another.

Below, the original problem is generalized: Associated with each method is a cost that must be paid, after trying the method, if another method is to be used. For example, the cost may be the time to undo the changes to the problem-solving state so that another method can be executed in the proper context.

The pairwise preference relation is no longer transitive and the simple insertion scheme is lost for the generalized problem. However, the criteria for optimal ordering is straightforward to derive. An algorithm that finds the optimal ordering is given , and it is shown to be of the same time complexity as the one for the original problem, namely o(n log n).

1 This research is supported by the Defense Advanced Research Projects Agency under Contract No. MDA903 81 C 0335. Views and conclusions contained in this report are the authors' and should not be interpreted as representing the official opinion or policy of DARPA, the U.S. Government, or any person or agency connected with them.

A WRINKLE ON SATISFICING SEARCH PROBLEMS 1

Jeffrey A. Barnett and Don Cohen USC Information Sciences Institute 4676 Admiralty Way

Marina del Rey, California 90291

The Original Problem

A set of methods is available, each of which has the potential to solve the same given problem. The methods can be applied to the problem in any order; however, they may only be tried one at a time. If one of the methods solves the problem, the remaining untried methods need not be used. In other words, only one solu ­ tion is desired or necessary, and there is no interest in extra solu­ tions nor any other results that might be produced by method ex­ ecution .

The usual statement of problems in this class assumes that the probability that a particular method is successful and the execu­ tion cost of the method are independent of the order of execution and whether or not any other method is successful. Without this independence assumption, there is no general optimal ordering because the tradeoff between higher probability of success and lower expected cost is an application-dependent issue; the most general result possible then, is a partial ordering for method ex­ ecution . However, with the independence assumption it follows that the total probability that at least one method will find a solu­ tion is independent of the order in which the methods are tried . Therefore, the residual problem is to determine the ordering with least expected cost.

A typical example of this class is the following: Let pi be the probability that method i solves the stated problem and define Q 1 = 1-pi. Further, let ci be the expected cost of trying method i. For example, ci = pisi + qiui ' where si is the expected cost when successful and ui is the expected cost when unsuccessful. What is the best order in which to apply a given set of methods to find a solution with the least expected cost?

The answer is simple: 2 Define cp . = p./c .. Apply first the method I I I with largest cp; if it fails, try the method with the next largest cp, etc. The order of application among methods with the same cp value is immaterial to the total expected cost of finding a solution.

Two features of this result are notewortl)y. First, a merit score {namely cpi = P/Ci) can be calculated for a method independent of what other methods exist. Thus, if a new method becomes avail ­ able, it can be evaluated separately and inserted into the current ordering of previously available methods with the assurance that the new ordering is optimal. Second, as a consequence, the pair­ wise preference ordering is transitive: Method i is preferred to method j if, given only methods i and j, the expected cost of trying i before j is less than trying j first , i.e., cp;>cpj' This preference rela­ tion is surely transitive: If i is preferred to j and j is preferred to k, then i is preferred to k.

2 See Simon, H. A., and J. B. Kadane, "Optimal Problem-Solving Search: Ali-or­ None Solutions," Artificial Intelligence 6 (1975), 235-247 for this and other related results.

Next, a slight generalization of this problem is considered where both the simple insertion property and transitivity disappear.

A Generalization

As in the original problem, P; is the probability that method i will solve the stated problem, q; = 1-P;· and c; is its expected cost. In addition , let d; be the cost incurred if method i fails and another method must be tried. For instance, if c; is interpreted as the time necessary to determine whether the i'th medication combats a dis­ ease, then d; can be interpreted as the detoxificat ion time neces­ sary before a different medication can be tested. Another inter­ pretation of d; is the expected cost to undo the effects of execut­ ing method i on the problem-solving state so that another method can be tried. The goal in this problem is to determine the correct medication, if any (or simply solve the problem) , in the least ex­ pected time. For the original problem, all d; = 0.

An Example

Define c .. as the expected cost of (1) trying method i, (2) if it fails, waitin~ for timed; , then (3) trying method j. It is evident that c .. = c.+ q.(d. +c.) and that method i is preferred to method j if IJ I I I J C .. <C .. . Suppose three methods are available with these values of IJ Jl p, c, and d-e and <I> are defined below.

Then the six possible values of Cii are

Thus, method 1 is preferred to method 2 (C 1 /C 21 ) , method 2 is preferred to method 3 (C 23 <C 32 ), but method 3 is preferred to method 1 (C 31 <C 13 ). Therefore, this example shows that the pair­ wise preference order is not transitive.

Formal Definitions

Though the pairwise preference relation does not induce a total ordering on .the set of methods, the optimal ordering can be deter­ mined in the same order of time as for the original problem, o(n log n) , where a simple sort on cp is sufficient. Some notation is necessary to develop this result. LetS be a sequence of methods and define P s as the probability that at least one method in S solves the problem; Qs = 1-P s· Let Cs be the expected cost · of trying the methods in S in the order mentioned (halting if one of them succeeds). Finally, Ds is the detoxification time necessary if all the methods in S fail and additional methods are to be tried.

Let 0 be the null sequence and i any method, then P 0 = 0, 0 0 = 1, C 0 = 0, and D 0 = 0; Pi= pi' 0; = qi, C; = ci, and D; = d;. The following recurrence relations hold where Sand T are sequences of methods and ST is the sequence formed by concatenating these two.

It is easy to see that these definitions are associative, i.e. , X(ST)U = XS(TU) where X= P, 0, C, or D.

Optimal Ordering

The criterion for ordering nonfinal methods is straightforward to develop using these definitions. Let S, T, U, V be any sequences of methods such that V;t0.

If i and j are methods, then Cs;;v :SCs;;v is the criterion that i come before j . The expansion above, first with T = i and U = j , then with T = j and U = i, allows the transformation

because all other terms cancel and Oii = Oii' Now, this form can be elaborated using the above definitions, then simplified as follows:

It is convenient to define e; = c; + q;d; and to note that e, is the total expected time, including detoxification, to try method i when it is in any nonfinal position in the ordering. (For sequences Sand T, the recurrence relation is EST= Es + OSET and in terms of C, 0 , and D the relation is Es = Cs + OsDs.) Thus, the criterion that method i come before method j is

Since the steps in the derivation are reversible, th is is both a necessary and sufficient condition. It is convenient to define <!>; = P/ e; and note that <I> plays the same role here for non final methods that cp did for all methods in the original problem.

The optimal ordering tries the nonfinal methods in order of decreasing <I> because <I>; depends only on the i'th method and clearly induces a total ordering on these methods. Among methods with equal <!> , the ordering is immaterial. The <I>; can be calculated and the methods sorted on its value in time O(n log n) .

However. the final method is not necessarily the one with lowest <1>. Let m 1 .. . mn be an ordering consistent with <1> ;:2:<1>;+ 1 Then for all except one method , say method j which should be final , the remaining methods are in this order. Therefore, the optimal order­ ing is the one of the form m; ... mi_ 1 mi + 1 ... mnmi for which Cis min­ imized.

Let S = m 1 ... mi_ 1 and T = mi + 1 ... mn such that T;t0. Then the optimal ordering is the one that maximizes CSiT-CsT/0. If all dif­ ferences are nonpositive, the original sorted ordering is optimal.

This difference expands as

For all j, the differences are calculated and the maximal one selected in time o(n) by the algorithm described next.

The Algorithm

The algorithm in Figure 1 is written in SIMULA as the class, method_ordering. There are n methods stored in the array m. Each method has the defined attributes id (a method identifier) and p, c, and d as described above. The derived attributes of a method are q, e, and phi, where phi= pie. The procedure, sort_on_phi , is not shown explicitly; it may be any sorting alga· rithm that orders m on nonincreasing values of phi in time o(n log n).

Procedure order uses sort_on_phi then finds an optimal order· in g. The steps are (1) find OS for each S = m 1 ... m; by noting that OS= q 1 · ... ·q; , (2) starting with T = mn' iterate backwards until T = m 2 ... mn and find the maximal difference. and (3) if the maximal difference is positive, rearrange minto the optimal ordering. In all cases, DT = dn. However, 0 1 and C 1 must be updated using OiT = qiOT and ciT= ci + qi(di + CT) so the iteration simulates T: =iT at each step.

If order is applied to the numerical example above, these steps occur.

1. The methods are sorted into the order {321} by their <t> values.
2. Two iterations are performed with the result that dif = .076 when j = 2 and dif = -.25 when j = 1. These iterations represent, respectively, the orderings {312} and {213}.
3. Since the maximal difference occurs when j = 2 and is positive, m is rearranged into the optimal ordering {312} .

For reference, the six values of Ciik are (321 32.580 (2 31 32.750 (312 = 32.504 (123 33 .930 [213 = 32.830 (1 32 33.960

Conclusion

It is noted above that the transitivity property of the pairwise preference relation is lost in the generalized problem. Further, the simple insertion property is lost too. In the original problem, a new method could be evaluated separately, i.e., cp = p/c is calculated and does not depend on what other methods exist, then the new methoa is inserted into the existing optimal ordering of other methods so that cp values are nonincreasing. The new ordering is then known to be optimal. In the new problem, this is not possible because the current optimal ordering may have an arbitrary method as the final method.

The reason that both transitivity and the simple insertion property are lost is easy to see - the expected cost of a method depends on its place in the ordering: If a method is in a nonfinal position, its cost is e; but if it is the final method , its cost is c;.

Another possible generalization of this class of ordering problems suggests itself; suppose the detoxification time between method i and method j is dii' i.e., d depends upon both the preced· ing and succeeding methods. Now the computation of the optimal ordering becomes at least as hard as the version of the traveling salesman problem where the salesman must visit each city once but does not need to return to his starting point . To see this, assume that p and care the same for all n methods and q = 1-p is very nearly equal 1. Then the cost of an ordering j = j 1 ... jn, where j is a permutation of the first n natural numbers is

The approximation is justified since q is very nearly equal to 1. Minimizing Ci reduces to minimizing the summation over the per· mutations, j, and this is the traveling salesman problem.

CLASS method_ordering(n); INTEGER n; BEGIN CLASS method(id.p,c.d); TEXT id; REAL p.c.d; BEGIN REAL PROCEDURE q; q:·1-p; REAL PROCEDURE e; e : ·c+q"d; REAL PROCEDURE phi; phi: ·pie; END method; REF(method) ARRAY m[1:n]; PROCEDURE sort_on_phi;; PROCEDURE order; BEGIN REAL ARRAY qs[O : n] ; INTEGER j.best_j; REAL dif,best_dif,qt,ct,dt ; REF(method) x; so rt_on_ph i; qs[O]:·l.O; FOR j:=1 STEP 1 UNTIL n DO qs[j]:·qs[j-l]"m[j].q; qt:·m[n] . q; ct:=m[n].c; dt : ·m[n].d; FOR j:·n-1 STEP -1 UNTIL 1 DO BEGIN dif : ·qs[j-1] END; "((1-qt)·m[j).c +m[j].q·m[j).d -(m[j].p·ct+qt"dt)); IF dif>best_dif THEN BEGIN best_dif : ·dif; best_j:·j; END; ct:·m[j].c+m[j].q· (m[j). d+ct); qt : =m[j]. q·qt; IF best dif>O.O THEN BEGIN x~-m[best_j]; END: END order: FOR j : ·best_j+1 STEP 1 UNTIL n DO m[j-1]:-m[j]; m[ n]:-x: END method_ordering: