Fact-Alternating Mutex Groups for Classical Planning (Extended Abstract)

1 Introduction

State invariants in domain-independent planning are certain intrinsic properties of a particular planning task that hold in all states reachable from the initial state. State invariants tell something about the internal structure of the problem, which can be further utilized in the process of solving the task. A rather scarce literature on the inference of state invariants include methods using different "guess, check, and repair" approaches [Gerevini and Schubert, 1998; 2000; Helmert, 2009; Rintanen, 2000], inference based on sampling of a state space [Mukherji and Schubert, 2005; 2006], a reachability analysis generalized to h m heuristics [Haslum and Geffner, 2000; Haslum, 2009; Alc´azar and Torralba, 2015], or an iterative weakening of more general invariants formed as a disjunction of possibly negated facts [Rintanen, 2008].

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Fiˇser and Komenda, 2018].

In this work, we are particularly interested in the inference of state invariants called mutex groups consisting of facts that are pairwise mutually exclusive. Therefore, a mutex group states that any reachable state can contain at most one fact from the mutex group.

The most straightforward application of mutex groups is in the translation to finite domain representation (FDR, or SAS+) [B¨ackstr ¨om and Nebel, 1995; Edelkamp and Helmert, 1999; Helmert, 2009]. Given a set of mutex groups, the FDR can be constructed by creating variables from those mutex groups that cover all facts. A special value "none of those" can be added to some variables, if needed, to cover a situation where none of the facts from the invariant is present in the state.

State invariants (including mutex invariants) are also critical for improving the performance of SAT planners [Kautz and Selman, 1992; Sideris and Dimopoulos, 2010].

Exploration of the state space in a symbolic search with Binary Decision Diagrams (BDDs) is not carried out through the expansion of single states but rather by construction of BDDs representing sets of states, which potentially provides an exponential saving in memory consumption. State invariants encoded as BDDs can be used for the pruning of unreachable states during search and also during the preprocessing of the planning task for pruning operators that generate deadend states [Torralba and Alc´azar, 2013]. The connection between state invariants and dead-end states was recently studied by Lipovetzky et al. [2016].

This work is aimed mainly at the analysis and inference of mutex groups in the context of STRIPS planning [Fikes and Nilsson, 1971]. We introduce a new type of mutex group called the fact-alternating mutex group and we discuss its relation to the general mutex group and to the mutexes inferred by the heuristic h m [Haslum and Geffner, 2000]. We also discuss the properties of fact-alternating mutex groups, in particular their connection to dead-end states.

We provide a complexity analysis showing that the inference of the maximum sized mutex group is PSPACEComplete whereas inferring the maximum sized factalternating mutex group is NP-Complete. The complexity analysis leads to a novel inference algorithm that is complete with respect to maximal fact-alternating mutex groups.

This paper is an extended abstract of the previously published work [Fiˇser and Komenda, 2018], so it contains only the main results without any proofs. Detailed explanations and proofs can be found in the original paper.

2 Mutex Groups

Definition 1. A STRIPS planning task Π is specified by a tuple Π = 〈F, O, sinit , sgoal 〉, 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, sinit ⊆ F is an initial state and sgoal ⊆ F is a goal specification. An operator o is a triple o = 〈pre(o), add(o), del(o)〉, where pre(o) ⊆ F is a set of preconditions of the operator o, and add(o) ⊆ F and del(o) ⊆ F are sets of add and delete effects, respectively. All operators are well-formed, i.e., add(o) ∩ del(o) = ∅ and pre(o) ∩ add(o) = ∅. 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 o[s] = (s \ del(o)) ∪ add(o). A state s is a goal state iff sgoal ⊆ s.

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 = oi[si-1] for 1 ≤ i ≤ n. The resulting state of this application is π[s0] = sn. A state s is called a reachable state if there exists an applicable operator sequence π such that π[sinit ] = s. A set of all reachable states is denoted by R. An operator o is called a reachable operator iff it is applicable in some reachable state. A state s is called a deadend state iff sgoal ̸⊆ s and there does not exist any applicable operator sequence π such that sgoal ⊆ π[s].

Definition 2. A mutex M ⊆ F is a set of facts such that for every reachable state s ∈ R it holds that M ̸⊆ s.

Definition 3. A mutex group M ⊆ F is a set of facts such that for every reachable state s ∈ R it holds that |M ∩ s| ≤ 1. A mutex group that is not a subset of any other mutex group is called a maximal mutex group.

A mutex and a mutex group are both defined as invariants with respect to all states reachable from the initial state by a sequence of operators. A mutex invariant states that certain facts cannot be part of the same reachable state at the same time. So for example, a mutex {f1, f2, f3} states that there is no reachable state containing all three facts, but a state containing {f1, f2}, or {f1, f3}, or {f2, f3} can still be reachable.

A mutex group is defined as a set of facts out of which, maximally, one can be true in any reachable state, i.e., the facts from a mutex group are pairwise mutex. It is also easy to see that every mutex containing exactly two facts (mutex pair) is also a mutex group, because if two facts cannot both be part of the same reachable state, then, at most, one of them can be a part of any reachable state, which is exactly the definition of a mutex group

Proposition 4. Let M ⊆ F denote a set of facts such that |M| ≥ 2 and let DM denote a set of all pairs of all facts from M, i.e., DM = {p | p ⊆ M, |p| = 2}. M is a mutex group iff every P ∈ DM is a mutex group.

It is well known that determining existence of a plan of a STRIPS planning task is PSPACE-Complete [Bylander, 1994]. And as it turns out, finding the maximum sized mutex group is also PSPACE-Complete.

Theorem 5. Let MAXIMUM-MUTEX-GROUP denote the following decision problem: Given a planning task Π and an integer k, does Π contain a mutex group of size at least k? MAXIMUMMUTEX-GROUP is PSPACE-Complete.

Since the facts from a mutex group are pairwise mutex, we can infer mutex groups in the following way. Given a set of mutex pairs, we construct a graph where each node corresponds to a fact and each edge connects two facts that form a mutex pair. In such a graph, any set of nodes that is a clique (a complete induced subgraph) corresponds to a set of facts that is a mutex group.

Therefore it follows that if we somehow obtain a complete set of mutex pairs, we can determine the maximum sized mutex group simply by finding the maximum sized clique which is NP-Complete [Karp, 1972]. However, finding the maximum sized mutex group is as hard as planning itself, therefore, it follows that inference of a complete set of mutex pairs is also as hard as finding a plan.

In the next section we introduce a novel subclass of mutex groups of which inference is NP-Complete.

3 Fact-AlternatingMutex Groups

Definition 6. A fact-alternating mutex group (fam-group) M ⊆ F is a set of facts such that |M ∩ sinit | ≤ 1 and |M ∩ add(o)| ≤ |M ∩ pre(o) ∩ del(o)| for every operator o ∈ O. A fam-group that is not a subset of any other famgroup is called a maximal fam-group.

Proposition 7. Every fam-group is a mutex group.

The name fact-alternating mutex group was chosen to stress its interesting property, which lies in the mechanism by which facts from a fam-group appear and disappear in particular states after the application of the operators. Consider a fam-group M and a state s that does not contain any fact from M (M ∩s = ∅). Now we can ask whether any following state π[s] can contain any fact fromM. The answer is that it cannot because any operator o applicable in s that could add a new fact fromM to the following state o[s] would need to have a fact from M in its precondition (M ∩ pre(o) ̸= ∅) which is in contradiction with the assumption that s contains no fact from M. So it follows that facts from each particular famgroup alternate between each other as new states are created and once the facts disappear from the state they cannot ever reappear again in any following state.

Proposition 8. Let M denote a fact-alternating mutex group and let s denote a state. If |M ∩ s| = 0, then for every operator sequence π applicable in s it holds that |M ∩ π[s]| = 0.

Proposition 8 can be used for the detection of dead-end states. A dead-end state is a state from which it is impossible to reach any goal state by a sequence of applied operators. Consider a fam-group M having a non-empty intersection with the goal (|M ∩ sgoal | ≥ 1) and a reachable state s that does not contain any fact fromM (|M ∩ s| = 0). Such a state must be clearly a dead-end state, because it follows from Proposition 8 that all states reachable from s, including the goal states, cannot contain any fact fromM, which is formally stated in the following simple corollary of Proposition 8.

Corollary 9. Let M ⊆ F denote a set of facts and let s denote a state. If M is a fam-group and |M ∩ sgoal | ≥ 1 and |M ∩ s| = 0, then s is a dead-end state.

The operators that have more than one fact from some mutex group (and, therefore, also from some fam-group) in its preconditions cannot be applicable in any reachable state. Similarly, the operators with add effects containing more than one fact from some mutex group (fam-group) are also unreachable, because the resulting state would be in contradiction with the mutex group (fam-group). 1 Such operators can be safely removed from the planning task. These two simple rules are not limited to the fact-alternating mutex groups, but they can be used with any type of mutex group.

However, fam-groups provide one additional method for pruning superfluous operators. Consider a fam-group M having a non-empty intersection with the goal and an operator o that does not have any fact from M in its add effects, but it has a non-empty intersection with its preconditions, delete effects, and the fam-group M. The resulting state of the application of the operator o would not contain any fact from the fam-group M. Therefore, such a state would be a deadend state for the reasons already explained. This means that the operator o can be safely removed from the planning task because it can only produce dead-end states. In other words, the states resulting from the application of the operator are not useful in finding a plan and, therefore, the operator itself is not useful too.

Corollary 10. Let M ⊆ F denote a set of facts, let s denote a state and let o ∈ O denote an operator applicable in s. If M is a fam-group and |M ∩ sgoal | ≥ 1 and |M ∩ pre(o) ∩ del(o)| ≥ 1 and |M ∩ add(o)| = 0, then o[s] is a dead-end state.

Since fam-groups are not defined using restrictions over all reachable states, but only over the initial state and all operators, it is easy to see that given a set of facts, we can check whether this set is a fam-group in a polynomial time. This suggests that the inference of the maximum sized fam-group is not as hard as the inference of the maximum sized mutex group-and indeed, it is only NP-Complete.

Theorem 11. Let MAXIMUM-FAM-GROUP denote the following decision problem: Given a planning task Π and an integer k, does Π contain a fam-group of size at least k? MAXIMUMFAM-GROUP is NP-Complete.

Considering the tight relationship between graph cliques and mutex groups, it is not surprising that the maximum possible number of mutex groups is exponential in the number of facts. However, the same holds for fam-groups and this number can be expressed exactly as is done in the following proposition.

Proposition 12. Let Π = 〈F,O, sinit , sgoal 〉 denote a planning task and let n = |F| denote a number of facts in Π. The maximum possible number µ(n) and µfa(n) of maximal mutex groups and maximal fam-groups, respectively, for n ≥ 2, is the following:

1 This is a special case of disambiguation proposed by Alc´azar et al. [2013].

4 h2 Mutex Pairs and Fact-AlternatingMutex Groups

The h m heuristic [Haslum and Geffner, 2000] is able to produce a set of mutexes as its side effect. Specifically, the h2 heuristic is the most common method for generating pairs of facts that cannot hold together in any reachable state, i.e., mutex pairs. The mutex pairs generated by h2 will be referred to as h2 -mutexes from now on. We already know that given a set of mutex pairs (and therefore also h2 -mutexes) we can infer mutex groups using an algorithm for finding cliques in a graph. An interesting question now is, what is the relationship between fam-groups and h2 -mutexes?

The formal definition of an h2 -mutex below is based on an alternative characterization of the h m heuristic using a modified planning task introduced by Haslum [2009].

Definition 13. Let Π = 〈F,O, sinit , sgoal 〉 denote a planning task. The planning task Π2 = 〈Φ, Ω, ψinit , {}〉 consists of a set of facts Φ = {φc | c ⊆ F, |c| ≤ 2}, a set of operators Ω, an initial state ψinit = {φc | c ⊆ sinit , |c| ≤ 2}, and an empty goal specification. For each operator o ∈ O and for each subset of facts g ⊆ F such that |g| ≤ 1 and g is disjoint with add(o) and del(o), the planning task Π2 contains an operator ωo,g ∈ Ω with: pre(ωo,g) = {φc | c ⊆ (pre(o) ∪ g), |c| ≤ 2}, add(ωo,g) = {φc | c ⊆ (add(o) ∪ g), c ∩ add(o) ̸= ∅, |c| ≤ 2}, del(ωo,g) = ∅.

Let Ψ denote a set of all reachable states in Π2 . A pair of facts {f1, f2} ⊆ F such that f1 ̸= f2 is an h2 -mutex iff for every reachable state ψ ∈ Ψ, it holds that φ{f1,f2} ̸∈ ψ.

The definition is altered so that it contains empty goal specification, because it is not necessary for inference of mutex pairs, and it is formulated specifically for h2 , not for a general h m . The Π2 is an ordinary STRIPS planning task, but we used Greek letters to describe its parts to prevent confusion with the original planning task Π.

Now once we have formally defined mutex pairs generated by h2 , we find that h2 always produces a (possibly non-strict) superset of decomposition of all fam-groups. More precisely, any mutex pair that is a subset of a fam-group must be an h2 - mutex, but not the other way around. This also means that if we infer h2 -mutexes and use an algorithm for listing maximal cliques to join the h2 -mutexes into larger mutex groups, then the resulting mutex groups will be non-strict supersets of fam-groups. However, the mutex groups created from h2 - mutexes do not necessarily have the same properties regarding detection of dead-end states as fam-groups described in Proposition 8, Corollary 9 and Corollary 10.

Theorem 14. Let M ⊆ F denote a set of facts such that |M| ≥ 2 and let H = {p | p ⊆ M, |p| = 2}. If M is a fam-group, then every h ∈ H is an h2 -mutex.

Input: Planning task Π = 〈F, O, sinit , sgoal 〉

Output: A set of fam-groups M

Initialize ILP with constraints according to Equations 1 and 2;

Set objective function of ILP to maximize ∑fi∈F xi;

M ← ∅;

Solve ILP and if a solution was found, save the resulting fam-group into M;

while |M| ≥ 1 do

Add M to the output set M;

Add constraint according to Equation (3) using M; M ← ∅;

Solve ILP and if a solution was found, save the resulting fam-group into M;

end

Algorithm 1: Inference of fam-groups using ILP.

5 Inference of FAM-Groups

In this section, we describe an algorithm for the inference of fam-groups that is complete with respect to maximal famgroups. The main part of the algorithm consists of an integer linear program (ILP) based on the definition of fam-groups (Definition 6) rewritten into a set of constraints. The ILP is constructed in the following way.

Each variable xi of the ILP corresponds to a fact fi ∈ F from the planning task. Variables can acquire binary values 0 or 1 only, 0 meaning that the corresponding fact is not present in the fam-group and 1 meaning the corresponding fact is part of the fam-group. Definition 6 can be rewritten into ILP constraints as follows:

Equation (1) corresponds to the restriction on the initial state, and Equation (2) to the restrictions on the operators. The objective function of the ILP is to maximize ∑fi∈F xi, which enforces the inference of the maximal fam-group.

The solution to this ILP is only one fam-group, so the ILP is solved repeatedly, each time with added constraints excluding already inferred fam-groups. The constraint excluding a fam-group M and all its subsets from the next solution is the following:

The whole algorithm is encapsulated in Algorithm 1. First, the ILP constraints are constructed according to Equations 1 and 2, which ensures that the solutions of the ILP will be fam-groups. Then, in turn, a maximal fam-group is inferred through the ILP solution and consequently removed from future solutions using the added constraint corresponding to Equation (3). The cycle continues until the inferred famgroups consist of, at least, one fact.

Theorem 15. Algorithm 1 is complete with respect to the maximal fact-alternating mutex groups.

6 Experimental Results

The inference of fam-groups was experimentally evaluated on all domains from the optimal deterministic track of the International Planning Competition (IPC) 2011 and 2014 that do not contain any conditional effects after grounding (using Intel Xeon E5-4617 2.9GHz, 8 GB RAM). Here we present a singificantly reduced results from the original paper. We compare the implementation of Algorithm 1 (fa) and the state-of-the-art algorithm for inference of mutex groups from the Fast Downward planner (fd) [Helmert, 2006].

Every mutex group that was generated by fd was also generated by fa or it was a subset of some mutex group generated by fa. Overall, fa generated a richer set of mutex groups in 202 out of 540 problems (10 281 vs. 14 012). However, fa was much slower than fd. fd computed mutex groups under 1 second for almost all problems, but fa spent at average 6 seconds on a problem. Fig. 1 (left) shows a scatter plot of the number of inferred mutex groups in each problem for fa and fd.

We also compared the algorithms in terms of their pruning power. Mutex groups can be used for detection of operators that are either not reachable because their preconditions cannot be met, or the operators can generate only dead-end state, so they cannot be part of any plan. Also in this case fa provides better results than fd as can be seen on the scatter plot on Fig. 1 (right).

7 Conclusion

This paper is focused on the state invariants called mutex groups in the context of STRIPS planning. We provide the complexity analysis showing that the inference of the maximum sized mutex group is PSPACE-Complete. We introduce a new weaker type of mutex group called a fact-alternating mutex group (fam-group) and we show that the inference of the maximum sized fam-group is NP-Complete. Moreover, we describe an algorithm for inference of fam-groups that is complete with respect to the maximal fam-groups.

We prove that the h2 variant of h m heuristics [Haslum and Geffner, 2000] generates mutex pairs that are a superset of a pair decomposition of fam-groups. However, we also show that fam-groups has certain unique properties regarding detection of dead-end states, which is experimentally evaluated.

Acknowledgements

This Research was funded by the Czech Science Foundation (project no. 18-07252S).