Notation for Specifying Flaw Selection Strategies

In order to better understand the differences between various flaw selection strategies, and to simplify comparative studies, Pollack et al. (1997) proposed a unifying notation for specifying flaw selection strategies. We adopt their notation with only slight modifications.

A flaw selection strategy is an ordered list of selection criteria. Each selection criterion is of the form

{flaw types}_{$\leq$ max refinements}ordering criterion,

and applies to flaws of the given types that can be resolved in at most max refinements ways. If there is no limit on the number of refinements, we simply write

{flaw types}ordering criterion.

The ordering criterion is used to order flaws that the selection criterion applies to. LIFO order is used if the ordering criterion cannot be used to distinguish two or more flaws.

Pollack et al. define the flaw types ``o'' (open condition), ``n'' (non-separable threat), and ``s'' (separable threat). They also define the ordering criteria ``LIFO'', ``FIFO'', ``R'' (random), ``LR''<sup>3</sup> (least refinements first), and ``New''. The last one applies only to open conditions, and gives preference to open conditions that can be resolved by adding a new action. The rest apply to both open conditions and threats.

Flaws are matched with selection criteria, and it is required for completeness that every flaw matches at least one selection criterion in a flaw selection strategy. The flaw that matches the earliest selection criterion, and is ordered before any other flaws matching the same criterion (according to the ordering criterion), is the flaw that gets selected by the flaw selection strategy. Note that we do not always need to test all flaws. If, for example, the first selection criterion is {n, s}LIFO, and we have found a threat, then we do not need to consider any other flaws for selection.

Using this notation, we can specify many different flaw selection strategies in a concise manner. Table 3 specifies the flaw selection strategies mentioned earlier. A summary of flaw types recognized by VHPOP, including three new flaw types defined below, is given in Table 4.

Table 3: A few of the flaw selection strategies previously proposed in the planning literature.

Name	Specification
UCPOP	{n, s}LIFO  /  {o}LIFO
DSep	{n}LIFO  /  {o}LIFO  /  {s}LIFO
DUnf	{n, s}$\leq$ 0LIFO  /  {n, s}$\leq$ 1LIFO  /  {o}LIFO  /  {n, s}LIFO
LCFR	{n, s, o}LR
LCFR-DSep	{n, o}LR  /  {s}LR
ZLIFO	{n}LIFO  /  {o}$\leq$ 0LIFO  /  {o}$\leq$ 1New  /  {o}LIFO  /  {s}LIFO

Table 4: Summary of flaw types recognized by VHPOP.

Flaw Type	Description
n	non-separable threat
s	separable threat
o	open condition
t	static open condition
l	local open condition
u	unsafe open condition