Safe Learning of PDDL Domains with Conditional Effects

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 15:45:13

Abstract: Powerful domain-independent planners have been developed to solve various types of planning problems. 
These planners often require a model of the acting agent's actions, given in some planning domain description language. 
Manually designing such an action model is a notoriously challenging task. 
An alternative is to automatically learn action models from observation. 
Such an action model is called safe if plans consistent with it are also consistent with the real, unknown action model. 
Algorithms for learning such safe action models exist, yet they cannot handle domains with conditional or universal effects, which are common constructs in many planning problems.   
We prove that learning non-trivial safe action models with conditional effects may require an exponential number of samples.
Then, we identify reasonable assumptions under which such learning is tractable and propose Conditional-SAM, the first algorithm capable of doing so. 
We analyze this Conditional-SAM  theoretically and evaluate it experimentally. 
Our results show that the action models learned by Conditional-SAM can be used to solve perfectly most of the test set problems in most of the experimented domains.

Main paper: 
 introduction: 
 Planning is the fundamental task of choosing which actions to perform in order to achieve a desired outcome. An automated domain-independent planner refers to an Artificial Intelligence (AI) algorithm capable of solving a wide range of planning problems (Ghallab, Nau, and Traverso 2016) . Developing a domain-independent planner is a long-term goal of AI research. Researchers developed many domainindependent planners for various types of planning problems.Such planners include Fast Downward (Helmert 2006) , Fast Forward (Hoffmann 2001) , ENHSP (Scala et al. 2016) , and more. These planners require a model of the acting agent's actions, given in some domain description language such as the Planning Domain Definition Language (PDDL) (Ghallab et al. 1998)) . Defining an agent's action model to solve real-world problems is extremely hard. Researchers acknowledged this modeling challenge and algorithms for learning action models from observations have been proposed (Cresswell and Gregory 2011; Aineto, Celorrio, and Onaindia 2019; Yang, Wu, and Jiang 2007; Juba, Le, and Stern 2021; Mordoch, Stern, and Juba 2023) . Since the learned model may differ from the domain's actual action model, using it to plan raises two challenges: completeness and soundness. The completeness challenge is that the learned model may be too restrictive, in the sense that it does not allow generating plans for solvable planning problems. The soundness challenge is that the learned model may be too permissive, in the sense that it allows plans that either cannot be applied in the domain or do not reach a state that satisfies the problem goals. There is an inherent trade-off between the soundness and completeness of the learned model. In problem settings where execution failures are unacceptable or are very costly, e.g., autonomous vehicles, high-end robotics, and medical treatment planning, soundness becomes a hard constraint. We focus on such cases, and aim to learn an action model that satisfies the strongest form of soundness: every plan allowed by the learned model must be applicable and yield the same states in the real, unknown, model. An action model that satisfies this requirement has been called safe (Juba, Le, and Stern 2021; Juba and Stern 2022; Mordoch, Stern, and Juba 2023) . 1 We view this as a "safety" notion in part since it enables more conventional notions of safety to be enforced during planning, and provides assurance that they will carry over to the actual execution.Algorithms from the Safe Action Model Learning (SAM) family (Stern and Juba 2017; Juba, Le, and Stern 2021; Juba and Stern 2022; Mordoch, Stern, and Juba 2023) address the challenge of learning safe action models under different sets of assumptions. However, these algorithms are not suitable for learning actions that may include conditional effects. A conditional effect is an effect that occurs only when a specific condition holds. For example, consider an AI for planning treatments to patients and the action of giving a flu medicine to a patient, where that medicine causes an allergic reaction in patients with a certain rare blood type. This action's effects include not having the flu, but there is also a conditional effect specifying that an allergic reaction occurs if the patient has a rare blood type. Clearly, if the patient has a rare blood type, we would want to avoid applying this type of treatment. A safe action model would never permit the execution of the action in these cases.Previous works on action model learning with conditional effects (Oates and Cohen 1996; Zhuo et al. 2010) made no safety guarantees for the learned models. This work addresses this gap by exploring the problem of learning safe action models for PDDL (Ghallab et al. 1998 ) domains with conditional effects. Specifically, we introduce the Conditional-SAM algorithm, which is guaranteed to outputs a safe action model. We show that Conditional-SAM requires an asymptotically optimal number of trajectories when the size of the antecedents for the conditional effects is restricted, which is the only case where the problem is tractable. Then, we describe how Conditional-SAM can be extended to support lifted action models (i.e., parameterized) and effects with universally quantified variables. Finally, we demonstrate the usefulness of Conditional-SAM in practice on a set of benchmark planning problems that have conditional and universal effects.Our results show that given a few observations, the model Conditional-SAM learns is logically identical to the real action models and can be used to solve test problems for most of the experimented domains. 
preliminaries: 
 We focus on planning problems in domains where action outcomes are deterministic, the states are fully observable, and contain Boolean variables only. Such problems are commonly modeled using a fragment of the ADL (Action Description Language) (Pednault 1989 ) and formulated in PDDL (Planning Domain Definition Language) (Ghallab et al. 1998) . In PDDL, a planning problem is described by a PDDL domain and a PDDL problem. A PDDL domain is a tuple D = ⟨F, A⟩ where F is a finite set of Boolean variables, referred to as fluents and A is a set of actions. A literal refers to either a fluent or its negation. Let L be the set of every possible literal. A state is a conjunction of literals that includes, for every fluent f , either f or ¬f . The value of a fluent f is a state s is true if s includes f and false otherwise. An action a ∈ A is a triple ⟨name(a), pre(a), eff(a)⟩ corresponding to the name of the action, its preconditions, and effects. The preconditions of an action a, pre(a), is a conjunction of literals that are sufficient and necessary conditions for applying a. If the preconditions of a are satisfied in a state s we say that a is applicable in s.If an action has no preconditions, then it is applicable in any state. The effects of an action a, eff(a), specify the outcome of applying a. An effect is defined by a tuple ⟨c, e⟩ where c is called the antecedent (condition) and e is called the result. Both c and e are conjunctions of literals. The semantics of an effect ⟨c, e⟩ for an action a is that if a is applied in a state s where the antecedent c holds then the result e will be true in the next state. The antecedent can also be true, representing that the result occurs regardless of the state where the action has been applied. An effect where the antecedent is not true is called a conditional effect. The outcome of applying a to a state s, denoted a(s), is a state in which the value of every fluent is as in state s except those fluents changed by the action's effects.A PDDL problem is defined by a tuple P = ⟨I, G, D⟩ where I is the initial state of the world, G is a conjunction of literals that define the desired goal, and D is a PDDL domain. A plan Π = ⟨a 1 , a 2 , ...a n ⟩ is a sequence of actions. A planΠ is called valid for a PDDL problem P = ⟨I, G, D⟩ if a 1 is applicable in I, a i is applicable in a i-1 (• • • (a 1 (I)) • • • ), and G ⊆ a n (a n-1 (• • • (a 1 (I)) • • • )).An action model for a PDDL domain D = ⟨F, A⟩ is a pair M = ⟨pre M , eff M ⟩ where pre M maps every action in 145 A to a (possibly empty) conjunction of literals in F , and eff M maps actions in A to a (possibly empty) set of effects over F . The real action model of a domain, denoted M * , is the action model where for every action a is mapped to its real precondition and effects, i.e., pre M * (a) = pre(a) and 150 eff M * (a) = eff(a). For an action a, state s, and action model M , we denote by a M (s) the state that results from applying a in s assuming that M is the real action model.). An action model M is safe w.r.t. an action model M ′ if for every state s and action 155 a it holds that if a is applicable in s according to M then (1) it is also applicable in s according to M ′ , and (2) applying a in s results in exactly the same state according to both M and M ′ . Formally:EQUATIONAn action model is said to be safe in a domain if it is safe 160 w.r.t. its real action model. This paper deals with the case where the planning agent does not know the real action model of a given domain, yet it aims to learn an action model that is safe in it. A major benefit of learning such a safe action model is that any plan generated with the learned action model for 165 any problem in the same domain is also valid with respect to the real, unknown, action model. Following prior works on learning action models (Amir and Chang 2008; Cresswell, McCluskey, and West 2013; Aineto, Jiménez, and Onaindia 2018) in general and safe action models in particular (Stern 170 and Juba 2017; Juba, Le, and Stern 2021; Mordoch, Stern, and Juba 2023) , we assume as input a set of observations of previously executed plans, represented as a set of trajectories. A trajectory T = ⟨s 0 , a 1 , s 1 , . . . a n , s n ⟩ is an alternating sequence of states (s 0 , . . . , s n ) and actions (a 1 , . . . , a n ) that 175 starts and ends with a state. The trajectory created by applying π to a state s is the sequence s 0 , a 1 , . . . , a |π| , s |π| such that s 0 = s and for all 0 < i ≤ |π|, s i = a i (s i-1 ). A trajectory is often represented as a set of action triplets⟨s i-1 , a i , s i ⟩ |π| i=1 .180We deal with the problem of learning a safe action model for a domain D given a set of trajectories T collected by executing plans for different problems in D. Ideally, the learned action model will be able to generalize beyond the given set of 185 trajectories and enable finding plans for other problems in D.We make the following assumptions: 1. The given trajectories are fully observable and noise-free. 2. For each literal l ′ and action a, there is at most one effect of a for which l ′ is a result. 3. The maximal number of literals in an antecedent is at most n, a fixed parameter known in advance.Assumption 1 means we observe all the actions and the values of all the fluents in all states in every trajectory in O. This assumption is common in the action model learning 195 literature and lifting it in the context of conditional effects is left for future work. Assumption 2 means that there are no disjunctive antecedents, i.e., multiple effects for the same action having the same result but with different antecedents. The implication of this assumption is that if (c, e) is an effect of some action a, then no conjunction of literals except c is an antecedent of the literals in the result e. Formally:∀l ′ , a : ((c, e) ∈ eff(a) : l ′ ∈ e) → (∄(c ′ , e ′ ) ∈ eff(a) : l ′ ∈ e ′ ∧ c ̸ = c ′ ) (2)This assumption crucially improves the efficiency of learning. We discuss relaxing this assumption later. Assumption 3 means that a human modeler must specify an upper bound 205 on the number of literals in an antecedent for the domain at hand. Specifying such a bound is significantly easier than manually defining the entire action model. We prove later that without the third assumption, learning conditional effects is intractable. 
approach: 
 Conditional-SAM learns an action model by applying the following rules: Definition 2 (Conditional-SAM Inductive Rules). For every action triplet ⟨s, a, s′ ⟩ ∈ T 1. [Not a precondition] For every literal l / ∈ s, l / ∈ pre(a) 2. [Not a result] For every literal l ′ / ∈ s ′ , ∄(c, e) ∈ eff(a) where (c ∧ s ⊬ ⊥) ∧ (l ′ ∈ e) 3. [Must be an effect] For every literal l ′ ∈ s ′ \ s, ∃(c, e) ∈ eff(a) : (c ∧ s ⊬ ⊥) ∧ (l ′ ∈ e)4.[Not an antecedent] For every literal l ′ ∈ s ′ \ s, and conjunction of literals c:if c∧s ⊢ ⊥, then ∄(c ′ , e) ∈ eff(a)such that c ⊆ c ′ and l ′ ∈ e. The first three rules generalize the SAM-Learning (Juba, Le, and Stern 2021) inductive rules to support conditional effects.The fourth inductive rule is derived from Assumption 2 (no disjunctive conditional effects): if we observe l ′ as the result of the action, any conjunction of literals c that is not satisfied in s cannot be the antecedent of the conditional effect for l ′ . Example 1. Consider a domain with three fluents f 1 , f 2 , and f 3 , where the size of antecedents is bounded by 1 (i.e., n = 1), and assume a Boolean vector of size 3 represents a state. Now, assume we observed an action triplet ⟨(T, T, F ), a, (F, T, F )⟩. Using the first inductive rule, we infer that ¬f 1 , ¬f 2 , and f 3 are not preconditions of the action a. By applying the second inductive rule, a cannot include an effect (c, e) such that c is consistent with f 1 ∧ f 2 ∧ ¬f 3 and the result is either f 1 , ¬f 2 , or f 3 . Since n = 1, this rules out the conditional effects where c is one of the following {true, f 1 , f 2 , ¬f 3 } and e is either f 1 or ¬f 2 or f 3 , e.g., (c, e) = (f 1 , ¬f 2 ). According to the third inductive rule there exists (c, e) ∈ eff(a) such that c is one of {true, f 1 , f 2 , ¬f 3 } and e = ¬f 1 . Finally, according to the fourth inductive rule (¬f 2 , ¬f 1 ) and (f 3 , ¬f 1 ) cannot be conditional effects.Next, we describe the Conditional-SAM algorithm, which uses the Conditional-SAM inductive learning rules (Definition 2). The pseudo-code for Conditional-SAM is given in Algorithm 1. Let A(T ), L(T ) be the set of actions and literals observed in the trajectories T . Conditional-SAM maintains three data structures: pre(a) and PosAnte(•, a) for every action a, and MustBeResult(a, l) for action a and literal l. pre(a) is a set of literals, representing which literals may be preconditions of a. It is initialized to all the literals l ∈ L(T ). PosAnte(l, a) is a set of conjunctions of literals, representing all the conjunctions that may be antecedents of a conditional effect of a that results in l.2 This data structure is initialized to include every conjunction of literals of size n or less. Must-BeResult(a) maintains the set of literals observed to be a result of applying a. This data structure is initialized as an empty set. Conditional-SAM updates these data structures by applying the Conditional-SAM inductive learning rules for each action triplet in the given trajectories. That is, it removes literals from pre(•) according to Rule 1, removes conjunctions of literals from PosAnte(l, a) using Rules 2 and 4, and adds literals to MustBeResult(a) using Rule 3.Then, Conditional-SAM iterates over every action a ∈ A(T ) using pre(a), PosAnte(•, a), and MustBeResult(a) to generate the preconditions and effects of a in the resulting safe action model. This part of Conditional-SAM is encapsulated in the function BuildActionModel, listed in Algorithm 2. BuildActionModel stores the preconditions and effects of the resulting safe action model in pre * (a) and eff * (a), respectively. Initially, eff * (a) is an empty set and pre * (a) is set to be pre(a). Then, it iterates over every literal l and considers adding an effect to eff * (a) with a l as a result, as follows. Let P A be the subset of PosAnte(l, a) containing only conjunctions that are disjoint from pre(a). Conditional-SAM uses P A to compute two formulas, Ante and NotAnte. NotAnte is the conjunction of the negation of every clause c in P A, and Ante is the conjunction of all the clauses c ∈ P A. Observe that applying a in a state where Ante is true guarantees that l will be true in the subsequent state. Similarly, applying a in a state where NotAnte is true guarantees that l will not be true in the subsequent state unless it was true before. To minimize the number of clauses and their size, we apply unit propagation on each of them. Afterward, the function verifies whether l ∈ MustBeResult(a). If so, the tuple (Ante, l) is added to eff(a). If PosAnte(l, a) includes more than a single clause of possible antecedents, then there is an ambiguity on which antecedent causes l. To mitigate this, Conditional-SAM adds to pre * (a) the disjunction (l ∨ NotAnte ∨ Ante). This disjunction is composed of three parts as follows: First, allowing the action to be applicable if the result, l, is observed in the pre-state. Second, the action is permitted if none of the antecedents hold in the pre-state. Last, a is applicable if all the antecedents hold in the pre-state. If one of the above holds, the action can be executed.If l was not observed as a result of the action, i.e., l / ∈ MustBeResult(a), the function adds (l ∨ NotAnte) to pre * (a). Since we have yet to observe l as a result of the action, then l / ∈ eff(a); Thus, to prevent l from triggering unexpectedly, we do not permit the action to be executed if Ante is true. After repeating this for every action, BuildActionModel returns the safe action model comprising pre * and eff * .Algorithm 1: Conditional-SAM Algorithm 1: Input: T , n 2: Output: A safe action model. 3: for a ∈ A(T ) do 4:pre(a) ← L(T ) 5:MustBeResult(a) ← ∅ 6: PosAnte(l, a) ← n i=1 {l1 ∧ ... ∧ li|∀1 ≤ j ≤ i : lj ∈ L(T )} ∪ {true} 7: for ⟨s, a, s ′ ⟩ ∈ T do 8:for l such that l / ∈ s do 9:pre(a) ← pre(a) \ {l} ▷ Rule 1 10: The resulting preconditions and effects after applying Buil-dActionModel are pre * (a) = (l 1 ) ∨ (¬l 2 ∧ ¬l 3 ) ∨ (l 2 ∧ l 3 ) that the real model does not have actions with disjunctive antecedents (Assumption 2), but the safe action model we learn may include such actions. This highlights that the learned model may be different from the real model. Nevertheless, the learned model is guaranteed to be safe w.r.t to it.for l ∈ s ′ \ s do ▷ Rule 3 11: MustBeResult(a) ← MustBeResult(a) ∪ {l} 12: for l ′ / ∈ s ′ and c ∈ PosAnte(l ′ , a) s.t. (c ∧ s ⊬ ⊥) do 13: PosAnte(l ′ , a) ← PosAnte(l ′ , a) \ c ▷ Rule 2 14: for l ′ ∈ s ′ \ s and c ∈ PosAnte(l ′ , a) s.t. c ∧ s ⊢ ⊥ do ▷ Rule 4 15: PosAnte(l ′ , a) ← PosAnte(l ′ , 
theoretical analysis: 
 Next, we analyze the Conditional-SAM algorithm. We prove that under a fixed antecedent size (n) its space, runtime, and sample complexity are tractable, and show that our sample complexity bound is tight. O |A||L| n e n ) n + |T ||L| n+1 e n ) nAs can be seen from Lemmas 4.1 and 4.2, the complexity of the algorithm is independent of the number of effects and is only affected by the maximal size of the antecedents and the number of literals and actions in the domain. The complexity does, however, increase exponentially with n.Theorem 4.3. Let D be a distribution over pairs ⟨P, Π⟩ where P is a problem from a fixed domain D and Π is a plan solving P . Givenm ≥ 1 ϵ ln(3)|F ||A| + 2 ln(2)|F ||A| 2|F |e n n + ln 1 δtrajectories obtained by executing Π for m independent draws from D, Conditional-SAM returns an action model M ′ such that with probability 1 -δ, for a new P drawn from D, the probability that there exists a plan consistent with M ′ solving P is at least 1 -ϵ.We supply the proofs for the space, runtime, and sample complexity in the supplementary material. At a high level, the sample complexity follows since the learned preconditions of each action of a plan Π sampled from D are satisfied and the action model is safe. Either at least one literal is deleted from pre or at least one clause c is deleted from some PosAnte(e, a) when such an action a would be used by the plan Π. Thus if a specific literal or clause would prohibit the action with probability greater than ϵ, that literal/clause is eliminated with high probability given a sample of the specified size.Conditional-SAM, therefore enjoys approximate completeness with high probability so long as the number of training trajectories is sufficiently large. The one unsatisfying aspect of our bound is that the number of trajectories is exponential in the size of the antecedents of the conditions in the conditional effects we consider. Unfortunately, we find that this is unavoidable and our bound is asymptotically optimal (for any fixed n) for safe action model learning for domains with conditional effects: Theorem 4.4. Any learning algorithm that is guaranteed to return a safe action model must be given at leastm ≥ Ω( 1 ϵ (|F ||A||(|F |/3n) n |+log 1 δ ))samples to be able to guarantee that with probability at least 1 -δ the learned model permits a plan solving Π drawn from D with probability at least 1 -ϵ for 0 < ϵ, δ < 1/4.The full proof of the lower bound is in the supplemental material. At a high level, the hard distribution involves initial states that have all |A| "goal" fluents set to false, all but one (uniformly random) of the (p -|A|)/2 "forbidden" fluents true, and exactly n out of the (p -|A|)/2 "flag" fluents (uniformly at random) true. With probability 4ϵ, the goal includes a single goal fluent, chosen uniformly at random, that should be set to true. All other goal fluents, as well as the one forbidden fluent, must be set to false. The corresponding Π consists of a plan with a single action, where the agent takes an action corresponding to the fluent to be set true in the goal. Otherwise there is an empty goal, where the agent takes a no-op action. For any problem with a non-empty goal that we did not observe in the training set, no safe action model can permit taking the action needed to achieve the goal. We need to observe at least a 3/4 fraction of the possible goals for a safe action model to attain probability 1 -ϵ. 
learning lifted action models: 
 It is common to define PDDL domains and problems in a lifted manner. A lifted domain defines fluents and actions in a parameterized manner, where every parameter has a type. For example, the action (stop ?f -floor) and the fluent (destin ?person -passenger ?floor -floor) from the IPC Miconic domain are parameterized by objects of type floor and person. A state is a conjunction of grounded fluents, which are pairs of the form ⟨l, b l ⟩ where l is a fluent, and b l is a function that maps parameters of l to concrete objects. A plan is a sequence of grounded actions, which are pairs in the form ⟨a, b a ⟩ where a is an action and b a maps action parameters to objects. A trajectory is an alternating sequence of states and grounded actions.Generally, the parameters in an action's preconditions and effects are bound to the action's parameters. Thus, preconditions and effects of an action in a lifted domain are parameter-bound literals. A parameter-bound literal for an action a is a pair (l, b la ) where l is a literal and b la is a function that maps every parameter of l to a parameter in a. Let bindings(a) be the function that returns all parameterbound literals that can be bound to a. For a grounded action a G = ⟨a, b a ⟩ and parameter-bound literal l ∈ bindings(a), we define g(a G , l) to be the grounded literal resulting from assigning the objects in the parameters of a G to the parame- 6 Learning Effects with Universal Quantifiers Some PDDL domains and planners support universal quantifiers which allow actions' preconditions and effects to in-440 clude additional parameters that are not bound to the actions' parameters. More formally, Universally quantified preconditions and effects define one or more universally quantified variables (UQV) that may be bound to any parameter of a literal used in them. The result of universally quantified con-445 ditional effects must include at least one UQV. Otherwise, if only the antecedents include UQVs, then we can interpret such antecedents as disjunctive universal preconditions. To clarify the formulation of universal effects, suppose that we need to represent an elevator with a stopping functionality 450 that ensures that all waiting passengers get in or out once the elevator stops. Figure 1 presents the stop action schema to implement this functionality. The UQV in this example is ?p.(:action stop :parameters (?f -floor) :precondition (and (lift-at ?f)) :effect (and (forall (?p -passenger) (when (and (boarded ?p) (destin ?p ?f)) (and (not (boarded ?p)) (served ?p))))))Figure 1 : Parts of the action stop from Miconic domain that contains universally conditional effects.We focus below on learning universal effects since they 455 are more common, but our approach also supports learning universal preconditions. Note that universal effects may be unconditional and might occur every time the action is executed, in which case the antecedent is the trivial antecedent true. Conditional-SAM can learn these universal effects as 460 well. We briefly describe how Conditional-SAM can be extended to support universal effects.In general, the number of UQVs a universal effect can define is exponential in the arity of the domain fluents. Still, universal effects with more than two UQV are rare. Thus, 465 we will assume the number of UQVs in a universal effect is a known fixed constant k. To support universal effects, the bindings(a) function is modified to also return parameterbound literals that bind one or more literal parameters to UQVs that may be used in action a's effects. Similarly, the 470 g(a G , l) function is modified such that if l is a parameterbound literal that includes UQVs then g(a G , l) returns a set of grounded literals matching the grounded action's parameters combined with the UQVs. In addition, g(a G , c, e) returns a set of matching pairs (c G , e G ) if either c or e include one or more UQVs. We now present the changes in the inductive rules to support universally quantified variables.Definition 4 (Conditional-SAM Inductive Rules with UQVs). For every action triplet ⟨s, a G = ⟨a, b a ⟩ , s ′ ⟩ ∈ T : 1. For every l ∈ bindings(a) such that ∃l G ∈ g(a G , l) wherel G / ∈ s, then l / ∈ pre(a) 3 2. For every l ′ ∈ bindings(a) such that ∃l ′ G ∈ g(a G , l ′ ) and l ′ G / ∈ s ′ then ∄(c, e) ∈ eff(a) such that ∃(c G , e G ) ∈ g(a G , c, e) where (c G ∧ s ⊬ ⊥) ∧ (l ′ G ∈ e G ) 3. For every l ′ ∈ bindings(a) if ∃l ′ G ∈ g(a G , l ′ ) such that l ′ G ∈ s ′ \ s then ∃(c, e) ∈ eff(a), where ∃(c G , e G ) ∈ g(a G , c, e) such that c G ∧ s ⊬ ⊥ ∧ l ′ G ∈ e G 4. For every l ′ ∈ bindings(a) and c ⊆ bindings(a) if ∃(l ′ g , c G ) ∈ g(a G , c, l ′ ) such that l ′ G ∈ s ′ \ s and c G ∧ s ⊢ ⊥ then ∄(c ′ , e) ∈ eff(a) such that c ⊆ c ′ and l ′ ∈ eHere too, the core Conditional-SAM algorithm remains the same, where MustBeResultand PosAntemay now contain parameter-bound literals that include UQVs. We assume that for each action the algorithm is aware of the types of objects that might include universal effects. 
experimental results: 
 We implemented Conditional-SAM and conducted experiments on six planning domains that include conditional effects. Specifically, we used the CityCar, Nurikabe, and Maintenance domains from the International Planning Competition (IPC) 2014 (Vallati et al. 2015) ; the Briefcase and Miconic are from AIPS-2000 (Bacchus 2001) , and Satellite, which is an ADL version of the classical IPC (Long and Fox 2003) domain. 4 . Table 1 presents relevant information about the domains we experimented on. The column 'Domain' represents the domain's name that was experimented on, and the columns '|A|' and '|P |' present the number of actions and predicates in the domain respectively. The column '# U.E.' presents the number of universally conditional effects present in the domains (The satellite domain has conditional effects that do not contain UQVs) and the column 'n' is the maximal number of antecedents for the conditional effects in the domains. The column |T | represents the size of the trajectories dataset of the domain. The column |t| is the average number of action triplets in a trajectory (the standard deviation is displayed in brackets).For each domain, we generated our problems dataset using a PDDL problem generator (Seipp, Torralba, and Hoffmann 2022). 5 Using the problem generator, we created a dataset of 100 problems that were used to create the trajectories. To solve the generated problems and create the input trajectories, we used two well-known classical planners that support ADL, Fast-Downward (FD) (Helmert 2006) using FF heuristic and context-enhanced additive heuristic, and 525 Fast-Forward (FF) (Hoffmann 2001 ) with a Greedy BFS configuration. We restricted the solvers to solve the problems in up to 60 seconds. For the Nurikabe domain, only 52 problems were solved with our planners, resulting in a smaller dataset.We split our dataset into train and test sets, trained 530 Conditional-SAM on the trajectories in the train set, and used the generated action models to solve the test set problems. To validate the correctness of the generated plans we used VAL (Howey, Long, and Fox 2004) . We followed a 5-fold cross-validation methodology by repeating each experiment 535 5 times, sampling different trajectories for learning and testing. All the presented results are averaged over the five folds. The experiments were run on a Linux machine with 8 cores and 16 GB of RAM. We evaluated our algorithm using two metrics: the percentage of the test set problems solved using Conditional-SAM's learned model, and the correctness of the learned model using precision and recall measures. A test set problem is regarded as solved if one of the planners we used (FD and FF) was 545 able to solve it with the learned action model. Measuring the syntactic precision and recall of the learned model, i.e., measuring the textual difference between the real and learned domains, may not represent the usefulness of the learned domain in solving problems. Instead, we measure the semantic 550 precision and recall of the learned model's preconditions and effects, as follows. For each state in our trajectories, we try to apply the actions of the learned and real action models on the state. We measure the precision and recall based on which action is applicable in the tested states. Formally, the 555 semantic precision and recall of the preconditions are: Where app M (a) denotes the states in a set of trajectories where a is applicable according to the action model M . Finally, average the results over all actions of the domain.Since Conditional-SAM learns a safe action model, the 560 semantic precision of the preconditions is always one. Furthermore, the Conditional-SAM's safety property indicates that whenever an action is applicable according to Conditional-SAM its effects are identical to the real domain's effects. Thus the precision and recall of the effects is always 565 one as well. Thus, our evaluation below only presents semantic recall of the actions' preconditions.Table 2 displays which the planner had timed out (i.e., reached our 60 seconds time limit), and %N S represents the percent of problems that were declared unsolvable with the learned domain. This is caused when the learned domain is too restrictive and thus some problems cannot be solved with it. The column %ERROR represents the percentage of problems in which the solver encountered an error while solving the test set problems. Such errors were caused when the planner was killed due to extensive resource consumption. The column Planner represents the planner that had the best performance and their results are being presented. Finally, the column R pre denotes the preconditions' semantic recall.For the Satellite, Maintenance, and Miconic domains, all the test set problems were solved perfectly using the domain learned with Conditional-SAM. The results for CityCar and Briefcase are significantly worse, where the percent of problems that were solved are 25% and 19%, repsectively. A possible explanation for these results is that the learned domain returned by Conditional-SAM may contain complex universal preconditions. These preconditions affect the solvers in their ability to solve the test set problems. Indeed, every problem that was not solved in CityCar domain was not solved due to our timeout restrictions. Similarly, in Briefcase domain in many occasions, the planning process was terminated because it consumed too many resources (expressed in the %ERROR column). However, the calculated preconditions' semantic recall for both domains is 0.99. That suggests that while the learned domains may appear to be more complex than their original counterpart, they are nearly semantically identical. For the Nurikabe domain, Conditional-SAM could not solve any test problem with the learned domain. This may be because this domain has the largest antecedents (n = 3).Figures 2, 3, 4, 5 presents the solving statistics as a function of the number of trajectories used to train Conditional-SAM for the domains Satellite, Miconic, CityCar, and Briefcase. We do not present the results for the Maintenance domain graphically since after a single trajectory all the test set problems were solved perfectly. We note that for both Satellite and Miconic domains, the percentage of problems increases monotonically, on the other hand, for CityCar domain, we observe a decrease in the number of solved problems as the number of trajectories increases. We note that with one trajectory the domain Conditional-SAM learns does not contain the action destroy_road which has universal effects. Without this action the domain was less complex and the planners could solve more test set problems. Once the action was learned the domain became much more complex which resulted in the increase. Finally, we note that the poor results observed in the Briefcase domain were due to insufficient resources as can be observed in Figure 5 with 59% of the test set problems not being solved since the planning process was killed due to high resource consumption.We focused on conditional effects where the result can appear only once in each action (Assumption 2. There are cases where such an assumption does not hold. For example, in our flu treatment action imagine that now the allergic reaction can appear if the patient has a rare blood type or if they are 630 sleep deprived. In this case, our action would look as follows:(:action treat-flu-symptoms-X :parameters (?p -patient ?b_type -bloodType) :precondition (and (has-flu ?p)) :effect (and (when (is-rare-blood-type ?b_type) (allergic-reaction ?p)) (when (sleep-deprived ?p) (allergic-reaction ?p)) (and (not (has-flu ?p)))))Figure 6 : An action representing a flu medicine with a conditional effect.In Figure 6 we present the action treat-flu-symptoms-X that now contains disjunctive antecedents. Supporting disjunctive antecedents requires altering the first assumption to address 635 only the actions' preconditions and completely removing the second assumption. Removing the second assumption affects Conditional-SAM's fourth inductive rule since it no longer holds that if a conjunction of literals does not hold in a state, it cannot be and antecedent of the observed result. That is since now conditional effects might be disjunctive.Supporting the new capability requires a minor change to the Conditional-SAM algorithm. We change the initialization process of PosAnte to have every possible CNF clause with up to n antecedents, i.e., now PosAnte includes CNFs and not just conjunctions of literals. The rest of the algorithm is not affected. We note that this change highly increases the algorithm's complexity since now it has to eliminate every possible CNF expression before it can determine the correct set of antecedents. Note that the available benchmark domains do not contain disjunctive antecedents for conditional effects. Furthermore, due to its prohibitive complexity, we decided not to support disjunctive antecedents in Conditional-SAM and leave this functionality for future work.Several prior works learn action models from trajectories. The Action-Relation Modelling System (ARMS) (Yang, Wu, and Jiang 2007) algorithm learns a PDDL description of action models by extracting a set of weighted constraints from the input plan examples. The Simultaneous Learning and Filtering (SLAF) (Amir and Chang 2008) algorithm is a different algorithm for learning action models designed for partially observable deterministic domains. The Learning Object-Centred Models (LOCM, LOCM2) (Cresswell, McCluskey, and West 2013; Cresswell and Gregory 2011) is another action model learning algorithm that analyzes plan sequences, where each action appears as an action name and arguments in the form of a vector of object names. FAMA (Aineto, Celorrio, and Onaindia 2019) is a state-of-the-art algorithm that learns action models with minimal state and action observability. FAMA can learn from gapped action sequences of actions, and in the extreme, FAMA can even learn when only given the initial and the final states as input.The algorithms presented above learn action models that do not guarantee that the actions learned are applicable according to the agent's actual action model definition. Contrary to these algorithms, the SAM family of algorithms is designed to learn action models in a setting where execution failures must be avoided (Stern and Juba 2017; Juba, Le, and Stern 2021; Juba and Stern 2022) . To this end, SAM generates a conservative action model. Planning with such an action model produces sound plans but may failu to find a plan even if such exists (i.e., it is incomplete).To the best of our knowledge, there is no work focusing on learning safe action models with conditional effects. In (Oates and Cohen 1996) , the authors created an algorithm that can learn planning operators for STRIPS (Fikes and Nilsson 1971) by interacting with the environments and performing random actions, and using search techniques to learn the context-dependent operators. This approach uses random walks which are costly in case that the agent cannot recover from failures. Furthermore, the resulting action model generated is grounded while our approach learns a lifted PDDL domain. In (Zhuo et al. 2010) , the authors' main focus was learning action models with quantifiers and implications. The authors also proved that their algorithm could learn simple conditional effects with only one antecedent. Since the authors' goal is to reduce the domain compilation time for domain experts, the domains their algorithm outputs may be incomplete or even wrong. This means that their algorithm does not work in mission-critical settings. 
conclusions and future work: 
 In this work, we presented Conditional-SAM, an algorithm that can learn action models for domains that include conditional and universal effects. We showed that Conditional-SAM learns a safe action model w.r.t the real unknown action model and runs in reasonable time. Moreover, we presented tight sample complexity results, showing that Conditional-SAM is, in a sense, asympotitcally optimal. Our experimental results show that using a small number of trajectories, Conditional-SAM learns an action model that solves the test set problems. In future works, we aim to explore methods to improve the algorithm's scalability and support domains with more expressive conditional effects that might contain unbounded disjunctive antecedents or even include numeric conditions and effects. 
: 
 An alternative is to automatically learn action models from observation. Such an action model is called safe if plans consistent with it are also consistent with the real, unknown action model. Algorithms for learning such safe action models exist, yet they cannot handle domains with conditional or universal 10 effects, which are common constructs in many planning problems. We prove that learning non-trivial safe action models with conditional effects may require an exponential number of samples. Then, we identify reasonable assumptions under which such learning is tractable and propose SAM Learning of Conditional Effects (Conditional-SAM) the first algorithm capable of doing so. We analyze this Conditional-SAM theoretically and evaluate it experimentally. Our results show that the action models learned by Conditional-SAM can be used to solve perfectly most of the test set problems in most of the 20 experimented domains. 
 
 Appendix: This notion of safety has different definitions in different contexts. For example, safe Reinforcement Learning often refers to ensuring that some safety function of the current state never goes below some threshold value(Wachi andSui 2020).According to Assumption 2, in the real action model there can be only one such conjunction. Conditional-SAM maintains in PosAnte(l, a) a set of conjunctions since it does not know the real action model.The first inductive rule enables learning universal preconditionsAll the domains are available in https://github.com/AI-Planning/classical-domains We provide an extensive explanation of the experimented domains as well as domains that were not used in our experiments in the supplementary material.5 Action costs were ignored in all domains we experimented on. 


Decision: The paper extends the SAM algorithm for learning PDDL models from observations to conditional effects and to lifted representations (including universally quantified effects). In the discussion, all authors still agreed that they support or at least are ok with acceptance.

Pros:
- overcoming earlier limitations of SAM
- theoretical analysis of required number of samples
- empirical evaluation overall well-done (mixed results) 

Cons:
- somewhat incremental
- clarity should be improved (specific hints in reviews)
- limited scalability (already an issue of original SAM)
- details of theoretical results only in supplemental material
- universal quantification not sufficiently represented in benchmarks

Reviews: review: strength_weakness: strength_weakness: 1. Lines 119-121 describe preconditions as conjunction of literals whereas lines 291-298 move to a disjunctive precondition. Not sure if this is a typo, but this is a major discrepancy that should be fixed. 

2. I am a bit confused about the assumption 2 mentioned in lines 189-190. Does this mean that for an action we cannot have these conditional effects? Here p4 appears in both the effects.
$(p1 \land p2) \rightarrow (p3 \land p4 \land p5)$
$(p2 \land p6) \rightarrow (p4 \land p8)$

3. The clarity of the paper would increase a lot if the line numbers corresponding to the algorithm were mentioned in the section “Conditional-SAM Algorithm.” For example, It took me some time to understand that lines 10-13 correspond to rule 3, not just lines 10-11. 

4. A major weakness in clarity is about how the algorithm will be updated corresponding to Sections 5 and 6. Lifted operator learning is not trivial, and lines 435-437 and 492-496 handwaves around this complex process. I strongly suggest adding the algorithm with modifications, at least in the supplementary, with these changes. Right now, I have to guess what the correct changes would be, and it would be great not to have to guess them.

5. The high number of antecedents (n=3) results in fewer solutions, as mentioned in lines 602-604. And n=3 does not seem that high a number given that there are 12 predicates (or propositions?) in the domain. This points to a problem in the scalability of the approach. And since there is only one domain with n=3, it is difficult to evaluate the algorithm’s scalability.

6. Experiments on UQVs might be missing. Looking at the supplemental, only airport-adl has "Existential preconditions/effects". And the 4 IPC domains whose results are presented do not have this feature. So it is possible that this feature of the algorithm was not tested at all in the empirical evaluation.

7. Presentation Suggestion: I strongly recommend combining Figures 2-5 into a single figure and using a common x or y-axis. It would greatly improve the presentation of the results.
questions: questions: 1. In table 1, |A| and |P| corresponds to the number of lifted actions and predicates or grounded actions and predicates?
2. A different planner (FF) for Briefcase is presented compared to FD for other domains in Figure 5. Lines 581-583 do mention the presented results are for best-performing planners, but how much worse is the performance on FD? If the difference is substantial, what might be the reason for it?
3. About assumption 2 mentioned in lines 189-190, can an action have the following conditional effects?
$(p1 \land p2) \rightarrow (p3 \land p4 \land p5)$
$(p2 \land p6) \rightarrow (p4 \land p8)$
4. Please comment on the algorithm’s scalability in terms of number of antecedents (n). 
5. Were there any experiments done to test the correct learning of UQVs? If yes, was it separated for quantifies preconditions and effects?
strength_weakness: strength_weakness: The paper does not include empirical analysis of model build time.  It would be nice to see these; does model building take hours?  Days?

The paper also has a few minor notational inconsistencies (see detailed comments to follow.)
the citation for PDDL should be McDermott, not Ghallab
p. 3: when you say you add condition l V  NotAnte V Ante when there is ambiguity, perhaps explain a little more why you add NotAnte to the disjunction.  Does this protect against the possibility that l is added unconditionally due to ambiguity in the set PostAnte?
p. 2,4: the notation in Thm 4.3 and 4.4. uses the symbol F, pls add |L| = 2|F| somewhere so reader won’t be confused switching from lemmas to theorems.
p. 6: the tables use P for number of predicates instead of L (or F).  which is it?  Looks like F is what you want here.
p. 6: how does the number of trajectories (100) compare to the theoretical sample trajectory complexity?  If I understand the theorems and table 1 right, let’s pick Satellite. A=5, F=8, so the term ’40’ appears twice in thm 4.3 with coefficients > 1 (never mind that nasty F^n term!) and with the leading term 1/\epsilon that we want to be small.  So I’d expect a vast number of trajectories.  I am somewhat surprised at the high quality of results with so few trajectories.  comments?
questions: questions: are the theorems and table 1 really only counting predicate symbols and not true ground predicates?  Yes, they are, because classical domains only propagate bindings, and don’t have complex constraints on the parameters.  Presumably if we move to a more sophisticated language like SAS or a Timeline based framework, the resulting theorems need to be generalized to capture the number of ground fluents?
strength_weakness: strength_weakness: See above.
questions: questions: i do not have any questions.