
## Appendix A. A Short Review Of Pop, Causal Links And Threats

We represent a plan as a tuple: hA, O,Li, where A is a set of unary operators, O **is a set of**
ordering constraints over A, and L is a set of causal links. For example, if A = {A1, A2, A3}
then O might be the set {A1 < A3, A2 < A3}**. These constraints specify a plan in which**
A3 is necessarily the last operator, but do not commit to a particular order on A1 and A2.

Naturally, the set of ordering constraints must be consistent, i.e., there must exist some total order satisfying them. A causal link has the form Ap →
ϑi Ac, where Ap and Ac are operators and ϑiis a possible value for some propositional variable vi**. It denotes the fact** that Ap produces (i.e., has the postcondition) vi = ϑi which is consumed by Ac **(i.e., used to**
satisfy a pre- or prevail-condition of Ac**). Causal links help us detect whether one operator**
Atinterferes with the work done to enable the execution of some other operator Ac**. In that**
case, Atis said to constitute a threat **to one of** A′c s **causal links. Formally, suppose that**
hA, O,Li **is a plan, and** Ap →
ϑi Ac is a causal link in L. Let At **be a different operator in** A.

We say that At **threatens** Ap →
ϑi Ac **when the following two criteria are satisfied:**
- O ∪ {Ap < At < Ac} **is consistent, and**
- At has ¬ϑi **as an effect.**
When a partial order plan P **contains threats, it is possible that the goal will not be** achieved by some (or all) of the total order plans consistent with P**'s ordering constraints.**
To prevent this, the plan generator must check for threats and remove them by adding one of two possible ordering constraints: At < Ap (demotion) or Ac < At **(promotion).**
A tutorial introduction to POP algorithms can be found in (Weld, 1994). POP is a regressive framework for partial order planning that starts with the null plan and continuously updates it by inserting new actions and removing threats. This process continues until the precondition and the prevail conditions of every operator in the plan are supported by some causal link and no threats exist. The first argument to POP is a plan and the second argument is an agenda of goals that need to be supported by causal links. Each item on the agenda is represented by a pair hϑi, Ai where ϑi**is either pre- or prevail condition of a plan**
action A**. The last argument to POP is the whole collection of the operators defined by**
the planning instance. The initial call to POP contains the null plan, a specially initialized agenda, and the operator set Λ of the given problem.

In this paper we introduce a specialized, deterministic **POP algorithm that starts the**
planning process using a variant of the null plan which encodes the planning problem. In particular, if the planning instance has v
∗
1
, . . . , v∗n **as the goal then the corresponding null**
plan has exactly 2n **dummy unary operators,** A = {A01
, . . . , A0n
, A∗1
, . . . , A∗n}, n **ordering**
constraints, O = {{A01 < A∗1
}, . . . , {A0n < A∗n}}, and no causal links, L = {}**. For every**
vi ∈ V, A0 i is the corresponding "start" operator - it has neither pre- nor prevail conditions, and its effect specifies the value of the variable vi**in the initial state, which is denoted by**
v 0 i
. Similarly, A∗
i is the "end" operator - it has no effect, no prevail conditions, but its precondition is set to the value of vi**in the goal state, which in turn is denoted by** v
∗
i
.

8