Notation

** Next:** Flaw Selection Strategies
**Up:** Background
** Previous:** Node and Flaw Selection

## Notation

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 range}tie-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-1}R / {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.)

** Next:** Flaw Selection Strategies
**Up:** Background
** Previous:** Node and Flaw Selection
*TOM Conversion *

Wed Jun 25 17:40:58 EDT 1997