a(x1**, ..., x**n) to be dependent on some specific variables xj1**, ..., x**jl *without any knowledge of their restricted values*. This annotation essentially requires less amount of knowledge of the domain incompleteness from the domain writer. Semantically, the possible precondition/effect p(xi1**, ..., x**ik
) : depends (xj1**, ..., x**jl
) of an action schema a(x1**, ..., x**n) means that (1) there is at least one instantiated action a(c1**, ..., c**n) (ci ∈ Xi) having p(ci1**, ..., c**ik
) as its precondition, and (2) for any two assignments (x1 := c1**, ..., x**n := cn),(x1 := c
′
1
, ..., xn :=
c
′ n
) such that cjt = c
′ jt

(1 ≤ t ≤ l), either both p(ci1**, ..., c**ik
) and p(c
′
i1
, ..., c′ik

) are preconditions of the corresponding actions, or they are not. Similar to the
: **when** above, the : **depend** construct also subsumes the annotations at the ground level when l = n, and at the schema level if l = 0 (or the : **depend** field is not specified).

Another interesting modeling issue is the correlation among the possible preconditions and effects across actions. In particular, the domain writer might want to say that two actions (or action schemas) will have specific possible preconditions and effects in tandem. For example, we might say that the second action will have a particular possible precondition whenever the first one has a particular possible effect. We note that annotations at the lifted level introduce correlations among possible preconditions and effects at the ground level.

Although our notion of plan robustness and approach to generating robust plans (see below) can be adapted to allow such flexible annotations and correlated incompleteness, for ease of exposition we limit our discussion to *uncorrelated* possible precondition and effect annotations specified at the schema level (i.e. without using the : **when** and : **depend**
constructs).

## 4. A Robustness Measure For Plans

Given an incomplete domain planning problem Pe =
hDe**, I, G**i, a valid plan (by our definition above) need only to succeed in at least one completion of De. Given that **hhDii** e can be exponentially large in terms of possible preconditions and effects, validity is too weak to guarantee on the quality of the plan. What we need is a notion that π succeeds in most of the highly likely completions of De. We do this in terms of a robustness measure.

The robustness of a plan π for the problem Pe is defined as the cumulative probability mass of the completions of De under which π succeeds (in achieving the goals). More formally, let Pr(Di) be the probability distribution representing the modeler's estimate of the probability that a given model in P
hhDii e is the real model of the world (such that Di**∈hhDii** e Pr(Di) = 1). The robustness of π is defined as follows:

$$R(\pi,\widetilde{\mathcal{P}}:\langle\widetilde{\mathcal{D}},I,G\rangle)\stackrel{{def}}{{=}}\sum_{\mathcal{D}_{i}\in\langle\langle\widetilde{\mathcal{D}}\rangle\rangle,\gamma(\pi,I,\mathcal{D}_{i})\models G}\mathbf{Pr}(\mathcal{D}_{i})\tag{2}$$

It is easy to see that if R(π,Pe) > 0, then π is a valid plan for Pe.

Figure 1: An example of different complete domain models,

![0_image_0.png](0_image_0.png) and the corresponding plan status. Circles with solid and dash boundary are propositions that are known to be T and may be F (respectively) when the plan executes. (See text.)
Note that given the uncorrelated incompleteness assumption, the probability Pr(Di) for a model Di **∈ hhDii** e can be computed as the product of the weights w pre a(p), w add a(p),
and w del a(p) for all a ∈ A and its possible preconditions/effects p if p is realized in the model (or the product of their "complement" 1 − w pre a(p), 1 − w add a(p), and 1 − w del a(p) if p is not realized).

Example: Figure 1 shows an example with an incomplete domain model De = h**F, A**i with F = {p1, p2, p3} and A = {a1, a2} and a solution plan π = (a1, a2) for the problem Pe = hDe, I = {p2}, G = {p3}i. The incomplete model is: **P re**(a1) = ∅, **P re** g(a1) = {p1}, Add(a1) = {p2, p3},
Add g(a1) = ∅, Del(a1) = ∅, Del g(a1) = ∅; **P re**(a2) =
{p2}, **P re** g(a2) = ∅, Add(a2) = ∅, Add g(a2) = {p3},
Del(a2) = ∅, Del g(a2) = {p1}. Given that the total number of possible preconditions and effects is 3, the total number of completions (**|hhDii|** e ) is 2 3 = 8, for each of which the plan π may succeed or fail to achieve G, as shown in the table.

The robustness value of the plan is R(π) = 34 if Pr(Di)
is the uniform distribution. However, if the domain writer thinks that p1 is very likely to be a precondition of a1 and provides w pre a1
(p1) = 0.9, the robustness of π decreases to R(π) = 2×(0.9×0.5×0.5)+ 4×(0.1×0.5×0.5) = 0.55
(as intutively, the last four models with which π succeeds are very unlikely to be the real one). Note that under the STRIPS model where action failure causes plan failure, the plan π would considered failing to achieve G in the first two complete models, since a2 is prevented from execution.

## 4.1 A Spectrum Of Robust Planning Problems

Given this set up, we can now talk about a spectrum of problems related to planning under incomplete domain models:
Robustness Assessment (RA): Given a plan π for the problem Pe, assess the robustness of π.