
## Maximally Robust Plan Generation (Rg∗): Given A

problem Pe, generate the maximally robust plan π
∗.

Generating Plan with Desired Level of Robustness (RGρ):
Given a problem Pe and a robustness threshold ρ
(0 < ρ ≤ 1), generate a plan π with robustness greater than or equal to ρ.

Cost-sensitive Robust Plan Generation (RG∗
c
): Given a problem Pe and a cost bound c, generate a plan π of maximal robustness subject to cost bound c (where the cost of a plan π is defined as the cumulative costs of the actions in π).

Incremental Robustification (RIc): Given a plan π for the problem Pe, improve the robustness of π, subject to a cost budget c.

The problem of assessing robustness of plans, RA, can be tackled by compiling it into a weighted model-counting problem. For plan synthesis problems, we can talk about either generating a maximally robust plan, RG∗, or finding a plan with a robustness value above the given threshold, RGρ.

A related issue is that of the interaction between plan cost and robustness. Often, increasing robustness involves using additional (or costlier) actions to support the desired goals, and thus comes at the expense of increased plan cost. We can also talk about cost-constrained robust plan generation problem RG∗
c
. Finally, in practice, we are often interested in increasing the robustness of a given plan (either during iterative search, or during mixed-initiative planning). We thus also have the incremental variant RIc.

In this paper, we will focus on RGρ, the problem of synthesizing plan with at least a robustness value of ρ.

## 5. Compilation To Conformant Probabilistic Planning

In this section, we will show that the problem of generating plan with at least ρ robustness, RGρ, can be compiled into an equivalent conformant probabilistic planning problem. The most robust plan can then be found with a sequence of increasing threshold values.

## 5.1 Conformant Probabilistic Planning

Following the formalism in
(Domshlak and Hoffmann 2007), a domain in conformant probabilistic planning (CPP) is a tuple D′ = hF
′, A′i, where F
′and A′are the sets of propositions and probabilistic actions, respectively. A belief state b : 2F
′ → [0, 1]
is a distribution of states s ⊆ F
′(we denote s ∈ b if b(s) > 0). Each action a
′ ∈ A′is specified by a set of preconditions **P re**(a
′) ⊆ F
′and conditional effects E(a
′).

For each e = (**cons**(e), O(e)) ∈ E(a
′), **cons**(e) ⊆ F
′
is the condition set and O(e) determines the set of outcomes ε = (P r(ε), add(ε)**, del**(ε)) that will add and delete proposition sets add(ε), del(ε) into and from the resulting state with the probability P r(ε) (0 ≤ P r(ε) ≤ 1
,
Pε∈O(e) P r(ε) = 1). All condition sets of the effects in E(a
′) are assumed to be mutually exclusive and exhaustive.

The action a
′is applicable in a belief state b if **P re**(a
′) ⊆ s for all s ∈ b, and the probability of a state s
′in the resulting belief state is ba′ (s
′) = Ps⊇**P re**(a′)
b(s)
Pε∈O′(e) P r(ε),
where e ∈ E(a
′) is the conditional effect such that cons(e) ⊆ s, and O′(e) ⊆ O(e) is the set of outcomes ε such that s
′ = s ∪ add(ε) \ del(ε).

Given the domain D′, a problem P
′is a quadruple P
′ =
hD′, bI , G′, ρ′i, where bI is an initial belief state, G′is a set of goal propositions and ρ
′is the acceptable goal satisfaction probability. A sequence of actions π
′ = (a
′
1
, ..., a′n
) is a solution plan for P
′if a
′ i is applicable in the belief state bi
(assuming b1 ≡ bI ), which results in bi+1 (1 ≤ i ≤ n), and it achieves all goal propositions with at least ρ
′ probability.

## 5.2 Compilation

Given an incomplete domain model De = h**F, A**i and a planning problem Pe = hDe**, I, G**i, we now describe a compilation that translates the problem of synthesizing a solution plan π for Pe such that R(π,Pe) ≥ ρ to a CPP problem P
′. At a high level, the realization of possible preconditions p ∈ **P re** g(a) and effects q ∈ Add g(a), r ∈ Del g(a)
of an action a ∈ A can be understood as being determined by the truth values of *hidden* propositions p pre a, q add aand r del athat are certain (i.e. unchanged in any world state) but unknown. Specifically, the applicability of the action in a state s ⊆ F depends on possible preconditions p that are realized (i.e. p pre a = T), and their truth values in s. Similarly, the values of q and r are affected by a in the resulting state only if they are realized as add and delete effects of the action (i.e., q add a = T, r del a = T). There are totally 2 |P re g(a)|+|Add g(a)|+|Del g(a)|realizations of the action a, and all of them should be considered simultaneously in checking the applicability of the action and in defining corresponding resulting states.

With those observations, we use multiple conditional effects to compile away incomplete knowledge on preconditions and effects of the action a. Each conditional effect corresponds to one realization of the action, and can be fired only if p = T whenever p pre a = T, and adding (removing)
an effect q (r) into (from) the resulting state depending on the values of q add a(r del a, respectively) in the realization.

While the partial knowledge can be removed, the hidden propositions introduce uncertainty into the initial state, and therefore making it a *belief* state. Since the action a may be applicable in some but rarely all states of a belief state, certain preconditions **P re**(a) should be modeled as conditions of all conditional effects. We are now ready to formally specify the resulting domain D′and problem P
′.

For each action a ∈ A, we introduce new propositions p pre a, q add a, r del aand their negations nppre a, nqadd a, nrdel afor each p ∈ P re g(a), q ∈ Add g(a) and r ∈ Del g(a) to determine whether they are realized as preconditions and effects of a in the real domain.2 Let Fnew be the set of those new propositions, then F
′ = F ∪ Fnew is the proposition set of D′.

2These propositions are introduced once, and re-used for all actions sharing the same schema with a.