Notation next up previous
Next: Flaw Selection Strategies Up: Background Previous: Node and Flaw Selection  


The flaw selection strategies that have been discussed in the literature typically have been given idiosyncratic names (e.g., DUnf, LCFR, ZLIFO). It is useful, in comparing them, to have a precise unifying notation. We therefore specify a flaw strategy as a sequence of preferences. A strategy begins by attempting to find a flaw that satisfies its first preference; if it is unable to do so, it then looks for a flaw that satisfies the second preference; and so on. To ensure that a POCL algorithm using the strategy is complete, the sequence of preferences must be exhaustive: every flaw must satisfy some preference. If a flaw satisfies more than one preference in a strategy, we assume that the first match is what counts.

In principle, a preference could identify any feature of a flaw. In practice, however, flaw selection strategies have only made use of a small number of features: the type of a flaw (open condition, nonseparable threat, or separable threat), the number of ways it can be repaired, and the time at which it was introduced into the plan. Often, more than one flaw will have a given feature, in which case a tie-breaking strategy may be specified for choosing among the relevant flaws.

We therefore describe a preference using the following notation

{flaw types}repair cost rangetie-breaking strategy

which indicates a preference for any flaw f of the specified type or types, provided that the repair cost for f falls within the range of values specified. (If there are no restrictions on repair cost, we omit the repair cost range.) If more than one flaw meets these criteria, then the tie-breaking strategy is applied to select among them.

We abbreviate flaw type as ``o'' (for open condition), ``n'' (for nonseparable threat), and ``s'' (for separable threat). We also use abbreviations for common tie-breaking strategies, e.g., ``LC'' (least (repair) cost), ``LIFO'' and ``R'' (Random). In the case of LC, if a choice must be made between flaws that have the same repair cost, LIFO selection is used.

Thus, for example


specifies a preference for nonseparable threats with a repair cost of zero or one; if more than one flaw meets these conditions, a random selection will be made among them. We use the term forced to describe flaws with repair cost of one or less.

An example of a complete flaw selection strategy is then:

{n}0-1R / {o}LIFO / {n,s}R

This strategy would begin by looking for a forced nonseparable threat; if more than one flaw meets this criterion, the strategy would select randomly among them. If there are no forced nonseparable threats, it would then look for an open condition, with any repair cost, using a LIFO scheme to select among them. Finally, if there are neither forced nonseparable threats nor open conditions, it would randomly select either an unforced nonseparable threat or a separable threat.

While we have distinguished between flaw type and maximum repair cost, on the one hand, and tie-breaking strategy, on the other, it is easy to describe strategies that use something other than flaw type as the main criterion for selection. For example, a pure LIFO selection strategy would be encoded as follows. (Henceforth, we give the name of a strategy in boldface preceding the specification.)

LIFO {o,n,s}LIFO

next up previous
Next: Flaw Selection Strategies Up: Background Previous: Node and Flaw Selection

TOM Conversion
Wed Jun 25 17:40:58 EDT 1997