Weak and Strong Reversibility of Non-Deterministic Actions: Universality and Uniformity

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

Abstract: Classical planning looks for a sequence of actions that transform the initial state of the environment into a goal state. Studying whether the effects of an action can be undone by a sequence of other actions, that is, action reversibility, is beneficial, for example, in determining whether an action is safe to apply. This paper deals with action reversibility of non-deterministic actions, i.e. actions whose application might result in different outcomes. Inspired by the established notions of weak and strong plans in non-deterministic (or FOND) planning, we define the notions of weak and strong reversibility for non-deterministic actions. We then focus on the universality and uniformity of action reversibility, that is, whether we can always undo all possible effects of the action by the same means (i.e. policy), or whether some of the effects can never be undone. We show how these classes of problems can be solved via classical or FOND planning and evaluate our approaches on FOND benchmark domains.

Main paper: 
 : 
 to apply. This paper deals with action reversibility of nondeterministic actions, i.e. actions whose application might result in different outcomes. Inspired by the established notions of weak and strong plans in non-deterministic (or FOND) planning, we define the notions of weak and strong reversibil-Automated planning is a subfield of Artificial Intelligence dealing with the problem of whether there exists a sequence 20 of actions that lead from an initial state to some goal state of the environment (Ghallab, Nau, and Traverso 2004, 2016) . In Fully Observable Non-Deterministic (FOND) planning, actions have non-deterministic effects, i.e. if an action is applied, one of the effects will (randomly) occur and hence the formalism can model the uncertainty associated with applying such actions (Cimatti et al. 2003) .An important research question concerns whether the effects of an action can be undone by means of other actions. In the literature, this problem is referred to as action reversibility (Morak et al. 2020) . One of the main motivations of studying action reversibility is that actions identified as reversible, that is, those whose effects can be undone, are safe to apply. In other words, if a reversible action is applied, its application does not lead to a dead-end state (unless the action was applied in a state that already was a deadend). This property is especially useful in online planning, where an agent plans and acts w.r.t. a short time horizon, as it might provide information about safe states (Cserna et al. 2018) . Another possible benefit of action reversibility can 40 be in post-planning plan optimization in which it might contribute to more efficient computations of redundant "action cycles" in plans (Med and Chrpa 2022) . In FOND planning, the potential benefits of action reversibility also include determining whether recovery from undesirable effects is possible, which might lead to more efficient generation of strong cyclic plans (Muise, McIlraith, and Beck 2012; Camacho, Muise, and McIlraith 2016) , or whether we can safely perform deterministic replanning in unknown states (cf. FFreplan (Yoon, Fern, and Givan 2007) ).A specific form of action reversibility involving the search for an inverse action has been investigated (Koehler and Hoffmann 2000; Chrpa, McCluskey, and Osborne 2012) . The existence of a pair of inverse actions is a special case of action reversibility, where the reverse plan contains only one action. Eiter, Erdem, and Faber (2008) introduced the concept of reverse plans that corresponds to the notion of uniform reversibility established by Morak et al. (2020) referring to reversibility of action effects by the same means (i.e., by the same action sequence). A more general notion of (non-uniform) reversibility has been tackled by compilation of the problem into contingent planning (Daum et al. 2016) or logic programs (Faber, Morak, and Chrpa 2021) . Recent work of Chrpa, Faber, and Morak (2021) investigates under which condition we can find universal reverse plans.This paper studies the reversibility of non-deterministic actions in FOND planning, which is, to the best of our knowledge, the first work in this area. Inspired by the established notions of weak and strong plans (Cimatti et al. 2003) we propose notions of weak and strong reversibility that, in a nutshell, refer to "all effects might be undone" and "all the effects can always be undone", respectively. We then focus on a subclass of the problem concerning universal uniform reversibility, that is, whether we can always undo all effects of a (non-deterministic) action by the same (weak or strong) policy, or whether some of the effects can never be undone, i.e. they are universally irreversible. We show how these problems can be compiled into classical planning (for weak reversibility and irreversibility) or FOND planning (for strong reversibility). Our approaches are evaluated on a range of FOND benchmark domains.We adopt terminology from the Simplified Action Structures (SAS + ) formalism (Bäckström and Nebel 1995) and the FOND planning (Cimatti et al. 2003) .Let v be a variable (or a state variable) and dom(v) be its domain. A fact (v, x) is a pair that contains a variable v and its value x ∈ dom(v). The set of all facts over the set of variables V is denoted as F (V). A set Σ ⊆ F(V) is called a variable assignment over V if and only if for all (v, x) ∈ Σ does not exist y ∈ dom(v) such that y ̸ = x and (v, y) ∈ Σ. The value of the variable v in Σ, denoted as Σ [v] , is equal to x if and only if (v, x) ∈ Σ. The set of all variables in Σ, denoted as vars(Σ), is defined as vars(Σ) = {v | (v, x) ∈ Σ}. A variable assignment Σ over the set of variables V is called a complete variable assignment if and only if vars(Σ) = V. Otherwise, it is called a partial variable assignment. The set of all complete variable assignments over V is denoted as S(V).An action a over a set of variables V is a pair (pre(a), eff (a)), where pre(a) is a variable assignment over V representing the precondition of the action a, and eff (a) is a non-empty set of variable assignments over V representing the set of possible effects of the action a. The action a is called deterministic if and only if |eff (a)| = 1. A determinisation of an action a with respect to the effect e ∈ eff (a), denoted as a d e , is an action a d e = (pre(a), {e}). The set of variables related to an action a, denoted vars(a), is the set of variables vars(pre(a)) ∪ e∈eff (a) vars(e). We say that an action a is applicable in a variable assignment Σ 110 if and only if pre(a) ⊆ Σ. The set of applicable actions in the variable assignment Σ from the set of actions A is denoted as α(Σ, A). The application of a deterministic action a = (pre(a), {e}) in a variable assignment Σ such that pre(a) ⊆ Σ, denoted as γ(Σ, a), is the variable assignmentγ(Σ, a) = {(v, x) ∈ Σ | v /∈ vars(e)} ∪ e (the application is undefined if a is not applicable in Σ). Given a deterministic action a = (pre(a), {e}), we define ha(a) as the variable assignment γ(pre(a), a). It is easy to prove ha(a) is the largest set of facts that satisfies ha(a) ⊆ γ(Σ, a) for all variable assignment Σ that a is applicable in; for this reason, we say that ha(a) necessarily holds after applying action a.The application of a (non-deterministic) action a in a variable assignment Σ, denoted as δ(Σ, a), is the set of variable assignments δ(Σ, a) = {γ(Σ, a d e ) | e ∈ eff (a)}.A FOND planning domain D is a pair ⟨V, A⟩, where V is a set of variables, and A is a set of actions over V. An SAS + planning domain is a pair ⟨V d , A d ⟩, where V d is a set of variables and A d is a set of deterministic actions overV d .A state s of the domain D = ⟨V, A⟩ is a complete variable assignment over the set of variables V.A FOND (resp. SAS + ) planning task T is a triple ⟨D, s I , G⟩, where D = ⟨V, A⟩ is a FOND (resp. SAS + ) planning domain, s I ∈ S(V) is an initial state and G ⊆ F(V) is a variable assignment representing a goal. When we refer to a planning task or a domain, we mean a nondeterministic task or domain, unless stated otherwise.A sequence of deterministic actions π = ⟨a 1 , . . . , a n ⟩, ∀i ∈ N, 1 ≤ i ≤ n : a i ∈ A d , is called a plan for the SAS + planning domain D d . An application of the plan π = ⟨a 1 , . . . , a n ⟩ in a variable assignment Σ, denoted as γ(Σ, π), is a variable assignment γ(Σ, π) = γ(γ(Σ, a 1 ), ⟨a 2 , . . . , a n ⟩).If π = ⟨⟩, then γ(Σ, ⟨⟩) = Σ.A state s is reachable in SAS + planning task T d if and only if there exists a plan π for the domain D d such that γ(s I , π) = s. Otherwise, s is unreachable. We say that T d is solvable if and only if some goal state s G ⊇ G is reachable in the planning task T d . Otherwise, T d is unsolvable. A plan π is called a goal plan of the SAS + planning task T d if and only if γ(s I , π) ⊇ G.A policy Π for the domain D = ⟨V, A⟩ is a binary relation over the set of states S(V) and the set of applicable actions of A, i.e., Π ⊆ {(s, a) | s ∈ S(V), a ∈ α(s, A)}.The set of all states related in Π is the set σ(Π) = {s | (s, a) ∈ Π}. The n-step application of Π in a state s, denoted as δ n (s, Π), is the set δ n (s, Π) = s ′ ∈δ n-1 (s,Π) (s ′′ ,a ′ )∈Π,s ′′ =s ′ δ(s ′ , a ′ ) for n ≥ 1 with δ 0 (s, Π) = {s}. We say that s ′ is reachable from s with a policy Π if and only if s ′ ∈ δ i (s, Π) for some i ≥ 0. We say that s ′ is a terminal state for Π with respect to a state s if and only if s ′ is reachable from s with Π and s ′ / ∈ σ(Π). The set of all terminal states is denoted as τ (Π, s). Note that our policy definition as a binary relation (i.e., more actions might be associated with a single state) straightforwardly supports a combination of two (or more) policies together by a union.A policy Π is called a weak goal policy for T if and onlyif τ (Π, s I ) ∩ {s G ∈ S(V) | G ⊆ s G } ̸ = ∅. A policy Π is called a strong goal policy for T if and only if τ (Π, s I ) ⊆ {s G ∈ S(V) | G ⊆ s G }and for each s ∈ σ(Π) at least one state that satisfies the goal G is reachable by Π. Note that our definitions coincide with Def. 2.10 of Cimatti et al. (2003) . A task T is called solvable if and only if there exists a weak goal policy for task T . Otherwise, it is called unsolvable.Let Ψ be a set of pairs (Σ, a), where Σ is a variable assignment, and a ∈ A is an action that is applicable in Σ. The set Ψ is called an implicitly-defined policy for the domain D. We say that Ψ implicitly defines the policy Π if and only if Π = (Σ,a)∈Ψ {(s, a) | s ∈ S(V), Σ ⊆ s}.Action reversibility, concerning the problem of whether the effects of an action can be undone by means of other actions, has been studied in deterministic settings (see Eiter, Erdem, and Faber (2008) ; Daum et al. (2016) ; Morak et al. (2020) ).In our work, we introduce the concept of action reversibility for non-deterministic actions in the FOND planning formalism. Non-deterministic action reversibility, in contrast to the deterministic variant, has to deal with non-deterministic actions-not only those whose effects we try to undo, but also those that have to be considered in the "reverting" process. In FOND planning, we usually consider two types of solutions, weak and strong (Cimatti et al. 2003) . For a weak solution, we have a chance to achieve the goal if everything "goes well", while for a strong solution, there is a guarantee that the goal will eventually be achieved. We adopt these notions to establish weak and strong action reversibility such that for weak reversibility we require that there is a chance to undo all action effects, while for strong reversibility this has to be guaranteed. Note that in this paper we consider strong cyclic solutions that guarantee success if each effect of each non-deterministic action has a nonzero chance to oc-cur if the action is applied (in other words, we consider the fairness assumption) (Aminof, Giacomo, and Rubin 2020) .Inspired by the work of Morak et al. (2020) , we classify the notion of (non-deterministic) action reversibility into three categories, S-reversibility, uniform reversibility and universal reversibility, which will be now introduced.Naturally, it might be useful to study whether an action a is reversible in some subset of states S ⊆ S(V). That is, for each state from S in which a is applicable, we have to find a sequence of other actions that undoes the effects of a. This property is called S-reversibility (Morak et al. 2020) .To address non-deterministic actions, we introduce the notions of weak S-reversibility and strong S-reversibility, in the context of work of Cimatti et al. (2003) as described above. Informally speaking, we call an action weakly Sreversible if, in each state from S in which the action is applicable, the action's effects can be undone by a sequence of (non-deterministic) actions while assuming the "correct" action effect always occurs. We call an action a strongly Sreversible if, in each state s ∈ S where a is applicable, the action's effects are eventually undone by some policy Π s having precisely s as its terminal state.We also establish the notion of action S-irreversibility. It refers to a situation in which there is no way to undo any of the action's effects (even by means of a weak solution). The following definition formalises the above notions.Definition 1. Let D = ⟨V, A⟩ be a planning domain, a ∈ A be an action, and S ⊆ S(V) be a set of states of the domain D. The action a is called weakly (resp. strongly) Sreversible in the domain D if and only if for each state s ∈ S, pre(a) ⊆ s, there exists a policy Π for the domain D such that for each s ′ ∈ δ(s, a) it holds that s ∈ τ (Π, s ′ ) (resp. {s} = τ (Π, s ′ ) and for each state s ′′ that is reachable by Π from the state s ′ it holds that s is reachable by Π from s ′′ ). The action a is called S-irreversible in the domain D if and only if for each state s ∈ S, pre(a) ⊆ s, there does not exist a policy Π for the domain D such that for each s ′ ∈ δ(s, a) it holds that s ∈ τ (Π, s ′ ). As the application of both policies may eventually end in a broken window, neither of them is a strong reverse policy for the above set of states. Intuitively, close-window action is irreversible in any state in which the action is applicable since no action can "fix" the broken window. Now, consider the same domain, except that there are two variants of the former close-window . First, close-window -draught-free, which cannot break the window, and on top of the former action requires that the door is closed; and second, close-window , on top of the former action requires that the door is open, with the same effects as the former. In such a domain, the policy that applies close-door if the door is not closed and close-window -draught-free if the window is not closed (and the door is) is a strong {{(window , closed ), (door , closed )}}-reverse policy for the action vent.A special case of S-reversibility is uniform reversibility, which refers to the existence of a common solution concept that can undo the effects of the action in question, for each state of S in which the action can be applied (Morak et al. 2020) , i.e. the same solution concept reverses the effects of the action in question applied in any state from the set S where the action is applicable. The following definition formalises the notions of weak and strong uniform Sreversibility for non-deterministic actions. Definition 2. Let D = ⟨V, A⟩ be a planning domain, a ∈ A be an action, S ⊆ S(V) be a set of states of the domain D. The action a is called weakly (resp. strongly) uniformly Sreversible in the domain D if and only if exists policy Π for the domain D such that for each state s ∈ S, pre(a) ⊆ s, it holds that for each s ′ ∈ δ(s, a) we have s ∈ τ (Π, s ′ ) (resp. {s} = τ (Π, s ′ ) and for each state s ′′ that is reachable by Π from the state s ′ it holds that s is reachable by Π from s ′′ ).Having a single policy that can undo the effects of an action in all relevant situations (i.e. states from S in which a is applicable) is practical as we do not need to consider multiple state-specific policies. Analogously to the notion of reverse plan in classical planning (Morak et al. 2020) , we define the notion of reverse policy. Definition 3. Let D = ⟨V, A⟩ be a planning domain and a ∈ A be an action. A policy Π for the domain D is called a weak (resp. strong) S-reverse policy for the action a if and only if the action a is weakly (resp. strongly) uniformly S-reversible by the policy Π. Universal reversibility is a specific case of S-reversibility covering all states, i.e. S = S(V). Informally speaking, if an action is universally reversible (or irreversible), its effects can always (or never) be undone. Definition 4. Let D = ⟨V, A⟩ be a planning domain and a ∈ A be an action. The action a is called weakly (resp. strongly) universally (uniformly) reversible in the domain D if and only if the action a is weakly (resp. strongly) (uniformly) S(V)-reversible in the domain D. The action a is called universally irreversible in the domain D if and only if the action a is S(V)-irreversible in the domain D. Example 3. Consider the domain of Example 1. The states with a closed window and the door being open or closed are the only states where the action vent is applicable. Recall that there is a weak reverse policy for any such state. Therefore, the action vent is weakly universally reversible. The common policy of Example 2 proves the weak universal uniform reversibility of the action vent.Example 4. Now, as an example of strong universal uniform reversibility, let us consider a domain of well-known Transport domain (Helmert, Do, and Refanidis 2010) . In the domain, packages have to be transported from one location to another through various vehicles. Packages can be loaded and unloaded into vehicles without restrictions and the loading or unloading process can fail, leaving the package in its former position (at the location or inside the truck, respectively). The actions of the load and unload "families" are strongly universally uniformly reversible as if the package is successfully loaded or unloaded, respectively, we can always undo it by unloading, or loading the package back.Having defined the relevant notions, we will first establish some theoretical properties that follow from our definitions.It can be easily derived that weak or strong (uniform) S-(ir)reversibility implies weak or strong (uniform) S ′ -(ir)reversibility if S ′ ⊆ S. Weak or strong uniform S-reversibility implies weak or strong S-reversibility, and strong (uniform) S-reversibility implies weak (uniform) S-reversibility. Furthermore, we can observe that if an action is weakly (resp. strongly) S 1 -and S 2 -reversible, then it is weakly (resp. strongly) (S 1 ∪ S 2 )-reversible. However, for uniform reversibility such an implication does not hold in general.A more interesting property of any S-reverse policy is that it cannot assign any action to any state of S in which the action the policy is reverting is applicable.Example 5. Consider a domain that describes the result of coin tossing with the only variable with domain {heads, tails} and toss-coin (without preconditions). The action has a strong universal uniform {(coin, head)}-reverse policy that applies toss-coin as long as the state is {(coin, tails)}.The same holds symmetrically for tails. Hence, the action is weakly and strongly universally reversible. However, there is no weak or strong universal reverse policy, since, e.g., the policy of union of mentioned policies has no terminal state (it relates each state with some action). Proposition 6. Let D = ⟨V, A⟩ be a planning domain, Π be a policy for the domain D, and a ∈ A be an action. If Π is a weak (resp. strong) S-reverse policy for the action a, then{s | s ∈ S, pre(a) ⊆ s} ∩ σ(Π) = ∅.Proof. Proof by a contradiction. Assume that{s ′ | s ′ ∈ S, pre(a) ⊆ s ′ } ∩ σ(Π) ̸ = ∅. Then, there is a state s ∈ {s ′ | s ′ ∈ S, pre(a) ⊆ s ′ } ∩ σ(Π).According to the assumption and since {s} ⊆ S, the action a is weakly (resp. strongly) 375 uniformly {s}-reversible by the policy Π. Since s is also in σ(Π), s cannot be a terminal state of the policy Π. Therefore, for each s ′ ∈ δ(s, a) it holds that s / ∈ τ (Π, s ′ ). This is in contradiction with the assumption of Π being a weak (resp. strong) S-reverse policy for the action a.An important consequence of Proposition 6 concerns universal uniform reversibility. It simply follows that when the set S is equal to the set S(V), then the situation of Proposition 6 can be simplified to the fact that the universal reverse policy can contain only the states in which the action we 385 want to reverse is not applicable.In contrast to deterministic planning which deals with action sequences, policies have a different structure as they assign appropriate actions to apply in relevant states. This property gives grounds to raise a question of how combin-390 ing two policies affects S-reversibility of non-deterministic actions. In the case of weak reversibility, in which reverse policies are constructed along a sequence of actions, we can safely combine policies as long as the other policy does not compromise the assumption of Proposition 6.Theorem 7. Let D = ⟨V, A⟩ be a planning domain, a ∈ A be an action, Π 1 be a weak S-reverse policy for the action a and Π 2 be a policy for the domain D. The policy Π 1 ∪ Π 2 is a weak S-reverse policy for the action a if and only if{s | s ∈ S, pre(a) ⊆ s} ∩ σ(Π 2 ) = ∅. 400Proof. The "if" part is proven by a contraposition. Let us assume that there is some states ′ ∈ {s | s ∈ S, pre(a) ⊆ s} ∩ σ(Π 2 ). Then, as σ(Π 2 ) ⊆ σ(Π 1 ∪ Π 2 ), s ′ ∈ {s | s ∈ S, pre(a) ⊆ s} ∩ σ(Π 1 ∪ Π 2 ).That violates the assumption of Proposition 6 and hence the policy Π 1 ∪ Π 2 cannot be a 405 weak S-reversible policy for the action a.For the "only if" part, we can observe that extending a policy (by adding a pair of some state and some action) does not affect the reachability of any state that was reachable before (including the terminal states). From the assumption 410 {s | s ∈ S, pre(a) ⊆ s} ∩ σ(Π 2 ) = ∅ and the fact that {s | s ∈ S, pre(a) ⊆ s}∩σ(Π 1 ) = ∅ (see Proposition 6), we get {s | s ∈ S, pre(a) ⊆ s}∩σ(Π 1 ∪Π 2 ) = ∅. Therefore, all states {s | s ∈ S, pre(a) ⊆ s} are terminal with respect to a given starting state for the policy Π 1 ∪ Π 2 (see the definition 415 of terminal states). Hence, the policy Π 1 ∪ Π 2 is a weak Sreverse policy for the action a.Regarding the strong S-reverse policy, since every strong S-reverse policy is also a weak S-reverse policy, the same conditions apply in this case as well. However, the condi-420 tions of Theorem 7 are not sufficient since, if the second policy assigns an action to a state that is considered by the first strong S-reverse policy, the union of such policies could introduce a different terminal state; and this would violate the definition of strong S-reverse policy. Hence, to combine 425 a strong S-reverse policy with a second one, the latter should not interfere with the former, as summarised in the following theorem.Theorem 8. Let D = ⟨V, A⟩ be a planning domain, a ∈ A be an action, Π 1 be a strong S-reverse policy for the action a and Π 2 be a policy for the domain D. If σ(Π 2 ) ∩ {s | s ∈ S, pre(a) ⊆ s} = ∅ and σ(Π 1 ) ∩ σ(Π 2 ) = ∅, then Π 1 ∪ Π 2 is a strong S-reverse policy for the action a.Proof. Let s be a state s ∈ {s ′′ | s ′′ ∈ S, pre(a) ⊆ s ′′ }. From the assumption of Π 1 being a strong S-reverse policy 435 for the action a, we get {s} = τ (Π 1 , s ′ ) for all s ′ ∈ δ(s, a). Let D 0 be a set of reachable states from the state s ′ by policy Π 1 . The set can be divided into two disjoint sets D 0 ∩ σ(Π 1 ) andD 0 \ σ(Π 1 ) = τ (Π 1 , s ′ ) = {s}.Now, we show that if we add an arbitrary state-action pair (s ′′ , a ′′ ) ∈ Π 2 to the policy Π 1 , the set of reachable states D 0 from the state s ′ by the extended policy remains unchanged. Therefore, if the policy Π 1 is extended by any state-action pair (s ′′ , a ′′ ) ∈ Π 2 , i.e.,Π ′ 1 = Π 1 ∪ {(s ′′ , a ′′ )}, D 0 remains unchanged, because s ′′ ̸ ∈ D 0 ∩ σ(Π ′ 1 ) (due 445 to the fact that σ(Π 1 ) ∩ σ(Π 2 ) = ∅) and neither is in D 0 \ σ(Π ′ 1 ) = τ (Π 1 , s ′ ) = {s} (due to the fact that σ(Π 2 ) ∩ {s ′′′ | s ′′′ ∈ S, pre(a) ⊆ s ′′′ } = ∅).Therefore, we can derive that D 0 remains the same for the combined policy Π 1 ∪ Π 2 . Furthermore, we can see that no other state could become terminal since no other state became reachable, i.e., τ (Π 1 ∪Π 2 , s ′ ) ⊆ {s}. From Theorem 7 we know s ∈ τ (Π 1 ∪ Π 2 , s ′ ). Hence, Π 1 ∪ Π 2 is a strong S-reverse policy for the action a.A practical consequence of the above theorems is that they 455 provide conditions under which we can merge two reverse policies into one. If Π 1 is a weak (resp. strong) S 1 -reverse policy for some action a and Π 2 is a weak (resp. strong) S 2 -reverse policy for the action a, Π 1 ∪ Π 2 is a weak (resp. strong) (S 1 ∪ S 2 )-reverse policy for a if the conditions of Theorem 7 (resp. Theorem 8) are satisfied. We note that the possibility of combining policies is not applicable for the deterministic case in which reverse plans are considered sequences of actions (Eiter, Erdem, and Faber 2008; Morak et al. 2020) .termine universal uniform reversibility (for deterministic actions), it is sufficient to consider only actions that contain only variables present in the precondition of a "to be reversed" action. Such a property is practically very useful, as it usually (considerably) simplifies the problem.However, in the non-deterministic context, the theoretical findings of Chrpa, Faber, and Morak (2021) can only be partially adopted. Due to the different nature of policies, we show that allowing only actions operating over the set of variables present in the precondition of a "to be reversed" action while looking for weak or strong universal reverse policies is a sufficient but not necessary condition. In other words, if a strong or weak reverse policy containing only "restricted" actions is found, then such a policy is universal, but the opposite implication does not generally hold (as we argue later in this section).At first, we show that for an action to be strongly universally uniformly reversible, its effects may modify only variables that are also present in its preconditions. Note that an analogous claim also holds for the deterministic case (Chrpa, Faber, and Morak 2021) . The intuition behind the claim is that if a variable is present in action's effects but not present in its precondition, then multiple states (each refers to a different value of the variable while assuming that the variable can have at least two different values) "collapse" into a single state referring to the value of the variable present in the action's effects.Lemma 9. Let D = ⟨V, A⟩ be a planning domain such that ∀v ∈ V : |dom(v)| ≥ 2 and a ∈ A be an action. If e∈eff(a) vars(e) ⊈ vars(pre(a)), then the action a is not strongly universally uniformly reversible.Proof. Assume there exists a strong universal reverse policy Π for the action a.W.l.o.g., let e ∈ eff (a) be an action effect for which there exists v ∈ vars(e) \ vars(pre(a)). Since |dom(v)| ≥ 2, there exist two distinct states s 1 , s 2 in which a is applicable and which differ in the value of the variable v. As states s 1 and s 2 differ only in the value of the variable v and since the effect e modifies v, we haves ′ = γ(s 1 , a d e ) = γ(s 2 , a d e ).As we initially assumed, Π is a strong universal reverse policy for the action a and this implies τ (Π, γ(s 1 , a d e )) = {s 1 } and τ (Π, γ(s 2 , a d e )) = {s 2 } (see Definition 2). However, since s ′ = γ(s 1 , a d e ) = γ(s 2 , a d e ), we get τ (Π, s ′ ) = {s 1 , s 2 }. This is in contradiction with s 1 ̸ = s 2 .In the case of weak universal uniform reversibility, an analogous claim cannot be made. For a weak universal reverse policy Π ′ , we can derive an analogous claim as we did in the proof of Lemma 9, that is, τ (Π ′ , s ′ ) = {s 1 , s 2 }. Such a claim does not contradict the definition of weak uniform reversibility, as both cases, that is, s 1 ∈ τ (Π ′ , s ′ ) and s 2 ∈ τ (Π ′ , s ′ ), might be satisfied.As an example, consider a bowling domain, with a variable bowled with the domain {true, false} and an action that resets bowling pins that restores any combination of pins being down or standing to all pins standing, and that sets bowled to false. The action is applicable if and only bowled is true. The action's effects contain variables of pins that are not in its preconditions. There is another action that rolls the bowling ball, without any preconditions, and which can non-deterministically push over none, some, or all standing pins, and always sets bowled to true. The rolling action can weakly universally uniformly undo the reset action, as each state before the reset can be obtained, but it cannot strongly universally uniformly undo the reset action, as no state before the reset can be guaranteed to be obtained.The following theorem shows that if we generate a weak or strong universal reverse policy in a restricted state and action space that takes into account only variables that are present in the precondition of "to be reversed" action, then such a reverse policy is universal. Theorem 10. Let D = ⟨V, A⟩ be a planning domain, a ∈ A be an action such that e∈eff(a) vars(e) ⊆ vars(pre(a)). If exists an implicitly defined policy Ψ for the domain D such that ∀ (Σ ′ , a ′ ) ∈ Ψ : vars(Σ ′ ) ⊆ vars(pre(a)) and that the policy Π implicitly defined by Ψ is weak (resp. strong) Sreverse policy for the action a such that {s | s ∈ S, pre(a) ⊆ s} ̸ = ∅ and ∀(s ′ , a ′ ) ∈ Π : vars(a ′ ) ⊆ vars(pre(a)), then Π is a weak (resp. strong) universal reverse policy for the action a.Proof. Let s ∈ S be a state such that pre(a) ⊆ s and Π be a weak (resp. strong) {s}-reverse policy for the action a implicitly defined by Ψ.To show that Π is a weak (resp. strong) universal reverse policy for the action a, we need to prove that for each state s ′ ∈ S(V) such that pre(a) ⊆ s ′ the policy Π is also a weak (resp. strong) {s ′ }-reverse policy for the action a. If there does not exist any other state s ′ ∈ S(V) such that pre(a) ⊆ s ′ and s ̸ = s ′ , then the policy Π is a weak (resp. strong) universal reverse policy for the action a. If there exists such a state s ′ , then we can observe that s ′ differs from s only in values of variables that are not part of vars(pre(a)) (otherwise it would compromise the applicability of a).Assumption e∈eff (a) vars(e) ⊆ vars(pre(a)) states that any effect e of the action a can modify only the variables present in pre(a). Therefore, the values of the variables of V \ vars(pre(a)) remain unchanged after the application of the action a regardless of what effect takes place.As for any state-action pair (s x , a x ) ∈ Π it is the case that vars(a x ) ⊆ vars(pre(a)), none of the actions of the policy Π can change any variable from V \ vars(pre(a)) or require a specific value of any of such variables.From the assumption stating ∀ (Σ ′ , a ′ ) ∈ Ψ : vars(Σ ′ ) ⊆ vars(pre(a)) it holds that each variable assignment Σ ′ does not contain variables from V \ vars(pre(a)). Therefore, the policy Π behaves independently on values of variables V \ vars(pre(a)) which means that Π yields the same outcome (apart from the values of the variables of V \ vars(pre(a)) that remain constant) from both states s and s ′ .According to the other theorem assumption, if we apply Π in any state in δ(s, a), we may (resp. have to) return to the state s, which is terminal. As we have shown that Π and a can modify only variables present in pre(a), we can derive that for each state s ′ ∈ S(V) in which a is applicable, Π is weak (resp. strong) {s ′ }-reverse policy for a. Hence, the policy Π is a weak (resp. strong) universal reverse policy for the action a.In contrast to deterministic universal uniform reversibility (Chrpa, Faber, and Morak 2021) , the opposite implication, i.e. there is a weak/strong universal reverse policy for an action if Theorem 10's assumption is true, does not hold.Regarding weak universal uniform reversibility, Lemma 9 indicates that a "to be reversed" action might modify variables that are not present in its precondition and still be (potentially) weakly universally uniformly reversible. This observation can also be applied to other actions that are part of the weak universal reverse policy. As an example, we might have an action whose non-deterministic effects contain all states in which the "to be reversed" action is applicable.In the strong universal uniform reversibility case, the issue 600 with the opposite implication of Theorem 10 is in the possibility of merging policies. If the conditions of Theorem 8 are satisfied, we can merge two strong reverse policies to obtain another strong reverse policy applicable to the union of states of the individual policies. Hence, it is possible to 605 obtain a strong universal reverse policy by combining more specific strong reverse policies.As an example, let us have a domain where an agent can move between three locations -A, B, C. However, there is another variable that determines whether the agent can move 610 from B to A, or from B to C. Moving from A to B and from C to A is unrestricted. Depending on the value of the other variable, we undo the effects of moving from A to B by either moving directly back to A, or moving through C. These two reverse policies can be combined, as the states they are 615 operating over are disjoint (because of different values of the other variable). The combined policy is a strong universal reverse policy for the action that moves us from A to B. As the other variable is involved in the policy and there is no other strong universal reverse policy, there is no Ψ of Theorem 10. 620Theorem 10 provides us with a blueprint on how classical (respectively, FOND planning) can be leveraged in finding weak (resp. strong) universal reverse policies.The following theorem shows how a weak universal re-625 verse policy can be generated by means of classical planning by specifying multiple classical planning tasks (one for each determinisation of the "to be reversed" action). Since, for weak reversibility, we need only to consider the "correct" effects of actions, we replace each non-deterministic action 630 with its respective determinisations. We consider only determinisations that operate only on the variables present in the precondition of the "to be reversed" action. Proof (Sketch). Each plan π e = ⟨a e1 , . . . , a en ⟩ can be transformed into a policy Π e = {(γ(ha(a d e ), ⟨a e1 , . . . , a ei-1 ⟩), a ei ) | i ∈ N, 1 ≤ i ≤ n}. Since for each effect e i determined by the corresponding determinisation a ei it is the case that vars(e i ) ⊆ vars(pre(a)), we can observe that 645 none of the variables other than vars(pre(a)) is modified in the process. Also, each determinisation a d e of the action a modifies only the variables of vars(pre(a)). All policies resulting from transformed plans that are solutions of the SAS + tasks for each determinisation a d e contain pre(a) 650 as one of the terminal states. By combining all the policies into one (meeting the conditions of Theorem 7) we ob-tain an implicitly-defined policy for the domain ⟨V, {(a ′ ) d e | a ′ ∈ A, e ∈ eff (e), vars((a ′ ) d e )} ∪ {a}⟩. If we replace the determinisations by their corresponding stochastic actions of A, we obtain an equivalent (from the perspective of weak reversibility) implicitly-defined policy Ψ for the domain ⟨V, A⟩. Then, a policy implicitly defined by Ψ is a weak universal reverse policy for the action a.A similar claim can be made about strong universal uniform reversibility, albeit in the context of FOND planning, since strong universal uniform reversibility needs to guarantee that the only terminal state is the state in which a "to be reversed" action is applied. The compilation of the problem of finding a strong universal reverse policy to a FOND planning task is analogous to the weak universal uniform reversibility case. In addition, to be able to merge the found policies, their sets of related states have to be pairwise disjoint, as Theorem 8 suggests. Proof (Sketch). It can be observed that each policy Π e is an implicitly defined policy that strongly universally uniformly reverses the determinisation a d e . These policies can be combined (since the sets of related states are pairwise disjoint) according to Theorem 8. Hence, the resulting policy implicitly defined by e∈eff (a) Π e is a strong universal reverse policy for the action a.We also consider the possibility of identifying universal irreversibility. The idea is derived from the work of Chrpa, Faber, and Morak (2021) that concerns universal irreversibility of deterministic actions. Informally speaking, if for some effect of a non-deterministic action, we cannot reachieve the precondition of that action, then the action is universally irreversible. We can "project" the problem onto the variables related to a "to be reversed" action a, i.e., vars(a). In contrast to the above theorems, we do not discard actions that also operate on the other variables, but we project their preconditions and effects to vars(a).Let Σ be a variable assignment over the set of variables V and let V ′ ⊆ V be a set of variables. The projection of Σ on the set of variables V ′ is a variable assignment vars(e) ⊆ vars(pre(a)) (⊆ or ⊈), and "?" indicates "no class of action (ir)reversibility was identified". The column labelled as "FM" represents a proven weak universal uniform reversibility, where uniform strong reverse policies were found for all determinizations, but due to the condition on empty related state intersection, we were unable to merge them. "¬S" stands for actions which are proven not to be strongly universally uniformly reversible.Σ |V ′ = {(v, x) ∈ Σ | v ∈ V ′ }.Proof. If the specified SAS + planning task is unsolvable, it means that the precondition of a is unreachable from some of its effects. Since we focus only on a subset of variables, the applicability of actions is more optimistic than in the 710 general case. So, if an abstract task created by projecting into a subset of variables is unsolvable, then the original task is unsolvable as well (Helmert, Haslum, and Hoffmann 2007) . Hence, we can derive that if for any determinisation of a, the specified SAS + planning task is unsolvable, then a is univer-715 sally irreversible.The section presents empirical evidence on the existence of investigated phenomena in many benchmark domains.Based on the claims of previous sections, we have designed 720 and performed the experiments for the resolution of investigated classes of non-deterministic action reversibility.We have evaluated our approaches for non-deterministic action reversibility on 20 FOND domains of two sets of benchmarks: one from the repository of the PRP plan-725 ner (Muise, McIlraith, and Beck 2012; Muise, Belle, and McIlraith 2014; Muise, McIlraith, and Belle 2014) , and second set proposed by Geffner and Geffner (2018) ; viz., Acrobatics (A.), Beam Walk (BE. W.), Blocks World (BL. W.), Bus Fare (B. F.), Climber (C.), Doors (D.), Earth Observation (E. O.), Elevators (EL.), Exploding Blocks World (E. BL.), Faults (FA.), First Responders (F. R.), Forest (FO.), Islands (I.), Miner (M.), River (R.), Spiky Tire World (S. TI.), Tire World (TI.), Tire World Truck (TI. TRU.), Triangle Tire World (TRI. TI.), and Zeno Travel (Z.).For each action, we initially check whether they satisfy the condition e∈eff (a) vars(e) ⊆ vars(pre(a)). If the action does not satisfy the condition, we use Theorem 13 to check its universal irreversibility. Based on the result, we either conclude "universally irreversible" or "we have not identified anything, besides the action is not strongly uniformly universally reversible" (since the action does not satisfy the conditions, from Theorem 10 we know that the action is not strongly universally uniformly reversible; Theorem 11 is inapplicable and Theorem 13 is an implication only). If the action satisfies the initial condition, we check if it is weakly universally uniformly reversible (which is a necessary condition for strong reversibility) by leveraging Theorem 11. Based on the result, strong universal uniform reversibility or universal irreversibility is checked using the respective Theorems 12 and 13, respectively. If all of them "fail", we conclude that "we have not identified anything", which is denoted in Table 1 as "?". To check weak reversibility and irreversibility, we use the LAMA planner (Richter and Westphal 2010) and to check strong reversibility, we use the PRP planner (both planners are built on top of the Fast Downward planner framework (Helmert 2006)) .All experiments 1 ran on a machine with an Intel ® Core™ i7-7700HQ processor and 32 GB of DDR4 RAM operating at a frequency of 2400 MHz. The operating system was Ubuntu 22.04.3 in WSL 2 (version 2.0.9.0) of Windows 10.Table 1 provides an overview of what actions have been identified as (weakly or strongly) universally uniformly reversible, universally irreversible, or unidentified.The results indicate that the weakly universally uniformly reversible actions identified by Theorem 11 are likely also identified as strongly universally uniformly reversible by Theorem 12, since this happened in the vast majority of situations in our experiments. The only exceptions are three actions for which we have found strong universal uniform reverse plans for each determinisation (see Theorem 12), but we were unable to merge them into a general policy since the reverse plans had conflicting states.On average, we were able to identify some class of (ir)reversibility in approximately 68.30±33.64% of actions, with the lowest relative amount of approx. 2.63% in the BL. W. domain, while in the BE. W., B. F., C., E. O., I., R. and TRI. TI. domains all the actions were identified in some class. In domains such as FA., FO. or E. BL., most of the actions did not satisfy the "⊆" condition and hence could not be identified as weakly universally uniformly reversible through our theoretical study. Overall, on average, approx. 60.91 ± 40.13% of actions satisfied the "⊆" condition on action's preconditions. In an 1 We plan to release the code if the paper gets accepted."average" case, approx. 33.49% of actions were identified as universally irreversible, 34.81% as weakly universally uniformly reversible, 32.39% as strongly universally uniformly reversible, and 31.70% of actions remained undetermined (columns labeled with the question mark in Table 1 ) out of 790 which 23.88% is proven not to be strongly universally uniformly reversible (with respect to the total number of actions). The relatively high number of undetermined actions is caused by the requirement for universality and uniformity. Although these requirements are practically desirable, ac-795 tions might not always conform to them. Also, as we have shown, the methods are not theoretically complete and hence some cases might not have been identified (as we observed in the case of universal irreversibility in TI. domain).On average, the measured mean compilation time per ac-800 tion in a domain is 7.037 ± 5.748 milliseconds for weak, 7.028 ± 5.772 milliseconds for strong, and 9.113 ± 5.715 milliseconds for irreversibility reformulation with minimal, resp. maximum values, 0.994, 0.846, 3.031 milliseconds, resp. 17.337, 17.743, 22.441 milliseconds. As for run-805 times for solving the reformulations, we have measured the time required to find a plan or policy, or to decide the (un)solvability of an abstract SAS + planning task for all determinisations. The mean runtimes are 156.111±60.408, 47.712±18.495 and 186.015±81.118 milliseconds to deter-810 mine weak universal uniform reversibility, strong universal uniform reversibility and universal irreversibility according to Theorems 11, 12 and 13, respectively. Minimum values are 118.091, 22.970, 120.439, and maximum values are 462.132, 87.549, and 711.832 milliseconds, respectively. 815 The results show the practical viability of our methods.In this paper, we have conceptualised the notions of weak and strong reversibility of non-deterministic actions in FOND planning. These notions are inspired by weak and 820 strong plans in FOND planning (Cimatti et al. 2003 ) and share the same meaning, i.e., weak reversibility refers to a possibility of undoing all effects of an action, while strong reversibility refers to the certainty of undoing all effects. We specifically focused on universal uniform cases that refer to 825 the fact that effects of a non-deterministic action can always be undone by the same reverse policy. We proposed methods based on compiling the weak and strong universal uniform reversibility problem into classical or FOND planning, respectively, and we proposed a method for determining uni-830 versal irreversibility via classical planning.An experimental evaluation that we conducted on existing FOND benchmarks has shown that we were able to identify a type of reversibility for about 56.32% actions and the running time of any of the methods was in the lower hundreds of 835 milliseconds on average. These results demonstrated practical usefulness of our methods in spite of their narrow focus.In the future, we plan to investigate computational complexity of proposed classes of non-deterministic action reversibility. We also plan to focus on more general sub-840 classes of non-deterministic action reversibility (e.g. strong S-reversibility) and we would also like to generalise the results for lifted representation of FOND planning tasks. 
 
 Appendix:  


Decision: This paper considers action reversibility of non-deterministic actions, distinguishing weak and strong reversibility, and propose methods how these notions can be tested by means of compilation to classical or FOND planning.
Although the concept of action reversibility is well-understood for classical planning, it is a novel and interesting contribution to study it for FOND planning. This paper is a solid and original first step but its long-term significance is hard to predict (there is no motivating application). The clarity of the paper is overall good but should be improved in some details. The reviewers where satisfied with the rebuttal.

Pros:
- high novelty
- reversibility present in benchmark domains

Cons:
- unclear usefulness of the new notions
- computational complexity left for future work

Reviews: review: strength_weakness: strength_weakness: - The algorithms are not properly specified. The authors should provide pseudo-codes instead of defining solutions by Theorem 11 (for weak reversibility detection) and Theorem 12 (for strong reversibility detection). 

- Experiments are run over specific instances of each domain without any explanation of why those instances were selected for each domain.

- The concepts "projection of a set Sigma of variable assignments" or "projection of an action" only appears in the paragraph before the experiments and are not properly explained. Thus Theorem 13 is not easy to understand since  it envolves determinization and projection.

- Some domains listed in lines 729-735 are listed in Table 1 with different names. E.g.: Tire World Truck (TI. TRU.) and Tire World (TRI. TI.).

- Typo: In Theorem 11 instead of “e \in eff(e)” should be  “e \in eff(a)”
- Typo: Line 750  “respective Theorems 12 and 13, respectively.”
questions: questions: 1. A FOND planner can either return a strong, strong-cyclic or "weak policy". Thus, if the FOND planner returns a weak policy can we say that the action is weakly reversible? This would be a theorem not cover by Theorems 11 or 12?

2. For the analyzed domains, it was observed that the majority of actions classified as "weakly universally uniformly reversible" are also classified as "strongly universally uniformly reversible". Is this a particular characteristic of the FOND benchmark domains analysed? If so, could be this characteristic responsable for making possible for the FOND planners to find strong cyclic solutions? It could be an interesting result of this study if you recognize that the most difficult problems for the state-of-the-art FOND planners are the ones with no (or few) strong reversible actions. What do you think about this?

3. Line 628: "Since for weak reversibility, we need only to consider the “correct” effects of actions, we replace each non-deterministic action with its respective determinisations." What you mean by correct? How the algorithm recognize the correct effect of an action? 

4. Theorem 12, Line 670:  "... If for each determinisation  there exists a strong goal policy ..." It could be also a strong-cyclic policy?
strength_weakness: strength_weakness: As for the motivations of the work, I am not sure that the addressed topic is “an important research question”, as the authors write in the introduction (it seems to me that most of the contributions in the literature come from a restricted group of people); surely, it is  topic of interest.

The notation introduced in Section 2 (Preliminaries) is very heavy and not easy to deal with: the single notions are fairly clear, but there are a number of them, and it is not easy to master them all. 

From a technical point of view, I did not detect any major flaw. A significant limitation is that complexity issues are not addressed at all (they are left to future work).

The running example looks quite elementary/artificial, and thus not fully convincing.

The quality of the writing is globally satisfactory. There is some punctuation to fix here and there, e.g,, to replace “i.e.” by “i.e.,” 

Minor/specific points

Line 145: has {\cal t}^d been explicitly introduced?

Lines 156-158: please check whether everything is ok.

Page 3, Defs. 1 and 2: I would point out that Def. 1 differs from Def. 2 for the exchange of quantifiers: “for each state there exists a policy ..” is replace by: “ there exists a policy such that for each state ..”

Line 332: please check and possibly rewrite the sentence: “let us consider a domain of well-known Transport domain”.

Lines 356-357: please check and possibly rewrite the sentence: “in which the action the policy is reverting”.

Line 359: please check and possibly rewrite the sentence:  “with the only variable with domain”.

Line 845, Giacomo must be replaced by “De Giacomo”.
questions: questions: Taking into account also the outcomes of the experiments, I ask the authors (and myself) whether the proposed notions of reversibility are the most useful/appropriate ones. As a matter of fact, in the conclusion the authors mention the intention of investigating more general classes off non-deterministic action reversibility.

As for the adopted notation/formalism, I wonder whether there are any more compact and natural representations to be used, e.g., automata-based ones.
strength_weakness: strength_weakness: Personally, I see no major weaknesses in the paper, but I do have some minor comments and points for consideration for improving the paper, as follows.

# Minor Comments and Points of Consideration:

C1. The preliminary section (Preliminaries) is really good, but you don't define strong cyclic policies for FOND Planning. Please, include the definition of strong cyclic polices as part of the preliminary section, since it is part of the types of FOND Planning solutions you consider for action reversibility.

C2. In Line 190: What do you mean by the "reverting process"? Do you mean action reversibility? Please, clarify that.

C3. In Line 220: where you define that an action is weakly $S$-reversible, what do you mean by "assuming the "correct" action effect always occurs"? Is that related to (one of) the effects (outcomes) of non-deterministic actions that are able to undo an action? If so, please, clarify that.

C4. What is the difference between Definitions 1 and 2? It seems to me that they broadly define the same thing. Please, clarify that.

C5. In your examples, it would be good if you use a different notation for facts (e.g., $fact$), actions (e.g., $\texttt{action}$), and policies (e.g., $\{fact1, fact2\}: \texttt{action}$). That would improve the readability of the examples. 

C6. In Example 2, the action shouldn't be $close-door$ instead of "door-close"? 

C7. In Theorem 8, you define $D^0$ as a set of reachable states from the state $s'$. It would be more intuitive to use $S^{s'}$ instead of $D^0$ because $D$ refers to a planning domain.

C9. With respect to your experiments, I have the following (minor) concerns:
- Table 1 could be placed where you comment on the results presented in this table.
- The way you describe the used domains in Table 1 is very confusing (and it is not consistent with the acronyms you describe in Lines 725-730). Moreover, sometimes you use a similar symbol for domain names and action properties (e.g., I. and I).
- How many planning tasks have you used for each of the domains? I couldn't find this information in the paper (see question Q1).

# Writing Issues and Typos:

W1. "i.e." -> "i.e.,".
W2. "... the concept of reverse plans that corresponds to the notion of uniform reversibility..." -> "... the concept of reverse plans, that corresponds to the notion of uniform reversibility...".
W3. There are two sections with the same title, e.g., "Theoretical Properties". Please, consider changing these titles in order to be more informative with respect to the theoretical properties you are presenting and proving.
W4. The sentence in Line 355 doesn't read well.
W5. In Lines 280-285: "applied in any state from the set $S$" -> "applied in any state of the set $S$".
W6. In Example 5 (Lines 360-365): "the policy of union of mentioned policies has no terminal state" -> "the policy of union of the mentioned policies has no terminal state".
W7. "summarised" -> "summarized", "conceptualised" -> "conceptualised", and other occurrences. It seems there's a blend of American and British English in your writing. Pick one and be consistent throughout the paper.
W8. "the resolution of investigated classes" -> "the resolution of the investigated classes".
W9. "strongly uniformly universally" -> Too many adverbs in one sentence.
W10. Line 725: "viz."?!
questions: questions: Please, address the following questions in your response/rebuttal.

Q1. How many planning tasks have you used for each of the domains? I couldn't find this information in the paper. Please, clarify that.

Q2.  PRP strong cyclic policies. So, I have two questions regarding this comment.
- Have you modified PRP to extract strong polices? 
- If not, have you (simply) ignored the cycles in the extracted polices in your experiments to check strong reversibility?

Q3. My following question may be out of the scope of your paper, but do you see any relation between the presence of action reversibility and irreversibility (and the other notions you proposed in the paper) in the domains' actions and the complexity (and difficulty) of solving problems for these domains? I am asking this because we have seen in recent FOND papers (Geffner and Geffner, 2018, Pereira et al., 2022, and Muise, McIlraith, Beck, 2024) that some FOND planners struggle to find solutions in some domains, especially the ones proposed by Geffner and Geffner in 2018.