# symbolic_numeric_planning_with_patterns__5896b5cf.pdf

Symbolic Numeric Planning with Patterns

Matteo Cardellini*1, 2, Enrico Giunchiglia*2, Marco Maratea3

1 DAUIN, Politecnico di Torino, Italy 2 DIBRIS, Universit a di Genova, Italy 3 De Ma CS, Universit a della Calabria, Italy matteo.cardellini@polito.it, enrico.giunchiglia@unige.it, marco.maratea@unical.it

In this paper, we propose a novel approach for solving linear numeric planning problems, called Symbolic Pattern Planning. Given a planning problem Π, a bound n and a pattern defined as an arbitrary sequence of actions we encode the problem of finding a plan for Π with bound n as a formula with fewer variables and/or clauses than the stateof-the-art rolled-up and relaxed-relaxedencodings. More importantly, we prove that for any given bound, it is never the case that the latter two encodings allow finding a valid plan while ours does not. On the experimental side, we consider 6 other planning systems including the ones which participated in this year s International Planning Competition (IPC) and we show that our planner PATTY has remarkably good comparative performances on this year s IPC problems.

Introduction Planning is one of the oldest problems in Artificial Intelligence, see, e.g., (Mc Carthy and Hayes 1969). Starting from the classical setting in which all the variables are Boolean, in simple numeric planning problems variables can also range over the rationals and actions can increment or decrement their values by a fixed constant, while in linear numeric planning problems actions can also update variables to a new value which is a linear combination of the values of the variables in the state in which actions are executed, see, e.g., (Arxer and Scala 2023). Current approaches for solving a numeric planning problem Π are either search-based (in which the state space is explored using techniques based on heuristic search, see, e.g., (Bonet and Geffner 2001)) or symbolic-based (in which a bound n on the number of steps is a priori fixed and the problem of finding a plan with bound n is encoded into a formula for which a decision procedure is available, see, e.g., (Kautz and Selman 1992)). In this paper, we propose a novel symbolic approach for solving numeric planning problems, called symbolic pattern planning. Given a problem Π and a pattern defined as a sequence of actions we show how it is possible to generalize the state-of-the-art rolled-up encoding ΠR proposed in (Scala et al. 2016b) and the relaxed-relaxed- (R2 ) encoding ΠR2 proposed in (Bofill, Espasa, and Villaret 2017),

*These authors contributed equally. Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

and define a new encoding Π which provably dominates both ΠR and ΠR2 : for any bound n, it is never the case that the latter two allow to find a valid plan for Π while ours does not. Further, our encoding produces formulas with fewer clauses than the rolled-up encoding and also with far fewer variables than the R2 encoding, even when considering a fixed bound. Most importantly, we believe that our proposal provides a new starting point for symbolic approaches: a pattern can be any sequence of actions (even with repetitions) and, assuming n = 1, the formula produced by Π encodes all the sequences of actions in which each action in is sequentially executed zero, one or possibly even more than one time. Thus, any planning problem can be solved with bound n = 1 when considering a suitable pattern, and such pattern can be symbolically searched and incrementally defined also while increasing the bound, bridging the gap between symbolic and search-based planning. To show the effectiveness of our proposal, we (i) considered the 2 planners, benchmarks, and settings of the just concluded IPC, Agile track (Arxer and Scala 2023); and (ii) added 4 other planning systems for both simple and linear numeric problems. Overall, our comparative analysis included 6 other planners, 3 of which symbolic and 3 search-based. The results show that, compared to the other symbolic planners, our planner PATTY has always better performance on every domain, while compared to all the other planners, PATTY has overall remarkably good performances, being the fastest system able to solve most problems on the largest number of domains. The paper is structured as follows. After the preliminaries, we present the rolled-up, R2 and our pattern encodings, and prove that the latter dominates the previous two. Then, the experimental analysis and the conclusion follow. One running example is used throughout the paper to illustrate the formal definitions and the theoretical results.

Preliminaries We consider a fragment of numeric planning expressible with PDDL2.1, level 2 (Fox and Long 2003). A numeric planning problem is a tuple Π = VB, VN, A, I, G , where VB and VN are finite sets of Boolean and numeric variables with domains { , } and Q, respectively ( and are the symbols we use for truth and falsity). I is the initial state mapping each variable to an element in its domain. A propo-

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

sitional condition for a variable v VB is either v = or v = , while a numeric condition has the form ψ 0, where { , >, =} and ψ is a linear expression over VN, i.e., is equal to P w VN kww +k, for some kw, k Q. G is a finite set of goal formulas, each one being a propositional combination of propositional and numeric conditions. Finally, A is a finite set of actions. An action a is a pair pre(a), eff(a) in which (i) pre(a) is the union of the sets of propositional and numeric preconditions of a, represented as propositional and numeric conditions, respectively; and (ii) eff(a) is the union of the sets of propositional and numeric effects, the former of the form v := or v := , the latter of the form w := ψ, with v VB, w VN and ψ a linear expression. We assume that for each action a and variable v VB VN, v occurs in eff(a) at most once to the left of the operator := , and when this happens we say that v is assigned by a. In the rest of the paper, v, w, x, y denote variables, a, b denote actions and ψ denotes a linear expression, each symbol possibly decorated with subscripts. Example. There are two robots l and r for left and right, respectively, whose position xl and xr on an axis correspond to the integers 0 and 0, respectively. The two robots can move to the left or to the right, decreasing or increasing their position by 1. The two robots carry ql and qr objects, which they can exchange. However, before exchanging objects at rate q, the two robots must connect setting a Boolean variable p to , and this is possible only if they have the same position. Once connected, they must disconnect before moving again. The quantity q can be positive or negative, corresponding to l giving objects to r or vice versa. This scenario can be modelled in PDDL with VB = {p}, VN = {xl, xr, ql, qr, q} and the following set of actions:

lftr : {xr > 0}, {xr = 1} , rgtr : {p = }, {xr += 1} , lftl : {p = }, {xl = 1} , rgtl : {xl < 0}, {xl += 1} , conn : {xl = xr}, {p := } , disc : {p = }, {p := } , exch : {p = , ql q, qr q}, {ql = q, qr += q} , lre : {}, {q := 1} , rle : {}, {q := 1} . (1) As customary, v += ψ is an abbreviation for v := v + ψ and similarly for v = ψ and we abbreviate ψ > 0 with the equivalent ψ < 0. Let Π = VB, VN, A, I, G be a numeric planning problem. A state s maps each variable v VB VN to a value s(v) in its domain, and is extended to linear expressions, Boolean and numeric conditions and their propositional combinations. An action a A is executable in a state s if s satisfies all the preconditions of a. Given a state s and an executable action a, the result of executing a in s is the state s such that for each variable v VB VN, 1. s (v) = if v := eff(a), s (v) = if v := eff(a), s (v) = s(ψ) if (v := ψ) eff(a), and 2. s (v) = s(v) otherwise. Given a finite sequence α of actions a0; . . . ; an 1 of length n 0, the state sequence s0; . . . ; sn induced by α in s0 is such that for i [0, n), si+1 (i) is undefined if either ai is not executable in si or si is undefined, and (ii) is the result of executing ai in si otherwise. Consider a finite sequence of actions α. We say that α is executable in a state s0 if each state in the sequence induced

by α in s0 is defined. If α is executable in the initial state I and the last state induced by α in I satisfies the goal formulas in G, we say that α is a (valid) plan. In the following, we will use α and π to, respectively, denote a generic sequence of actions and a plan, possibly decorated with subscripts. For an action a and k N, ak denotes the sequence consisting of the action a repeated k times. Example (cont d). Assume the initial state is I = {p = , xl = XI, xr = XI, ql = Q, qr = 0, q = 1}, where XI, Q are positive integers. Assuming G = {ql = 0, qr = Q, xl = XI, xr = XI}, one of the shortest plans is

rgt XI l ; lft XI r ; conn; exch Q; disc; lft XI l ; rgt XI r (2)

corresponding to the robots going to the origin, connect, exchange the Q items, disconnect, and then go back to their initial positions.

Symbolic Planning With Patterns Symbolic Planning Let Π = VB, VN, A, I, G be a numeric planning problem. An encoding ΠE of Π is a 5-tuple ΠE = X, A, I(X), T (X, A, X ), G(X) where 1. X is a finite set of state variables, each one equipped with a domain representing the values it can take. We assume VB VN X. 2. A is a finite set of action variables, each one equipped with a domain representing the values it can take. 3. I(X) is the initial state formula, a formula in the set X of variables defined as

x,k:I(x)=k x = k.

4. T (X, A, X ) is the symbolic transition relation, a formula in the variables X A X , where X is a copy of X. Together with T (X, A, X ), a decoding function has to be defined enabling to associate to each model of T (X, A, X ) at least one sequence of actions in A. Standard requirements for T (X, A, X ) are: (a) correctness: for each sequence of actions α corresponding to a model µ of T (X, A, X ), (i) α is executable in the state s in which, for each variable v VB VN, s(v) = µ(v); and (ii) the last state induced by α executed in s is the state s such that, for each variable v VB VN, s (v) = µ(v ); (b) completeness: for each state s and action a A executable in s with resulting state s , there must be a model µ of T (X, A, X ) such that, for each state variable v VB VN, µ(v) = s(v), µ(v ) = s (v) and the sequence of actions containing only a corresponds to µ. 5. G(X) is the goal formula, obtained by making the conjunction of the formulas in G, once v = and v = are substituted with v and v, respectively. Example (cont d). The initial state and goal formulas are ( p xl = XI xr = XI ql = Q qr = 0 q = 1) and (ql = 0 qr = Q xl = XI xr = XI), respectively.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Let ΠE = X, A, I(X), T (X, A, X ), G(X) be an encoding of Π. As in the planning as satisfiability approach (Kautz and Selman 1992), we fix an integer n 0 called bound or number of steps, we make n + 1 disjoint copies X0, . . . , Xn of the set X of state variables, and n disjoint copies A0, . . . , An 1 of the set A of action variables, and define 1. I(X0) as the formula in the variables X0 obtained by substituting each variable x X with x0 X0 in I(X); 2. for each step i = 0, . . . , n 1, T (Xi, Ai, Xi+1) as the formula in the variables Xi Ai Xi+1 obtained by substituting each variable x X (resp. a A, x X ) with xi Xi (resp. ai Ai, xi+1 Xi+1) in T (X, A, X ); 3. G(Xn) as the formula in the variables Xn obtained by substituting each variable x X with xn Xn in G(X). Then, the encoding ΠE of Π with bound n is the formula

ΠE n = I(X0)

i=0 T (Xi, Ai, Xi+1) G(Xn). (3)

To each model µ of ΠE n , we associate the set of sequences of actions α0; . . . ; αn 1, where each αi is a sequence of actions corresponding to the model of T (Xi, Ai, Xi+1) obtained by restricting µ to Xi Ai Xi+1, i [0, n). In the following, (ΠE n ) 1 is the set of sequences of actions in A associated to a model of ΠE n . The correctness of T (X, A, X ) ensures the correctness of ΠE: for each bound n, each sequence in (ΠE n ) 1 is a plan. The completeness of T (X, A, X ) ensures the completeness of ΠE: if it exists a plan for Π, it will be found by considering ΠE 0 , ΠE 1 , ... . It is clear that the number of variables and size of (3) increase with the bound n, explaining why much of the research has concentrated on how to produce encodings allowing to find plans with the lowest possible bound n.

Rolled-up, Standard and R2 Encodings Let Π = VB, VN, A, I, G be a numeric planning problem. Many encodings have been proposed, each characterized by how the symbolic transition relation is computed. In most encodings (see, e.g., (Rintanen, Heljanko, and Niemel a 2006; Bofill, Espasa, and Villaret 2017; Leofante et al. 2020)), each action a A is defined as a Boolean variable in A which will be true (resp. false) in a model µ of T (X, A, X ) if action a occurs once (resp. does not occur) in each sequence of actions corresponding to µ. Here we start presenting the state-of-the-art rolled-up encoding ΠR of Π proposed by (Scala et al. 2016b). In ΠR, each action a A is defined as an action variable which can get an arbitrary value k N, and this corresponds to have k (consecutive) occurrences of a in the action sequences corresponding to the models of the symbolic transition relation of ΠR. 1 However, in ΠR it is not the case that each action a can get

1To ease the presentation, our definition of ΠR considers just the cases α = 0 and α = 1 of Theorem 1 in (Scala et al. 2016b), which (quoting) cover a very general class of dynamics, where rates of change are described by linear or constant equations .

a value > 1, (e.g., because a cannot be executed more than once, or it is not useful to execute a more than once), and the definition of when it is possible to set a > 1 depends on the form of the effects of a. For this reason, each effect v := e of an action a is categorized as 1. a Boolean assignment, if v VB and e { , }, as for the effects of the actions conn and disc in (1), or as 2. a linear increment, if e = v+ψ with ψ a linear expression not containing any of the variables assigned by a, as for the effects of the action exch and lftr in (1), or as 3. a general assignment, if it does not fall in the above two categories. General assignments are further divided into (a) simple assignments, when e does not contain any of the variables assigned by a, as in the effects of the actions lre and rle in (1), and (b) self-interfering assignments, otherwise. Then, an action a is eligible for rolling if 1. v = pre(a) (resp. v = pre(a)) implies v := eff(a) (resp. v := eff(a)), and 2. a does not contain a self-interfering assignment, and 3. a contains a linear increment. The result of rolling action a for k 1 times is such that 1. if v += ψ eff(a) is a linear increment, then the value of v is incremented by k ψ, while 2. if v := e eff(a) is a Boolean or simple assignment, then the value of v becomes e, equal to the value obtained after a single execution of a. On the other hand, if an action a is not eligible for rolling, a > 1 is not allowed, and this can be enforced through atmost-once ( amo ) axioms. In ΠR, the symbolic transition relation T R(X, A, X ) is the conjunction of the formulas in the following sets: 1. pre R(A), consisting of, for each a A, v = and w = in pre(a),

a > 0 ( v w), 2

and, for each a A and ψ 0 in pre(a),

a > 0 ψ 0, a > 1 ψ[a] 0,

where ψ[a] is the linear expression obtained from ψ by substituting each variable x with (a) x + (a 1) ψ1, whenever x += ψ1 eff(a) is a linear increment, (b) ψ1, if x := ψ1 eff(a) is a simple assignment. The last two formulas ensure that ψ 0 holds in the states in which the first and the last execution of a happens (see (Scala et al. 2016b)). 2. eff R(A), consisting of, for each a A, v := , w := , linear increment x += ψ and general assignment y := ψ1 in eff(a),

a > 0 ( v w x = x + a ψ y = ψ1).

2We do not use the equivalent formulation (a > 0 v), (a > 0 w), which has a more direct translation to clauses, in order to save space. Analogously in the rest of the paper.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

3. frame R(VB VN), consisting of, for each variable v VB and w VN,

(V a:v:= eff(a) a = 0 V a:v:= eff(a) a = 0) v v, V a:w:=ψ eff(a) a = 0 w = w.

4. mutex R(A) consisting of (a1 = 0 a2 = 0), for each pair of distinct actions a1 and a2 such that there exists a variable v with (a) v VB, v = (resp. v = ) in pre(a1) and v := (resp. v := ) in eff(a2), or (b) v VN, v := ψ eff(a1) and v occurring either in eff(a2) or in pre(a2). 5. amo R(A) consisting of, for each action a not eligible for rolling, (a = 0 a = 1).

Notice that if for action a the formula (a = 0 a = 1) belongs to T R(X, A, X ), we can equivalently (i) define a to be a Boolean variable, and then (ii) replace a = 0, a > 0, a = 1 and a > 1 with a, a, a and , respectively, in T R(X, A, X ). It is clear that if T R(X, A, X ) contains (a = 0 a = 1) for any action a, then the rolled-up encoding ΠR reduces to the standard encoding as defined, e.g., in (Leofante et al. 2020). Equivalently, in the standard encoding ΠS of Π, the symbolic transition relation T S(X, A, X ) is obtained by adding, for each action a, (a = 0 a = 1) to T R(X, A, X ). The decoding function of the rolled-up (resp. standard) encoding associates to each model µ of T R(X, A, X ) (resp. T S(X, A, X )) the sequences of actions in which each action a occurs µ(a) times. The biggest problem with the rolled-up and standard encodings is the presence of the axioms in mutex(A), which (i) cause the size of T R(X, A, X ) to be possibly quadratic in the size of Π; and (ii) forces some actions to be set to 0 even when it is not necessary to maintain the correctness and completeness of T R(X, A, X ), see, e.g., (Rintanen, Heljanko, and Niemel a 2006). Indeed, allowing to set more actions to a value > 0 while maintaining correctness and completeness, allows finding solutions to (3) with a lower value for the bound. Several proposals along these lines have been made. Here we present the R2 encoding presented in (Bofill, Espasa, and Villaret 2017) which is arguably the state-of-the-art encoding in which actions are encoded as Boolean variables (though there exist cases in which the -encoding presented in (Rintanen, Heljanko, and Niemel a 2006) allows to solve (3) with a value for the bound lower than the one needed by the R2 encoding). In the R2 encoding, action variables are Boolean and assumed to be ordered according to a given total order <. In general, different orderings lead to different R2 encodings. In the following, we represent and reason about < considering the corresponding sequence of actions (which indeed contains each action in A exactly once) and define Π< to be the R2 <-encoding of Π. In Π<, for each action a and variable v assigned by a, a newly introduced variable va with the same domain of v is added to the set X of state variables. Intuitively, each new variable va represents the value of v after the sequential execution of some actions in the initial

sequence of < ending with a. The symbolic transition relation T <(X, A, X ) of Π< is the conjunction of the formulas in the following sets: 1. pre<(A), consisting of, for each a A, v = , w = and ψ 0 in pre(a),

a ( v ,a w ,a ψ ,a 0),

where, for each variable x VB VN, x ,a stands for the variable (i) x, if there is no action preceding a in < assigning x; and (ii) xb, if b is the last action assigning x preceding a in <. Analogously, ψ ,a is the linear expression obtained from ψ by substituting each variable x VN with x ,a. 2. eff<(A), consisting of, for each a A, v := , w := and general assignment x := ψ in eff(a),

a ( va wa xa = ψ ,a), a (va v ,a wa w ,a xa = x ,a).

3. frame<(VB VN), consisting of, for each variable v VB and w VN,

v v ,g, w = w ,g,

where g is a dummy action assumed to follow all the other actions in <. The decoding function of the R2 <-encoding associates to each model µ of T <(X, A, X ) the sequence of actions obtained from < by deleting the actions a with µ(a) = . In the R2 <-encoding, there are no mutex axioms and the size of T <(X, A, X ) is linear in the size of Π. However, as we mentioned previously, it introduces many new state variables (in the worst case, |VB VN| |A|). The main advantage of ΠR and Π< over ΠS is that the first two allow to find plans with lower values for the bound. Example (cont d). The rolled-up (resp. standard) encoding of the two robots problem admits a model with bound n = 5 (resp. n = 2XI + Q + 2, and thus n = 5 when XI = Q = 1). The R2 <-encoding admits a model with bound n = 2(XI 1)+Q if actions in < are ordered as in the plan (2), and thus n = 1 when XI = Q = 1. In the worst case, the R2 <-encoding admits a solution with a bound equal to the one needed by the standard encoding, and this happens when actions in < are in reverse order wrt the plan (2). As the example shows, ΠR and Π< dominate ΠS, while ΠR and Π< do not dominate each other. Given two correct encodings ΠE1 and ΠE2 of Π, ΠE1 dominates ΠE2 if for any bound n, ΠE2 n satisfiability implies ΠE1 n satisfiability. Theorem 1. Let Π be a numeric planning problem. Let < be a total order of actions. The rolled-up encoding ΠR, the R2 <-encoding Π< and the standard encoding ΠS of Π are correct and complete. ΠR and Π< dominate ΠS.

Proof. (Sketch) For the correctness of ΠR (and thus of ΠS) and Π< see Prop. 3 and Theorem 1 in the respective original papers. The completeness of ΠS is taken for granted. A model of ΠS n with a corresponding plan π is also a model of ΠR n , and can be easily used to define a model of Π< n with the same corresponding plan π. This implies the completeness of ΠR and Π< and the fact that they dominate ΠS.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Pattern Encoding Let Π = VB, VN, A, I, G be a numeric planning problem. In the pattern encoding we combine and then generalize the strengths of the rolled-up and R2 encoding by (i) allowing for the multiple executions of actions; (ii) considering an ordering to avoid mutexes; and (iii) allowing for arbitrary sequences of actions. Consider a pattern , defined as a possibly empty, finite sequence of actions. In the pattern -encoding Π of Π, 1. X = VB VN V , where V contains a newly introduced variable v 1;a with the same range of v, for each variable v and initial pattern 1; a of (i.e., starts with 1; a) in which a contains a general assignment of v, and 2. A contains one action variable a 1 ranging over N, for each initial pattern 1; a of . Then, the value of a variable v VB VN after one or more of the actions in are executed (possibly consecutively multiple times) is given by σ (v), where σ (v) is inductively defined as (i) σ (v) = v if is the empty sequence; and (ii) for a non-empty pattern = 1; a, 1. if v is not assigned by a, σ (v) = σ 1(v); 2. if v := eff(a), σ (v) = (σ 1(v) a > 0); 3. if v := eff(a), σ (v) = (σ 1(v) a = 0); 4. if v += ψ eff(a) is a linear increment, σ (v) = σ 1(v) + a σ 1(ψ); 5. if v := ψ eff(a) is a general assignment σ (v) = v . Above and in the following, for any pattern 1 and linear expression ψ, σ 1(ψ) is the expression obtained by substituting each variable v VN in ψ with σ 1(v). Example (cont d). Consider (1), and assume is

lre; rle; lftr; rgtl; conn; exch; disc; rgtr; lftl.

We have two newly introduced variables qlre and qlre;rle, and for the Boolean variable p,

σ (p) = (p conn > 0) disc = 0,

and, for the numeric variables in VN = {xl, xr, ql, qr, q},

σ (xl) = xl + rgtl lftl, σ (xr) = xr lftr + rgtr, σ (ql) = ql exch qlre;rle, σ (qr) = qr + exch qlre;rle, σ (q) = qlre;rle.

The symbolic transition relation T (X, A, X ) of Π is the conjunction of the formulas in the following sets: 1. pre (A), which contains, for each initial pattern 1; a of , and for each v = and w = in pre(a), a 1 > 0 ( σ 1(v) σ 1(w)),

and, for each numeric precondition ψ 0 in pre(a), a 1 > 0 σ 1(ψ) 0, a 1 > 1 σ 1(ψ[a]) 0.

2. eff (A), consisting of, for each initial pattern 1; a of and variable v such that v := ψ eff(a) is a general assignment,

a 1 = 0 v 1;a = σ 1(v), a 1 > 0 v 1;a = σ 1(ψ).

3. amo (A) which contains, for each initial pattern 1; a of in which a is not eligible for rolling, a 1 = 0 a 1 = 1.

4. frame (VB VN), consisting of, for each variable v VB and w VN, v σ (v), w = σ (w).

If = a1; a2; . . . ; ak (with a1, a2, . . . ak A, k 0), the decoding function associates to each model µ of T (X, A, X ) the sequence of actions aµ(a1) 1 ; aµ(a2) 2 ; . . . ; aµ(ak) k , i.e., the sequence of actions listed as in , each action a repeated µ(a) times. Notice the similarities and differences with ΠR n and Π< n . In particular, our encoding (i) does not include the mutex axioms; and (ii) introduces variables only when there are general assignments (usually very few, though in the worst case, |VB VN| |A|). Notice also that we did not make any assumption about the pattern , which can be any arbitrary sequence of actions. In particular, can contain multiple non-consecutive occurrences of any action a: this allows for models of T (X, A, X ) corresponding to sequences of actions in which a has multiple non-consecutive occurrences. At the same time, may also not include some action a A: in this case, our encoding is not complete (unless a is never executable). Even further, it is possible to consider multiple different patterns 1, . . . , n, each leading to a corresponding symbolic transition relation T i(X, A, X ), and then consider the encoding (3) with bound n in which T (Xi, Ai, Xi+1) is replaced by T i(Xi, Ai, Xi+1): in this case each model of the resulting encoding with bound n will still correspond to a valid plan, (though we may fail to find plans with n or fewer actions). Even more, with a suitable pattern , any planning problem can be solved with bound n = 1 . Such pattern can be symbolically searched and incrementally defined while increasing the bound, bridging the gap between symbolic and search-based planning. Such outlined opportunities significantly extend the possibilities offered by all the other encodings, and for this reason, we believe our proposal provides a new starting point for the research in symbolic planning. Here we focus on -encodings with bound n in which we have a single, a priori fixed, simple and complete pattern. A pattern is simple if each action occurs at most once, and is complete if each action occurs at least once. If 1; a is a simple pattern, a 1 A (resp. v 1;a V ) can be abbreviated to a (resp. va) without introducing ambiguities, as we do in the example below. Example (cont d). In our case, the given pattern is simple and also complete, and pre (A) is equivalent to lftr > 0 xr > 0, lftr > 1 xr (lftr 1) > 0, rgtr > 0 ((p conn > 0) disc = 0), lftl > 0 ((p conn > 0) disc = 0), rgtl > 0 xl < 0, rgtl > 1 xl + (rgtl 1) < 0, conn > 0 xl + rgtl = xr lftr, disc > 0 (p conn > 0), exch > 0 ((p conn > 0) ql qrle qr qrle), exch > 1 (ql qrle (exch 1) qrle), exch > 1 (qr qrle + (exch 1) qrle).

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

eff (A) is lre = 0 qlre = q, lre > 0 qlre = 1, rle = 0 qrle = qlre, rle > 0 qrle = 1. amo (A) is lre = 0 lre = 1, rle = 0 rle = 1, conn = 0 conn = 1, disc = 0 disc = 1.

frame (VB VN) is p ((p conn > 0) disc = 0), x l = xl + rgtl lftl, x r = xr lftr + rgtr, q l = ql exch qrle, q r = qr + exch qrle, q = qrle.

The plan (2) belongs to (Π 1 ) 1. Indeed, in the case of the example, the chosen pattern allows finding a plan with bound n = 1, compared to the rolled-up and standard encodings which need at least n = 5, while any R2 encoding needs a bound of at least 2(XI 1) + Q which is equal to 1 only if XI = Q = 1. Of course, as for the R2 encoding, depending on the selected pattern, we get different results. However, our pattern -encoding dominates any R2 <-encoding, of course if < is compatible with . A total order < of actions is compatible with if < (seen a sequence of actions) can be obtained from by removing 0 or more actions. Theorem 2. Let Π be a numeric planning problem. Let be a pattern. 1. Π is correct. 2. For any action a, Π ;a dominates Π . 3. If is complete, then Π is complete. 4. If is complete, then Π dominates ΠR. 5. If < is a total order compatible with , then Π dominates Π< .

Proof. (Sketch) The correctness of Π follows from the correctness of T (X, A, X ) which can be proved by induction on the length k of : if k = 0 is trivial, if k > 0 the thesis follows from the induction hypothesis, mimicking the proof of Proposition 3 in (Scala et al. 2016b). Π ;a dominates Π , since each model µ of T can be extended to a model µ of T ;a with µ (a ) = 0. If is complete, Π completeness follows from its correctness, the completeness of ΠR, and Π dominates ΠR. Π dominates ΠR because for each model µR of T R we can define a model µ of T in which each action a is executed µR(a) times. Formally, if for each action a A, 1; a, . . . , k; a (k 1) are all the initial patterns of ending with a, we have to ensure Pk i=1 µ (a i) = µR(a). Since < is compatible with , for any action a there exists an <-compatible action a 1 with 1 an initial pattern of . Π dominates Π< because for each model µ< of T < there is a model µ of T assigning 1 to the <-compatible actions assigned to by µ<, and 0 to the others.

According to the Theorem, even restricting to simple and complete patterns , our pattern -encoding allows to find plans with a bound n which is at most equal to the bound necessary when using the rolled-up, standard and R2 <- encodings, the latter with < compatible with .

Implementation and Experimental Analysis

Consider a numeric planning problem Π. Clearly, the performances of the encoding Π may greatly depend on the pattern . For computing the pattern, we use the Asymptotic Relaxed Planning Graph (ARPG) (Scala et al. 2016a). An ARPG is a digraph of alternating state (Si) and action (Ai) layers, which, starting from the initial state layer, outputs a partition A1, . . . , Ak on the set of actions which is totally ordered. If a Ai+1 then any sequence of actions which contains a and which is executable in the initial state, contains at least an action b Ai (0 i < k). In the computed pattern, a precedes b if a Ai and b Aj with 1 i < j k, while actions in the same partition are randomly ordered.

Example (cont d). The ARPG construction leads to the following ordered partition on the set of actions: {lftr, rgtr, lftl, rgtl, lre, rle}, then {conn}, and finally {exch, disc}. Depending on whether exch occurs before or after disc in the pattern, the plan in equation (2) is found with bound n = 2 or n = 3, respectively.

For the experimental analysis we considered all the domains and problems of the 2023 Numeric International Planning Competition (IPC) (Arxer and Scala 2023). We compared our planner PATTY with the three symbolic planners SPRINGROLL (based on the rolled-up ΠR encoding (Scala et al. 2016b)), a version of PATTY computing the R2 <- encoding Π< with < compatible with , and called it R2 ; and OMTPLAN (based on the ΠS standard encoding), and the three search-based planners ENHSP (Scala et al. 2016a), METRICFF (Hoffmann 2003) and NUMERICFASTDOWNWARD (NFD) (Kuroiwa, Shleyfman, and Beck 2022). NFD and OMTPLAN are the two planners that competed in the last IPC, ranking first and second, respectively. The planner ENHSP has been run three times using the sat-hadd, sat-hradd and sat-hmrphj settings, and for each domain we report the best result we obtained (Scala, Haslum, and Thiebaux 2016; Scala et al. 2020). All the symbolic planners have been run using Z3 v4.12.2 (De Moura and Bjørner 2008) for checking the satisfiability of the formula (3), represented as a set of assertions in the SMT-LIB format (Barrett, Fontaine, and Tinelli 2016). We then considered the same settings used in the Agile Track of the IPC, and thus with a time limit of 5 minutes. Analyses have been run on an Intel Xeon Platinum 8000 3.1GHz with 8 GB of RAM. For lack of space, Table 1 presents the results for all the planners but OMTPLAN, since its encoding is dominated by the one of SPRINGROLL.3 In the sub-tables/columns, we show: the name of the domain (sub-table Domain); the percentage of solved instances (sub-table Coverage); the average time to find a solution, counting the time limit when the solution could not be found (sub-table Time); the average bound at which the solutions were found, computed considering the problems solved by all the symbolic planners able to solve at least one problem in the domain (sub-table

3The table shows the results only for those domains for which at least one planner was able to solve one problem in the domain. Our planner is available at https://pattyplan.com

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Coverage (%) Time (s) Bound |X A X | |T(X, A, X )| Domain P R2 SR EN FF NFD P R2 SR EN FF NFD P R2 SR P R2 SR P R2 SR Bl Group (S) 100 65 100 100 10 - 1.5 126.5 2.1 48.0 270.2 - 1.0 6.0 1.0 40 250 40 101 331 122 Counters (S) 100 60 100 100 60 50 0.8 153.4 1.1 6.9 129.0 149.1 1.0 14.8 1.0 83 1.3k 83 185 1.4k 250 Counters (L) 95 60 35 45 40 25 4.6 152.2 204.1 180.5 180.0 225.4 2.0 2.0 2.5 26 125 26 58 169 112 Drone (S) 25 15 15 85 10 80 242.8 255.6 257.2 59.9 270.0 65.4 4.7 7.7 9.7 30 146 29 64 191 211 Watering (S) 25 - - 100 10 60 226.8 - - 9.8 276.5 185.2 8.4 - - 61 540 61 145 654 610 Farmland (S) 100 - 100 100 35 75 0.9 - 1.6 0.7 206.8 85.5 1.0 - 2.2 63 690 63 120 773 501 Farmland (L) 100 10 - 75 75 55 1.6 275.1 - 96.8 90.7 151.7 1.0 8.0 - 19 61 17 32 79 62 HPower (S) 100 25 - 10 5 5 14.8 233.3 - 270.4 285.0 285.1 1.0 1.0 - 448 22k 448 788 23k 11k Sailing (S) 100 - 90 100 5 50 1.0 - 20.0 1.4 285.0 150.3 3.2 - 7.2 49 380 49 86 434 293 Sailing (L) 95 5 - 20 40 70 1.0 297.9 - 241.2 182.9 109.4 1.0 5.0 - 84 951 82 200 1.1k 490 Delivery (S) 25 20 - 65 95 45 232.7 256.0 - 121.2 48.5 165.2 1.0 2.0 - 250 8.0k - 662 8.5k - Expedit. (S) 15 5 - 10 - 15 253.5 289.0 - 270.3 - 253.7 5.0 10.0 - 105 1.5k - 225 1.6k - MPrime (S) 55 35 50 85 80 65 139.7 205.4 171.2 49.7 47.5 133.6 1.5 1.5 5.2 467 39k 467 1.2k 39k 19k Pathways (S) 100 5 5 60 50 5 4.7 286.7 286.4 133.9 154.9 285.0 1.0 6.0 3.0 186 3.3k 186 318 3.5k 521 Rover (S) 85 45 55 35 50 20 77.6 194.5 185.5 204.4 142.1 241.0 1.9 2.0 7.7 360 20k 367 754 20k 10k Satellite (S) 10 5 15 30 20 20 277.3 292.6 267.7 222.6 229.4 242.2 4.0 4.0 10.0 222 7.4k 183 566 7.8k 5.4k Sugar (S) 100 25 - 95 65 25 6.8 247.2 - 23.7 119.9 232.9 2.0 2.2 - 495 31k - 1124 32k - TPP (L) 10 5 - 20 10 10 275.3 284.4 - 244.3 268.4 270.0 3.0 3.0 - 355 10k 278 917 10k 4.0k Zeno (S) 55 55 - 100 55 45 119.2 129.8 - 20.4 135.0 178.5 2.1 2.3 - 198 6.2k - 577 6.6k - Total 12 0 3 10 1 1 11 0 0 6 2 0 19 5 2 14 0 14 18 0 0

Table 1: Comparative analysis between the Patty (P) planner, the symbolic planners R2 (R2 ), Spring Roll (SR) and the search-based planners ENHSP (EN), Metric FF (FF) and Numeric Fast Downward (NFD). The labels S and L specify if the domain presents simple or linear effects, respectively, see (Arxer and Scala 2023). k means 1000

Bound); the number of variables (sub-table |X A X |) and assertions (sub-table |T (X A X )|) of the encoding with bound n = 1. For the symbolic planners, the bound is increased starting from n = 1 until a plan is found or resources run out. A - indicates that no problem in the domain was solved by the planner with the given resources. The table has been divided based on the average value of |VB|/|VN|: if |VB|/|VN| < 1 the domain is considered Highly Numeric (above), and Lowly Numeric (below) otherwise. From the table, considering the data about the symbolic planners in the last three sub-tables, two main observations are in order. First, PATTY always finds a solution within a bound lower than or equal to the ones needed by the others (accordingly with Theorem 2). Second, even considering the bound n = 1, PATTY produces formulas with (i) roughly the same number of variables as SPRINGROLL and far fewer than R2 ; and (ii) (far) fewer assertions than SPRINGROLL and R2 . Considering the sub-tables with the performance data, (i) on almost all the Highly Numeric domains, PATTY outperforms all the planners, both symbolic and search-based; (ii) in the DRONE and PLANTWATERING domains and in all the Lowly Numeric domains, PATTY outperforms all the other symbolic planners but performs poorly wrt the search-based planners: indeed the solution for such problems usually requires a bound unreachable for PATTY (and for the other symbolic planners as well); (iii) overall, PATTY and ENHSP are the planners having the highest coverage on the highest number of domains, with PATTY having the best average solving time on more domains than ENHSP (and the other planners as well). Finally, we did some experiments with the time-limit set to 30 minutes, obtaining the same overall picture. We also considered the LINEEXCHANGE domain, which is a generalization of the domain in the Example. In this do-

5 10 15 20 25 30 35 40 Number of objects

Planning Time (s)

Figure 1: Performance on the LINEEXCHANGE domain.

main, N = 4 robots are positioned in a line and need to exchange items while staying in their adjacent segments of length D = 2. At the beginning, the first robot has Q N items and the goal is to transfer all the items to the last robot in the line. In Figure 1, we show how the planning time varies with Q: when Q = 1, all the variables are essentially Boolean (since they have at most two possible values) and all the symbolic planners are outperformed by the search-based ones. As Q increases, rolling-up the exchange actions becomes more important, and thus PATTY and SPRINGROLL start to outperform the search-based planners. Patterns allow PATTY to perform better than SPRINGROLL, while our R2 planner performs poorly because of the high number of assertions and variables produced.

Conclusions

We presented the pattern encoding which generalizes the state-of-the-art rolled-up and R2 encodings. We provided theoretical and experimental evidence of its benefits. We believe that our generalization provides a new starting point for the research in symbolic planning. Indeed, more research is needed to extend the ARPG construction for better patterns.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

References Arxer, J. E.; and Scala, E. 2023. International Planning Competition 2023 - Numeric Tracks. https://ipc2023numeric.github.io. Accessed: 2023-08-01. Barrett, C.; Fontaine, P.; and Tinelli, C. 2016. The Satisfiability Modulo Theories Library (SMT-LIB). www.SMTLIB.org. Accessed: 2024-01-06. Bofill, M.; Espasa, J.; and Villaret, M. 2017. Relaxed Exists Step Plans in Planning as SMT. In Sierra, C., ed., Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 563 570. ijcai.org. Bonet, B.; and Geffner, H. 2001. Planning as heuristic search. Artificial Intelligence, 129(1 2): 5 33. De Moura, L.; and Bjørner, N. 2008. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems, 337 340. Springer. Fox, M.; and Long, D. 2003. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research, 20: 61 124. Hoffmann, J. 2003. The Metric-FF Planning System: Translating Ignoring Delete Lists to Numeric State Variables. Journal of artificial intelligence research, 20: 291 341. Kautz, H. A.; and Selman, B. 1992. Planning as Satisfiability. In Neumann, B., ed., 10th European Conference on Artificial Intelligence, ECAI 92, Vienna, Austria, August 3-7, 1992. Proceedings, 359 363. John Wiley and Sons. Kuroiwa, R.; Shleyfman, A.; and Beck, J. C. 2022. LMCut Heuristics for Optimal Linear Numeric Planning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 32, 203 212.

Leofante, F.; Giunchiglia, E.; Abr aham, E.; and Tacchella, A. 2020. Optimal Planning Modulo Theories. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 4128 4134. Yokohama, Japan: International Joint Conferences on Artificial Intelligence Organization. ISBN 978-0-9992411-6-5. Mc Carthy, J.; and Hayes, P. 1969. Some Philosophical Problems From the Standpoint of Artificial Intelligence. In Meltzer, B.; and Michie, D., eds., Machine Intelligence 4, 463 502. Edinburgh University Press. Rintanen, J.; Heljanko, K.; and Niemel a, I. 2006. Planning as satisfiability: parallel plans and algorithms for plan search. Artif. Intell., 170(12-13): 1031 1080. Scala, E.; Haslum, P.; and Thiebaux, S. 2016. Heuristics for Numeric Planning via Subgoaling. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16). Scala, E.; Haslum, P.; Thiebaux, S.; and Ramirez, M. 2016a. Interval-Based Relaxation for General Numeric Planning. In Proceedings of the Twenty-second European Conference on Artificial Intelligence, 655 663. Scala, E.; Ramirez, M.; Haslum, P.; and Thiebaux, S. 2016b. Numeric Planning with Disjunctive Global Constraints via

SMT. Proceedings of the International Conference on Automated Planning and Scheduling, 26: 276 284. Scala, E.; Saetti, A.; Serina, I.; and Gerevini, A. E. 2020. Search-guidance mechanisms for numeric planning through subgoaling relaxation. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, 226 234.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)