Custom-Design of FDR Encodings: The Case of Red-Black Planning

1 Introduction

Classical planning tasks are usually defined in PDDL [McDermott, 2000], which is a lifted representation based on first-order logic. Yet, most state-of-the-are planners, in particular the systems based on Fast Downward (FD) [Helmert, 2006], use a finite-domain representation (FDR) encoding, where subsets of propositional facts are grouped into finitedomain state variables. This is possible only if reachable states make at most one of the grouped facts true, i. e., if they form a mutex group. FDR encodings are useful for a wide variety of purposes like abstraction based heuristics [Haslum et al., 2007; Katz and Domshlak, 2010; Helmert et al., 2014; Seipp and Helmert, 2018], or red-black planning heuristics [Domshlak et al., 2015; Gnad and Hoffmann, 2015;

∗Contact Author

Katz, 2019], where a subset of (red) variables are deleterelaxed while the rest (black) keep their true semantics.

The translation of PDDL into FDR is complex-deciding whether a set of facts forms a mutex group is as hard as planning itself. There are many choice points in identifying mutex groups and grouping facts into state variables. Systems based on Fast Downward almost universally rely on its translator [Helmert, 2009] and do not question the choices made there.

Yet the translation choices can impact performance. In prior work [Dvoˇr´ak et al., 2013; Dvoˇr´ak et al., 2015], a minimization of the number of FDR variables was proposed assuming fewer variables result in more information being aggregated into them. The results show that significantly reducing the number of variables can improve the performance of FDR-based techniques. The improvements are moderate though, and there is a lot of variance depending on domain and planning technique; a consistent picture does not emerge.

Here we show that this picture can change when going one step further in the target of FDR optimization: we propose to custom-design FDR encodings, optimizing the encoding to suit particular planning techniques. 1 We develop such a custom design for red-black planning, which distinguishes between relaxed (red) and non-relaxed (black) variables. We focus on a polynomial-time solvable fragment of red-black planning [Katz et al., 2013b] which uses a heuristic function based on generating a red-black plan for a given state [Katz et al., 2013a]. The tractability of red-black planning is determined by the decision which variables are painted red or black. The state-of-the-art approach uses painting strategies [Domshlak et al., 2015] assuming the FDR encoding is given and fixed, and decides only on variable colors. Here, we open up this design space and allow to custom-design the FDR variables and their painting at the same time.

The tractability of red-black planning is governed by the FDR encoding's causal graph (whose projection onto the black variables must be acyclic) and domain transition graphs (that must be invertible for the black variables). We develop techniques optimizing these explicit syntactic criteria, to be able to choose from different viable FDR encodings of tractable red-black planning tasks. The optimization itself is then formulated as an integer linear program, where the allocation of black (non-relaxed) variables is controlled by the program's objective function.

1 Vallati et al. [2015; 2017] have explored domain model optimization tailored to specific planners before, but for PDDL not for FDR variable design, and changing only the ordering of artefacts in the input model (which had previously been observed to be relevant for the performance of some planners [Howe and Dahlman, 2002]).

2 Background

A STRIPS planning task Π is specified by a tuple Π = 〈F, O, sI , sG〉, where F = {f1, . . . , fn} is a set of facts, and O = {o1, . . . , om} is a set of grounded operators. A state s ⊆ F is a set of facts, sI ⊆ F is an initial state and sG ⊆ F is a goal specification. A state s is a goal state iff sG ⊆ s. An operator o is a tuple o = 〈pre(o), add(o), del(o)〉, where pre(o) ⊆ F is the set of preconditions of o, and add(o) ⊆ F and del(o) ⊆ F are the sets of add and delete effects, respectively. All operators are well-formed, i.e., add(o) ∩ del(o) = ∅ and pre(o) ∩ add(o) = ∅. We assume unit costs. An operator o is applicable in a state s if pre(o) ⊆ s. The resulting state of applying an applicable operator o in a state s is the state oJsK = (s \ del(o)) ∪ add(o).

A set of facts M ⊆ F is called a mutex if M ̸⊆ s for every reachable state s. A set of facts M ⊆ F is called a mutex group if |M ∩ s| ≤ 1 for every reachable state s, and M is called a fact-alternating mutex group (fam-group) if |M ∩ sI| ≤ 1 and |M ∩ add(o)| ≤ |M ∩ pre(o) ∩ del(o)| for every operator o ∈ O. Every fam-group is a mutex group. Every subset of a mutex group is a mutex group, but not every subset of a fam-group is a fam-group. Facts from every mutex group form pairwise mutexes [Fiˇser and Komenda, 2018].

A sequence of operators π = 〈o1, . . . , on〉 is applicable in a state s0 if there are states s1, . . . , sn such that oi is applicable in si-1 and si = oiJsi-1K for 1 ≤ i ≤ n. The resulting state of this application is πJs0K = sn. A sequence of operators π is called a plan iff π is applicable in sI and sG ⊆ πJsK.

Given a set of mutex groups G, MG ⊆ 2F denotes an upper set of mutexes induced by G, i.e., for every mutex group G ∈ G and every f, f ′ ∈ G, f ̸= f ′ , it holds that {f, f ′ } ∈ MG, and for every M ∈ MG and every f ∈ F it holds that M ∪ {f } ∈ MG .

An FDR planning task P is specified by a tuple P = 〈V,O, ψI, ψG〉. V is a finite set of variables, each variable V ∈ V has a finite domain dom(V ). A fact 〈V, v〉 is a pair of a variable V ∈ V and one of its values v ∈ dom(V ). A partial state p is a variable assignment over some variables vars(p) ⊆ V. We write p[V ] for the value assigned to the variable V ∈ vars(p) in the partial state p. Given a set of variables U ⊆ V, p[U] denotes a partial state p restricted to U. We also identify p with the set of facts contained in p, i.e., p = {〈V, p[V ]〉 | V ∈ vars(p)}. A partial state s is a state if vars(s) = V. ψI is an initial state. ψG is a partial state called goal, and a state s is a goal state iff ψG ⊆ s. O is a finite set of operators, each operator o ∈ O has a precondition pre(o) and effect eff(o), which are partial states. An operator o is applicable in a state s iff pre(o) ⊆ s. The resulting state of applying an applicable operator o in a state s is the state oJsK where oJsK[V ] = eff(o)[V ] for every V ∈ vars(eff(o)), and oJsK[V ] = s[V ] for every V ∈ V \ vars(eff(o)). Operator sequences and plans are defined analogously to STRIPS.

The domain transition graph (DTG) of a variable V , denoted by DV , is an edge-labeled multi-digraph with vertices dom(V ) and with an edge from d to d′ induced by an operator q ∈ O and denoted by (d, q, d′ ) iff d ̸= d′ , eff(q)[V ] = d′ , and either pre(q)[V ] = d or V ̸∈ vars(pre(q)).

Let U ⊆ V denote a subset of variables. The causal graph CGU of U is a digraph with vertices U. An edge (V, V ′ ) is in CGU iff V ̸= V ′ and there exists an operator o ∈ O such that (V, V ′ ) ∈ (vars(pre(o)) ∪ vars(eff(o))) × vars(eff(o)).

A red-black planning task Π is specified by a tuple Π = 〈V R, V B , O, ψI , ψG〉, where V R and V B are state variables, called red variables and black variables, respectively. Black variables have the value-switching semantics as in FDR. Red variables have the value-accumulating semantics, i.e., operators "extend" the value of V ∈ V R from {x} to {x, y}. Applicability of operators, sequences of operators, and red-black plans are defined accordingly [see Domshlak et al., 2015].

Given a variable V ∈ V, an edge (d, q, d′ ) fromDV is relaxed side effects invertible (RSE-invertible) if there exists an edge (d′ , q′ , d) such that pre(q′ )[V \V ] ⊆ pre(q)[V \V ] ∪ eff(q)[V \ V ]. V is RSE-invertible if every edge in DV is RSE-invertible.

RSE-invertibility is a sufficient criterion for tractability in the case when the subgraph of the causal graph restricted to the black variables is acyclic [Katz et al., 2013a]. The actual algorithm presented in that work handles only the arc-less black causal graph case. Later, an algorithm for devising redblack plans for the acyclic causal graph case was presented [Katz and Hoffmann, 2014; Domshlak et al., 2015]. In what follows, we focus on the red-black heuristic hRB for a state s, that returns the length of a red-black plan for s, computed for that tractable fragment.

3 Translation from STRIPS to FDR

A concise translation from STRIPS to FDR requires mutex groups that are used for creating FDR variables from STRIPS facts. Before we formalize the translation process, we formulate an intermediate STRIPS representation where we assume the mutex groups are already inferred and the STRIPS planning task is pruned with the mutex information contained in them. Moreover, we need to preserve the DTG structure of mutex groups from which black variables are created to preserve their RSE-invertibility. For this purpose, we introduce a mapping from mutex groups to fam-groups containing these mutex groups, called fam-group map. We choose specifically fam-groups because of their simpler structure [Fiˇser and Komenda, 2018]. It is not a limitation, since fam-groups are the most commonly used type of mutex groups anyway [Fiˇser, 2020].

Definition 1. Given a set of mutex groups G, γ : G ↦→ 2F is a fam-group map if for every G ∈ G it holds that either γ(G) = ∅ or γ(G) is a fam-group such that G ⊆ γ(G).

Definition 2. Given a STRIPS planning task Π = 〈F,O, sI, sG〉, and a set of non-empty mutex groups G, and a fam-group map γ over G, EΠ = 〈Π, G, γ〉 denotes a STRIPS planning task extended with mutex groups (MGE-STRIPS) if all of the following hold:

• (S2) for every operator o ∈ O it holds that pre(o) ̸∈MG and oJpre(o)K ̸∈MG and for every f ∈ del(o) it holds that {f } ∪ pre(o) ̸∈ MG ,
• (S3) sI ̸∈MG and sG ̸∈MG,
• (S4) ⋃G∈G G = F,
• (S5) for every G,G′ ∈ G, G ̸= G′ it holds that G∩G′ = ∅,
• (S6) {f} ∈ G for every f ∈ ⋃o∈O (del(o) \ pre(o)),
• (S7) γ(G) ̸= ∅ for every G ∈ G such that |G| ≥ 2.

Condition (S1) makes sure that there are no "static" facts, i.e., facts that either do not appear in any reachable state, or that are set in the initial state and remain set in all reachable states. (S2) corresponds to pruning of unreachable operators and delete effects that are not applicable. (S3) can be false only for unsolvable tasks. (S4) ensures that the set of mutex groups cover all facts. Pairwise disjoint mutex groups (S5) ensure that each STRIPS fact is encoded only once. (S6) ensures a polynomial translation without conditional effects (for a detailed explanation see [Helmert, 2009, Section 7.3]). The fam-group γ is used for encoding preconditions of operators in the translation to FDR, and, as we described before, we assume all mutex groups G to be based on fam-groups, i.e., each mutex group from G is either a singleton or it is mapped to some fam-group (S7).

Our formulation of the translation from MGE-STRIPS to an FDR planning task differs from the translation described by Helmert [2009] in the way preconditions of operators are encoded. We use the value ⊥G to express that none of the facts from the mutex group G is set. Whenever the fam-group map γ maps G to a non-empty fam-group and pre(o) ∩ (γ(G) \ G) ̸= ∅, we set the variable VG to ⊥G in a precondition of operator qo, i.e., VG is set to ⊥G only if pre(o) is mutex with G and we can infer this fact from the given fam-group map. Note also that if γ(G) = ∅ for every G ∈ G, then we get the same FDR encoding as Helmert [2009].

Definition 3. Given an MGE-STRIPS planning task EΠ = 〈Π = 〈F,O, sI, sG〉, G, γ〉, P(EΠ) = 〈V,O, ψI, ψG〉 is an FDR planning task such that:

• (T1) V = {VG | G ∈ G} where dom(VG) = G ∪ {⊥G} for every VG ∈ V;
• (T2) O = {qo | o ∈ O} where
• (T2a) pre(qo) = {〈VG, f〉 | G ∈ G, G ∩ pre(o) ̸= ∅, f ∈ G ∩ pre(o)} ∪ {〈VG, ⊥G〉 | G ∈ G, G ∩ pre(o) = ∅, γ(G) ∩ pre(o) ̸= ∅},
• (T2b) eff(qo) = {〈VG, f〉 | G ∈ G,G∩ add(o) ̸= ∅, f ∈ G ∩ add(o)} ∪ {〈VG, ⊥G〉 | G ∈ G, G ∩ del(o) ̸= ∅, G ∩ add(o) = ∅},
• (T3) ψI = {〈VG, f〉 | G ∈ G,G ∩ sI ̸= ∅, f ∈ G ∩ sI} ∪ {〈VG,⊥G〉 | G ∈ G,G∩ sI = ∅}
• (T4) ψG = {〈VG, f〉 | G ∈ G, G ∩ sG ̸= ∅, f ∈ G ∩ sG}

Although encoding ⊥G in preconditions of operators is not necessary, because this fact is true implicitly, we use it to ensure that the structure of a projection to the mutex group in STRIPS is preserved in the corresponding DTG in FDR. Why we need this will become clear in the next section where we deal with RSE-invertibility. For now, see the example depicted in Figure 1. The projection to the famgroup F = {f1, . . . , f4} is shown in Figure 1a. Now suppose we decide to encode only a subset of F as an FDR variable, namely G = {f1, f2}. If we set γ(G) = ∅, then the resulting DTG of VG will be as depicted in Figure 1c, i.e., it will have additional edges between f1 and f2 not present in the original projection, because the operators o31 and o42 have f3 and f4, respectively, in their preconditions. Therefore VG is not set in pre(qo31 ) and pre(qo42 ). However, if we set γ(G) = F, then we preserve the structure, as depicted in Figure 1b, because VG will be set to ⊥G in the preconditions of qo31 and qo42 .

Proposition 4. Let EΠ = 〈Π = 〈F,O, sI, sG〉, G, γ〉 denote an MGE-STRIPS planning task. π = 〈o1, . . . , on〉 is a plan for EΠ iff π′ = 〈qo1 , . . . , qon 〉 is a plan for P(EΠ).

Proof Sketch. P(EΠ) is well-defined, because (T3) assigns one value to every variable, i.e., ψI is a state. Similarly, (T4) ensures that ψG is a partial state, and (T2a-b) produce partial states, because only one value is assigned to each variable.

Note that f ∈ sI iff 〈VG, f〉 ∈ ψI for every G s.t. G∩sI = {f}, and 〈VG,⊥G〉 ∈ ψI only if sI ∩ G = ∅. Similarly, f ∈ sG iff 〈VG, f〉 ∈ ψG; and for every o ∈ O it holds that f ∈ pre(o) iff 〈VG, f〉 ∈ pre(qo), and 〈VG,⊥G〉 ∈ pre(qo) only if pre(o) ∩ G = ∅ and pre(o) ∩ γ(G) ̸= ∅. Hence o is applicable in sI iff qo is applicable in ψI for every o ∈ O. Furthermore, from (T2b) it follows that f ∈ oJsIK iff 〈VG, f〉 ∈ qoJψIK for every G s.t. G ∩ oJsIK = {f}, and 〈VG,⊥G〉 ∈ qoJψIK only if G is mutex with oJsIK. The rest follows by induction.

4 RSE-Invertible Variables

Now, we show how to identify mutex groups in EΠ whose counterparts form variables in P(EΠ) that are RSE-invertible. This condition is required for black variables in the tractable fragment of red-black planning we consider. First, we formulate conditions for RSE-invertibility of facts and mutex groups. Then, we show that, given a fam-group map, these conditions are both sufficient and necessary for RSEinvertibility of the resulting FDR variables.

For the rest of this section, let EΠ = 〈Π, G, γ〉 for Π = 〈F,O, sI, sG〉 denote an MGE-STRIPS planning task, and let P(EΠ) = 〈V,O, ψI, ψG〉 denote an FDR planning task constructed from EΠ according to Definition 3.

Definition 5. A fact f ∈ F is RSE-invertible if

• (I1) there exist o, o′ ∈ O such that f ∈ add(o) and f ∈ del(o′ ), and
• (I2) for every operator o ∈ O such that f ∈ del(o) it holds that there exists an operator o′ ∈ O such that f ∈ add(o′ ) and pre(o′ ) ⊆ pre(o) ∪ add(o), and
• (I3) for every operator o ∈ O such that f ∈ add(o) it holds that there exists an operator o′ ∈ O such that f ∈ del(o′ ) and pre(o′ ) ⊆ pre(o) ∪ add(o).

We also call a set of facts (or mutex group) F ⊆ F RSEinvertible if every f ∈ F is RSE-invertible.

For the main result of this section (Theorem 9), we need to prove several auxiliary lemmas first. We start by showing that the condition pre(o) ⊆ pre(o′ ) ∪ add(o′ ) from (I2-3) corresponds to the RSE-invertibility condition on edges in DTGs as long as we have transitions in both directions.

Lemma 6. Let G ∈ G be a mutex group and o, o′ ∈ O be two operators with edges (x, qo, x′ ) and (x′ , qo′ , x) in the DTG of VG. Then pre(o) ⊆ pre(o′ ) ∪ add(o′ ) iff pre(qo)[V \ VG] ⊆ pre(qo′ )[V \ VG] ∪ eff(qo′ )[V \ VG].

Proof. "⇐": It is easy to see that f ∈ pre(o) iff 〈VG′ , f〉 ∈ pre(qo), and f ∈ pre(o′ ) iff 〈VG′ , f〉 ∈ pre(qo′), and f ∈ add(o′ ) iff 〈VG′ , f〉 ∈ eff(qo′) for every G′ ∈ G, therefore it holds that pre(o)\G ⊆ (pre(o′ )∪add(o′ ))\G. It remains to show that also pre(o)∩G ⊆ (pre(o′ )∪add(o′ ))∩G (because, for all G′ ∈ G, 〈VG′ ,⊥G′〉 is never explicitly represented as a fact in pre(o)). There are two cases:

1. If VG ∈ vars(pre(qo)), then pre(o)[VG] = f = x ∈ G, because (x, qo, x′ ) is an edge in the DTG of VG, therefore pre(o) = f . Moreover, since there is also an edge (x′ , qo′ , f) in the DTG of VG, it follows that eff(qo′)[VG] = f and therefore f ∈ add(o′ ). (2) If VG ̸∈ vars(pre(qo)) or pre(qo)[VG] = ⊥G, then G ∩ pre(o) = ∅.
2. "⇒": For every G ∈ G s.t. G∩pre(o) ̸= ∅ there exists f ∈ G s.t. f ∈ pre(o), and pre(qo)[VG] = f , and pre(qo′ )[VG] = f or eff(qo′)[VG] = f. So, it remains to show that the claim holds also for every H ∈ G, H ̸= G, such that H∩pre(o) = ∅ and VH ∈ vars(pre(qo)) and therefore pre(qo)[VH] = ⊥H. If pre(qo)[VH] = ⊥H, then γ(H) ∩ pre(o) ̸= ∅. Let y ∈ γ(H) ∩ pre(o). Therefore, y ∈ pre(o′ ) or y ∈ add(o′ ).
3. If y ∈ pre(o′ ) then H ∩ pre(o′ ) = ∅, because pre(o′ ) is not a mutex (S2). Therefore, pre(qo′ )[VH] = ⊥H.
4. If y ∈ add(o′ ) then H ∩ add(o′ ) = ∅ (because o′ Jpre(o′ )K is not mutex (S2)) and there exists y′ ∈ pre(o′ ) ∩ del(o′ ) s.t. y′ ∈ γ(H) (because γ(H) is a fam-group). (2a) If y′ ∈ H, then eff(qo′ )[VH] = ⊥H, because H ∩ add(o′ ) = ∅. (2b) If y′ ∈ γ(H) \ H, then H ∩ pre(o′ ) = ∅ (because y′ ∈ pre(o′ ) and pre(o′ ) ̸∈ MG), therefore pre(qo′)[VH] = ⊥H.

Now, we are ready to prove that RSE-invertibility of mutex groups implies RSE-invertibility of the corresponding FDR variables, and vice versa. We separate the case of singleton mutex groups, and larger mutex groups, which require the additional condition (S7).

Lemma 7. Let G = {f} be a mutex group. Then f is RSEinvertible iff VG is RSE-invertible.

• Proof. "⇒": Since dom(VG) = {f,⊥G} and we need to prove that every edge in the DTG of VG is RSE-invertible, we need to investigate two cases:
• Let (f, qo,⊥G) be an edge in the DTG of VG. Then eff(qo)[V ] = ⊥G and either pre(qo)[V ] = f or V ̸∈ vars(pre(qo)). So we have f ̸∈ add(o) and f ∈ del(o), therefore there exists o′ s.t. f ∈ add(o′ ) and pre(o′ ) ⊆ pre(o)∪add(o). So, f ̸∈ pre(o′ ) because f ∈ add(o′ ), therefore pre(qo′)[VG] = ⊥G or VG ̸∈ vars(pre(qo′)), therefore there is an edge (⊥G, qo′ , f ). The rest follows from Lemma 6.
• Let (⊥G, qo, f) be an edge in the DTG of VG. Then eff(qo)[VG] = f and either pre(qo)[VG] = ⊥G or V ̸∈ vars(pre(qo)). So, we have f ∈ add(o) and therefore f ̸∈ pre(o) and f ̸∈ del(o). Therefore, there exists o′ ∈ O s.t. f ∈ del(o′ ) and pre(o′ ) ⊆ pre(o) ∪ add(o). Now, to prove that there is an edge (f, qo′ ,⊥G) (and therefore this lemma follows from Lemma 6), we need to show that pre(qo′)[VG] ̸= ⊥G, i.e., pre(qo′)[VG] = f or V ̸∈ vars(pre(qo′)). If pre(qo′)[VG] = ⊥G, then there is f ′ ∈ γ(G) s.t. f ′ ∈ pre(o′ ) ∩ del(o′ ), because γ(G) is a famgroup. Therefore, {f, f ′ } ⊆ del(o′ ), which is a contradiction because {f} ∪ pre(o′ ) is a mutex (S2).

"⇐": If VG is RSE-invertible, then for every edge (x, qo, x′ ) in DVG there exists (x′ , qo′ , x) such that pre(qo′)[V \ VG] ⊆ pre(qo)[V \ VG] ∪ eff(qo)[V \ VG]. Therefore, it follows from Lemma 6 that also pre(o′ ) ⊆ pre(o) ∪ add(o). Moreover, from the construction (T2b) it follows that if x′ = f, then f ∈ add(o) and f ∈ del(o′ ), and vice versa, if x = f, then f ∈ del(o) and f ∈ add(o′ ). Therefore, the conditions (I1-3) are satisfied.

A mutex group M ∈ G such that |M| ≥ 2 requires the fam-group map γ to map M to its superset fam-group (S7). Recall the example in Figure 1. The facts f1 and f2 are RSEinvertible, but f3 and f4 are not, because of the operator o34. So, we would like to construct an RSE-invertible variable from G = {f1, f2}. If we set γ(G) = ∅, then the resulting DTG (Figure 1c) will have edges between f1 and f2 that are not RSE-invertible, because the operator o31 has f3 as its precondition, which is not part of pre(o42)∪add(o42). However, γ(G) = F results in the RSE-invertible DTG (Figure 1b).

Lemma 8. Let G ∈ G be a mutex group with |G| ≥ 2 and γ(G) ̸= ∅. Then G is RSE-invertible iff VG is RSE-invertible.

Proof. "⇒": Since γ(G) is a fam-group s.t. G ⊆ γ(G) and |G| ≥ 2 and (S6), for every operator o ∈ O and every f ∈ G it holds that f ∈ del(o) implies f ∈ pre(o). Let (d, qo, d′ ) denote an edge in the DTG of VG. Then eff(qo)[VG] = d′ and either pre(qo)[VG] = d or VG ̸∈ vars(pre(qo)). Now, if we show that there also exist an edge (d′ , qo′d) for some o′ ∈ O s.t. pre(o′ ) ⊆ pre(o) ∪ add(o), then the rest follows from Lemma 6. So three cases need to be investigated.

1. If d, d′ ∈ G, then d′ ∈ add(o). And since γ(G) is a fam-group, we have VG ∈ vars(pre(qo)) and d ∈ pre(o) ∩ del(o). Therefore, there exists o′ ∈ O s.t. d ∈ add(o′ ) and pre(o′ ) ⊆ pre(o) ∪ add(o). Thus, d′ ∈ pre(o′ ), because d ̸∈ pre(o′ ) and γ(G) ∩ (pre(o) ∪ add(o)) = {d, d′ }. Therefore, there exists an edge (d′ , qo′ , d).

(2) If d ∈ G and d′ = ⊥G, then add(o) ∩ G = ∅ and del(o) ∩ G ̸= ∅, therefore d ∈ del(o), because otherwise there would exist x ∈ G, x ̸= d, s.t. x ∈ del(o), therefore x ∈ pre(o), therefore pre(qo)[VG] = x which is in contradiction. So we have d ∈ del(o) and also d ∈ pre(o). Therefore, there exists o′ s.t. d ∈ add(o′ ) and pre(o′ ) ⊆ pre(o) ∪ add(o). So since d ∈ pre(o) and add(o) ∩ G = ∅, then pre(o′ )∩G = ∅, therefore we have eff(qo′ )[VG] = d and either pre(qo′)[VG] = ⊥G or VG ̸∈ vars(pre(qo′)). Therefore, we have an edge (⊥G, qo′ , d).

(3) If d = ⊥G and d′ ∈ G, then d′ ∈ add(o), therefore there exists f ∈ γ(G) \ G s.t. f ∈ pre(o) ∩ del(o). Thus, there exists o′ ∈ O s.t. f ∈ add(o′ ) and pre(o′ ) ⊆ pre(o) ∪ add(o). Hence, d′ ∈ pre(o′ ) ∩ del(o′ ) because γ(G) ∩ pre(o′ ) ∩ del(o′ ) ̸= ∅ (γ(G) is a fam-group) and (pre(o) ∪ add(o)) ∩ γ(G) = {f, d′ } and f ̸∈ pre(o′ ). Therefore, pre(qo′ )[VG] = d′ and eff(qo′ )[VG] = ⊥G, and thus we have (d′ , qo′ , ⊥G).

"⇐": Let (x, qo, x′ ) denote an edge in DVG . If x′ ∈ G, then x′ ∈ add(o) (T2b). Since γ(G) is a fam-group, either pre(qo)[VG] = ⊥G, or pre(qo)[VG] = x s.t. x ∈ G. Therefore if x ∈ G, then x ∈ pre(o) ∩ del(o). Therefore, for every such qo it holds that either G∩del(o) ̸= ∅ or G∩add(o) ̸= ∅. Since VG is RSE-invertible, for every edge (x, qo, x′ ) there exist an edge (x′ , qo′ , x) s.t. pre(qo′ )[V \ VG] ⊆ pre(qo)[V \ VG]∪eff(qo)[V \VG], therefore it follows from Lemma 6 that pre(o′ ) ⊆ pre(o) ∪ add(o). Hence, the conditions (I1-3) are satisfied.

Theorem 9. Let G ∈ G be a mutex group with |G| = 1 or γ(G) ̸= ∅. Then G is RSE-invertible iff VG is RSE-invertible.

Proof. It follows directly fromLemma 7 and Lemma 8.

5 Causal Graph

Besides RSE-invertibility of black variables, the tractable fragment of red-black planning requires the black causal graph to be acyclic. To achieve that, we show how to find a causal link between mutex groups that is translated into FDR.

Definition 10. Given a mutex group G ∈ 2F , two distinct facts f ∈ G and f ′ ̸∈ G, and a fam-group map γ on 2F , we say that there is a causal link from (G, f) to f ′ iff there exists an operator o ∈ O such that (i) f ′ ∈ del(o) ∪ add(o), and (ii) f ∈ pre(o)∪del(o)∪add(o), or γ(G)∩pre(o) ̸= ∅.

Theorem 11. Let EΠ = 〈Π, G, γ〉 be an MGE-STRIPS task with operators O, A,B ∈ G be two distinct mutex groups, and CGV be the causal graph of P(EΠ). There is an edge (VA, VB) in CGV iff there exist f ∈ A and f ′ ∈ B such that there is a causal link from (A, f) to f ′ .

Proof. "⇐": Let o ∈ O be the operator inducing the causal link from (A, f) to f ′ . If f ∈ pre(o), then pre(qo)[VA] = f. If f ∈ add(o), then eff(qo)[VA] = f. If f ∈ del(o), then either eff(qo)[VA] = ⊥A or there exist x ∈ A s.t. eff(qo)[VA] = x. If γ(A) ̸= ∅ and γ(A)∩pre(o) ̸= ∅, then either pre(qo)[VA] = x for some x ∈ A, or pre(qo)[VA] = ⊥A. Therefore, VA ∈ (vars(pre(qo))∪vars(eff(qo)), and for similar reasons VB ∈ vars(eff(qo)).

"⇒": If (VA, VB) in CG{VA,VB}, then there exists qo ∈ O s.t. VA ∈ (vars(pre(qo)) ∪ vars(eff(qo))) and VB ∈ vars(eff(qo)). If pre(qo)[VA] ∈ A or eff(qo)[VA] ∈ A, and eff(qo)[VB] ∈ B, then it follows trivially that A∩ (pre(o) ∪ add(o)) ̸= ∅ and B ∩ add(o) ̸= ∅. So what remains is to show that (i) if pre(qo)[VA] = ⊥A, then γ(A) ̸= ∅ and γ(A) ∩ pre(o) ̸= ∅ (T2a); (ii) if eff(qo)[VA] = ⊥A, then A ∩ del(o) ̸= ∅ (T2b); (iii) if eff(qo)[VB] = ⊥B, then B ∩ del(o) ̸= ∅ (T2b).

Theorem 11 shows that causal graphs in the FDR planning task P(EΠ) correspond exactly to the causal links in EΠ as per Definition 10. So, extracting acyclic causal graphs needed for the tractable fragment of red-black planning require to find subsets of mutex groups consisting of facts whose causal links form an acyclic graph. In the next section, we show how to find such subsets of mutex groups.

6 Inference of Black Variables

We have shown how to find RSE-invertible mutex groups and what conditions must be met in order to form a causal link between FDR variables created from mutex groups. Now, we put everything together and show how to select mutex groups that can be translated into RSE-invertible FDR variables that form an acyclic causal graph, and thus can be painted black.

Definition 12. Given a STRIPS planning task Π with facts F, a fam-group map γ over 2F , and a set of mutex groups K ⊆ 2F such that for every G ∈ K it holds that either |G| = 1, or γ(G) ̸= ∅, X(Π, K, γ) = (V, E) denotes a digraph with vertices V ⊆ K×F and edges E ⊆ V ×V , where (G, f ) ∈ V iff G ∈ K and f ∈ G, and ((G, f), (G′ , f ′ )) ∈ E iff f = f ′ or there is a causal link from (G, f) to f ′ . Given a cycle c in X(Π, K), let C(c) = {G | (G, f) ∈ c}.

Theorem 13. Let EΠ = 〈Π, G,MG〉 be an MGE-STRIPS planning task, K ⊆ G be a set of RSE-invertible mutex groups such that |G| = 1 or γ(G) ̸= ∅ for every G ∈ K, and VK be the set of corresponding variables from P(EΠ). Then CGVK is acyclic iff for every cycle c in X(Π,K, γ) it holds that |C(c)| = 1.

Proof Sketch. It follows directly from Theorem 11, because if |C(c)| = 1, then every cycle of causal links is contained within one mutex group.

Algorithm 1 encapsulates the algorithm for inference of a set of RSE-invertible mutex groups K, and a fam-group map γ, that can be translated into red-black planning task as black variables. We assume we are given a STRIPS planning task Π, and a set of fam-groups H ⊆ 2F that can be inferred by one of the algorithm proposed by Helmert [2009], Fiˇser and Komenda [2018], or Fiˇser [2020]. In steps 1-3, we prepare RSE-invertible mutex groups and a mapping to the corresponding fam-groups. In step 1, H′ is constructed as a set of singletons, each corresponding to the RSE-invertible fact that is not covered by any input fam-group, i.e., these facts can be translated only to binary FDR variables. In step 2, the fam-group map is constructed in the following way: (i) each singleton fromH′ is mapped to an empty set, and (ii) for each fam-group G containing at least one RSE-invertible fact, we Algorithm 1: Inference of RSE-invertible mutex groups forming acyclic causal graph.

Input: A STRIPS planning task Π = 〈F, O, sI , sG〉, a set of fam-groups H ⊆ 2F , a set of

• RSE-invertible facts N ⊆ F. Output: A set of RSE-invertible mutex groups K, a fam-group map γ over K 1 H′ ← {{f} | f ∈ N \ ⋃G∈H G}; 2 Construct a fam-group map γ ′ : γ ′ (G) = ∅ for every G ∈ H′ , and γ ′ (G ∩ N ) = G for every G ∈ H s.t. G∩N ̸= ∅; 3 H⋆ ←H′ ∪ {G∩N | G ∈ H,G∩N ̸= ∅}; 4 Construct the digraph X(Π,H⋆ , γ ′ ) = (V, E).; 5 Find vertices V ′ ⊆ V such that for every cycle c in the subgraph of X(Π,H⋆ , γ) induced by V ′ it holds that |C(c)| = 1; 6 Z ← {(G, {f | (G, f) ∈ V ′ }) | (G, f ′ ) ∈ V ′ }.; 7 Construct a fam-group map γ: For every (G,X) ∈ Z,
• set γ(X) = ∅ if |X| = 1 and γ(X) = G otherwise; 8 K← {X | (G,X) ∈ Z};

map its RSE-invertible subset G∩N to G. In step 3, H⋆ is constructed as a set of RSE-invertible mutex groups covering all RSE-invertible facts. In step 4, the graph defined in Definition 12 is constructed, and in step 5, we find a subset of vertices having cycles only within each mutex group. Finally, in the last three steps we extract the solution.

Note that the step 5 is a variant of an NP-complete feedback vertex set problem [Karp, 1972]. We decided to use a naive approach and solve this problem by an integer linear program (ILP), where each vertex from X(Π,H⋆ , γ ′ ) corresponds to a binary variable, and each constraint corresponds to a cycle that has to be avoided. Instead of listing all cycles, we first add all cycles between pairs of vertices from different mutex groups, then we solve the problem, and check whether the resulting solution has a cycle. If we find a cycle, we add it as another constraint, solve the problem, and continue in this manner until we find a feasible solution.

As objective function of the ILP, we tried two variants. The first variant is simply a maximization of the number of facts in the resulting mutex groups. The second variant weights facts using the number of conflicts in a relaxed plan π+ obtained from the FF heuristic [Hoffmann and Nebel, 2001] computed on the STRIPS representation. Following prior work [Domshlak et al., 2015], we say a fact f has a conflict if there is an operator o in π+ such that f ∈ pre(o) and f is not satisfied when executing π+ with the non-relaxed semantics. For each mutex group M, we sum the number of conflicts from all f ∈ M, and we set the weight of each fact f ∈ M as the sum over |M|. This way we prioritize mutex groups containing facts with most conflicts in the relaxed plan.

Note that Algorithm 1 describes only the inference of RSEinvertible variables. The rest of the FDR variables, i.e., the red variables, are constructed from the remaining facts not covered by the resulting black variables by greedy approach described by Helmert [2009], i.e., we greedily maximize the size of red variables.

7 Experimental Evaluation

We implemented Algorithm 1 in C, used fam-groups inferred from PDDL [Fiˇser, 2020] 2 , and used the red-black heuristic hRB [Domshlak et al., 2015] implemented in FD [Helmert, 2006]. The experiments were performed on Intel(R) Xeon(R) Scalable Gold 6146 machines with CPLEX solver v12.6, and time and memory limits of 30min and 8GiB. Out of all benchmarks from International Planning Competitions of 1998 to 2018 satisficing planning tracks, we selected all tasks where no conditional effects were created and at least one variable could be painted black.

We compare the following configurations: the baseline configuration B runs the painting strategy denoted as A 3 by Domshlak et al. [2015] on the default FDR encoding [Helmert, 2009]; M maximizes the number of black facts using Algorithm 1; C is the variant of Algorithm 1 using conflicts in a relaxed plan; and the "oracle" O picks the best FDR encoding and painting for each tested task. It considers B, and five best encodings (by objective value) from each of M and C, which we obtain by repeatedly solving the corresponding ILP, each time disallowing previous solutions by additional constraints. The encodings are chosen in terms of coverage, preferring tasks solved in the initial state by hRB. O serves to illustrate the potential of our customized encodings, assuming perfect knowledge about which encoding works best for a given task.

The most time-demanding part of Algorithm 1 is solving the ILP (step 5). The average and median time spent in this step was 3.3 seconds and 12 milliseconds, respectively, for both C and M. The maximum was more than six minutes, but it took more than a minute only for 15 tasks in transport, 7 tasks in visitall, and 1 task in the satellite domain. Figure 2 shows a comparison of running times (in seconds) of the whole translation process. Although Algorithm 1 often requires more time in comparison to the greedy approach of the baseline, it, for most cases, leaves enough time for the planner, as we describe below.

The scatter plots in Figure 3 show that our methods are able to increase the number of black facts by several orders of magnitude. The oracle often uses significantly less black facts than B, indicating that it is not necessarily beneficial to have more black facts. In fact, having more black variables (facts) can negatively impact heuristic computation time, without improving informativeness.

2 https://gitlab.com/danfis/cpddl, branch ijcai21-fdr-red-black

3 The painting strategy greedily paints variables red until the black causal graph is acyclic, preferring keeping variables with larger number of incident edges to black variables.

Table 1 shows the number of tasks solved (coverage) in the left, and the number of tasks solved by hRB in the initial state in the center. B clearly outperforms M which, again, shows that maximizing the number of black facts is not necessarily the best painting strategy. C and B are very similar in coverage, with strengths in different domains. C can solve six more tasks in the initial state resulting from only two domains, blocks and satellite.

The oracle variant O demonstrates the potential of our approach if we better understand how to select the best encoding for a given task. B already solves a large portion of tasks, but here we show that it is still possible to create an encoding and painting that could further increase this number by at least 25 tasks, and 14 more can be solved in the initial state. Unfortunately, it is unclear how to directly compare the quality of individual encodings for a given task without running the search. Maximizing the number of black facts turned out to be too simplistic as an optimization criterion. Considering conflicts in a relaxed plan improves the results in some domains, but it is still unclear what properties identify a good FDR encoding and painting for red-black planning.

The rightmost column in Table 1 shows the number of tasks with a single maximal set of black variables. That is, it shows the number of tasks where different paintings can only be achieved by painting black a subset of the facts that were already painted black by C and M. In other words, both C and M created exactly the same set of black variables, but B could paint only less variables black. This is exactly what happened in the depot domain where painting less variables black proved to generate a more suitable FDR for the redblack heuristic.

8 Conclusion

We devised a method to custom-design FDR encodings of classical planning tasks, showcasing how a tractable fragment of red-black planning can be formulated into the translation from PDDL to FDR. By describing this translation as an integer linear program, we can explore the space of possible tractable red-black FDR encodings. Our evaluation shows an increase in the number of black facts by several orders of magnitude. Our approach is flexible, allowing to express complex properties based on, e.g., DTGs or causal graphs. Thus, custom-designed FDR encodings have the potential of benefiting planning techniques beyond red-black planning, opening up a wide range of possibilities for future research.

Acknowledgements

Daniel Gnad was supported by the German Research Foundation (DFG), under grant HO 2169/6-2, "Star-Topology Decoupled State Space Search". J¨org Hoffmann's research group has received support by DFG grant 389792660 as part of TRR 248 (see perspicuous-computing.science).