Capturing (Optimal) Relaxed Plans with Stable and Supported Models of Logic Programs (Extended Abstract)

1 Introduction

AI Planning is the task of finding a sequence of actions, called a plan, that when applied to a given initial state transforms it to a state that satisfies all members of a given set of goal conditions. According to the STRIPS formulation of AI Planning, states and goal conditions are represented by sets of atomic propositions, and each action can have separate sets of atomic propositions as its preconditions, positive effects, and negative effects. Delete-free planning problems are those for which actions have no negative effects. A given planning problem can be relaxed into a delete-free problem, optimal solving of which provides lower bound of the optimal cost of the original problem. However, computing this lower bound, denoted by h+, is NP-equivalent [Bylander, 1994]. Also, h+ is hard to approximate [Betz and Helmert, 2009].

Computing h+ in an efficient way is important for multiple reasons. There have been many admissible heuristic functions that approximate h+ in polynomial time by computing lower bounds. Examples are the hmax heuristic [Bonet and Geffner, 2001], LM-cut heuristic [Helmert and Domshlak, 2009], set-additive heuristic [Keyder and Geffner, 2008], and cost-sharing approximations of hmax [Mirkis and Domshlak,

∗This is an extended abstract of [Rankooh and Janhunen, 2023] that received the Best Paper Award of ICLP 2023.

2007]. The informativeness of these heuristic functions cannot be evaluated unless we can compute the exact value of h+. Also, efficient solving of relaxed planning problems is in itself of importance, as there exist planning tasks of interest for the AI community whose actions are all delete-free [Gefen and Brafman, 2011; Robinson et al., 2014]. Another reason for the importance of efficient optimal relaxed planning is that optimal plans for non-relaxed planning problems can always be produced by iterative solving and reformulating relaxed planning tasks [Haslum, 2012].

Several approaches to solving relaxed planning problems have previously been introduced. The approaches include Boolean satisfiability (SAT) based encodings [Rankooh and Rintanen, 2022b], integer programming based models [Imai and Fukunaga, 2015; Rankooh and Rintanen, 2022a]; and a minimum-cost hitting set based method introduced by Haslum et al. [2012]. Here, we take an approach based on the stable and supported models of logic programs [Gelfond and Lifschitz, 1988; Marek and Subrahmanian, 1992]. Such models provide the semantical basis for answer set programming (ASP); see, e.g., [Brewka et al., 2011] for an overview. The ASP paradigm offers rule-based general-purpose modeling languages for knowledge representation and reasoning.

Both stable and supported models implement a form of minimality, i.e., atomic propositions are false by default. This is highly useful in the context of AI planning since state predicates are falsified in this sense and the encodings of planning problems can concentrate on specifying which state predicates become true or remain true inertially. This tends to lead to more compact encodings compared to those based on pure SAT and, furthermore, enable memory savings if native answer set solvers are used for actual computations.

In this work, we give an encoding of relaxed planning problems in ASP. We show that all relaxed plans can be bijectively captured with stable models of the produced logic program. While the supported model semantics of logic programs cannot be directly employed for this purpose, we show how by guaranteeing acyclicity in an underlying graph of the logic program, one may deploy supported models to harvest (optimal) relaxed plans of the planning problem. The logic program produced in this way inherits the causal nature of our stable model based encoding, in the sense that the direction of explanations provided by the rules is from causes/preconditions to effects. By reversing this direction, we establish a diagnostic encoding, which while still using the supported model semantics of logic programs, is shown to be more efficient than our causal encoding by our empirical study. Our experimental results show that our diagnostic supported model based encoding enables CLASP [Gebser et al., 2015] to solve more problems compared to the integer programming solver based state-of-the-art method.

2 Preliminaries

A STRIPS-style planning problem is a 5-tuple Π = 〈X, I,A,G, cost〉 where X is a finite set of Boolean state variables, also called atomic propositions. The initial state I and the set of goal conditions G are subsets of X. The finite set A is the set of actions. Each member ⃗a of A is a triple 〈pre(⃗a), add(⃗a), del(⃗a)〉, where pre(⃗a), add(⃗a) and del(⃗a) are sets of atomic propositions denoting the set of preconditions, positive effects, and negative effects of ⃗a, which are the atomic propositions that ⃗a requires, adds, and deletes, respectively. The cost function cost maps members of A to non-negative integers. We use the vector sign to distinguish actions from the corresponding atoms that represent them in logic programs.

States are represented as subsets of X. The successor s′ = exec⃗a(s) of a state s with respect to action ⃗a ∈ A is defined if pre(⃗a) ⊆ s, where the definition of s′ is (s\del(⃗a))∪add(⃗a). An action sequence ⃗ a1, ..., ⃗ an is executable (in a state s) if exec ⃗ a1,..., ⃗ an (s) = exec ⃗ an (...exec ⃗ a2 (exec ⃗ a1 (s))...) is defined. A plan for Π is a sequence π of actions from A such that G ⊆ execπ(I). The cost of plan π = ⃗ a1, ..., ⃗ an for Π, is defined by Σi=1,...,ncost( ⃗ ai). An optimal plan for Π is a plan with minimal cost.

For a given STRIPS planning problem Π = 〈X, I,A,G, cost〉, the delete relaxation [Bonet and Geffner, 2001] is defined as Π+ = 〈X, I,A+,G, cost〉, where A+ is defined from A by replacing the set of negative effects of each member of A with the empty set. Without loss of generality, we can define Π+ = 〈X, ∅,A+,G, cost〉, with an additional requirement that all members of I have been removed from G, and also from the preconditions and effects of members of A+.

A plan for Π+ is called a relaxed plan for the original problem Π. The minimal cost of plans of Π+ is denoted by h+(Π). If there is no relaxed plan for Π, we set h+(Π) to ∞.

In order to translate planning problems to logic programs, we consider logic programs that consist of rules of the forms:

The symbols a, b1 , . . . , bn with n ≥ 0, and c1 , . . . , cm with m ≥ 0 occurring in the rules are (propositional) atoms and "not" denotes negation by default. Rules of the forms (1) and (2) are known as normal and choice rules, respectively [Simons et al., 2002]. Intuitively, each rule r gives a reason to derive its head head(r) = a if the conditions in its body body(r) are met, i.e., atoms involved can be either derived or not by other rules. For a choice rule r of form (2), the derivation of head(r) is optional, enabling an exception to head(r) being false by default. We write body+(r) and body-(r)

for the sets of atoms b1 , . . . , bn (resp. c1 , . . . , cm) occurring positively (resp. negatively) in body(r). We say that r is a positive rule if body-(r) is empty.

The signature of a logic program P, denoted by At(P), is the set of atoms that occur in P. The positive dependency graph of P is DG+(P ) = 〈At(P ), ⪰〉 where a ⪰ b holds for a, b ∈ At(P) if head(r) = a and b ∈ body+(r) for some rule r ∈ P. If a ⪰ b, we say that a depends on b, and also denote this by 〈a, b〉 ∈ DG+(P).

An interpretation I ⊆ At(P ) determines which atoms a ∈ At(P) are true (a ∈ I) and which are false (a ̸∈ I). Then I satisfies a rule r ∈ P of form (1), denoted I |= r, if the satisfaction of the body, denoted I |= body(r), implies that head(r) ∈ I, i.e., I |= head(r). For a choice rule r of form (2), I |= r unconditionally. Moreover, the interpretation I is a (classical) model of P if I |= r holds for every r ∈ P . Each positive normal program P has a unique least model LM(P) obtained as the intersection ⋂{I ⊆ At(P) | I |= P}.

Given an interpretation I, the reduct rI of r with respect to I is obtained by partially evaluating the negative conditions of r. For a normal rule (1), rI = ∅ if ci ∈ I for some 1 ≤ i ≤ m and rI = {a ← b1 , . . . , bn} otherwise. For a choice rule (2), the latter case additionally requires that a ∈ I. Finally, for an entire logic program P, the reduct P I = ⋃r∈P rI and I is a stable model of P iff I = LM(P I ). We distinguish the supporting rules of P with respect to I, denoted by SRP (I), which are the normal rules whose bodies are satisfied, and the choice rules whose bodies and heads are satisfied. A model I |= P is supported (by P) when I = {head(r) | r ∈ SRP (I)}. Each stable model of P is supported, but supported models are not necessarily stable, such as I = {a} for P = {a ← a.}.

3 Relaxed Plans Captured with Stable Models of Logic Programs

Let Π = 〈X, I, A, G, cost〉 be a STRIPS planning problem, Π+ = 〈X, ∅, A+, G, cost〉 be the delete relaxation of Π, and P be a logic program consisting of rules of the form (1) g ← not g for every g ∈ G; (2) {a} ← q1 , . . . , qn for every ⃗a ∈ A with pre(⃗a) = {q1 , . . . , qn}; (3) p ← a for every ⃗a ∈ A and p ∈ add(⃗a). Intuitively, the first rule guarantees all goal atoms to be true in a model. The second rule explains the necessary conditions for the execution of an action ⃗a. The third rule enforces the positive effects in case ⃗a has been chosen to be in the model. We formally show that P captures the relaxed plans of Π as its stable models.

Theorem 1. There is a bijection f(A′ ) = ⋃⃗a∈A′(add(⃗a) ∪ {a}) between all subsets A′ of A+ which can be ordered to produce a relaxed plan for Π, and all stable models of P .

Theorem 1 shows that if P is augmented with an optimization constraint requiring minimization over the summation of the costs of actions in the answer sets, the cost of an optimal stable model of P is equal to h+(Π). The program P can be seen as a causal encoding of relaxed plans of P. That is because the direction of relaxed plan computation in P is from preconditions to actions, and from actions to effects. In other words, the direction is from causes to effects.

4 Relaxed Plans Captured with Supported Models of Logic Pograms

In this section, we recall the instrumentation of logic programs with acyclicity constraint, which allows capturing the stable models of a given logic program P with the supported models of another program TrACYC(P) [Bomanson et al., 2016]. We provide an adaptation of this method based on the structure of program P explained above. We then review the vertex elimination method, used previously for cycle prevention in the produced models of SAT formulas [Rankooh and Rintanen, 2022c; Rankooh and Janhunen, 2022]. We next show how this method could also be used to translate TrACYC(P) to new programs whose supported models represent stable models of P and relaxed plans of Π.

4.1 Instrumentation of Logic Programs with Acyclicity Constraint

We adopt the acyclicity translation TrACYC(P) of a logic program P [Bomanson et al., 2016] that deploys special dependency atoms dep(x, y) to express the activation of the respective arc 〈x, y〉 ∈ DG+(P) in the acyclicity constraint. For the sake of the compactness of the output program, we circumvent the introduction of dependency atoms for actions, by establishing dependencies only between atoms of the original planning problem. This way, the underlying graphs for which acyclicity must be guaranteed become considerably smaller than DG+(P).

The idea is to instrument P explained in the previous section with additional rules that capture well-support for atoms p ∈ X. For each pair 〈p, q〉, if there exists ⃗a ∈ A such that p ∈ add(a) and q ∈ pre(a), the potential dependency of p on q is expressed using a choice rule {dep(p, q)} ← q. Also, atoms ws(a1, p) , . . . , ws(ak, p), for actions {⃗a1 , . . . ,⃗ak} that add p enforce the well-support for p in terms of k rules p ← ws(ai, p) for i = 1, ..., k. For an atom p ∈ X, the rule (3) below captures the option that the well-support for p is provided by some action ⃗a such that pre(⃗a) = {q1 , . . . , qn} and p ∈ add(⃗a).

Also, the rule a ← ws(a, p) captures the atom a in the supported models, in the case that it has been used to provide well-support for p. As in program P, we need a rule g ← not g for every g ∈ G to guarantee that every goal atom has been produced by some action.

For TrACYC(P) obtained in this way, the distinction between stable and supported models disappears if we insist on acyclic models I for which the digraph induced by the set of arcs {〈a, b〉 | dep(a, b) ∈ I} is acyclic. We deploy the following result:

Proposition 1 ([Bomanson et al., 2016]). If M is a stable model of P , then TrACYC(P ) has an acyclic supported model N such that M = N ∩ At(P). If N is an acyclic supported model of TrACYC(P ), then M = N∩At(P ) is a stable model of P .

Similarly to the stable model based encoding, TrACYC(P) is a causal encoding, expressing the inference in the direction from preconditions to actions, and from actions to effects.

4.2 Vertex Elimination Graphs

The concept of vertex elimination for digraphs was originally introduced by Rose and Tarjan [1975]. Given a digraph G = 〈V, E〉, an ordering of V is a bijection α : {1, . . . , n} → V . For a vertex v, the fill-in of v, denoted by F(v), is the set of arcs from the in-neighbors of v to the out-neighbors of v, formally defined by

The v-elimination graph of G is produced by removing v from G, and adding the fill-in of v to the resulting graph. Formally, G(v) = 〈V \ {v},E(v) ∪F(v)〉, where E(v) = {〈x, y〉 | 〈x, y〉 ∈ E, x ̸= v, y ̸= v}.

Given a digraph G and an ordering α of its vertices, the elimination process of G according to α is the sequence G = G0, G1, . . . , Gn-1, where Gi is the α(i)-elimination graph of Gi-1 for i = 1, . . . , n - 1.

The fill-in of the digraph G according to α, denoted by Fα(G), is the set of all arcs added to G in the vertex elimination process. Formally, Fα(G) is defined by (5), where Fi-1(α(i)) is the fill-in of α(i) in Gi-1, with G0 = G:

The vertex elimination graph of G according to α, denoted by G ∗α, is the union of all graphs produced in the elimination process of G according to α:

One important property of vertex elimination is that if the original graph G has a directed cycle, then G ∗α will have a cycle of length 2, regardless of the ordering α.

4.3 The Causal Encoding

Consider TrACYC(P) explained above. Let G be the graph of all dependencies of TrACYC(P). Formally, G = 〈X,E〉, where E = {〈p, q〉 | dep(p, q) ∈ At(TrACYC(P))}. Also, for each supported model M of TrACYC(P), let GM be the graph of all dependencies in M, i.e., GM = 〈X, EM〉, where EM = {〈p, q〉 | dep(p, q) ∈ M}. Assume that α is an ordering of the members of X, G = G0, G1, . . . , Gn-1 is the elimination process of G according to α, and for i = 1, . . . , n, Fi-1(α(i)) is the fill-in of α(i) in Gi-1. Let G ∗α = 〈X,E∗ 〉 and G ∗M,α = 〈X, E∗M 〉 be the vertex elimination graphs of G and GM according to α, respectively.

We produce the causal supported model semantics based encoding of Π as logic program Pc by adding the following rules to TrACYC(P). For every 〈p, q〉 ∈ Fi-1(α(i)), add

Also, for every p and q such that 〈p, q〉 ∈ G ∗α and 〈q, p〉 ∈ G ∗α, we add

Intuitively, for any vertex ordering α, and any supported model M of TrACYC(P), the rule (7) extends M by atoms representing the arcs in G ∗M,α, the vertex elimination graph of GM according to α, while the rule (8) guarantees that G ∗M,α has no cycle of length 2. We have the following result:

Theorem 2. There exists a permutation π of members of A′ ⊆ A+ such that π is a relaxed plan for Π iff Pc has a supported model M such that A′ = {⃗a ∈ A+ | a ∈ M}.

4.4 The Diagnostic Encoding

Inferring causes from effects can be understood as diagnostic inference [Russell and Norvig, 2020]. In our causal encoding, we express the inference direction from preconditions to dependencies, from dependencies to well-supports, and from well-supports to effects. We can alternatively reverse all these directions to produce a diagnostic encoding.

In our diagnostic encoding Pd, we assume that all atoms could possibly be in the model by using the rule {p} for every p ∈ X. However, if p is in the model, then it must have wellsupport by at least one action. We establish this by adding {ws(a, p)} ← p for every ⃗a ∈ A such that p ∈ add(⃗a), and also f ← p, not ws(a1, p) , . . . , not ws(am, p), not f for p ∈ X and all actions ⃗a1, ...,⃗am that could add p. To represent the inference from well-supports to dependencies, we add dep(p, q) ← ws(a, p) for ⃗a ∈ A, q ∈ pre(⃗a), and p ∈ add(⃗a). Finally, to establish the inference direction from dependencies to preconditions, we add q ← dep(p, q). As in Pc, all rules in the forms of (7) and (8) must be included to enforce acyclicity in the supported model. Moreover, we add a ← ws(a, p) for ⃗a ∈ A and p ∈ add(⃗a), to enable an action atom a to represent its cost in the minimization constraint, and also g ← not g for every g ∈ G to guarantee that goal atoms are included in the model.

It is quite easy to check that if Pd has a supported model M, then M is also a supported model of Pc. On the other hand, it can be shown in a straightforward manner that if N is a supported model of Pc, then N \ L is a supported model of Pd, where L is the set of atoms dep(p, q) for which there is no action ⃗a such that ws(a, p) ∈ N and q ∈ pre(⃗a). Thus, we have the following result:

Theorem 3. There exists a permutation π of members of A′ ⊆ A+ such that π is a relaxed plan for Π iff Pd has a supported model M such that A′ = {⃗a ∈ A+ | a ∈ M}.

5 Empirical Results

We have implemented our encoding methods inside the HSP* planner [Haslum, 2015]. The implementation is available under the ASPTOOLS collection 1 . All experiments have been run on a cluster of Linux machines with Intel Xeon 2.40 GHz CPUs, using a timeout of 1800 seconds per problem, and a memory limit of 8 GB. For our supported model based encodings, where vertex elimination is used, for determining the order of vertex elimination, we have implemented the minimum degree heuristic, i.e., eliminating a vertex with a minimal total number of incoming and outgoing arcs in the graph produced after the elimination of previously eliminated vertices.

Our three implemented encodings are (1) our stable model based encoding P; (2) our causal supported model based encoding Pc; and (3) our diagnostic supported model based encoding Pd. As the solver we use CLASP 3.3.5, which is capable of optimizing over both stable and supported models. The CLASP solver searches for stable models by default. We enable the search for supported models only for our Pc and Pd encodings. As the optimization strategy we use the unsatisfiable core (USC) method. Henceforth, we refer to the solver obtained by combing CLASP with our P, Pc, and Pd encodings simply by the name of the corresponding encoding.

1 https://github.com/asptools/software

To evaluate the efficiency of our methods, we have compared them based on the total time of encoding and solving with IP, the integer programming based encoding by Rankooh and Rintanen [2022a], which uses IBM ILOG CPLEX Optimization Studio 20.1 2 as the optimizer.

As benchmark problem sets, we use the STRIPS planning problem sets of the planning repository 3 . In total, 2212 problem instances from 84 problem sets are used for comparison.

The cumulative number of problems solved by all methods are presented in Figure 1. Our supported model based encodings significantly outperform the stable model based one, with the diagnostic encoding performing visibly faster than the causal one. Also, even though the number of problems solved within 1800 seconds by our diagnostic encoding is not much higher than that of IP, Pd solves problems considerably faster than IP. In fact, regardless of the time limit, Pd solves more problems compared to any other solver.

6 Conclusions

In this work, we study the previously uninvestigated application of ASP solvers to optimal relaxed planning. Three different encodings of relaxed planning problems into logic programs are provided, one based on the stable model semantics, and two based on the supported model semantics of logic programs. According to our empirical results, all our encodings enable CLASP to outperform the state-of-the-art method if the time limit is small. Moreover, our diagnostic supported model based method outperforms the state-of-the-art solver on the studied benchmark problems regardless of the used time limit.

2 https://www.ibm.com/products/ilog-cplex-optimization-studio

3 https://github.com/AI-Planning/classical-domains

Acknowledgements

Financial support from the Research Council of Finland (Project XAILOG, #345633) is gratefully acknowledged.