# Phase Transitions of Contingent Planning Problem

Authors: Junping Zhou; Weihua Su; Zhiqiang Ma; Minghao Yin
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper explores the phase transitions of the contingent planning
problems. We present CONTINGENT PLAN-EXISTENCE algorithm and CONTINGENT
PLAN-NONEXISTENCE algorithm for quickly proving that the contingent
planning instances have solutions and have no solutions, respectively. By
analyzing the two algorithms, the phase transition area of the contingent planning
problems is obtained. If the number of the actions is not greater thanθub, the CONTINGENT PLAN-NONEXISTENCE algorithm can prove that nearly
all the contingent planning instances have no solution. If the number of the actions
is not lower than θlb, the CONTINGENT PLAN-EXISTENCE algorithm can
prove that nearly all the contingent planning instances have solutions. The results
of the experiments show that there exist phase transitions from a region where
almost all the contingent planning instances have no solution to a region where
almost all the contingent planning instances have solutions.


---

## Body

## 1. Introduction

There are many artificial intelligence (AI) problems that have been shown to be inherently intractable. For example, the propositional satisfiability problem, ork-SAT problem for short, is a prototypical NP-complete problem [1], which means that k-SAT problem cannot be solved in polynomial time if P≠NP. It is significant to investigate the phase transitions of the intractable problems. That is because by working on it the researchers cannot only analyze the structure of intractable problems, but also understand the average-case performance of the solvers that solve these AI problems.In recent years, much attention has been given to the phase transitions of the randomk-SAT problems [2–8]. The researchers found that the phase transitions of the random k-SAT problems did exist, where instances changed from being almost all satisfiable to being almost all unsatisfiable, and the hard instances only occurred in the phase transition area. The same phenomena were also observed for some other NP-complete problems, such as the traveling salesman problems [9], the constraint satisfaction problems [10], and the Max-SAT problems [11]. Some other researchers made tremendous progress towards the phase transitions of the artificial planning problems, for instance, STRIPS planning problems [12], conformant planning problems [13], and plan modification of the conformant planning problems [14]. In consequence, one interesting question was put forward whether there were phase transitions in other artificial planning problems.The aim of this paper is to explore the phase transitions of the contingent planning problems. In order to investigate the phenomena, CONTINGENT PLAN-EXISTENCE algorithm and CONTINGENT PLAN-NONEXISTENCE algorithm are presented. The phase transition point of the contingent planning problems is obtained by providing probabilistic analyses of the CONTINGENT PLAN-EXISTENCE algorithm and the CONTINGENT PLAN-NONEXISTENCE algorithm. The results of the experiments show that the empirical results match the phase transitions from the theoretic analyses.


## 2. Background

### 2.1. Definitions and Notations

This section describes some notations about contingent planning problem relevant to our work. Further details, such as the exclusive actions and the consistent actions, can be found in [15–19].Definition 1 (contingent planning problem).
A contingent planning problem is a 5-tupleP=〈S,A,O,I,G〉 with the following components:(i)
Sis a finite set of states and the subset of S is called belief state;(ii)
A is a finite set of actions. An action is a pair 〈pre,eff〉, respectively, called preconditions and effects. Effects are a triple 〈cond,del,add〉, where cond is the effect conditions, del is the deleting effects and add is the adding effects;(iii)
O is a finite set of observations;(iv)
I⊆S is a set of states over S, which is called the initial belief state;(v)
G≠⊘ is the goal, which is actually a partial state composed of the goal conditions.More specifically, contingent planning problem is the task of generating a conditional plan given uncertainty about the initial state and action effects, but with the ability to observe some aspects of the current state [20]. In this paper we only focus on the contingent planning problem with uncertainty about the initial state and determinacy about the actions effects, but with the ability to sense the current state.Definition 2 (action applicability).
LetBs be a belief state. The action a is applicable in Bs if ∀s∈Bs: pre(a)⊆s.If the preconditions of an action are satisfied by all states of the belief state, then the action can be applicable. On the contrary, if the preconditions of an action are not satisfied, the action cannot be carried out, which means that the belief state is changeless. The resulting belief state by executing an action is determined by the adding effects and the deleting effects.Definition 3 (observation function).
LetO be a finite set of observations and Bs an arbitrary belief state. The observation function over Bs and O is a function φ:Bs→2O∖∅ such that ∀s∈Bs:φ(s)⊆O.In the following, we will useφ-(o) to denote the set of states that are compatible with the observation o; φ-(o-) to denote the set of states that are compatible with other observations rather than o.Definition 4 (conditional plan).
The set of conditional plansΠ is the minimal set such that(i)
∅∈Π;(ii)
for an actiona, if a∈A and π∈Π, then a∘π∈Π;(iii)
ifo∈O and π1,π2∈Π, then if o then π1 else π2∈Π.Definition 5 (contingent plan).
Given a contingent planning problemP=〈S,A,O,I,G〉, a contingent plan or solution is a conditional plan π to the problem P if and only if(i)
π is applicable in the initial belief state I;(ii)
every run ofπ from the initial belief state I ends in G.A random contingent planning model, called variable model, is used to carry out an investigation on the phase transitions, which we will address in the following.Definition 6 (variable model).
A variable modelMv is a 5-tuple 〈S,A,O,I,G〉, where(i)
S is a finite set of states and every state is made up of some propositions;(ii)
A is a finite set of actions. For ∀a1,a2∈A, Num(pre(a1))=Num(pre(a2)) and Num(eff(a1))=Num(eff(a2)), where Num(pre(a1)) and Num(pre(a2)) are the numbers of preconditions of a1 and a2 respectively, Num(eff(a1)) and Num(eff(a2)) are the numbers of postconditions of a1 and a2, respectively;(iii)
O is a finite set of observations;(iv)
I⊆S is a set of initial states over S, which is also called the initial belief state;(v)
G≠⊘ is the goal, which is actually a partial state composed of the goal conditions.


### 2.2. The Fundamental Analysis of the Variable Model

In this section, we present the distributions of instances under the variable model. Before addressing the analysis of the variable model, two assumptions of the random contingent planning instances generated in this paper are provided. The first one is that each precondition of an action is selected independently of other precondition and postcondition. Similar rule is hold for the postconditions. The second one is that each action has a fixed number of preconditions. And the number of postconditions also agrees with the rule.Because of the assumptions that each precondition (or postcondition) of an action is selected independently of other preconditions and postconditions, and the precondition or the postcondition is either a proposition or its negation, the random contingent planning instances under the variable model are distributed as follows.Givenn propositions, m actions, r preconditions, c postconditions, and g goal conditions, for a random proposition p and an action a, p is a precondition of the action with the probability r/(2n); alternatively ¬p is a precondition with the probability r/(2n). And c/(2n) is the probability for postconditions.Because the initial state of the contingent planning problem is partially known, there exists a set of initial states, where the number of the initial states isk in this paper. Every initial state is made up of conditions, each of which is selected at random from the 2n conditions since there are n propositions. For the goal conditions, the g goal conditions are also selected at random from the 2n conditions.Furthermore, in the rest of paper, three inequalities are also used to analyze the phase transitions. The detailed proofs can be found in [21]
(1)e-x/(1-x)≤1-x,x∈[0,1)(2)1-x≤e-x(3)xy1+xy≤1-(1-x)y,x∈[0,1).Actually, the following analyses for the phase transitions of the contingent planning problems are based on the fundamental analysis of the variable model. Because it is very simple to solve the sort of contingent planning problems that the goal conditions are satisfied when there is not any actions, in this paper we only deal with the sort of contingent planning problems that the goal conditions are not satisfied by the initial belief state.


## 2.1. Definitions and Notations

This section describes some notations about contingent planning problem relevant to our work. Further details, such as the exclusive actions and the consistent actions, can be found in [15–19].Definition 1 (contingent planning problem).
A contingent planning problem is a 5-tupleP=〈S,A,O,I,G〉 with the following components:(i)
Sis a finite set of states and the subset of S is called belief state;(ii)
A is a finite set of actions. An action is a pair 〈pre,eff〉, respectively, called preconditions and effects. Effects are a triple 〈cond,del,add〉, where cond is the effect conditions, del is the deleting effects and add is the adding effects;(iii)
O is a finite set of observations;(iv)
I⊆S is a set of states over S, which is called the initial belief state;(v)
G≠⊘ is the goal, which is actually a partial state composed of the goal conditions.More specifically, contingent planning problem is the task of generating a conditional plan given uncertainty about the initial state and action effects, but with the ability to observe some aspects of the current state [20]. In this paper we only focus on the contingent planning problem with uncertainty about the initial state and determinacy about the actions effects, but with the ability to sense the current state.Definition 2 (action applicability).
LetBs be a belief state. The action a is applicable in Bs if ∀s∈Bs: pre(a)⊆s.If the preconditions of an action are satisfied by all states of the belief state, then the action can be applicable. On the contrary, if the preconditions of an action are not satisfied, the action cannot be carried out, which means that the belief state is changeless. The resulting belief state by executing an action is determined by the adding effects and the deleting effects.Definition 3 (observation function).
LetO be a finite set of observations and Bs an arbitrary belief state. The observation function over Bs and O is a function φ:Bs→2O∖∅ such that ∀s∈Bs:φ(s)⊆O.In the following, we will useφ-(o) to denote the set of states that are compatible with the observation o; φ-(o-) to denote the set of states that are compatible with other observations rather than o.Definition 4 (conditional plan).
The set of conditional plansΠ is the minimal set such that(i)
∅∈Π;(ii)
for an actiona, if a∈A and π∈Π, then a∘π∈Π;(iii)
ifo∈O and π1,π2∈Π, then if o then π1 else π2∈Π.Definition 5 (contingent plan).
Given a contingent planning problemP=〈S,A,O,I,G〉, a contingent plan or solution is a conditional plan π to the problem P if and only if(i)
π is applicable in the initial belief state I;(ii)
every run ofπ from the initial belief state I ends in G.A random contingent planning model, called variable model, is used to carry out an investigation on the phase transitions, which we will address in the following.Definition 6 (variable model).
A variable modelMv is a 5-tuple 〈S,A,O,I,G〉, where(i)
S is a finite set of states and every state is made up of some propositions;(ii)
A is a finite set of actions. For ∀a1,a2∈A, Num(pre(a1))=Num(pre(a2)) and Num(eff(a1))=Num(eff(a2)), where Num(pre(a1)) and Num(pre(a2)) are the numbers of preconditions of a1 and a2 respectively, Num(eff(a1)) and Num(eff(a2)) are the numbers of postconditions of a1 and a2, respectively;(iii)
O is a finite set of observations;(iv)
I⊆S is a set of initial states over S, which is also called the initial belief state;(v)
G≠⊘ is the goal, which is actually a partial state composed of the goal conditions.


## 2.2. The Fundamental Analysis of the Variable Model

In this section, we present the distributions of instances under the variable model. Before addressing the analysis of the variable model, two assumptions of the random contingent planning instances generated in this paper are provided. The first one is that each precondition of an action is selected independently of other precondition and postcondition. Similar rule is hold for the postconditions. The second one is that each action has a fixed number of preconditions. And the number of postconditions also agrees with the rule.Because of the assumptions that each precondition (or postcondition) of an action is selected independently of other preconditions and postconditions, and the precondition or the postcondition is either a proposition or its negation, the random contingent planning instances under the variable model are distributed as follows.Givenn propositions, m actions, r preconditions, c postconditions, and g goal conditions, for a random proposition p and an action a, p is a precondition of the action with the probability r/(2n); alternatively ¬p is a precondition with the probability r/(2n). And c/(2n) is the probability for postconditions.Because the initial state of the contingent planning problem is partially known, there exists a set of initial states, where the number of the initial states isk in this paper. Every initial state is made up of conditions, each of which is selected at random from the 2n conditions since there are n propositions. For the goal conditions, the g goal conditions are also selected at random from the 2n conditions.Furthermore, in the rest of paper, three inequalities are also used to analyze the phase transitions. The detailed proofs can be found in [21]
(1)e-x/(1-x)≤1-x,x∈[0,1)(2)1-x≤e-x(3)xy1+xy≤1-(1-x)y,x∈[0,1).Actually, the following analyses for the phase transitions of the contingent planning problems are based on the fundamental analysis of the variable model. Because it is very simple to solve the sort of contingent planning problems that the goal conditions are satisfied when there is not any actions, in this paper we only deal with the sort of contingent planning problems that the goal conditions are not satisfied by the initial belief state.


## 3. Contingent Plan Nonexistence Algorithm

In this section, we present the CONTINGENT PLAN-NONEXISTENCE algorithm for quickly proving that a contingent planning instance has no solutions. By analyzing the algorithm, the phase transition area is obtained. The framework of the CONTINGENT PLAN-NONEXISTENCE algorithm is presented in Algorithm1.Algorithm 1:Contingent plan-nonexistence algorithm.
Algorithm CONTINGENT PLAN-NONEXITENCE (S,A,O,I,G)
for each  s∈I
if pre(A)⊄s;
then return  failure;
endfor
for each  g∈G
if g⊄eff(A)
then return  failure;
endfor
for each  o∈O
Bs
T
=
I
∩
φ
-
(
o
);
Bs
F
=
I
∩
φ
-
(
o
-
);
for each  s∈BsT
if pre(A)⊂s;
then return don’t know;
endfor
for each s′∈BsF
if
p
r
e
(
A
)
⊂
s
′;
then return don’t know;
endfor
endfor
return  failure;
endThe CONTINGENT PLAN-NONEXISTENCE algorithm firstly considers whether the preconditions of all actions are not in any states in the initial belief state. If a state in the initial belief state does not satisfy the preconditions of all actions, then the instance has no solutions. Then the algorithm checks out whether a goal condition is not a postcondition of any action. If the postconditions of the actions do not cover all the goal conditions, then the instance has no solutions. The algorithm finally applies an observation to split the initial belief state into two belief states and checks out whether the preconditions of all actions are in any state in the two belief states, respectively. If there is a state in one of the belief states that satisfies the preconditions of all actions, then we cannot decide whether the instance has solutions or not. In addition, if there is not a state in all the split belief states that satisfies the preconditions of all actions, the instance has no solutions. For a contingent planning instance with k initial states, m actions, b observations, and g goal conditions, the time complexity of the algorithm is O((k+g+2kb)m). Therefore, the CONTINGENT PLAN-NONEXISTENCE algorithm can decide that the instance has no solutions efficiently.Theorem 7.
The contingent planning instance has no solution if CONTINGENT PLAN-NONEXISTENCE algorithm returnsfailure; the contingent planning instance cannot be determined whether it has solutions if CONTINGENT PLAN-NONEXISTENCE algorithm returns do not know.Proof.
Let us first list the cases that the CONTINGENT PLAN-NONEXISTENCE algorithm returnsfailure. (1) The initial belief state involves a state that does not contain the preconditions of all the actions. As we know, if the preconditions of all the actions are not in the state, any action cannot be executed. Because in this paper we only deal with the sort of contingent planning problems that no goal conditions are satisfied by the initial belief state, a sequence of empty actions cannot be the solution of the instances. Therefore, the contingent planning instances do not have solutions. (2) There is a goal condition that is not an effect of any action, which means that the goal condition cannot be obtained by executing any action. Therefore, the contingent planning instances do not have solutions. (3) There is not a state in all the split belief states that satisfies the preconditions of all actions, which means that any action cannot be executed. Therefore, the contingent planning instances have no solutions. Then let us discuss the case that the CONTINGENT PLAN-NONEXISTENCE algorithm returns do not know. There is a state in one of the belief states that satisfies the preconditions of all actions, which means that at least an action can be executed from the belief state. However, we cannot guarantee that all the goal conditions are satisfied by executing any conditional plan from each state in the initial belief state. Therefore, the contingent planning instance cannot be determined whether it has solutions.
By Theorem7, we know that the CONTINGENT PLAN-NONEXISTENCE algorithm is correct, but it cannot guarantee the completeness. In other words, if a contingent planning instance has solutions, the CONTINGENT PLAN-NONEXISTENCE algorithm could not determine that the instance has solutions. However, we can prove in Theorem 8 that nearly all contingent planning instances have no solutions when σ is small enough (σ is a constant and 0<σ<1).Theorem 8.
For random contingent planning instances under the variable model, if the number of actions satisfies(4)m≤θub,θub=min((1-(1-r/2n)n)(-ln
ln1/σ)(1-r/2n)n,((2n-c)c)(lng-ln
ln1σ)(1-(1-r/2n)n)(-lnln1/σ)(1-r/2n)n),
where n is the number of propositions; m is the number of actions; r and c, respectively, are the expected numbers of preconditions and postconditions within an action; g is the number of goal conditions; k is the number of initial states; σ (0<σ<1) is a constant, then the CONTINGENT PLAN-NONEXISTENCE algorithm proves that no solution exists for at least 1-σ of the instances.Proof.
If we are to prove that the algorithm determines that no solution exists for at least1-σ of the instances, we only need to prove that the probability that every initial state satisfies the preconditions of any action, the probability that a goal condition is not a postcondition of any action, and the probability that every initial state in the belief state BsT (or BsF) satisfies the preconditions of any action are not more than σ. Suppose (4) is true, we have
(5)m≤min((1-(1-r/2n)n)(-ln
ln1/σ)(1-r/2n)n,((2n-c)c)(lng-ln
ln1σ)(1-(1-r/2n)n)(-lnln1/σ)(1-r/2n)n).
Because the initial state of the contingent planning problem is partially known, there exists a set of initial states, where the number of the initial states isk in this paper. Every initial state is made up of conditions, each of which is selected at random from the 2n conditions since there are n propositions. At first, the probability that every initial state satisfies the preconditions of any action is given as follows:(1-r/2n)n: probability that a state satisfies the preconditions of an action;1-(1-r/2n)n: probability that a state does not satisfy the preconditions of an action;(1-(1-r/2n)n)m: probability that a state does not satisfy the preconditions of any action;1-(1-(1-r/2n)n)m: probability that a state satisfies the preconditions of any action;(1-(1-(1-r/2n)n)m)k: probability that every initial state satisfies the preconditions of any action.
Then, the probability that every initial state in the belief stateBsT satisfies the preconditions of any action is given as follows, where the number of the states in BsT (or BsF) is x (1≤x≤k),(1-r/2n)n: probability that a state satisfies the preconditions of an action;1-(1-r/2n)n: probability that a state does not satisfy the preconditions of an action;(1-(1-r/2n)n)m: probability that a state does not satisfy the preconditions of any action;1-(1-(1-r/2n)n)m: probability that a state satisfies the preconditions of any action;(1-(1-(1-r/2n)n)m)x: probability that every initial state in the belief state BsT (or BsF) satisfies the preconditions of any action.
For the goal conditions, theg goal conditions are also selected at random from the 2n conditions. Then, the probability that a goal condition is not a postcondition of any action is as follows:c/2n: probability that the goal condition is a postconditions of the action;1-c/2n: probability that the goal condition is not a postconditions of the action;(1-c/2n)m: probability that the goal condition is not a postconditions of any action;1-(1-c/2n)m: probability that the goal condition is a postconditions of some action;(1-(1-c/2n)m)g: probability that every goal condition is a postconditions of some action.
In the following, we will prove that the probability that every initial state satisfies the preconditions of any action and the probability that every initial state in the belief stateBsT (or BsF) satisfies the preconditions of any action both are not more than σ. Because the probability that every initial state satisfies the preconditions of any action is less than the probability that every initial state in the belief state BsT (or BsF) satisfies the preconditions of any action, we only prove that the probability that every initial state in the belief state BsT (or BsF) satisfies the preconditions of any action is not more than σ.
By (5), we get
(6)m≤(1-(1-r/2n)n)(-ln
ln1/σ)(1-r/2n)n.
This is equivalent to(7)ln(1ln(1/σ))≥m(1-r/2n)n1-(1-r/2n)n,(8)ln(ln(1σ))≤-m(1-r/2n)n1-(1-r/2n)n.
Letx=(1-r/2n)n. By (1), we have
(9)e-(1-r/2n)n/(1-(1-r/2n)n)≤1-(1-r2n)n.
From (8) and (9), we have
(10)ln(ln(1σ))≤mln(1-(1-r2n)n).
This is equivalent to(11)-(1-(1-r2n)n)m≤(lnσ).
Letx=(1-(1-r/2n)n)m. By (2), we have
(12)ln(1-(1-(1-r2n)n)m)≤-(1-(1-r2n)n)m.
From (11) and (12), we have
(13)ln(1-(1-(1-r2n)n)m)≤(lnσ).
Simplify (13), and we get
(14)1-(1-(1-r2n)n)m≤σ.
In addition, for(15)(1-(1-(1-r2n)n)m)x≤1-(1-(1-r2n)n)m;
therefore, we obtain
(16)(1-(1-(1-r2n)n)m)x≤σ.
Thus, if the inequality of the theorem is satisfied, then the probability that every initial state in the belief stateBsT (or BsF) does not satisfy the preconditions of any action and the probability that every initial state satisfies the preconditions of any action are at least 1-σ.
Finally, we prove that the probability that a goal condition is not a postcondition of any action is not more thanσ.
From (5), we get
(17)m≤((2n-c)c)(lng-ln
ln1σ).
This is equivalent to(18)-mc(2n-c)≥ln(ln(1/σ)g).
By (1), we get
(19)-c(2n-c)≤ln(1-c2n).
From (18) and (19), we have
(20)ln(ln(1/σ)g)≤mln(1-c2n).
This is equivalent to(21)-(1-c2n)m≤(lnσ)g.
By (2), we get
(22)ln(1-(1-c2n)m)≤-(1-c2n)m.
From (21) and (22), we have
(23)ln(1-(1-c2n)m)≤(lnσ)g.
Simplify (23), and we get
(24)(1-(1-c2n)m)g≤σ.
Thus, if the inequality of the theorem is satisfied, then the probability that some goal condition is not a postcondition of any action is at least 1-σ.
Therefore, if the inequality of the theorem is satisfied, then the algorithm will determine that no solution exists for at least1-σ of the instances.Theorem8 presents an upper bound of the phase transition. If we can obtain a lower bound, the phase transition area of the contingent planning problems will be acquired. Therefore, in the next section, we will present the CONTINGENT PLAN-EXISTENCE algorithm and discuss the lower bound of the contingent planning problems by analyzing the algorithm.


## 4. Contingent Plan Existence Algorithm

In this section, we present the CONTINGENT PLAN-EXISTENCE algorithm for powerfully determining that a contingent planning instance has solutions. By analyzing the algorithm, the lower bound of the phase transition is obtained. The framework of the CONTINGENT PLAN-EXISTENCE algorithm is presented in Algorithm2.Algorithm 2:Contingent plan-existence algorithm.
Algorithm CONTINGENT PLAN-EXISTENCE (N,Y,Bs,A,O)
f
l
a
g
=
0;
for each  s∈Bs
if N⊄s
then flag=1;
endfor
if flag==0
then return true
for each  a∈A
if applicable(Bs,a) and N∩add(a)≠∅ and Y∩del(a)=∅
then Bs′=Bs+add(a)-del(a);
N
=
N
-
(
N
∩
a
d
d
(
a
)
);
Y
=
Y
+
(
N
∩
a
d
d
(
a
)
);
CONTINGENT PLAN-EXISTENCE(N,Y,Bs′,A,O);
endfor
for each  o∈O
B
s
T
=
B
s
∩
φ
-
(
o
);
B
s
F
=
B
s
∩
φ
-
(
o
-
);
if BsT≠∅ and BsF≠∅
then CONTINGENT PLAN-EXISTENCE (N,Y,BsT,A,O)∧
CONTINGENT PLAN-EXISTENCE(N,Y,BsF,A,O)
endfor
return don’t know
endIn the algorithm,N denotes the set of unsatisfied goal conditions, Y denotes the set of satisfied goal conditions, Bs denotes the considered belief state; add(a) denotes the adding effects of the action a, del(a) denotes the deleting effects of the action a, and applicable (Bs,a) denotes the action a applicable in the belief state Bs. The algorithm firstly initializes N, Y, and Bs, that is, N=G, Y=NULL, and Bs=I. Then it checks whether all states in the considered belief states satisfy the goal. If each state in the considered belief state satisfies the goal, the value of flag will not change, which means that the instance has solutions. Otherwise, the algorithm considers whether an action can be applied to the considered belief state to ensure that the postconditions of the actions satisfy more goal conditions. If there exists such actions, the process is repeated. The algorithm finally checks whether there is an observation that can split the considered belief state into two nonnull belief states. If the observation does exist, the similar process is repeated in the two branches, and the instance has solutions only when the two branches return true. Except the above three cases, the algorithm cannot determine whether the contingent planning instance has solutions.Theorem 9.
The contingent planning instance has solutions if the CONTINGENT PLAN-EXISTENCE algorithm returnstrue; the contingent planning instance cannot be determined whether it has solutions if the CONTINGENT PLAN-EXISTENCE algorithm returns do not know.Proof.
Let us first discuss the case that the CONTINGENT PLAN-EXISTENCE algorithm returnstrue. When all the goal conditions are satisfied by a conditional plan from each state in the initial belief state, we can determine that the instance has solutions. Then we list the cases that the CONTINGENT PLAN-EXISTENCE algorithm returns do not know. (1) The considered belief state has no applicable actions. (2) The number of unsatisfied goal conditions does not decrease by executing all applicable actions. (3) One of branches that the observation splits returns do not know. The above three cases imply that we cannot determine whether the instance has solutions or not.
The CONTINGENT PLAN-EXISTENCE algorithm is correct, but we also cannot guarantee the completeness. In the following, we prove that almost all the contingent planning instances have solutions by analyzing the algorithm whenσ is small enough (σ is a constant and 0<σ<1).Lemma 10.
Consider random planning instances under the variable model expecting thatd of the g goal conditions are not satisfied, if
(25)m≥e(1-(1-r/2n)n)k/(1-(1-(1-r/2n)n)k)ec(g-d)/n×((2ncd)+1)(ln1σ),
where n is the number of propositions; m is the number of actions; r and c, respectively, are the expected numbers of preconditions and postconditions within an action; g is the number of goal conditions; k is the number of initial states; x is the number of states of an arbitrary belief state; σ (0<σ<1) is a constant, then the CONTINGENT PLAN-EXISTENCE algorithm applying some action will increase the number of satisfied goal conditions for at least 1-σ of the instances.Proof.
At first, the probability that some action will increase the number of satisfied goal conditions is given as follows:(1-r/2n)n: probability that a state satisfies the preconditions of an action;1-(1-r/2n)n: probability that a state does not satisfy the preconditions of an action;(1-(1-r/2n)n)x: the least probability that every state in an arbitrary belief state does not satisfy the preconditions of an action;1-(1-(1-r/2n)n)x: probability that every state in the arbitrary belief state satisfies the preconditions of an action;1-(1-(1-r/2n)n)k: the most probability that every state in the arbitrary belief state satisfies the preconditions of an action. Because in this paper we research on the contingent planning problem whose actions have deterministic effects, the belief state during the execution has most k states;(1-c/2n)g-d: probability that the postconditions of an action are consistent with the g-d goal conditions already achieved;1-(1-c/2n)d: probability that the postconditions of an action achieve at least one of d remaining goal conditions.
Thus, the probabilityp that a particular action can be applied will not exclude any satisfied goals and will achieve at least one more goal condition which is
(26)p=(1-(1-(1-r2n)n)k)(1-c2n)g-d(1-(1-c2n)d).1-p is the probability that the action is missing one or more of these properties, and (1-p)m is the probability that m actions are unsatisfactory.
Because(1-p)m≤e-pm≤e-ln(1/σ)=σ, then there will be some satisfactory action with probability at least 1-σ. The inequality is satisfied if m≥(1/p)(ln1/σ).
By (1), we get
(27)1-(1-(1-r2n)n)k≥e-(1-(1-r/2n)n)k/(1-(1-(1-r/2n)n)k)(1-c2n)g-d≥e-c(g-d)/(2n-r)≥e-c(g-d)/n.
By (3), we get
(28)1-(1-c2n)d≥cd2n+cd.
Then, finally,(29)(1p)(ln1σ)=e(1-(1-r/2n)n)k/(1-(1-(1-r/2n)n)k)ec(g-d)/n×((2ncd)+1)(ln1σ).
Thus, if the inequality is satisfied by the number of the actions, the CONTINGENT PLAN-EXISTENCE algorithm applying some action will increase the number of satisfied goal conditions for at least1-σ of the instances.Theorem 11.
Consider random planning instances under the variable model if;(30)m≥θlb,θlb=e1/(1-(1-(1-r/2n)n)k)ecg/n×((2nc)+1)(lngσ),
where n is the number of propositions; m is the number of actions; r and c, respectively, are the expected numbers of preconditions and postconditions within an action; g is the number of goal conditions; k is the number of initial states; σ (0<σ<1) is a constant, the CONTINGENT PLAN-EXISTENCE algorithm will find solutions for at least 1-σ of the instances.Proof.
For a contingent planning instance withg goal conditions, the number of satisfied goal conditions will be increased at most g times. If each increase occurs with probability at least (1-σ)/g, g increase (the most possible) will occur with probability at least 1-σ.
Thus, Lemma10 can be applied using σ/g instead of σ. Maximizing over the g goal conditions leads to
(31)maxd=1ge(1-(1-r/2n)n)k/(1-(1-(1-r/2n)n)k)ec(g-d)/n×((2ncd)+1)(lngσ)≤e1/(1-(1-(1-r/2n)n)k)ecg/n((2nc)+1)(lngσ).
Therefore, if the inequality is satisfied by the number of the actions, the algorithm will find solutions for at least1-σ of the instances.Theorem11 shows that when the number of actions is not lower than θlb, the CONTINGENT PLAN-EXISTENCE algorithm can prove that nearly all the contingent planning instances have solutions.


## 5. Experimental Results

In this section, we take experiments on the contingent planning instances under the variable model in order to investigate the relationship between the densities (ratio of the number of actions to the number of propositions) and the effectiveness of the contingent planning instances. In the experiment, we generate a large collection of instances with three preconditions and two postconditions within an action,2i (i is a constant) initial states, one observation, and two goal conditions. In addition, the propositions are 6, 8, 10, 12, 14, 16, and 18, respectively. All experiments are run on a cluster of 2.4 GHz Intel Xeon machines with 2 GB memory running Linux CentOS 5.4. Figure 1 illustrates the relationship between the densities and the effectiveness of the contingent planning instances. From the results we can see that the effectiveness grows when the density increases and the numbers of propositions and goal conditions are constant. Furthermore, the experiments show that there is a transition from insoluble to soluble instances as the density grows and the transition points drop with the propositions growing.Figure 1
The Relationship between densities and effectiveness of contingent planning problems.


## 6. Conclusions

In this paper, we present analyses for the phase transitions of the contingent planning problems. By analyzing the CONTINGENT PLAN-NONEXISTENCE algorithm and the CONTINGENT PLAN-EXISTENCE algorithm, quantitative results are obtained. If the number of actions is not greater thanθub, the CONTINGENT PLAN-NONEXISTENCE algorithm can prove that almost all the contingent planning instances have no solution; if the number of actions is not lower than θlb, the CONTINGENT PLAN-EXISTENCE algorithm can prove that almost all the contingent planning instances have solutions. The results of the experiments also show that there exist the phase transition phenomena.



---

*Source: 687578-2013-08-24.xml*