Termination Properties of Transition Rules for Indirect Effects

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 11:29:38

Abstract: Indirect effects of agent's actions have traditionally been formalized as condition-effect rules that always fire whenever applicable, after each action taken by the agent.
In this work, we investigate a core problem of indirect effects, the possibility of arbitrarily or infinitely long sequences of rule firings. Specifically we investigate the termination of rule firings, as well as their confluence, that is, the uniqueness of the state that is ultimately reached. Both problems turn out to be PSPACE-complete. After this, we devise practically interesting syntactic and structural restrictions that guarantee polynomial-time termination and confluence tests.
Finally, in the context of planning languages that support indirect effects, we propose new implementation technologies.

Main paper: 
 introduction 15: 
 Actions that an agent takes can have un-anticipated, complex indirect effects. Formalizing them as part of the direct effects can be impractical, requiring representing them separately. Indirect effects can be formalized as condition-effect rules similarly to agents' actions, but with the requirement that they are fired whenever their condition part is true (Kartha and Lifschitz 1994) .Much of the expressive power of indirect effects, and the conceptual and computational complexity that follows from this power, has been earlier ignored. Earlier works either pose strong syntactic restrictions on indirect effects, limiting both their power and the complexity dramatically, or have left the problem unexplored.The two core questions, which are now addressed in this work, are the possibility of infinitely long sequences of indirect effects, and the impact of different orderings in which the rules for indirect effects are fired. These questions are respectively known as termination and confluence.Non-termination is the result of indirect effects generating an infinitely long state sequence, in which the same rules for indirect effects are fired repeatedly.Confluence is the property of there being a unique terminal state. Conflicting indirect effects may, but do not have to, lead to two or more different terminal states. Indirect effects may override each other's effects, or disable or enable each other, so that the order in which they are executed impacts which terminal state is reached in the end. If there is no unique terminal state, then it is unclear what is a correct implementation of the indirect effects. Questions about confluence (also known as the Church-Rosser property) have been researched in connection with different types of rewriting systems (Rosen 1973; Sethi 1974; Keller 1974; Jensen 1980) . Our work is the first one to address it explicitly and in full generality for state-space search problems expressed as precondition-effect rules, as used in planning, reasoning about action, and related problems.We first show that testing for both termination and confluence are PSPACE-complete. This entails that there is no general polynomial-time reduction from planning languages with indirect effects to languages without them, giving a strong justification for introducing indirect effects as an explicit concept in modeling languages for planning and related problems, and motivating at looking at tractable methods to determine confluence and termination. Despite the high worst-case complexity, many practically interesting planning problems have indirect effects that can be effectively analyzed and implemented. We investigate structural properties of rule sets for indirect effects that can be tested in polynomial-time and which yield sufficient conditions for confluence and termination. The methods we propose are based on graphs that represent relations between forced actions, and we obtain tractable termination and confluence tests by limiting to such graphs that are acyclic, or even more strictly, trees or chains.To make our results as broadly applicable as possible, we consider indirect effects in connection with the most basic model of acting and planning, the classical deterministic planning model. Our results directly apply to more general forms of planning that include the classical planning model.The structure of the paper is as follows. We start by discussing related work in Section 2. Section 3 formally defines the planning problem that interleaves agent's actions with the execution of all applicable indirect effects. Section 4 defines the termination and confluence properties, and determines their worst-case complexity. In Section 5 we give computationally easier sufficient conditions for confluence and termination. Section 6 proposes two approaches to implement classical planning with indirect effects. Finally, Section 7 reports on experiments with a basic implementation, before we conclude the paper in Section 8 by pointing out future work. Indirect effects have first been investigated as a part of solutions to the frame problem and the ramification problem in artificial intelligence (Kartha and Lifschitz 1994) . Many works have assumed, for simplicity, that the indirect effects of an action are always mutually consistent, or that conflicting indirect effects mean that an action cannot be taken (Giunchiglia and Lifschitz 1998; Gelfond and Lifschitz 1998) .Planning research has similarly adopted different notion of indirect effects, often called (exogenous) events. Petrick and Bacchus (2002) have update rules, which are essentially indirect effects. Fox et al. (2005) require that a rule for indirect effects is only fired once. Fox and Long (2006) introduce event-deterministic events, which exclude simultaneously applicable conflicting indirect effects, but do not give effective ways to achieve this. A variant of Theorem 1 shows that testing if indirect effects are event-deterministic is PSPACE-complete.1 None of these works analyze the concept of indirect effects deeper.Indirect effects in the above works, similarly to ours, are instantaneous. A different model, used in temporal planning, assigns a temporal duration to indirect effects (Gerevini, Saetti, and Serina 2006) . Other works consider unpredictable and non-deterministic exogenous events (Iocchi, Nardi, and Rosati 2000; Fritz and McIlraith 2008) . 
preliminaries: 
 Next we define our formal framework. We consider planning with Boolean state variables only.Definition 1 (Effects) Let X be the set of state variables. Then the following are effects over X.• x if x ∈ X • ¬x if x ∈ X • ϕ ▷ x if ϕ is a propositional formula over X and x ∈ X 120 • ϕ ▷ ¬x if ϕ is a propositional formula over X and x ∈ XThe notation ϕ ▷ l is for conditional effects: if ϕ is true, the literal l will be made true.Definition 2 (Actions) Let X be the set of state variables. An action is a pair (p, e) where p is a propositional formula 125 over X for the precondition, and e is a finite set of effects over X.Assumption 1 For actions (p, e), {x, ¬x} ̸ ⊆ e for all x ∈ X, and if (ϕ ▷ l) ∈ e, then l ̸ ∈ e and for any (ψ ▷ l) ∈ e, the precondition satisfies p |= ¬(ϕ ∧ ψ). So no action can make 130 a state variable both true and false at the same time.Define complement l of literals l by x = ¬x and ¬x = x. As indirect effects are expressed as condition-effect pairs similar to the agent's actions, we call them forced actions, as they must be executed whenever executable. Next we define classical planning extended with forced actions.Definition 3 (Problem instance) ⟨X, I, A, F, G⟩ is a prob- lem instance if • X is a finite set of state variables, • I ⊆ X is the initial state description, • A is a set of actions, • F is a set of actions,• G is a propositional formula over X for the goal states.Here F are the forced actions which must be fired whenever their precondition is true. The initial state description I denotes the unique state s 0 such that s 0 |= x for all x ∈ I and s 0 |= ¬x for all x ∈ X\I.Assumption 2 There are no forced actions applicable in the initial state.This assumption is just to simplify the presentation, to avoid separately talking about confluence and termination when forced actions are being triggered before any actions are taken. One could view the facts in the initial states as the unconditional effects of a special initial state action, so there is no loss of generality in this assumption.Assumption 3 Every forced action makes its own precondition immediately false, so that the forced action cannot be fired multiple times in a sequence without other actions in between. This can be often achieved with an effect literal l such that l |= p where p is the precondition.There are other ways to prevent infinite firings of a single action. First, an action could be fired only when its precondition becomes true. Second, an action could be fired only when it actually changes the value of at least one state variable (but this would prevent multiple firings only for actions that always have the same effects). But we do not investigate this further.Definition 4 (Successor state) s ′ = exec a (s) is the successor state of s with respect to action a = (p, e) such that• s ′ |= x if x ∈ e or (ϕ ▷ x) ∈ e and s |= ϕ, • s ′ |= ¬x if ¬x ∈ e or (ϕ ▷ ¬x) ∈ e and s |= ϕ, • s(x) = s ′ (x) if x ̸ ∈ e, ¬x ̸ ∈ e, s ̸ |= ϕ for any (ϕ ▷ x) ∈ e and (ϕ ▷ ¬x) ∈ e.The successor state is defined if s |= p.We define exec a1,...,an (s) = exec an (• • • exec a1 (s) • • •).Definition 5 (Executions) An execution of (forced) actions in state s 0 is a sequence a 1 , . . . , a n of action and a sequence s 0 , s 1 , . . . , s n of states such that s 0 = s and for all i ∈ {1, . . . , n}, s i-1 |= p i (where a i = (p i , e i )) and s i = exec ai (s i-1 ).The execution of an agent's action is followed by the execution of all applicable forced actions.Definition 6 (Forced executions) For ⟨X, I, A, F, G⟩ a forced execution in state s is any sequence a 1 , . . . , a n of actions with a i ∈ F for all i ∈ {1, . . . , n} such that a 1 , . . . , a n is an execution (as in Definition 5) and exec a1,...,an (s) ̸ |= p for all (p, e) ∈ F . So a forced execution is an execution of forced actions that ends in a state with no executable forced actions.Definition 7 (Reachable states) We define reachable states for problem instances ⟨X, I, A, F, G⟩ recursively.• The initial state s 0 for I is a reachable state.• s ′ is a reachable state if -s is a reachable state, -a ∈ A is an action,a 1 , . . . , a n is a forced execution in exec a (s), and s ′ = exec a,a1,...,an (s).So a state is reachable if it can be reached by a sequence of actions from A interleaved with maximal sequences of actions from F . Example 1 Consider forced actions (a, {¬a}) and (¬a, {a}). Starting from any state, these two actions have one execution which is infinitely long.So the question of termination of forced actions arises: are all executions of forced actions finite? Definition 8 (Termination) Forced actions in a problem instance are terminating if every forced execution for all states s that are reachable in ⟨X, I, A, F, G⟩ is finite.Often one wishes that the state reached with the forced actions is unique, the ordering in which the actions have been tried is therefore irrelevant, and therefore the implementation of the forced actions can use any ordering with no concerns about it having an impact on the terminal state.the Church-Rosser property (Rosen 1973; Sethi 1974) , and shows up prominently for example in the context of the λ-calculus (Barendregt 1984 ) and other similar systems in which tree-like syntactic expressions are transformed by a sequence of rewriting steps. We adapt this concept to transition systems and planning.Definition 9 (Confluence) Forced actions in a problem instance are confluent if exec σ1 (s) = exec σ2 (s) for all forced executions σ 1 and σ 2 and for all states s that are reachable in ⟨X, I, A, F, G⟩.Theorem 1 Testing for confluence of forced actions is PSPACE-complete.Proof: Idea: Construct actions for simulating deterministic PSPACE Turing machines (Bylander 1994) , with two additional actions, one going from the initial state to a special end state (the short cut), and another going from accepting state to the same special end state. The short-cut action is always applicable. If the Turing machine does not accept, then the execution ends in a non-accepting state different from the one reached by the short-cut action. Hence the forced actions are confluent if and only if the Turing machine has an accepting execution. This shows PSPACE-hardness.PSPACE membership is by finding a reachable state from which two different terminal states are reachable with forced actions. This is by nested calls to the standard PSPACE reachability test. □Theorem 2 Testing for termination is PSPACE-complete.Proof: Idea: Construct actions for simulating PSPACE Turing machines (Bylander 1994) with additional two actions that can be repeated indefinitely (similarly to Example 1) if reaching a non-accepting terminal state. Then the Turing machine accepts if and only if the rules are terminating. PSPACE-membership is by finding a reachable state from which a sequence of forced actions form a cycle in the state space. This is by nested calls to the standard PSPACE reachability test. □ 
sufficient conditions for confluence: 
 We discuss sufficient conditions for confluence that can be tested in polynomial time. The first condition is trivial and familiar from earlier works, and is given only as a starting point for the more broadly applicable conditions we develop. We first formalize four binary relations R c , R e , R d , and R i , and then derive sufficient conditions for confluence. These relations have the following meanings. R c the two actions have conflicting effects, that is, one can make some state variable true, and the other action can make it false. R e One action can enable another action by making the latter's precondition true. R d One action can disable another action by making the latter's precondition false. R i One action can impact the effects of another action by changing the truth-value of one of the conditions ϕ in a conditional effect ϕ ▷ l of the latter.Next we define the relations formally.Definition 10 (Relation R c ) The relation R c ⊆ (A ∪ F ) 2 is defined by a 0 R c a 1 whenever a 0 ̸ = a 1 and atEffs(a 0 ) ∩ {l|l ∈ atEffs(a 1 )} ̸ = ∅.Here atEffs(a) denotes the atomic effects of an action (p, e), defined as{x|x ∈ e} ∪ {¬x|¬x ∈ e} ∪ {x|(ϕ ▷ x) ∈ e} ∪ {¬x|(ϕ ▷ ¬x) ∈ e}.The relation for enabling is based on a syntactic condition that refers to the effects of the first action and the precondition of the second.Definition 11 (Relation R e ) a 1 R e a 2 iff a 1 ̸ = a 2 and 1. there is x ∈ atEffs(a 1 ) that occurs positively in the precondition of a 2 , or 2. there is ¬x ∈ atEffs(a 1 ) that occurs negatively in the 2. there is ¬x ∈ atEffs(a 1 ) that occurs positively in the precondition of a 2 .Additionally, in the presence of conditional effects ϕ ▷ l, we need to model the way an action may impact what effects another action actually has. The impact relation indicates whether it is possible that an action changes the effects another action can have.Definition 13 (Relation R i ) a 1 R i a 2 iff a 1 ̸ = a 2and x ∈ atEffs(a 1 ) or ¬x ∈ atEffs(a 1 ), and x occurs in ψ for some effect ψ ▷ l of a 2 .The simplest confluence test is the following.Theorem 3 For a problem instance ⟨X, I, A, F, G⟩, the forced actions are confluent if1. R c ∩ (F × F ) = ∅, 2. R d ∩ (F × F ) = ∅, and 310 3. R i ∩ (F × F ) = ∅.Proof: Idea: The conditions guarantee that no forced action that is applicable in s or in any state s reached with forced actions becomes inapplicable after firing other forced actions, and the effects of no forced action are overwritten by other forced actions, and the conditional effects of no action depend on whether other actions are fired before or after it. Hence the same actions are fired and the same terminal state is reached no matter what order the actions are fired in.Proof sketch: Assume that there are two executions that lead to different terminal states. Since none of the actions override the effects of other actions and since the conditions of the conditional effects have the same values in both, the terminal states can only differ because one execution includes at least one action not included in the other.Note that because of the requirement on R i , the formulas ϕ in conditional effects ϕ ▷ l are not changed by any of the forced actions, and hence they are evaluated in the state where the application of the forced actions begins in.Let a 1 , . . . , a n and a ′ 1 , . . . , a ′ n ′ be the two executions, and 330 by symmetry we assume that the first execution includes at least one action not included in the other. Let a i be the first such an action in that execution. Hence {a 1 , . . . , a i-1 } ⊆ {a ′ 1 , . . . , a ′ n ′ }. Let j ∈ {1, . . . , n ′ } be such that a ′ j = a i-1 . Since the effects of a 1 , . . . , a i-1 are not overridden by any action in the second execution, nor are any preconditions of any actions made false, the precondition of a i must be true right after a ′ j in the second execution. And later actions a ′ k , k > j will not make the precondition of a i false. Hence a i would continue to be applicable for the rest of the execution, and would have to be included in it. This contradicts the assumption that a i is not part of the second execution. Therefore it is not possible that there are two executions that have different actions. □These conditions are essentially what is required for actions at the same level in GraphPlan's plans (Blum and Furst 1997) and also in the planning as satisfiability approach (Kautz and Selman 1996) . The conditions in Theorem 3 are not necessary for confluence.Example 3 Consider actions (a, {¬b, c}), (a, {b, d}), (c ∧ d, {e, b}). Since the first two have conflicting effects, the conditions of Theorem 3 are not satisfied. Nevertheless, the rules are confluent, always leading to the same terminal state. The conflict on b between the first two actions is not important, as b will always be made true by the last action.Next we look at more powerful polynomial time tests for confluence. The first issue with Theorem 3 is that it looks at the set of forced actions as a whole, even though it would be sufficient to limit to only those forced actions that are fired when one of the agent's actions is executed.We denote the transitive closure of a relation R by R+.Definition 14 (Enabled Forced Actions) Let A be a set of actions, F a set of forced actions, and a an action. ThenF a = {a 1 ∈ F |(a, a 1 ) ∈ (R e ∩ ((A ∪ F ) × F ))+} is the set of enabled forced actions for a.The enabled actions is an over-approximation of the set of actions that possibly become executable after taking a and some (possibly empty) sequence of actions.Theorem 4 Let Π = ⟨X, I, A, F, G⟩ be a problem instance. Π is confluent if for every a ∈ A, the set of enabled forced actions for a has no pair of actions related by R c , R d , or R i .Proof: Like the proof of Theorem 3, restricted to the enabled forced actions for a. □The requirement of Theorem 4 that no two forced actions conflict is sometimes too restrictive. Next we present a more refined condition which is sufficient to determine confluence for a broader class of problems, including one of our sample problems that we will discuss later.We identify a broader classes of enabling relations that yields confluent planning problems even when actions disable other actions or have conflicting effects. Two actions a 0 and a 1 respectively with conflicting effects ¬x and x in general violate confluence because there could be two different executions in which these two actions are taken in opposite orders, either making x true first and then making it false, or vice versa, leading to different terminal states.But, we could allow two actions to have conflicting effects if they are always executed in the same order, and other actions cannot impact their execution so that the conflicting effects could play out in two different ways.Definition 15 (Enabling Graph) An enabling graph for an action a is a graph G a = ⟨G, E⟩ where G = {a} ∪ F a for the set of enabled forced actions F a for the action a, and395 E = R e ∩ (({a} ∪ F a ) × ({a} ∪ F a )).Cycles in enabling graphs are a potential indication of non-termination of forced actions. Enabling graphs in problems such as the one in Example 1 are clearly cyclic. For acyclic enabling graphs the executions of forced actions are 400 finite, but can be exponentially long.Example 4 Consider the following forced actions for all i ∈ {1, . . . , n}.a i = (x i , {x i+1 , x ′ i+1 , ¬x i }) a ′ i = (x ′ i , {x i+1 , x ′ i+1 , ¬x ′ i })For an action a with effects x 1 and x ′ 1 , the graph G a is acyclic.All of these forced actions are executed after x 1 and x ′ 1 become true, but there are several possible executions, and on some of them some actions are executed an exponential number of times.After both a n-1 and a ′ n-1 one can execute a n , a ′ n .Similarly, after both a n-2 and a ′ n-2 one can execute a n-1 , a n , a ′ n , a ′ n-1 , a n , a ′ n . As n increases, the length of executions of this form increases exponentially as 2 n+1 -2.Acyclicity of G a only guarantees boundedness of executions, but does not guarantee the uniqueness of the terminal state, as different paths in the graphs may be interleaved to executions in different ways.The same holds also if G a is a tree: even if there are only two branches in a tree-formed G a (and the executions are only polynomially long), the branches can be interleaved in an exponential number of different ways, and they could lead to an exponential number of different terminal states. So, confluence requires either even stronger restrictions on G a , like it being a chain, or other additional restrictions.Next we focus on graphs that are trees, and restrict the properties of forced actions in different branches of the tree so that confluence is achieved. Note that neither acyclicity nor being a tree is a necessary condition for confluence or termination, and we are here interested in practically useful sufficient conditions for these properties, especially ones that can be tested in low-polynomial time.To guarantee confluence we require that any variation in the order in which the forced actions are executed will never impact which terminal state is reached. In an extreme case, the tree consists of a single branch, a totally ordered se-435 quence of forced actions, which can only be executed in this particular order. Hence confluence trivially follows. If the tree has several branches, then none of the branches are allowed to impact how the execution in the other branches proceeds, and hence interleaving the different branches in arbitrary ways still always leads to the same terminal state. This is achieved simply by requiring that there is no interbranch interaction corresponding to three of the relations we have defined, R d for disabling, R i for changing the conditions of conditional effects, and R c for having conflicting effects.Theorem 5 Let Π = ⟨X, I, A, F, G⟩ be a problem instance. Π is confluent if the enabling graph G a of every a ∈ A satisfies the following.1. G a is a tree, and 2. for every (a 0 , a 1 )∈ (F × F ) ∩ (R d ∪ R i ∪ R c ), there is a directed path from a 0 to a 1 or from a 1 to a 0 in G a .Proof: Idea: The different maximal paths in the tree do not interfere with each other (except of course they may share parts of their initial segment), and attempting execution of any total ordering of the partial order represented by the tree -ignoring actions with a false precondition -leads to executing exactly the same set of actions, with the same terminal state for every execution.Let s be any reachable state for Π and let a ∈ A be an action applicable in s. Let σ 1 = a 1 1 , . . . , a 1 n and σ 2 = a 2 1 , . . . , a 2 m be sequences of forced actions so that s 1 0 , . . . , s 1 n and s 2 0 , . . . , s 2 m are their respective executions starting with s 1 0 = s = s 2 0 , and the sequences are maximal in the sense that no forced actions are applicable in s 1 n and s 2 m .We will next show that {a 1 1 , . . . , a 1 n } = {a 2 1 , . . . , a 2 m } so that exactly the same forced actions are executed after taking action a, and that s 1 n = s 2 m so that the resulting state is the same in both cases.To show that the same actions are in both, we assume that is an action a 1 i that does not appear in σ 2 , and choose such action with the least i. So forced actions a 1 1 , . . . , a 1 i-1 occur also in σ 2 , including those on the path from the root action a to a 1 i . These latter actions cannot interfere with any action in σ 2 , because there is not inter-branch interaction of the forced actions, and hence after the last of those actions the precondition of a 1 i is true. But now none of the forced actions following a 1 i in G a can be in σ 2 (as only a 1 i can make them applicable) and therefore cannot falsify the precondition of a 1 i , and also forced actions in other branches in G a cannot falsify the precondition of a 1 i , so a 1 i must be included in σ 2 as well, which is a contradiction with the assumption that there is a forced action in σ 1 that does not occur in σ 2 . Hence all forced actions in σ 1 must also be in σ 2 . By symmetry, same holds for σ 2 and σ 1 , so hence their forced actions coincide.It remains to show that both σ 1 and σ 2 lead to the same terminal state.We first prove an auxiliary result by induction on the distance of the (forced) actions from the root action a in G a .Induction hypothesis: For any (forced) action with distance i from the root of G a that occurs in σ 1 and σ 2 , in both execution σ 1 and in σ 2 the action has the same (conditional and unconditional effects).Base case i = 0: This action is the root action a, being executed in the same state s for both σ 1 and σ 2 , and hence has the same effects in both cases. Inductive case i ≥ 1: Let a ′ be an action in σ 1 and σ 2 with distance i from a. All (forced) actions that change state variables in the conditions c of conditional effects c ▷ e of a ′ before the execution of a ′ in σ 1 and σ 2 have distance < i, and hence have exactly the same conditional and unconditional effects in both σ 1 and σ 2 . Hence the effects of a ′ are the same in both executions.Finally, for every state variable x and every pair of actions that change x in σ 1 and σ 2 , these two actions have the same ordering in both σ 1 and σ 2 , as that ordering is determined by G a (actions that have conflicting effects cannot be in unordered in G a , that is, reside in different branches of the tree G a .)Hence the final value of x is the same in both executions σ 1 and σ 2 , and hence the terminal states are the same.□ 
implementation: 
 Often it can be guaranteed that taking an action can only trigger the firing of a small number of forced actions (for example by using the concept of enabled forced action in Definition 14). In these cases it is possible to implement the forced actions by reducing the whole planning problem to a conventional classical planning problem. If there is only one forced action that could become executable after an agent's chosen action, then simply compose them together, with the precondition p of the forced action first moved to the condition part of its effect ϕ ▷ l to obtain (p ∧ ϕ) ▷ l. However, compiling the potentially applicable forced actions into the enabling regular actions is infeasible if there are very many of them. We have not experimented with this option further.Next we consider general implementations in two main frameworks, heuristic state space search (Bonet and Geffner 2000) and the planning as satisfiability approach (Kautz and Selman 1996 ). An underlying assumption in both cases is confluence (Section 4). If a rule set does not have the confluence property, the results of the rule firings are not uniquely determined by the starting state, and will be affected by the ordering in which forced actions are considered. In the statespace search setting the most natural implementations would follow an arbitrary ordering. SAT-based methods could be implemented so that all possible firing orderings would be covered, so that a planner would return a plan whenever a plan exists for at least one firing ordering for every instance of firings, but we will not look at this in more detail.Implementation with standard state-space search algorithms in planners such as HSP and FF (Bonet and Geffner 2000; Hoffmann and Nebel 2001) is straightforward. Followed by a regular action, all applicable forced actions are applied until none are applicable. Assuming confluence, the resulting state is unique.For computing many well-known heuristics, a straightforward implementation is to treat forced actions and regular 550 actions alike, so not requiring any modification in the heuristic at all. An intuitively plausible modification would be to treat forced actions as having cost 0, but we will see in Section 7 that sometimes this does not work well.Extending encodings of planning as satisfiability (Kautz and Selman 1996) with forced actions is slightly more complicated. We need to force the execution of all forced actions after every regular action. The principles the encoding implements are the following. 560 1. At least one forced action must be taken whenever the precondition of at least one forced action is true. 2. An ordinary (non-forced) action can be taken only if no forced action is applicable at the same step.The first requires firing all applicable forced actions, in 565 one or more steps of a parallel plan (Kautz and Selman 1996) . The second means that agent's actions can only be considered after all applicable forced actions have been fired. Next we give an implementation of these principles.Let there be n forced actions, and let p 1 , . . . , p n be 570 their respective preconditions and let f 1 @t, . . . , f n @t be the atomic propositions indicating whether they are executed at time point t. Let a 1 @t, . . . , a m @t be the atomic propositions indicating whether the agent actions are executed.Requirement 1 is encoded as follows.575 p i @t → F @t for all i ∈ {1, . . . , n} (1)F @t → (f 1 @t ∨ • • • ∨ f n @t) (2)Requirement 2 is encoded as follows.a i @t → ¬F @t for all i ∈ {1, . . . , m}Here F @t is true if at time step t there are forced actions. This is the most basic encoding. We can strengthen the encoding so that forced actions following one regular action are never unnecessarily spread to more time points than what 580 is necessary. The additional condition that handles this is as follows.1b. If the precondition of the forced action is true and no forced action is executed that either has a conflicting effect or that is mutex with the forced action, then the 585 forced action must be taken.This could further be strengthened by removing ambiguity about which maximal consistent set of forced actions is taken by adding "no forced action with a lower index", so that in conflict situations always the lower indexed forced 590 action wins. This condition is encoded as follows.p i @t → F @t for all i ∈ {1, . . . , n}EQUATIONHere C i is the set of lower-indexed actions that have an effect that conflicts with the effect of forced action i or that is mutex with it, in the sense of Graphplan parallelism (Blum and Furst 1997; Kautz and Selman 1996) . 
control knowledge for logistics: 
 Forced actions can also be viewed as a form of control knowledge. Consider the standard logistics domain, with airplanes and trucks for transporting packages. Some of the actions can be viewed as forced actions which should be taken whenever it is possible.• A package at its target city but not at its target location must be loaded into a truck. • A package not in its target city must be loaded into a truck if it is not at the airport. • A package destined to a different city must be unloaded from a truck at the airport. • A package in its target city must be unloaded from the airplane. • A package in its target location must be unloaded from a truck.These forced actions refer to the target cities and locations of the packages, which must be accordingly modeled.The only actions left to the agent to decide about are the move actions for trucks and airplanes, and whether to load a package to an airplane. Loading a package to an arbitrary airplane may risk losing optimality of a plan.Note that these forced actions mostly satisfy the conditions of Theorem 3, except for immediate loads after unloads, as in unloading a package from a truck and then loading it into an airplane. The more relaxed conditions of Theorem 5 in this case show that confluence indeed holds.Our experiment uses 200 instances from the year 2000 planning competition Logistics domain, both in the original version, and a revised version with many of the actions turned to forced actions as described above. We first implemented FF with forced actions (which we call FFF0) according to Section 6.1, so that the heuristic computation considers the forced actions as having cost 0. The results turned out to be underwhelming, with FFF0 often not solving Logistics any better. It turned out that forced 650 actions having cost 0 turns the heuristic uninformative and makes the search quite blind. Then we modified the implementation so that forced actions are considered by the heuristic exactly like the rest of the actions, obtaining FFF1. Figure 1 gives the runtimes of FF on the original instances 655 and FFF1 with the same instances enhanced with forced actions. Using forced actions as control knowledge decimates the runtimes also for the very large Logistics instances that FF would otherwise need tens of minutes to solve.For the SAT approach, we used a basic SAT-based plan-660 ner with a standard parallel encoding (Kautz and Selman 1996) as a baseline. Then we extended it, as discussed in Section 6.2, to support forced actions (the most basic encoding only), and ran it with the same Logistics problems, with the results given in Figure 2 . The experiment used the state-665 of-the-art KisSAT SAT solver. While the results are not as impressive as with FFF1, substantial runtime improvement is still obtained, often by one order of magnitude.The results show that control knowledge in the form of forced actions can considerably improve performance when 670 some of the actions can be considered obligatory when- ever they are applicable. Although Logistics is a simple domain and is solved by many planners very efficiently, the reduction in the number of decision points, due to the smaller number of regular actions, still leads to a performance improvement. In some other domains these improvements could be still far bigger.Game of Life (Gardner 1970 ) is a cellular automaton. The cells in the grid are either live or dead. Given the current state, the following three rules determine the next state: Any cell with three live neighbors will be alive. Any live cell with two live neighbors will be alive. All other cells will be dead.For our second experiment, we based a planning problem on Game of Life. We partition a finite grid into three parts: source area, destination area, and the rest. The goal is to make at least one cell alive in the destination area by controlling the cells in the source area, and otherwise allowing the automaton run according to its usual rules. Figure 3 demonstrates an example of this problem with its solution.We implemented this problem with agent's actions controlling the source area, and with the cellular automaton rules implemented as forced actions. We use two copies of the grid, the old and the new, so that each cell's new state only depends on the cells' old values, with the new grid becoming the next new for the next stage of cell evolution. This problem is confluent, as the forced actions are used to determine the unique next state of the grid evolution.We generated ten problem instances for grid sizes 3 × 3 until 12 × 12. The leftmost column is the source area, and the rightmost column is the destination area. The results of this experiment are shown in Figure 4 . There is no baseline version of this benchmark, as expressing it in standard modeling languages is impractical. Finding cellular automata states satisfying complex criteria is computationally hard, so the runtimes in this problem unsurprisingly grow quickly as the grid dimensions increase. The SAT implementation finds solutions up to grid size 10 × 10 and FFF1 until 8 × 8. 
conclusion: 
 We have investigated methods and complexity of testing the termination and confluence of indirect effects expressed as condition-effect rules, showing the main decision problems PSPACE-complete, and giving incomplete but broadly applicable polynomial-time heuristic methods. Additionally, we have presented scalable implementation both for heuristic state space search and logic-based methods, which have Figure 4 : FFF1 and SAT runtimes on Game of Life not been presented in earlier research. Indirect effects can formalize complex uncontrollable but predictable environments, or they can be understood as control knowledge, as discussed in our experiments. 
7 experiments: 
 Following Section 6.2, we have implemented forced actions in FF (Hoffmann and Nebel 2001) , a well-known planner often used for benchmarking, as well as a basic SAT-based planner. Then we have run experiments, demonstrating two uses of forced actions, viewing the distinction between regular and forced actions as control knowledge, and using forced actions to describe complex indirect effects of the agent's actions.In our first experiment, we reformulated the well-known logistics domain with control knowledge, and then evaluated it against the original version without control knowledge.In the second experiment we demonstrate the use of forced actions in expressing indirect effects that would be difficult to encapsulate in regular actions. For this, we introduce a new domain derived from the well-known Game of Life (Gardner 1970 ) cellular automaton.All experiments were run on Intel Xeon E5-2680 CPUs, with 8 GB of memory and a time limit of 30 minutes. 
: 
 investigate the termination of rule firings, as well as their confluence, that is, the uniqueness of the state that is ultimately reached. Both problems are PSPACE-complete, and hence far more challenging than what existing literature suggest. To tackle this complexity, we devise practically interesting syntactic and structural restrictions that guarantee polynomialtime termination and confluence tests. Finally, in the context of planning languages that support indirect effects, we propose new implementation technologies. 
 
 Appendix: Future work includes further polynomial-time testable structural properties that guarantee confluence.The definition of event-deterministic is stated informally only, and it could alternatively mean actions being mutex(Blum and Furst 1997), in which case it is testable in polynomial time.Example 2 Consider forced actions (a, {¬a, b}) and (a, {¬a, c}) and a state s such that s |= a ∧ ¬b ∧ ¬c. There are two forced executions of the actions, each consisting of one forced action only, leading to two different states.The property we are after is known as the confluence or 


Decision: The reviewers agree that the paper makes a compelling argument for using indirect effects in planning languages. The theory is presented clearly and provides a thorough analysis of the topic (including complexity results), and the experimental analysis convicingly showcases the advantages of the approach. While the paper should be accepted, the discussion brought up two poins which the authors must integrate in the final version of the paper:

1) Clarify Figures 1 and 2 by briefly explaining in the text what the plots show (see review FHH9).
2) Add a brief discussion of related work on the use of Control Knowledge (see post rebuttal comment in review ibGX).

Reviews: review: strength_weakness: strength_weakness: Major: A Major weakness of this paper involves its experimental section, especially its Figures 1 and 2. The points/boxes are unlabeled here and I am not certain what is to be gleaned from these graphs. The paper discusses this being runtime but is the runtime the x-axis?   The x-axis is just labeled as "base".  Either a table breaking down the differences or something more akin to Figure 4 would greatly strengthen the argument/case for what is being discussed around line 670.

Minor: Overall, this paper is very... high-level. I found it difficult to follow along in the abstract when no example domain nor case study was given to help root the problem space to some form of specific forced-action. I was hoping the introduction of the logistics domain and game of life at the end would help, but they come off as slightly arbitrary. (Some of this is followed up with in the Questions section)
questions: questions: 1) One thing I was thinking about while reading this paper is how the area of static causal laws relate to this papers use of indirect actions, as they have very similar uses with closure functions? If these are completely separate concepts, how does this setup for transition functions differ from those closure function transitions?

2) Can you provide an example of indirect action in a given domain rather than at the abstract levels of (a,not_a)? Put another way, what types of problems or domains would this open up for future work?
strength_weakness: strength_weakness: Experimental evaluation (minor, but almost major):
The planners chosen for the evaluation are more than twenty years old. That makes it difficult to generalize the outcome to modern planners with more powerful heuristics and finely-tuned search implementations. It also limits the uptake of the work if accepted, as the techniques will have to be reimplemented from scratch to integrate into new research and applications.

Unsupported statement in intro (minor):
L52: PSPACE completeness implies no general polynomial time reduction
Either this statement is wrong, since all PSPACE-complete problems can be transformed into each other in polynomial time, or it refers to something else, such as without changing the language of accepted plans, in which case it needs a citation or more justification.

For fun, here is such a translation from a language with forced actions to one without:
Add two new propositions - forced and unforced. Add 'unforced' and 'forced' to the precondition of all unforced and forced actions, respectively. Add \neg unforced and forced to the effects of every unforced action. Add a new action whose precondition is the conjunction of the negation of every unforced action's precondition, and whose effect is to assert unforced and retract forced. Add unforced to the initial state.
To be clear, this translation does not diminish the work of the authors - planners would not be able to identify if and when all sequences of forced actions are confluent, and would likely search fruitlessly through different orders. Better translation might be possible for certain classes of indirect effects, such as those matching theorem 3 or 5, by enforcing an order of applications.


Errata:


L351: Example 3 violates Assumption 3 that forced events make their preconditions false
questions: questions: 1. Will code and experimental data be made available?

2. L396: the second {a} looks redundant and limiting - is there any reason to include interactions back to the non-forced action. Theorem 3 excluded those interactions.

3. What did you mean in line L52 (referenced above)?

======
Post-rebuttal:
I disagree with the authors that choosing older generations of planners has no effect. E.g., one could hypothesize that the advances of the underlying SAT solvers could explain the relative difference in solving time between the FF and SAT planners with and without CK, and that a comparison with with Lama for FD would also show less relative difference than FF.

On the GoL domain, I see less issue - it is good example of how transition rules enable planning in more dynamic (but still deterministic) domains, and its main contribution is as an example of the use of transition rules and showing that the implementation is feasible.

I remain eager to see the work published. I have a number of applications that I've run across that have dynamic portions of the environment, and having language support for transition rules would be helpful.
strength_weakness: strength_weakness: If I understood it correctly, Theorem 5 subsumes Theorem 4 (and 3), as it provides a more general condition. The main finding of Theorems 3 and 5 is that all enabled forced actions have to be applied at some point and that the enabling graph provides partial ordering of the forced actions. For Theorem 3, forced actions can be applied in any order, and the enabling graph in such a case would have edges only from the action a to each enabled forced action. Hence, it seems to be a special case of the conditions in Theorem 5 and in that context, Theorem 3 is a corollary of Theorem 5 (so the proof of Theorem 3 seems to be redundant).

The use of domain control knowledge in planning is studied in the literature (e.g., control rules, planning programs), yet the paper does not reference any of such works. Although I understand that the use of confluent forced actions as a control knowledge is not the main contribution of the paper, it would be great to include at least a short paragraph putting the use of forced actions in the context of some other types of control knowledge.

A small typo in Def.5: ".. a sequence a1,...,an of actionS"
questions: questions: 1. Is the condition of Theorem 3 a special case of the condition of Theorem 5 ?
2. Would it be possible to extract aggregated effects of the forced actions from an enabling graph ? (i.e., what literals change and how ?)

Post rebuttal:

Thank you for your answers.

I agree that Theorem 3 does not require an enabling graph (and thus its acyclicity). I still feel that a large part of the proof of Theorem 3 overlaps with the proof of Theorem 5, and as forced actions represent indirect effects of an action, the use of enabling graph seems to be natural. On the other hand, I see it now less of an issue that it was before the rebuttal.

If the paper is accepted, I would recommend the authors to add at least a brief paragraph comparing the use of forced actions as Control Knowledge with some well known techniques related to use of Control Knowledge in planning in the literature.