A Counter-Example Based Approach to Probabilistic Conformant Planning

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 01:06:16

Abstract: This paper introduces a counter-example based approach for solving probabilistic conformant planning (PCP) problems. Our algorithm incrementally generates candidate plans and identifies counter-examples until it finds a plan for which the probability of success is above the specified threshold. We prove that the algorithm is sound and complete. We further propose a variation of our algorithm that uses hitting sets to accelerate the generation of candidate plans. Experimental results show that our planner is particularly suited for problems with a high probability threshold.

Main paper: 
 introduction: 
 Probabilistic conformant planning (PCP) (Domshlak and Hoffmann 2006, 2007 ) is a planning problem in which an agent without observations is tasked to reach the goal with a certain probability guarantee. Because the agent does not have access to observations, the solution to a PCP problem is a sequence of actions. There is uncertainty about the initial state, given by a discrete initial state distribution and uncertainty in the effects of actions; in this paper, we focus on PCP with unknown initial states.PCP is a generalisation of conformant planning (CP) (Smith and Weld 1998) that assumes that the plan should succeed with probability 1. This assumption often means that CP plans are overly conservative in order to account for all unlikely situations: there may be no solutions within the horizon (maximum number of actions that we want to allow). Solutions to PCPs for similar domains are often shorter as they are allowed to (selectively) ignore unlikely contingencies. This is similar to the chance-constraints (Birge and Louveaux 2011) .Consider the scenario in Figure 1 , where a blind robot wants to reach the destination (x 2 , y 2 ) without prior knowledge of its initial position. Probability distributions to his initial positions are given as follows: {(x 1 , .2), (x 2 , .7), (x 3 , .1)} for the x-coordinate, and {(y 1 , .2), (y 2 , .7), (y 3 , .1)} for the y-coordinate. Since x and y are independent, we can compute the probability of each initial position by simple multiplication. For example, the probability that the robot starts in (x 1 , y 2 ) is .2 × .7 = .14. At each step, the robot can choose to move left (L), right (R), up (U), or down (D). The grid is surrounded by walls to prevent the robot from moving outside. If the robot hits Gy 3 , .1 → y 2 , .7 → y 1 , .2 → x 1 , .2 ↓x 2 , .7 ↓x 3 , .1 ↓ Figure 1 : Graphical representation of the GRID problem. The initial location of the robot is unknown with its initial vertical and horizontal locations indicated by the probabilities labeling rows and columns, respectively (e.g., the probability of starting in (x 1 , y 2 ) is .2 * .7 = .14). The arrows indicate the possible moves in each state. The goal is to reach the center location with probability .75.the wall, it will not move but just stand still. We assume that moving left and right is eligible only when the robot is on row y 1 . What sequence of moves will make the robot arrive at (x 2 , y 2 ) that ensures the combined probability of satisfied initial positions at least being .75? A valid plan for this example is U L R D. This plan works since if the robot initially stands at any location both in the two top-most rows and the two left-most columns, it will eventually reach (x 2 , y 2 ), and the probability of these satisfied initial positions is .81.In principle, PCP problems can be solved by tracking the belief states (probability function over the current state) over all executions up to the length of the planning horizon, and determining whether a goal state was reached with expected probability. In practice, relatively efficient algorithms have been developed that do not exhaustively expand all possible eventualities in the above sense. POND (Bryce, Kambhampati, and Smith 2006) placed in an international planning competition, and implemented a PCP procedure. Its approach involves the application of heuristic search techniques and planning graph heuristics initially developed for non-deterministic planning. POND further uses Sequential Monte Carlo to generate a set of samples (particles) that represent the distribution over reachable relaxed planning graph layers, and the probability that a particle takes on a particular value is proportional to the probability of that value in the true distribution. The performance of POND is more affected by the number of states, not the complexity of the problem. Probabilistic-FF (Domshlak and Hoffmann 2006, 2007 ) is another state-of-the-art planner. This algorithm integrates Conformant-FF's techniques with weighted model counting in (weighted) CNFs to define both the search space and the heuristic function. In particular, Probabilistic-FF extends Conformant-FF belief state formula to construct Bayesian networks, uses weighted model-counting to determine the probability of goals in a belief state, and adapts the heuristic function of Conformant-FF to the probabilistic setting. However, Probabilistic-FF faces challenges in determining the optimal frequency of applying specific actions early in the plan for achieving high confidence in goal attainment. Additionally, the heuristic function of Probabilistic-FF yield bad estimates in some problems.In 2006, Huang (2006) proposed an innovative algorithm that combines knowledge compilation and search for PCP. The algorithm encodes the PCP problem into a propositional formula, where a subset of propositional variables (chance variables) is assigned probabilities. Subsequently, it compiles these formulas into a Deterministic Decomposable Negation Normal Form (d-DNNF, introduced in Section 4.1), which can be used to compute the satisfied probability of a plan. The algorithm computes the upper bounds on the success probability at each node of the search tree, or for each partial plan generated during search, enabling the pruning of a depth-first search for optimal plans. Some other PCP are also outstanding. For example, Hyafil and Bacchus (2003) encode the problem by Constraint Satisfaction Problem (CSP) to search a plan; Taig and Brafman (2013) translate PCP problem to classical planning problem and the translation approach is built upon the techniques of Palacios and Geffner (2009) ; Taig and Brafman (2014) designed another approach in 2014, solving the problem by relevance-based compilation method.Grastien and Scala (2020) introduced a counter-example based approach CPCES, for solving CP problems. CPCES starts with an empty counter-example set (sample) and an empty candidate plan π. It then iteratively follows two steps: First, it uses a SAT solver to search for a counter-example (initial state) ce that invalidates the current π, adding ce to the sample; Second, it treanslates the CP problem into a classical planning problem using a multi-interpretation and uses a classical planner to determine a new candidate plan π. The updated π agrees with all the initial states in the sample. CPCES repeats these two steps until either no counterexample can be found, which indicates that the last candidate plan is a valid solution for the CP problem, or no candidate plan can be found, which means there is no solution to the CP problem.Inspired from CPCES (Grastien and Scala 2020 ) and Huang's algorithm (Huang 2006) , our approach involves encoding the problem using a propositional formula and us-ing a deterministic DNNF to assess the probability of a set of counter-tags (defined in Section 3) to a candidate plan. Our algorithm then translates the PCP problem to a classical problem by using counter-tags and uses classical planner to find a plan.This paper is structured as follows: we begin by providing the background of this paper. Then we introduce a counterexample based approach to solving PCP problems. Following that, we detail the process of computing a set of countertags and the candidate plan corresponding to these countertags. Additionally, we discuss the improvements made to our approach by applying hitting set. Finally, we present the experimental results and conduct an analysis. 
problem and background definitions: 
 Given a propositional formula φ, we write vars(φ) the set of propositional variables in φ. Every formula is understood as a conjunction ϕ = ϕ i ; it may consist of a single conjunct or even none.A PCP problem is a tuple P = ⟨F, A, I, G, τ ⟩. F is a set of Boolean facts. A state s ⊆ F is a subset of true facts; this state is also understood as the conjunction f ∈s f ∧ f ∈F \s ¬f and as the assignment s[f ] = True iff f ∈ s.A is a set of actions, where each action a ∈ A is a tuple ⟨name(a), pre(a), coneff (a)⟩. Here, name(a) is the unique action name, pre(a) is a propositional formula over F called the precondition.A precondition is trivial if it is true. coneff (a) = {⟨con 1 , eff + 1 , eff - 1 ⟩, . . . , ⟨con k , eff + k , eff - k ⟩} is a set of conditional effects.In each conditional effect ⟨con, eff + , eff -⟩, con is a propositional formula called the condition; eff + and eff -are sets of positive effects and negative effects, respectively.The action is applicable in a state s iff s |= pre(a). The positive effects of a in s are Pos(a, s) = ⟨con,eff + ,eff -⟩∈coneff (a),s|=con eff + , and the negative effects Neg(a, s) are computed similarly. The state s ′ after executing an action a is s[a] = s ∪ Pos(a, s) \ Neg(a, s). I : 2 F → [0, 1] is the initial probability function; when there is only one initial state i, we write I = {i} instead of I = {i → 1} ∪ {s → 0|s ̸ = i}. The probability function I is extended to sets of states with I(S) = s∈S I(s). G is a propositional formula over F called the goal, which is a condition the algorithm aims to achieve. τ is a rational number between 0 and 1 and is called the probability threshold.In this article, we assume that each planning problem whose name is decorated is defined as a tuple ⟨F, A, I, G, τ ⟩ with the corresponding decoration. For instance, a problem P Y X is implicitly defined as the tuple⟨F Y X , A Y X , I Y X , G Y X , τ Y X ⟩. A plan π = name(a 1 ) . . . name(a k ) is a sequence of ac- tion names. 1 A plan is valid for a state s if: (i) each action a j is appli- cable in state s[a 1 ]...[a j-1 ],and (ii) it leads to a goal state:s[π] |= G.We write π the set of states in which π is valid. A plan π is valid for the problem P, written π ∈ Π(P), if the probability of it being valid in the initial state is at least τ : I( π ) ≥ τ .The problem in Figure 1 includes six facts F = {x 1 , x 2 , x 3 , y 1 , y 2 , y 3 } and 4 actions A = ⟨L, R, U, D⟩ (left, right, up, down) . Actions L and R have precondition y 1 -I.e., the agent can only act to move horizontally when located in the top row. There are nine initial states. The goal is x 2 ∧ y 2 and τ = .75.The initial probability function is We now present the concepts of tag and context (Palacios and Geffner 2009). We define a subgoal to be a conjunct of the goal formula, or some action precondition. A fact f 1 depends on another fact f 2 if there is a conditional effect ⟨con, eff + , eff -⟩ that satisfies f 2 ∈ vars(con) andI = {x 1 , y 1 }→.04f 1 ∈ eff + ∪ eff -. A context c(ϕ)of a subgoal ϕ is the union of facts vars(ϕ) with all other facts they depend on, transitively. In other words, the context of a subgoal includes all the facts whose truth in the initial state can influence the validity of the subgoal in any state during the execution. Given a context c, the tag of initial state i is the intersection of i with c: t c (i) = i ∩ c; we generally add the context to the tag and write the tag as a pair ct = ⟨c, t⟩. The set of tags of P is Tags(P).Our running example of Figure 1 features three subgoals: x 2 and y 2 (i.e., each from the goal), and y 1 (precondition of actions L and R). Consider ssubgoal ϕ = y 1 . Here, y 1 depends on y 2 from conditional effect ⟨y 2 , {y 1 }, ∅⟩ of U, and y 2 depends on y 3 . Hence, the context of ϕ is {y 1 , y 2 , y 3 }, the facts characterising the agent's vertical position. This means that, to decide if action L is applicable after applying the known sequence of actions a 1 , . . . , a k from the unknown initial state i, knowing the vertical location of the robot in i suffices. 
a counter-example based approach: 
 In this paper, we develop a counter-example based approach similar to CPCES (Grastien and Scala 2020). In our running example, from sample {(x 2 , y 1 ), (x 2 , y 2 )}, CPCES might propose candidate plan π = UD, a sequence of action valid for both states. This plan is not conformant because it is not valid in state (x 1 , y 3 ). If that state is added to the sample, the candidate plan at next iteration might be U U L R D.One could be tempted to use a similar approach for PCP problems with the difference that a counter-example is generated only if the probability of success I( π ) for current# it Counter-tags CTS Proba Cand. plan. 0 - - - ε 1 x 1 , x 3 , y 1 , y 3 {x 1 , x 3 } .3 L 2 x 1 , x 2 , y 1 , y 2 , y 3 {x 2 } .7 L R 3 x 3 , y 1 , y 2 , y 3 {y 2 } .7 U R L D 4 x 1 , y 3 {x 1 , y 3 } .28 U L R D 5 x 3 , y 3 None N/A -Table 1 : Example execution of OURALGO for the running example with τ = .75.candidate plan π is below the threshold. However, this procedure is not complete. Indeed, if there is a state from which the goal is unreachable, then adding this state to the sample will corrupt it. This is because, if this procedure is to iteratively find plans with higher probability of success, then each call to the classical planner must pose a soluble classical problem. By adding states from which the goal is not reachable to the starting conditions, the posed classical problem is not soluble.In our running example, if we assume that there is a wall from the bottom row to the middle row-i.e., the robot cannot move from y 3 to y 2 -then adding state (x 1 , y 3 ) would mean that no more candidate plan can be generated although the problem is solvable for τ ≤ .9. More generally, the sample could be corrupted by a combination of states.Instead, we build on top of the tag/context theory (Palacios and Geffner 2009). We say that a tag is a 'counter-tag' (introduced in Section 4) to a candidate plan if the plan always fails to achieve one of its subgoals associated with the context when the initial state satisfies the tag. Counter-tags implicitly represent large groups of initial states (potentially exponentially large ones) in which the plan is invalid. Our algorithm (OURALGO) computes a 'counter-tag set' (CTS) that covers the initial belief with probability at least (1 -τ ). Then, when computing candidate plans in later iterations, OURALGO makes sure that the plan is valid for (or consistent with) at least one of these tags.Table 1 illustrates the execution of OURALGO for our running example with τ = .75. Notice that since all tags are singletons, we represent them with facts instead of sets: when we say 'tag x 1 ', we actually mean 'tag {x 1 } over context {x 1 , x 2 , x 3 }'. 0. The first candidate plan is the empty plan π 0 = ε. 1. The counter-tags to π 0 are x 1 , x 3 , y 1 , and y 3 : e.g., executing π 0 for an agent starting in x 1 will fail to achieve the goal. A counter-tag set is {x 1 , x 3 }, as these two tags add up to probability 0.3 > 1 -0.75. From that point on, the candidate plans should be such that either x 1 or x 3 will not be a counter-tag. OURALGO chooses π 1 = L which is consistent with x 3 . 2. The table lists the counter-tags to π 1 ; note that y 2 is a counter-tag as action L cannot be applied when the agent is in y 2 . A counter-tag set is {x 2 } with probability mass .7. Since this CTS contains only one tag, future plans will all make sure that x 2 is no longer a counter-tag. In this round, π 2 = LR is chosen as candidate plan, which if π = ⊥ then return no plan is consistent with both x 1 and x 2 . Notice that OURALGO chooses a plan consistent with x 1 , while it chose x 3 in the first iteration: unlike CPCES, OURALGO does not commit to a state/tag. 3. OURALGO keeps running and finds increasingly sophisticated candidate plans. 4. Consider the fourth counter-tag set, {x 1 , y 3 }. Note that while x 1 represents probability p 1 = .2 and y 3 probability p 2 = .1, their combined probability is not p 1 +p 2 = .3 but .28. OURALGO computes plan π 4 = U L R D. 5. Finally, {x 3 , y 3 } are counter-tags to π 4 , but their combined probability is 0.19, which is less than 0.25. As no CTS exists, the last candidate plan π 4 must be a valid plan. Indeed, π 4 has probability of success of .81 ≥ τ . OURALGO is summarised in Algorithm 1. B collects the counter-tag sets computed so far, and candidate plan π starts with ε. OURALGO computes a new counter-tag set; if no such set exists, the current candidate plan is a solution. Otherwise, the set is added to B. Next, OURALGO computes a candidate plan that is consistent with at least one tag of each counter-tag set from B; if no such plan exists, then there is no solution to the planning problem. Otherwise, a new iteration starts. 
computing counter-tags: 
 We define counter-tags and explain how to verify if a tag is a counter-tag. As described in Section 3, counter-tags are useful in that (i) they allow one to talk about many states in which a plan is invalid without enumerating these states, and (ii) they help find the next candidate plan.The definition of counter-tags is based on the notion of a projected planning problem. Projection restricts the planning problem to a context, and sets the initial state to be a tag. We define the projection bottom up, from simple objects to complex ones.Definition 1 Let ct = ⟨c, t⟩ be a tag.• The projection of a conjunction φ = j∈{1,...,k} φ j over ct is Proj (φ, ct) = j∈{1,...,k}.vars(φj )⊆c φ j . • The projection of a set of conditional effects coneff over ct is the subset of conditional effects Proj (coneff, ct) = {⟨con, c ∩ eff + , c ∩ eff -⟩ ∈ coneff | eff + ∪ eff -⊆ c}.• The projection of action a over ct is Proj (a, ct) = ⟨name(a), Proj (pre(a), ct), Proj (coneff (a), ct)⟩. • The projection of P = ⟨F, A, I, G, τ ⟩ over ct is the classical planning problem Proj (P, ct) = P ct defined byF ct = c, A ct = {Proj (a, ct) | a ∈ A}, I ct = {t}, and G ct = Proj (G, ct).A counter-tag to a plan is a tag such that the plan is invalid in the projected problem.Definition 2 A counter-tag to π is a tag ct ∈ Tags(P) such that π ̸ ∈ Π(Proj (P, ct)). The set of all counter-tags to π is CTags(π).To verify if a tag is a counter-tag to a plan, one can simply simulate the execution of the plan and check that each precondition and the goal condition are satisfied. The main property of a counter-tag is that any initial state in which a plan is invalid features a counter-tag to the plan. For tag ct = ⟨c, t⟩, we write ct the set of initial states i that satisfy this tag: i ∩ c = t; furthermore, given a set C of tags, we write C the set of initial states that satisfy at least one of these tags: C = ct∈C ct .Theorem 1 The set of states in which candidate plan π is invalid is CTags(π) .Proof sketch of Theorem 1 is in the Appendix. Theorem 1 characterises the states in which a candidate plan is invalid. Of particular interest is the fact that one does not need to enumerate all initial states.The probability of a set of counter-tags selected in each iteration is hard to compute by simply summing up the probability of each initial state. To enhance efficiency, we use Deterministic Decomposable Negation Normal Form, d-DNNF (Darwiche and Marquis 2002) , since it permits polynomial time implementations of computing probability (Darwiche 2001; Huang 2006) .d-DNNF is a language for propositional formulas that satisfies decomposability and determinism conditions. Decomposability guarantees that the variables within each conjunction are distinct, and do not overlap. Determinism guarantees that the disjuncts within any disjunction are logically contradictory -E.g., if ϕ 1 ∨ ϕ 2 appears as a subformula, then we also know ¬ϕ 1 ∨ ¬ϕ 2 . d-DNNF enables computation of certain logically complex queries in polynomial time in the size of the formula.Let φ be a formula in d-DNNF over a set of Boolean ('chance') variables X = vars(φ). Let P : X → [0, 1] be the a-priori probability of each variable to be true (P is independent for each variable). Then the probability that a random assignment of the variables of X satisfies φ, written count(φ), can be computed in polynomial time (Darwiche 2001; Darwiche and Marquis 2002; Huang 2006 ).In this section, we show how to compute the probability of the set of states C using d-DNNFs.Importantly, in order to be able to use symbolic tools to reason about the probability of a set of states, we need the distribution function I to be represented symbolically.We assume that the set F of facts is partitioned into m subsets F 1 , . . . , F m (i.e., F = F 1 ∪ • • • ∪ F m and for all j, k, F j ∩ F k = ∅). We further assume that each subset F j is associated with a oneof probability distribution M j of F j , i.e., a probability distribution over some subsets of F j . The probability of an initial state i is then the product of the probabilities of the intersections of this state with each F j :I(s) = M 1 (i ∩ F 1 ) × • • • × M m (i ∩ F m ).In our running example, the set of facts is partitioned into F x = {x 1 , x 2 , x 3 } and F y = {y 1 , y 2 , y 3 } and the oneof probability distributions are:M x = {x 1 } → 0.2 {x 2 } → 0.7 {x 3 } → 0.1 M y = {y 1 } → 0.2 {y 2 } → 0.7 {y 3 } → 0.1In this example, the subsets F x and F y both match a context, but this is not true in general.Consider a oneof probability distribution M j over F j , and let us write {i 1 , . . . , i k } the domain of M j (i.e., M j (i p ) is defined for all p ∈ {1, . . . , k}). We create a set X j = {χ j,1 , . . . , χ j,k } of k chance variables and, for each index p, a formula that associates χ j,p with i p as follows:φ j,p = χ j,p ∧ q<p ¬χ j,q →   f ∈ip f ∧ f ∈Fj \ip ¬f   .Finally, we write φ j = p∈{1,...,k} φ j,p . In other words, for any Boolean assignment α of F ∪ X j that satisfies φ j , if χ j,ℓ is the chance variable with the lowest ℓ-index such that α[χ j,ℓ ] is true, then the state i represented by α satisfies i ∩ F j = i j . Finally, we need to set the appropriate probabilities of the chance variables; these probabilities are calculated as follows:χ p → M j (i p )/ 1 - q<p M j (i q ) .Given a formula φ that represents a set of states (such as the set C ), the probability of the initial state satisfying φ can be computed via:count(∃F. φ ∧ j∈{1,...,m} φ j ).(1)In our running example, the value of chance variables under M x and M y are {χ x,1 = 0.2, χ x,2 = 0.7/(1 -0.2) = 0.875, χ x,3 = 1}, {χ y,1 = 0.2, χ y,2 = 0.7/(1 -0.2) = 0.875, χ y,3 = 1}, respectively. The formulas associated with these chance variables are:x1 →χ x1 x 2 →χ x2 ∧ ¬χ x1 x 3 →χ x3 ∧ ¬χ x1 ∧ ¬χ x1 y 1 →χ y1 y 2 →χ y2 ∧ ¬χ y1 y 3 →χ y3 ∧ ¬χ y1 ∧ ¬χ y1This six-clause formula φ has the property that each assignment of chance variables satisfying the formula will result in a unique initial state. In general, the probability of this state is determined by the production of values of chance variables assigned as true.Given a set of counter-tags C, the initial states with chance variables represented by C can be expressed as:φ ∧ c∈C cBy compiling the above formula into d-DNNF, the probability of initial states represented by a set of counter-tags can be computed via the function count. 
computing a candidate plan: 
 In this section, we show how to generate a classical planning whose solution set is exactly all the plans that are valid for a given set of CTS. For this purpose, we first show two operators that take as input two classical planning problems and compute a problem whose solution set is the union or the conjunctions of that of the input problems. Then we show how to use these operators.The following operations assume that the planning problems have disjoint sets of facts. If this is not the case, we assume that the facts are renamed to satisfy this condition.Definition 3 Let P 1 and P 2 be two classical planning problems withF 1 ∩ F 2 = ∅ and {name(a) | a ∈ A 1 } = {name(a) | a ∈ A 2 }.The conjunction of P 1 and P 2 is the classical planning problem P = P 1 ⊗ P 2 where• F = F 1 ∪ F 2 , i = i 1 ∪ i 2 , G = G 1 ∧ G 2 , and • A = {a 1 ⊗ a 2 | a 1 ∈ A 1 ∧ a 2 ∈ A 2 ∧ name(a 1 ) =name(a 2 )} where a = a 1 ⊗ a 2 is defined by name(a) = name(a 1 ), pre(a) = pre(a 1 ) ∧ pre(a 2 ), and eff (a) = eff (a 1 ) ∪ eff (a 2 ).⊗ is called 'conjunction' because of the following result:Lemma 1 Let P 1 and P 2 be two classical planning problems. The following holds: Π(P 1 ⊗ P 2 ) = Π(P 1 ) ∩ Π(P 2 )Proof sketch of Lemma 1 is in the Appendix. It is easy to extend Lemma 1 to multiple problems:Π(P 1 ⊗ • • • ⊗ P n ) = Π(P 1 ) ∩ • • • ∩ Π(P n ).Definition 4 Let P 1 and P 2 be two classical planning problems withF 1 ∩ F 2 = ∅ and {name(a) | a ∈ A 1 } = {name(a) | a ∈ A 2 }.The disjunction of P 1 and P 2 is the classical planning problem P = P 1 ⊕ P 2 = ⟨F, A, I, G⟩ where• F = F 1 ∪ F 2 , i = i 1 ∪ i 2 , G = G 1 ∨ G 2 , and • A = {a 1 ⊕ a 2 | a 1 ∈ A 1 ∧ a 2 ∈ A 2 ∧ name(a 1 ) = name(a 2 )} where a = a 1 ⊕ a 2 is defined by -name(a) = name(a 1 ), -pre(a) = pre(a 1 ) ∨ pre(a 2 ), and -eff (a) = eff (a 1 ) ∪ eff (a 2 ).Unlike the conjunction, the disjunction requires an addition condition in order to get the expected behaviour.Lemma 2 Let P 1 and P 2 be two classical planning problems. If P 1 and P 2 are such that their action preconditions are trivial (∀j ∈ {1, 2}. ∀a ∈ A j . pre(a) = true), then the following holds: Π(P 1 ⊕ P 2 ) = Π(P 1 ) ∪ Π(P 2 ) Proof sketch is in the Appendix. It is easy to extend Lemma 2 to multiple projected problems:Π(P ′ 1 ⊕ • • • ⊕ P ′ n ) = Π(P ′ 1 ) ∪ • • • ∪ Π(P ′ n ).For example, consider the candidate plan π = D, and {x 3 } and {y 3 } are counter-tags to π. Since {x 3 } belongs to c 1 and {y 3 } belongs to c 2 , we can have P ′x ⊕ P ′ y in which the goal is x 2 ∨ y 2 .To use the disjunction operator, we need planning problems with trivial preconditions. This is achieved with the trivialisation operation. Essentially, fact ζ is added to the problem. This fact is initially true and must remain true. When an action is taken whose original precondition is not satisfied, then ζ is made false through a conditional effect.Definition 5 The trivialisation of planning problem P is the planning problem T riv(P) = P ′ defined by• F ′ = F ∪ {ζ} where ζ ̸ ∈ F is a new fact; • A = {T riv(a) | a ∈ A} where T riv(a) = ⟨name(a), true, eff (a) ∪ ⟨¬pre(a), ∅, {ζ}⟩⟩; • I ′ = {(i ∪ {ζ} → v) | (i → v) ∈ I} ∪ {(i → 0) | i ⊆ F }; • G ′ = G ∧ ζ; • τ ′ = τ .Lemma 3 Let P be a planning problem. The following holds: Π(P) = Π(T riv(P)).Prove sketch of Lemma 3 is in the Appendix.Given a set T of CTS, we show how to generate a new planning problem (composite problem) such that all the valid plans are exactly those that the counter-tag sets are not counter-examples to:P B = P T1 ⊗ • • • ⊗ P Tnwhere B = {T 1 , . . . , T n } andP Ti = P c1 ⊕ • • • ⊕ P cmwhere T k = {c 1 , . . . , c m } and P c k is the trivialisation of the projection of P over c k . The composite problem is a classical planning problem.At each iteration, OURALGO must generate a new counter-tag set (or terminate). The number of counter-tag sets is finite: the algorithm must terminate. 
conjunctive goals: 
 Our general approach requires to compute candidate plans from the set Π(P 1 ) ∩ • • • ∩ Π(P n ) where Π(P j ) = Π(P ij ) ∪ • • • ∪ Π(P jkj ). This is difficult because it leads to planning problems with disjunctive goals (as hinted at by the union operator ∪).Notice that any candidate plan then belongs to the set Π(P H ) = Π(P 1h1 ) ∩ • • • ∩ Π(P nhn ) where for all j, h j ∈ {1, . . . , k j }, i.e., H = {h 1 , . . . , h n } forms a hitting To leverage this property, we propose to first search over the set of minimal hitting sets of B. This is summarised on Alg. 2. OURALGOHIT chooses a hitting set H, searches for a plan in P H and, if it fails, moves to the next hitting set. Searching for a candidate plan involves an extra loop to iterate over the hitting sets. Method unique min hit returns a different hitting set at each iteration. If all hitting sets fail to lead to a plan (Line 7 where the set of hitting sets has been exhausted), then there is no plan. 
experiments: 
 We compared four different probability thresholds: τ ∈ {0.99, 0.90, 0.75, 0.5}. The classical planners used in our implementations are the Fast Forward (FF) (Hoffmann 2001) and Madagascar3 (Rintanen 2014).Both OURALGO and OURALGOHIT are tested in the experiments. In Table 2 and Table 3 , column FF-OUR corresponds to FF used in OURALGO; column FF-HIT corresponds to FF used in OURALGOHIT; column MAD-OUR corresponds to Madagascar used in OURALGO; column MAD-HIT corresponds to Madagascar used in OURALGO-HIT. As FF times out for nearly all problems at a probability threshold of 0.5, we only executed Madagascar under the 0.5 probability threshold. We did also experiment using classical planners based on the Fast Downward System (Helmert 2006) but do not include those results due to poor runtime performance in the preprocessing component of that tool on composite problems we encounter in our study. Due to space limitations, not all experimental results are presented in the tables. Full results are in the supplementary material.We ran experiments over the set of benchmarks from Zhang, Grastien, and Scala (2020) . We modified these CP problem benchmarks by incorporating a uniform distribution into the initial states. The benchmark set contains 6 domains: BOMB, COINS, DISPOSE, ONEDISPOSE, LOOK-GRAB, and UTS. Because OURALGO and OURALGOHIT randomly select counter-tags in each iteration, to mitigate the impact of randomness on the experiment, each instance was solved nine times, and we report the median result. Timeout was set to 1800 secs. The experiment was conducted on an Intel(R) Core(TM) i7-7700 CPU with 8 cores and 16 GB memory. The experiment did not include a comparison with other PCP planners, such as probabilistic-FF and POND, as these planners were developed decades ago and would not compile and/or run correctly on systems available to us.The probability threshold 0.99 problems perform best over all the other probability threshold. This is because in each iteration the probability of counter-tags over 0.01 is enough to be used to search next candidate plan. In some problems, such as DISPOSE p-8-1 and UTS p7, there is only one context and the probability of any single initial state is more than 0.01, so only one counter-tag is needed in each iteration. This makes the composite problem become much easier to be solved as there is no disjunctive goal. Also, because of this reason, the benefit of hitting set strategy is not exhibited. For example, solving DISPOSE p-8-1 problem takes almost the same time by FF-OUR and FF-HIT.As the probability threshold τ decreases, the performance of both OURALGO and OURALGOHIT gradually deteriorates. This phenomenon is due to two reasons. First, as the number of contexts (intuitively, dimensionality) of a problem becomes large, so too does the typical length of clauses in the goal of composite problem. Thus, for low values of τ , we will oftentimes have many and long clauses in the goal of composite problem. The fact is that there are many correlates with the number of iterations required to solve the problem, and therefore the runtime. Moreover, for lower values of τ the number of clauses in the goal of the composite problem being posed is typically high. In practice, for low values of τ in problems with many initial states, we require many iterations of our algorithm to find a valid plan of PCP. The fact is that there are many correlates with the number of iterations required to solve the problem, and therefore the runtime. Both the length and number of clauses impact the performance of the base classical procedure, thus also negatively impacts overall performance.The algorithms we have described have a performance profile that is quite different to that of incumbent algorithms. Specifically, POND and probabilistic-FF exhibit their fastest performance with lower values of τ , with published performance degrading significantly with values of τ close to 1. (Domshlak and Hoffmann 2007) . This is an interesting phenomenon, as our algorithm is good at handling high probability thresholds because it uses counter-tags for plan searches, and the higher the probability threshold, the fewer counter-tags are required, i.e., intuitively, as τ approaches 1 the problem becomes more-and-more like a typical fully conformant problem. In doing so, our algorithm effectively mitigates the inherent weaknesses found in other algorithms.OURALGOHIT outperforms OURALGO significantly using both FF and Madagascar as the subplanner, especially when τ < .99. This is what we expected, as there are multiple counter-tags in each iteration for all the problems with τ < .99, and hitting set helps classical planners in selecting which counter-tag needs to be satisfied in the subse-quent candidate plan. This can be evidenced by the ratio (r) of classical planner runtime to the total runtime (shown on the supplementary material). When τ < .99, the value of r in OURALGOHIT is significantly lower than in OURALGO. For example, when solving BOMB p20-10 with τ < .99 using Madagascar, the r value in OURALGO is over 50%, while in OURALGOHIT, it is less than 20%. In principle, there are various strategies for choosing a hitting set, instead of simply choosing smallest one. For example, our algorithm could heuristically take the initial state distribution into account when selecting hitting sets.We observe that Madagascar performs better in solving problems with a small τ compared to FF. For example, when using OURALGO with a probability threshold of 0.75, MAD-OUR takes 14.8s to solve COINS p10, whereas FF-OUR times out. Another example is using OURALGOHIT with a probability threshold of 0.5, where MAD-HIT successfully solves UTS p9 and p20, whereas FF-HIT times out. This outcome implies that, in our algorithm, various classical planners can be chosen for different types of problems to enhance search efficiency. This underscores the flexibility of our algorithm. 
conclusion: 
 In this article we present a counter-example based approach to solving PCP problems with uncertain initial states. In OURALGO, a PCP problem is projected onto contexts, and a set of counter-tags is then selected whose probability is computed according to a d-DNNF representation. OURALGO iteratively defines a composite problem (classical planning problem) that, at the limit, faithfully represents some underlying PCP of interest. At each iteration a classical plan is computed for the current composite problem at hand, or otherwise it is shown to be unsolvable. If the latter is the case, the underlying PCP has no solution. Otherwise, either a plan for the PCP is found corresponding directly to the classical plan, or that plan is used as a basis for refining the classical problem for a subsequent iteration. Composite problems with disjunctive goals are hard to solve using classical planning systems, such as Mad and FF. Hence, we developed OURALGOHIT, introducing a hitting set to assist the classical planner in selecting subgoals that can be satisfied by candidate plans.From experimental results, we confirm the effective performance of both OURALGO and OURALGOHIT in solving PCP problems, and OURALGOHIT outperforms OURALGO. Our approach excels in addressing PCP problems with a high probability threshold, while other wellknown PCP planners like probabilistic-FF and POND are good at solving PCP problems with a low probability threshold. This feature enables our approach to compensate for the weaknesses of current PCP planners, providing the planning community with enhanced options for solving PCP problems with high probabilities.Another advantage of our approach is flexibility, allowing us to choose the classical planner based on the type of PCP problems and the features of different classical planners.In the future, we can further improve OURALGOHIT by using better strategies in selecting hitting sets. 
 
 Appendix: Traditionally, a plan is instead defined as a sequence of actions; using action names makes it possible to compare plans for problems that feature different actions-for instance because they are defined over a different set of facts-but the same action names.Note, in this case a sequential execution will achieve the goal with probability 1 or 0.We ran algorithm C with R=1.2, checking horizons from 0 to 50, using ∃-step -semantics. 


Decision: The reviewers were satisfied with the rebuttal, and we all converged on an "accept" recommendation.

The discussion for the paper largely centered around reacting to the rebuttal. Two of the reviewers wrote answers to the rebuttal that were specifically intended as answers to the authors. Because the authors won't be able to see these comments, I am including them here.

*Answer by Reviewer Bs74 to the rebuttal:*

Thank you for the detailed response. I don't have any concerns about the paper now, but I do have the following suggestion that came to mind.

Explainability: A good application of this work that may be worth discussing and/or exploring, which I think will definitely increase its impact, is explainability. Specifically, the fact that you use logic to represent PCP problems makes it a perfect candidate for generating explanations about these problems. For example, given your set of formulas (the d-DNNF), you can find which formulas are responsible for which particular behavior and use them to explain it. Indeed, the method of computing minimal hitting sets (that you also utilize )has been explored in the context of explanation generation in explainable planning (particularly, model reconciliation), where the planning models are represented in logic [1]. You can easily see the parallels between these two works.

[1] S.L Vasileiou, A. Previti, W. Yeoh, "On Exploiting Hitting Sets for Model Reconciliation", AAAI 2021

*Answer by Reviewer AjoV to the rebuttal:*

> Q1A. Your intuition is not entirely correct. In Conformant Planning, the proof that a candidate plan is invalid is a single
> counter-example/state; CPCES adds this state to the sample. In PCP, a proof that the plan is invalid is a set of counter-states with
> probability above . Therefore, we should not add a single state to the sample but a set of states. We do not want to enumerate these states
> so we use sets of counter-tags instead.

Okay, this does clarify question. Please make sure that the above is conveyed in the paper as crisply and precisely as above.

Regarding the answer to my second question above

> Note that pi is valid for P means that pi in Pi(P) not pi in Actions(P)*

The difference is noted but my comment refers to the fact that Pi(P) \subseteq Actions(P)*. There is no assumption in the paper to restrict the structure of plans when it comes to the number of times actions appear in them.

> Our only assumption is that P_1 and P_2 have the same set of actions; the assumption is
> guaranteed because it is a precondition of operator \otimes. The definitions (precond. effects)
> of the same action in P_1 and P_2 are different.

Thank you for the patient comment. I have realised that I did not take into account the clause in Definition 3 that goes F_1 \cap F_2 = \emptyset. Indeed, you can have a valid plan for P_1 that has actions with trivial preconditions and effects, this plan can indeed be executable as trivial actions a with pre(a) = top and eff(a) = \emptyset are (1) applicable in any state, and (2) they give rise to transitions (s, a, s') for any pair of s, s' in S. Optimal plans for P_1 need not be optimal plans for P_2 but that is not an issue.

Regarding my third question

> Consider the projections P_1 and P_2 of running examples on y_1 and y_2. Consider the plan L. This plan
> is invalid for P_1 (it does not reach the goal y=2) and for P_2 (action L is not applicable from y=2). So L should
> not be a valid plan for P_1 \oplus P_2. Using Def. 4. L is applicable in the initial state (because it is applicable
> for the first interpretation) and the goal is reached (because its reached in the second interpretation). The
> trivialisation operation makes sure the validity is only verified in the final state.

Thank you very much for the careful discussion provided. The argument provided addresses my question in a satisfactory manner.

I have no further major concerns (other than the dubious significance of the experimental results). While sceptical of the interpretation offered for some observations, I think the authors have proven they are rigorous and I trust they will make sure to clarify questions regarding the structure of the preconditions and conditions of conditional effects in the benchmarks.

Reviews: review: strength_weakness: strength_weakness: - The paper acknowledges that the approach shows a deterioration in performance as the probability threshold decreases. This is attributed to the increase in the number of contexts and the length of clauses in the goal of the composite problem. The impact of these factors on the performance of the algorithm should be further addressed. The algorithm faces challenges in solving problems with many initial states and low probability thresholds, but this is not thoroughly discussed.

- The benefit of the hitting set strategy is not exhibited in certain problems, and potential refinements or alternative approaches in such scenarios should be explored. Additionally, the complexity of computing minimal hitting sets should be in the second polynomial hierarchy, if I'm not mistaken. Thus, computing such sets is computationally hard and expensive. It is not clear in the paper how the hitting set approach actually speeds up the algorithm. This should be discussed.

- The paper does not provide publicly available code and domains, which is essential for reproducibility.
questions: questions: 1) How does the hitting set strategy specifically contribute to the acceleration of candidate plan generation?

2) You mention that the proposed approach involves encoding the problem using a propositional formula and using a d-DNNF to assess the probability of a set of counter-tags to a candidate plan. Can you further explain how this encoding and assessment process is carried out, and how it contributes to the overall soundness and completeness of the algorithm?

3) You mention that the probability of a set of counter-tags selected in each iteration is hard to compute by simply summing up the probability of each initial state. Could you provide more insights into the specific challenges (or complexities) involved in computing the probability of these counter-tags, and how the use of d-DNNF effectively addresses these challenges?
strength_weakness: strength_weakness: The ICAPS PC team prepared a useful modified AAAI style that numbers lines. This is a useful feature I wish the authors had used. The authors are lucky that there is no automated system rejecting submissions that do not comply with the publishing guidelines. 

# Occasional issues with clarity

The discussion in the related work section sometimes comes across as cryptic. For instance:

- The discussion of POND mentions that this algorithm is sensitive to the “number of states” but not the “problem complexity”. This is unclear to me because of two reasons. First, only states reachable with positive probability matter, regardless of what is syntactically possible. Secondly, existing complexity results that are specific for probabilistic conformant planning do not exist as far as I know. All we have is the existing theory for conformant planning. Its relation to problems with probabilistic lower bounds for success has not been studied deeply or systematically in the literature.

- When discussing Probabilistic-FF limitations, the authors make a distinction when I do not think there is any to make, these issues carry over from Conformant-FF, and it all links back to the properties of the Relaxed Planning Graph (RPG). If valid conformant plans require multiple instances of the same action, these will not appear on the RPG analysis, and the lookahead search will be less informed and more like that in POND. Also, when the RPG captures only a subset of the actions in valid conformant plans, this may result in a large search effort too.

- The clarity of Grastien & Scala's CPCES discussion could be improved. For instance, it is unclear how a plan $\pi$ can “agree” with all (initial) states in a set. Maybe it is too early to get into such detail.

- There is a typo in the text: “Second, it treanslates” for “Second, it translates”

# Minor issues in Problem and Background definitions

This section's quality is fair, but there are a number of issues with the definitions that warrant some further attention. Please find below some recommendations to improve quality and clarity:

- It would be possibly useful to preface the section by noting that the definitions and assumptions therein follow from those in STRIPS. Doing so allows us to locate this work precisely and quickly amongst formulations in the literature on AI planning.

- The wording of the definition of states is unfortunate. To my reading, it suggests that states are subsets of “true facts”. Therefore, states cannot reliably be used to interpret formulas $\varphi$, which is necessary to define the applicability relation between states and actions.

- A concise and precise way to define the propositional language for formulas $\varphi$ is that of the set of formulas over atoms $F$ without disjunction *and* negation.

- The notion of “name” is not defined. I would invite the authors to consider them to be function symbols (drawn from a suitably defined first-order theory), which plans to interpret into (possibly empty) sets of positive integer numbers.

- The characterization of $I$ (a probability distribution) via its graph (the set of pairs formed by elements of the domain and range of the function) is a hard sell. If $I$ is a probability distribution mappings states $S$ to $[0,1]$, then initial states for classical planning instances are probability distributions $I(s) = 1$ if $s = s_0$, and $I(s) = 0$ for every $s \neq s_0$. The way $I$ is used suggests that $I$ is taken to be the *support of* a probability distribution (the set of elements of the domain mapping to a positive real number) rather than the *actual* probability function.

- “a condition the algorithm aims to achieve”: what algorithm is this? Conformant plans can be used to compute automata satisfying a specification, and I guess one could reasonably imagine that probabilistic automata could also be captured by PCP plans. Please review this statement, as it seems to be a bit off. Interpreting plans as programs is not supported by your definitions.

- Regarding decorated “names,” perhaps a better word instead of "decoration" is "parametrization". That is, super and sub-indices are taken to be parameters used to define each of the elements in the definition of instances.

- I would suggest using captioning and italics for the paragraphs where the discussion of the motivating example is continued. This would be helpful to visually separate definitions from illustrations of the concepts being defined.

- I do not agree with the statement that “a PCP problem with only one initial state $i$ is equivalent to a classical planning problem”. This statement is only true when $\tau = 1$, as observed in footnote 2.

- There is a typo in the text (e.g. “ssubgoal”).

# Poor signposting and missing definitions in "A Counter-Example based Approach"

I found this section's quality to be mixed. There are some gaps in the explanation of Algorithm 1, and I found some of the points in the discussion to not follow clearly from the definitions provided in the previous section. I list below my suggestions to improve or bridge the issues I perceived:

- The section starts strong with an insightful discussion of why the strategy followed by the CPCES algorithm is not a good one for PCP problems because having unsolvable states in the sampled set of initial states would drive the probability of success to 0. In effect, CPCES strategy is too conservative for the PCP setting. I would suggest being more proactive in the text to signpost this insight to readers rather than leaving it as an exercise for them.

- A key concept is not defined explicitly: that of the probability of tags $t$ (e.g., sets of states satisfying the property represented by the tag). Since all states in the tag are mutually exclusive this is just the result of computing $P(t) = \sum_{s \models t} I(s)$. Less clear is the computation of the conjunction of two or more tags, since a state $s$ with $I(s) > 0$ can satisfy several tags. This should be addressed in the previous section.

- Algorithm 1 and the example computation seem to diverge in one critical aspect: the role of tags being accumulated through iterations. The discussion in step 2 does not provide any intuitions of why the tag $x_3$ selected in iteration $i=1$ is not considered by the plan generated in iteration $i=2$, but in contrast, $x_1$ is taken into account. The pseudo-code of Algorithm 1 does not suggest that tags not in $B \setminus CTS_i$ are “optional”.

# Some aspects in the Experimental Design and Analysis of Experimental Results

The experiments are designed sensibly, handling the random perturbations in a reasonable way. Benchmark selection seems to follow the inertia of previous publications rather than being informed by the specifics of the proposed approach. For instance, a key issue to my mind is the requirement to handle conditional effects where conditions are disjunctions. This only occurs when actions in domains (sets of instances sharing actions) have more than 1 precondition. As a matter of fact, FF does not support disjunction on conditional effects, unless they are compiled away (somehow). Such a compiler is not trivial and would warrant a detailed explanation. 

There should be also some explanation of what algorithms are being used to solve incrementally the hitting set problems, which I understand eventually represent a larger fraction of runtimes than solving classical planning problems. Also, as suggested by the discussion on heuristics for selecting hitting sets, runtimes, and coverage may be sensitive in very substantial ways to the specific hitting sets being selected.

I have some actionable suggestions for the authors:

- Rather than taking the instances in benchmarks for granted, try to generate instances according to some suitably defined parametrization that generates diverse sets of initial state distributions. Also, by exploring a broader range of instances (especially “small” ones), we would get more information about how the planners compare. To be honest, there are so many time-outs for FF that I would suggest a healthy dose of prudence when interpreting the results.

- Classifying instances/domains according to their potential runtimes is important. There are several ways to do that: for instance, using the notion of conformant width and structural complexity of preconditions and goals (and therefore of tags). The work on structural complexity by Palacios and Geffner should be (along with that of structural diversity) a major factor in the experimental design.
questions: questions: 1/ In the section "A Counter-Example based Approach" it is noted that unsolvable states $s$ are not to be added to the sample. This is a reasonable proposition, but the development of scalable algorithms depends on the assumption that proving the unsolvability of a state can be done quickly and feasibly. This seems to rule out the possibility of using classic SAT algorithms for classical planning unless one further assumes that all possible states in an initial conformant state are solvable. Could the authors please clarify what is meant in this passage? Is the sampling algorithm supposed to access an oracle for "weeding out" unsolvable states?

2/ Lemma 1 needs to consider relevant assumptions for its proof. Namely, that is the case that every valid plan, for instance ${\cal P}_1$, is also a valid plan for ${\cal P}_2$. At the moment, this assumption is "hidden" by having them very much in the first paragraph of the Proof of Lemma 1. I also think this assumption is of great consequence. What compelling reason can the authors give to accept this assumption in the first place? From what I have understood, it could well be the case that instances have plans that use entirely different sets of actions, and more frequently, I suspect, plans where valid plans for either instance use the same actions, but the plan assigns them different indices, or they have different multiplicity (e. g. here I am thinking of plans as functions mapping actions to *sets* of natural numbers representing the plan steps).

3/ Accepting the assumption in question 2 (which is also required by the proof of Lemma 1) and having checked the proof for Lemma 2 in the appendix, I am unsure of why the notion of "precondition triviality" is necessary. In the proof, I can read that "Condition 2 is trivial because preconditions are trivial", but there are no signposting numbering conditions. It is not clear to me what is exactly trivial. Could the authors please provide more clarity on this?
strength_weakness: strength_weakness: My primary concern lies with the technical intricacies of the work. The paper's style vacillates between formal definitions and theorems, and a high-level, abstract exposition of the approach. I find this to be exceedingly perplexing, as the impreciseness of the definitions renders it challenging to assess the soundness of the methodology. On the other hand, the abundance of details obfuscates the "fil rouge" of the approach, which is a closed-loop algorithm, iteratively seeking a valid plan by computing a series of counterexamples. I propose adhering to a consistent style (such as a "formal" one) and maintaining it within the main body of the paper.

There are few flaws in the definitions and in the description of the approach. The clarity depends also in the order of the presentation. I suggest, for instance , to move sec. 6 before 5.2 (p. 6), or describe OURALGO after introducing CTS (p. 3).

The approach looks expensive as the set of candidate plans is generated incrementally until a plan with the desired probability is found. In the worst case, the CTS is made of all initial states for which the plan is invalid, which looks like proportional to the superset of 2^F. Some complexity result would be welcome to justify this particular approach. 

Said that, I insist saying that this paper is interesting and relevant for the conference, even if, as it is now, it deserves further polishing.

# More important technical flaws

- Definitions must be well stated. For instance, the definition of subgoal, which is important,is vague but we encounter it all along the paper. I understood that a subgoal can be any goal or any precondition conjunct. More in general to the section 2: if you're using Palacions&Geffner's definition, please use the same terms as well. Here 'depends' means 'relevant'; 'contect' is 'relevant clause'; 'tag' is 'relevant initial clauses' (maybe?). In the present work, the author miss the transitivity of 'relevant' definition.
- p.3. "y_2 depends on y_3" is incorrect: y_2 depends on y_1 as well per D.
- p.3. "the context of a subgoal includes all the facts whose truth (value) in the initial state can influence the validity of the subgoal in any state" sounds a false statement. As defined, the context includes also facts that are preconditions of actions in the plan, not necessarily relevant for the initial state.
- p.4. another weakness in the formality of the writing is definition 1.
- - who are \phi_j?
- - if eff+ U eff- in c, then c \cap eff+ = eff+! I thus suggest to write directly the projection and get rid of the second part of the formula. Why the effects are in the context then?
- sec 5.2. Please define P, and c_k. I would rather write: "Let P be a planning problem and the set {P_{c_k}}_{c_k} the trivialisation of the projections of P over contexts c_k. It is clear that T_k is a collection of contexts s.t. B = {T_k}_0<k<n
- at the end of sec 5.2 you have a result relative to the termination of OURALGO placed here without any explaination. Better to say how the composite problem is made, and the counter-examples found, in order to solve the composition of the projections of the different problems over their contexts.
- Beginning of sec. 6 Not clear who are the different sets. you change the indexes from section to section, and it's really hard to follow. P_{jk_j} really puzzled me at this point. I really recommend to rewrite this section ,in order  to introduce you selection of counter-tags. It's here that the reader really misses a general descritpion of this version of OURALGO.

# Minor stuff

- p.1. A remark: in CP, 'weak' solutions are excluded
- p.1. to reach the destination G = (x_2, y_2)... and later specify for clarity that "its initial position, which can be anywhere in the grid".
- p.2. typo : "Second, it translates"
- p.3. "precondition y_2 - I.e.," is better rewritten "precondition y_2, i.e."
- p.3. typo: "Consider subgoal"
- p.3. I find the last sentence of sec. 2 really unclear: to apply L it is obvious that you must know its precondition, which is y_1, the vertical coordinate. Note that reasoning with 'merges' à la P&G, all but one vertical position would be needed, not all of them.
- p.3. ref to algo 1 when encountering OURALGO for the first time.
- It would be clearer if lines in algo 1 are linked during the example p. 3. E.g. the first candidate plan (line 4). Possibly move end of sec. 3 before the example.
- Algo 1. replace "explained" by "see" to save 2 lines.
- p.5. typo: to generate a classical planning problem whose solutions...
- In the results p.8, please empathise 'best' results using bold typeface.
- Still in the tables p.8, please give some indication of how difficult is to find the plan iteratively, e.g. indicating the size of the CTS.
- Def. 5, please define P' = {F', A', I', G'}
- Def. 5. typo: A' =
- Proof sketch of th.1. 
- - "we can have" -> "we have" (it's a proof, we do not want hypotheses here)
- - definition of subgoal of \phi is missing, because we don't know what \phi is.
- - I would rather write simply: The plan starts in the initial state i. If the plan fails, by definition i is a counter-tag to the plan.
questions: questions: 1. The authors focus on PCP with unknown initial states. What is the cost of extending the approach to ND actions?
2. Do you have some complexity results to show for the two algorithms?