Algorithm 1 **Generic POCL planning algorithm as formulated by Williamson and Hanks**
(1996).

Find-Plan(I, G)
P ⇐ {Make-Initial-Plan(I, G)}
while P 6= ∅ do π ⇐ some element of P ✄ **plan selection**
P ⇐ P \ {π}
if F(π) = ∅ **then**
return π else f ⇐ some element of F(π) ✄ **flaw selection**
P ⇐ P ∪ Refinements(π, f)
return **failure (problem lacks solution)**
An open condition, q
−→ ai, can be resolved by linking q **to the effect of an existing or**
new action. An unsafe link, aiq
−→aj threatened by the effect p of action ak**, can be resolved**
by either ordering ak before ai (demotion), or by ordering ak after aj (promotion**). If we**
use lifted actions instead of ground actions, a threat can also be resolved by adding binding constraints so that p and ¬q cannot be unified (**separation**).

## 3. Search Control

In the search for a complete plan, we first select a plan to work **on, and given a plan we**
select a flaw to repair. These two choice points are indicated **in Algorithm 1. Making**
an informed choice in both these cases is essential for good planner performance, and the following is a presentation of how these choices are made in VHPOP.

## 3.1 Plan Selection Heuristic

VHPOP uses the A∗ **algorithm (Hart, Nilsson, & Raphael, 1968) to search through plan**
space. The A∗ algorithm requires a search node evaluation function f(n) = g(n) + h(n),
where g(n) is the cost of getting to n from the start node (initial plan) and h(n**) is the** estimated remaining cost of reaching a goal node (complete plan). We want to find plans containing few actions, so we take the cost of a plan to be the number of actions in it. For a plan π = hA,L, O,Bi we therefore have g(π) = |A|.

The original implementations of SNLP and UCPOP used hf(π) = |F(π)| as the heuristic cost function, i.e. the number of flaws in a plan. Schubert **and Gerevini (1995) consider**
alternatives for hf(π), and present empirical data showing that just counting the open conditions (hoc(π) = |OC(π)|**) often gives better results. A big problem, however, with using**
the number of open conditions as an estimate of the number of actions that needs to be added is that it assumes a uniform cost per open condition. It **ignores the fact that some**
open conditions can be linked to existing actions (thus requiring no additional actions), while other open conditions can be resolved only by adding a whole chain of actions (thus requiring more than one action).