# Towards Canonical and Minimal Solutions in a Constraint-based Plan-Space Planner

Arthur Bit-Monnot, Roland Godet

<figure><img src="image_1.png" /></figure>

## To cite this version:

Arthur Bit-Monnot, Roland Godet. Towards Canonical and Minimal Solutions in a Constraint-based Plan-Space Planner. European Conference on Artificial Intelligence (ECAI), Oct 2025, Bologna, Italy. 10.3233/FAIA251373. http-05226061

HAL Id: hal-05226061

https://hal.science/hal-05226061v1

Submitted on 27 Aug 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Towards Canonical and Minimal Solutions in a Constraint-based Plan-Space Planner

Arthur Bit-Monnotª and Roland Godetª,b

ªLAAS-CNRS, Université de Toulouse, CNRS, INSA, Toulouse, France

ᵇONERA/DTIS, Université de Toulouse, France

**Abstract.** Temporal planning is the problem of selecting and scheduling a set of actions in order to achieve a distant objective from an initial state. Constraint Programming (CP) has historically played an important role in many automated temporal planners based on the Plan-Space Planning (PSP) algorithm. In a nutshell, PSP would drive the search for a plan by selecting which actions to add and how to resolve conflicts, with an embedded CP engine in charge of ensuring the coherence of the plan.

In this paper, we consider an existing encoding of temporal planning into constraint programming that adheres to a plan-space approach, but encodes the decision of the PSP algorithm as decision variables of the CSP, thus letting the CP engine entirely drive the search for a solution plan. Analyzing the encoding, we show that the induced search space contains many symmetries that would be absent from the original PSP algorithm. Another caveat of the encoding is that it allows for non-minimal solutions, i.e., solutions in which some actions may be removed without invalidating it.

We propose to extend the encoding with additional symmetry breaking constraints to enforce canonicity of the considered plans. The encoding is further improved with additional constraints to limit the presence of non-minimal plans. We show the extended encoding to very substantially improve the performance of the original version and to be competitive with state-of-the-art state-space temporal planners on the considered benchmarks.

## 1 Introduction

Temporal planning has been for a long time an area of interest to the planning community, thanks to its ability to capture critical features of real world problems. Historically, temporal planning has been developed along plan-space and timeline approaches, and leveraging constraint solvers [15, 6, 26]. However, the progress in heuristic search and SAT solvers has lead to a high interest in state-oriented approaches that explicitly model the state progression from the initial state [1, 10, 21]. LCP (Lifted Constraint-based Planner) [3] is a fairly recent proposal that aims at leveraging existing combinatorial solvers with a compilation of temporal planning problems into a task-indexed Constraint Satisfaction Problem (CSP). The resulting encoding shares most of its properties with plan-space approaches, seeking to establish causal links as supports for previously inserted actions while maintaining the coherence of the state progression by ruling out threats on causal links. While the proposed encoding has been shown to be efficient on scheduling-like tasks where it benefits from the optimization capabilities of the underlying engine, it still

suffers from a lack of scalability on more typical temporal planning problems whose essence is to identify the actions needed to establish a chain of causal supports.

The objective of this paper is to identify the sources of inefficiency in the encoding of LCP and propose dedicated constraints to address or mitigate them. Firstly, we identify and characterize the presence of *symmetries* in the original encoding. We propose an alternative, stronger, definition for the canonicity of the solutions and dedicated constraints to enforce it. Secondly, we identify typical patterns that may lead the planner to repetitively consider *non-minimal plans*, in which a subset of actions does not contribute to the achievement of the goals. For these patterns we propose minimality enforcement constraints to rule them out of the search space.

In the remainder of the paper, we introduce the targeted class of temporal planning problems and the approach taken by LCP. We then present the two contributions and evaluate them on a set of temporal benchmarks, showing the proposal to very substantially improve on the performance of LCP and being competitive with state-space search temporal planners.

## 2 Temporal Planning Background

**Definition 1 (Time Domain).** We represent time with a finite discretization step $\varepsilon \in \mathbb{Q}$. Our time domain $\mathbb{T}$ is defined as $\mathbb{T} = \{0, \varepsilon, 2\varepsilon, 3\varepsilon, \dots, \mathcal{H}\}$, i.e., the set of multiples of $\varepsilon$ until a finite horizon value $\mathcal{H}$. We denote as $\llbracket t, t' \rrbracket$ the subset time-points in $\mathbb{T}$ between $t$ and $t'$, i.e., $\llbracket t, t' \rrbracket = \{t, t + \varepsilon, t + 2\varepsilon, \dots, t'\} \subseteq \mathbb{T}$.

We denote as $\mathcal{O}$ a finite set of *objects* symbols. A parameter $p$ is a symbolic variable with a domain $\mathcal{D}_p \subseteq \mathcal{O}$. For instance, $\mathcal{O} = \{R_1, R_2, A, B, C, \top, \bot\}$ represents a set of robots $(R_1, R_2)$, locations $(A, B, C)$ and boolean values $(\top, \bot)$, while a parameter $p$ representing a robot would have $\mathcal{D}_p = \{R_1, R_2\}$.

**Definition 2 (State Variable).** A state variable $sv(x)$ represents the evolution of a particular state feature over time, where $sv$ is the fluent name and $x = [x_1, \dots, x_n]$ is the set of parameters of the state variable. The set of state variables is denoted as $SV$. We assume a Finite Domain Representation (FDR), with the codomain of each state variable being a subset of $\mathcal{O}$, i.e., $\forall sv \in SV, \mathcal{D}_{sv} \subseteq \mathcal{O}$.

**Example 1.** Consider a state variable $loc(r)$ representing the location of a robot $r$, its codomain is the set of locations $\mathcal{D}_{loc} = \{A, B, C\}$. The state variable $path(\ell_1, \ell_2)$ represents the presence of a path between two locations $\ell_1$ and $\ell_2$, whose codomain is $\mathcal{D}_{path} = \{\top, \bot\}$.
A symbolic expression is either a symbol from O, a parameter, or a state variable. A boolean expression is of the form $S_1 \bowtie S_2$ where $S_1$ and $S_2$ are symbolic expressions and $\bowtie \in \{=, \ne\}$.

**Definition 3 (Action Template).** An action template represents an operation that can be performed in the current environment, and is defined by the tuple $a = (name_a, P_a, \Delta_a, s_a, e_a, C_a, E_a)$ where:

* name_a is name of the action template.

* $P_a$ is the list of parameters of the action, $\forall p \in P_a, D_p \subseteq O$.

* $\Delta_a : O^{|P_a|} \to \mathbb{N}$ denotes the duration of the action (in number of steps $\varepsilon$) as a function of the parameters of the action.

* $s_a \in \mathbb{T}$ and $e_a \in \mathbb{T}$ are variables respectively denoting the start and end time-point of the action.

* $C_a$ denotes the set of conditions. Each condition $c \in C_a$ is of the form $[t, t']B$ where $t$ and $t'$ are time-points from $[s_a, e_a]$ and $B$ is a boolean expression that is required to hold over the temporal interval $[t, t']$.

* $E_a$ denotes the set of effects. Each effect in $E_a$ is of the form $[t, t'] sv(x) := v$ where $t$ and $t'$ are time-points from $[s_a, e_a]$, $sv(x)$ is a state variable with each parameter $x_i \in P_a \cup O$, and $v$ is a symbolic expression. $t$ represents the start time of the effect after which $sv(x)$ loses its previous value (becomes undefined) and $t'$ the end time of the effect at which the new value $v$ is established.

**Example 2.** Consider a move action template $m$ that models the movement of a robot $r$ from a location $\ell_1$ to a location $\ell_2$. The action would have a list of three parameters:

$$P_m = [r, \ell_1, \ell_2]$$

The duration of the action is expressed as a function based on the distance between the two locations and the speed of the robot:

$$\Delta_m(r, \ell_1, \ell_2) = \frac{\text{distance}(\ell_1, \ell_2)}{\text{speed}(r)}$$

The conditions to move the robot $r$ are that it is located at $\ell_1$ at the action start, and there is a path between $\ell_1$ and $\ell_2$:

$$C_m = \{[s_m, s_m] \text{ loc}(r) = \ell_1, \\ [s_m, e_m] \text{ path}(\ell_1, \ell_2) = \top\}$$

Finally, the effects state that the location of $r$ becomes $\ell_2$ at the action end and is undefined during the action (in the $]s_m, e_m[$ interval).

$$E_m = \{[s_m, e_m] \text{ loc}(r) := \ell_2\}$$

**Definition 4 (Planning Problem).** A planning problem is represented by the tuple $(O, A, \Gamma_0, G)$ where $O$ is the set object symbols, $A$ is the set of actions templates, the initial state $\Gamma_0: SV \to O$ associates each state variable to its initial value, and the goal $G$ is a conjunction of boolean expressions that must hold at the horizon $H$.

**Example 3.** Consider a problem where two robots $R_1$ and $R_2$ are initially located at $A$ and must respectively move to $C$ and $B$ in a graph $A \to B \to C$. The initial state and the goal are defined as:

$$\Gamma_0 = \left\{ \begin{array}{ll} \text{loc}(R_1) = A & \text{loc}(R_2) = A \\ \text{path}(A, B) = \top & \text{path}(A, C) = \bot \\ \text{path}(B, C) = \top & \text{path}(C, A) = \bot \end{array} \right\} \\ G = (\text{loc}(R_1) = C \land \text{loc}(R_2) = B)$$

**Definition 5 (Operation).** For a given action template $a \in A$, an operation $op: \langle a(P_{op})@t \rangle$ represent the execution of the action template $a$ with non-variable parameters $P_{op} \in O^{|P_a|}$ at time $t \in \mathbb{T}$. Its model is obtained by substituting in the model of $a$ all parameters $P_a$ by the corresponding argument in $P_{op}$, the start time $s_a$ by $t$ and the end time $e_a$ by $t + \Delta_a(P_{op})$.

Here, $move(R_1, A, B)@2$ would represent the operation of moving the robot identified by the object $R_1$ from location $A$ to location $B$ at time 2. It is an instance of the abstract action template $move$.

**Definition 6 (Plan).** A plan $\pi$ is a set of operations, each instantiated from the set of action templates $A$ of the problem.

Interpreting an initial assignment as an effect at the temporal origin, let us denote as $E_\pi$ the set of effects that appear in the plan or in the initial state:

$$E_{\pi} = \bigcup_{op \in \pi} E_{op} \cup \{[0,0] sv(x) := v \mid \langle sv(x) = v \rangle \in \Gamma_0\}$$

**Definition 7 (Coherent Plan).** A plan $\pi$ is said coherent if it has no two overlapping effects on the same state variable, i.e., for all pairs of distinct effects in $E_\pi$ $[t_1, t'_1]$ $sv_1(x_1) := v_1$ and $[t_2, t'_2]$ $sv_2(x_2) := v_2$, the following must hold $]t_1, t'_1] \cap ]t_2, t'_2] = \emptyset \lor sv_1 \neq sv_2 \lor x_1 \neq x_2$.

Let us refer to $E_\pi^{sv(x)}$ as the set of effects on the state variable $sv(x)$. Given a coherent plan $\pi$, the value of the state variable $sv(x)$ at time $t \in \mathbb{T}$ is either:

* undefined if $\exists \langle [t_e, t'_e] sv(x) := v \rangle \in E_\pi^{sv(x)}$ such that $t \in ]t_e, t'_e[$,

* $v$ if $\exists e = \langle [t_e, t'_e] sv(x) := v \rangle \in E_\pi^{sv(x)}$ such that $e$ is the latest effect before $t$, i.e., no other effect in $E_\pi^{sv(x)}$ starts in $[t'_e, t[$.

Note that as a result of merging the initial state as effects in $E_\pi$, each state variable has at least one preceding effect at every time $t \in \mathbb{T}$.

Let us denote as $C_\pi$ the set of conditions that appear in the plan or the goal:

$$C_{\pi} = \bigcup_{op \in \pi} C_{op} \cup \{[\mathcal{H}, \mathcal{H}]\}$$

A condition $c = \langle [t_c, t'_c] B \rangle$ is said to be entailed by the plan $\pi$, noted $\pi \models c$, if $B$ contains no undefined values and evaluates to true at all times $t \in [t_c, t'_c]$.

**Definition 8 (Solution Plan).** A plan $\pi$ is a solution to the planning problem iff it is coherent and for all conditions $c \in C_\pi, \pi \models c$.

## 3 Constraint-based planning in Lifted Plan-Space

In this paper, we consider the constraint-based planning approach of LCP [3] that essentially consists of (i) determining whether a finite set of lifted actions can be turned into a solution plan, and (ii) growing the considered set of lifted actions until a solution is found.

For a given depth $k$, the approach considers a finite set of action instances:

$$\Pi_k = \bigcup_{a \in A} \{a_i \mid i \in \llbracket 0, k \rrbracket\}$$

where each instance $a_i$ is obtained by a unique renaming of the parameters and time-points of the associated action template $a$. In the following, we will consider a given depth $k$ and refer to the set of instances $\Pi_k$ as $\Pi$.

Given a finite set of action instances $\Pi$, let us denote as $V_\Pi$ the set of all variables (parameters and time-points) in $\Pi$. The objective is to identify:

* a presence function $p: \Pi \to \mathbb{B}$ that indicates whether each action instance $a \in \Pi$ is present in the solution plan, and

* a substitution $\psi: V_\Pi \to O \cup \mathbb{T}$ that substitutes all variables in $\Pi$ with an appropriately typed object in $O$ or instant in $\mathbb{T}$,
such that {$ψ(a) | a ∈ Π ∧ p(a)$} is a solution plan. Note that $ψ(a)$ denotes the operation obtained when substituting all variables in the instance a with $ψ$.

The problem is framed as a CSP over all variables of $V_Π$ and presence variables {$p_a | a ∈ Π$} such that $p_a ⇐⇒ p(a)$. The constraints of the CSP are of two types. *Coherence constraints* ensure that the plan is coherent, i.e., that there are no conflicting effects. *Support constraints* ensure that each condition is supported by a previous effect. A solution to the CSP is a total assignment to all variables that satisfies all coherence and support constraints. From such an assignment, one can recover the presence *p* and substitution *ψ* functions that allow reconstructing the solution plan.

While a detailed presentation of the encoding of the constraints is beyond the scope of this paper, let us present the notion of causal support that is central in our contribution.

**Definition 9 (Support).** We say that an effect $[s, e] sv(x) := v$ supports a condition $[s', e'] sv(x') = v'$ if the following conditions hold:

* $x = x' ∧ v = v'$, i.e., the effect establishes the fact required by the condition,

* $e ≤ s'$, i.e., the effect precedes the condition, and

* there is no other effect $[t, t'] sv(x'') := v''$ such that $t ∈ [e, e'[ ∧ x'' = x, i.e., the effect's value persists until the end of the condition.

Recall that $p_a$ represents the presence of the action instance $a$ in the solution. For any condition $c ∈ C_a$ (resp. effect $e ∈ E_a$) we use the alias $p_c$ (resp. $p_e$) to denote that the condition (resp. the effect) is present in the solution.

For each condition $c ∈ C_Π$ and effect $e ∈ E_Π$, we assume the existence of a boolean variable $S_e^c$ that is true iff the effect $e$ supports the condition $c$ in the solution. Finally, for any condition $c ∈ C_Π$, the support constraint of LCP [3] boils down to enforcing:

$$ \neg p_c \lor \bigvee_{e \in E_\Pi} S_e^c $$

This ensures that for any condition appearing in the solution, there is at least one effect supporting it.

# 4 Symmetry Breaking

Consider the trivial planning problem depicted in Example 3 where two robots $R_1$ and $R_2$ must respectively move from $A$ to $C$ and from $A$ to $B$. The plan of Figure 1 is one solution to this problem.

<figure><img src="image_3.png" /><figcaption>**Figure 1.** Plan to move $R_1$ from $A$ to $C$ and $R_2$ from $A$ to $B$. Dashed arrows represent causal support from an effect of the source to a condition of the target.</figcaption></figure>

Assume our set of optional actions contains $n$ instances of this *move* action template, i.e., $Π = \{m_1, m_2, m_3, ..., m_n\}$. Note that initially, *nothing* distinguishes these instances: they are all copies of the *move* action template whose parameters could be set to obtain

any ground instance of *move*. One may wonder how many solutions to the CSP could represent the solution plan of Figure 1.

In essence, the solver must select (i) one move action (among $n$) to support the first goal $g_1$, (ii) one distinct move action (among the remaining $n-1$) to support the second goal $g_2$, and finally (iii) one move action (among the remaining $n-2$) to support the precondition of the first move. Put otherwise, there would be $\frac{n!}{(n-3)!}$ solutions to the CSP, that would only differ by the template instances used.

## 4.1 Symmetry breaking in LCP

This problem was identified in LCP and (partially) addressed with two complementary symmetry breaking constraints among instances of the same action templates. Consider a set of instances of the same action template $a$, in lexicographic order: $⟨a_1, ..., a_n⟩$. The first constraint states that if a solution plan contains $k$ instances of $a$, then only the $k$ first instances (in lexicographic order) are allowed to be part of the plan:

$$ \forall i, j, \text{ such that } i < j : p_{aj} \implies p_{ai} \quad (1) $$

If we consider this symmetry breaking constraints for the solution of Figure 1, we would only have 3! symmetric solutions left: the solver would be forced to only use the instances $m_1, m_2$ and $m_3$ but would otherwise be free to assign them arbitrarily.

Let us refer to $⟨m_i → m_j → g_1, m_k → g_2⟩$ as the solution where $m_i$ supports $m_j$, which itself supports the first goal ($g_1$), and $m_k$ supports the second goal $g_2$. The solutions allowed by Equation (1) are the following:

$$ \begin{align*} \langle m_1 \rightarrow m_2 \rightarrow g_1, m_3 \rightarrow g_2 \rangle &\quad \langle m_1 \rightarrow m_3 \rightarrow g_1, m_2 \rightarrow g_2 \rangle \\ \langle m_2 \rightarrow m_1 \rightarrow g_1, m_3 \rightarrow g_2 \rangle &\quad \langle m_2 \rightarrow m_3 \rightarrow g_1, m_1 \rightarrow g_2 \rangle \\ \langle m_3 \rightarrow m_1 \rightarrow g_1, m_2 \rightarrow g_2 \rangle &\quad \langle m_3 \rightarrow m_2 \rightarrow g_1, m_1 \rightarrow g_2 \rangle \end{align*} $$

LCP further imposes a total order among instances of the same templates with the following symmetry breaking constraint:

$$ \forall i, j, \text{ such that } i < j : p_{aj} \land p_{ai} \implies start(a_i) \leq start(a_j) \quad (2) $$

In our example, this constraint would enforce

$$ start(m_1) \leq start(m_2) \leq start(m_3) $$

Let us analyze the implications of this constraint in the solutions representing the plan of Figure 1. The instance $m_i$ causally supports instance $m_j$ and must thus precede it in the plan. From Equation (2), it follows that $i < j$, thus pruning three non-canonical solutions.

$$ \begin{align*} \langle m_1 \rightarrow m_2 \rightarrow g_1, m_3 \rightarrow g_2 \rangle &\quad \langle m_1 \rightarrow m_3 \rightarrow g_1, m_2 \rightarrow g_2 \rangle \\ \langle m_2 \rightarrow m_1 \rightarrow g_1, m_3 \rightarrow g_2 \rangle &\quad \langle m_2 \rightarrow m_3 \rightarrow g_1, m_1 \rightarrow g_2 \rangle \\ \langle m_3 \rightarrow m_1 \rightarrow g_1, m_2 \rightarrow g_2 \rangle &\quad \langle m_3 \rightarrow m_2 \rightarrow g_1, m_1 \rightarrow g_2 \rangle \end{align*} $$

The remaining three solutions pass the two symmetry breaking constraints, leading to three representation of the same partial-order solution plan in the search space. Note however that Equation (2) would forbid some linearization of these solutions. For instance, the plan obtained from $⟨m_1 → m_2 → g_1, m_3 → g_2⟩$ would require $m_3$ to start last even though this precedence is not required by the causal structure of the partial-order plan.

## 4.2 Symmetry Breaking on the Causal Graph

One of the limitation of the symmetry breaking of LCP is that it imposes an ordering between actions that are otherwise independent,
i.e., for which the causal links in the partial-order plan impose no ordering. We instead consider symmetries on the causal graph.

Assume an arbitrary ordering over all potential conditions in $C_{\Pi} = \{c_1, \dots, c_n\}$: $c_1 < c_2 < \dots < c_n$. A natural way of imposing a canonicity of the solution plan would be to ensure that if the $i$th instance $(a_i)$ of an action template supports a condition $c_j \in C_{\Pi \setminus \{a_{i-1}, a_i\}}$, the previous instance $a_{i-1}$ of the template should support an earlier condition $c_k \in C_{\Pi \setminus \{a_{i-1}, a_i\}}$ (with $k < j$).

Let us define the support signature $\Sigma_a$ of an action instance $a$ as a vector of its boolean support variables:

$$ \Sigma_a = \langle S_{e_1}^{c_1}, S_{e_2}^{c_1}, \dots, S_{e_m}^{c_1}, S_{e_1}^{c_2}, \dots, S_{e_m}^{c_2}, \dots \rangle $$

where $e_1, \dots, e_m$ are the $m$ effects of $a$. As we are interested in breaking symmetries between consecutive instances $a_i$ and $a_{i+1}$ of the same action template, we will impose that the signature of the first instance is not smaller than the signature of the second one.

Unsurprisingly, this question has been studied in context of symmetry breaking in graphs. Notably, Codish et al. [9] propose a constraint that (transposed to our setting) would impose $\Sigma_a$ to be no smaller than $\Sigma_{a'}$ when ignoring the support of conditions originating from either $a$ and $a'$.

If we denote as first-support $(a, C)$ the index of the first support of $a$ in the set of conditions $C$, this graph symmetry breaking constraint would effectively enforce:

$$ \text{first-support}(a, C_{\Pi \setminus \{a, a'\}}) \le \text{first-support}(a', C_{\Pi \setminus \{a, a'\}}) \quad (3) $$

This is already likely to bring an improvement over the symmetry breaking of LCP. However, we consider instead an improvement that allows to take into account all conditions including the ones of $a$ and $a'$. This done by adapting the graph symmetry breaking constraint of [22], a strict improvement over the previous one.

Transposed to our causal graph, it works by concatenating the support signatures of both $a$ and $a'$ into a single vector $\Sigma_{a,a'}$. In addition, we need to define the swapped vector $\Sigma_{a,a'}$ where all conditions and effects of $a$ are swapped for the conditions and effects of $a'$ and vice-versa. Recall that each element of $\Sigma_{a,a'}$ is a support boolean variable $S_e^c$. If $e$ is an effect in $E_a$ and $e'$ is the corresponding effect in $E_{a'}$, then $S_e^c$ becomes $S_{e'}^c$ and vice-versa. Similarly for conditions, if $c$ is a condition in $C_a$ and $c'$ is the corresponding condition in $C_{a'}$, then $S_e^c$ becomes $S_{e'}^c$ and vice-versa. If both the condition and the effect originate from $a$ or $a'$ then both would be swapped.

For any two consecutive instances $a_i$ and $a_{i+1}$ of the same action template, the constraint would impose that the swapped boolean vector be lexicographically smaller than the original one:

$$ \overline{\Sigma_{a_{i+1}, a_i}} \le_{lex} \Sigma_{a_{i+1}, a_i} \quad (4) $$

which effectively generalizes the first support principle of Equation (3) to consider the conditions of both $a$ and $a'$.

**Lexical constraint encoding** A number of encoding for the lexical constraint over boolean vectors have been proposed in the past [27]. Given two boolean vectors of length $n$, we encode the lexical constraint $b_1b_2b_3 \dots b_n \le_{lex} b'_1b'_2 \dots b'_n$ as follows:

$$ \bigwedge_{i \in [1, n]} \left( b_i \le b_{i'} \lor \bigvee_{j \in [1, i-1]} b_j < b_{j'} \right) \quad (5) $$

where each $b_i$ is a boolean variable interpreted as if it was a binary integer variable (with value 1 for true and 0 for false):

$$ x < y \Leftrightarrow \neg x \wedge y \qquad x \le y \Leftrightarrow \neg x \vee y $$

The most common case for us is to compare variables that are mutually exclusive. Indeed as a condition can only be satisfied by a single effect, it cannot be the case that $S_e^c$ and $S_{e'}^c$ be true at the same time for two distinct effects $e$ and $e'$. In the case where the boolean variables $x$ and $y$ are exclusive (i.e., $\neg x \vee \neg y$ always holds), the above equation can be trivially simplified to the following:

$$ x < y \Leftrightarrow y \qquad x \le y \Leftrightarrow \neg x $$

**Canonicity and Impact on the Causal Graph** Let us now consider what these symmetry breaking constraints would imply for our example of Figure 1. Assume an arbitrary ordering $g_1 < g_2 < c_{m_1} < c_{m_2} < c_{m_3}$ over the goals and action conditions on the loc fluent. The table below presents a visualization of the supports of a canonical solution where the first supports of action instances $m_i$ progresses from left to right as the $i$ increases. This would leave a single canonical solution $\langle m_3 \to m_1 \to g_1, m_2 \to g_2 \rangle$.

<table><thead><tr><th rowspan="2"></th><th colspan="2">goals</th><th>m<sub>1</sub></th><th>m<sub>2</sub></th><th>m<sub>3</sub></th></tr><tr><th>g<sub>1</sub></th><th>g<sub>2</sub></th><th>c<sub>m<sub>1</sub></sub></th><th>c<sub>m<sub>2</sub></sub></th><th>c<sub>m<sub>3</sub></sub></th></tr></thead><tbody><tr><th>e<sub>m<sub>1</sub></sub></th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>e<sub>m<sub>2</sub></sub></th><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>e<sub>m<sub>3</sub></sub></th><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></tbody></table>

Here, it is interesting to see that the first (left-most) conditions in the ordering would benefit from the strongest propagation. In our case, the symmetry breaking constraint between $m_1$ and $m_2$ would impose $S_{e_{m_2}}^{g_1} \le S_{e_{m_1}}^{g_1}$ while the one between $m_2$ and $m_3$ would impose $S_{e_{m_3}}^{g_1} \le S_{e_{m_2}}^{g_1}$. As these three supports are mutually exclusive, this is equivalent to stating $\neg S_{e_{m_2}}^{g_1}$ and $\neg S_{e_{m_3}}^{g_1}$. As at least one support must hold, we could then infer $S_{e_{m_1}}^{g_1}$, establishing the support of the first goal. Having established the values of the first column ($g_1$), the symmetry breaking constraint would be able to propagate on the variables of the second, here to establish that $g_2$ must necessarily be supported by $e_{m_2}$ (now that $e_{m_1}$ can no longer support it as it is incompatible with its support of $g_1$). In fact, for the simple example of Figure 1, it is easy to show that constraint propagation is sufficient to infer the entire causal structure of the plan, without any search.

**Plan-space planning and Condition Ordering** Given that they benefit from a stronger propagation, it is likely that the first conditions in the ordering will be fixed earlier in the search. Thus the ordering will play a role similar to the *flaw selection heuristic* of plan-space planners, whose role is notably to select the next condition to support. Unlike plan-space planners however, our ordering must be static to perform the encoding. Building on this analogy, we order the conditions by decreasing level in the *abstraction hierarchy* of [19] which is the most common static ordering in plan-space planners [14, 6]. In the experiments, we will compare this ordering (most abstract conditions first) with an arbitrary lexical ordering.

# 5 Minimality

Let us now focus on an orthogonal aspect, *plan minimality*.

**Definition 10 (Plan Minimality).** A solution plan $\pi$ is not minimal if there exists a non-empty subset of operations $X \subseteq \pi$ such that $\pi \setminus X$ is still a solution.

Note that the definition is conservative in that it only states a necessary condition for plan minimality. This definition is analogous to the one of Kambhampati for plan-space planning [18]. In this section, we identify several patterns corresponding to non-minimal plans and propose additional constraints to forbid them.
## 5.1 Outgoing Supports

We say that an action instance $a$ has an *outgoing support* if there is a condition $c \in C_{\Pi} \setminus C_a$ such that *supports*($a, c$).

**Lemma 1.** If a plan $\pi$ contains an action $a \in \pi$ with no outgoing support, then $\pi$ is not minimal.

*Proof.* We show that $\pi \setminus \{a\}$ is a valid solution plan. Removing an action is equivalent to removing its conditions $C_a$ and its effects $E_a$. Conditions can always be removed without invalidating the plan as they only induce additional requirements. On the other hand, removing an effect potentially means invalidating the conditions it supports. However, as $a$ has no outgoing support, all conditions supported by effects of $a$ are in $C_a$ and would be removed together with $a$. Thus, no invalidated conditions may remain in the plan. □

For any action instance $a \in \Pi$, we can hence enforce the following constraint that at least one of its effects is used if the action is present:

$$ \neg p_a \lor \bigvee_{e \in E_a} \bigvee_{c \in C_{\Pi} \setminus C_a} S_e^c \quad (6) $$

## 5.2 Useless supports

Given an action instance $a \in \Pi$, we say that an effect $e \in E_a$ is a *useless support* of a condition $c \in C_{\Pi}$ if this support is not sufficient to motivate the addition of $a$ in the plan.

More formally, we ought to identify support relations such that, if an action instance $a \in \Pi$ only has useless supports then the plan is not minimal. This would allow us to strengthen the constraint for outgoing support (Equation (6)) to require all instances $a \in \Pi$ to have at least one non-useless support:

$$ \neg p_a \lor \bigvee_{e \in E_a} \bigvee_{c \in C_{\Pi} \setminus C_a} \left( S_e^c \land \neg \text{useless}(e, c) \right) \quad (7) $$

Let us first identify a common pattern in the Finite Domain Representation (FDR) of actions that will be useful for defining useless supports.

**Definition 11 (Transition).** In an action $a$, an effect $\langle [t, t'] sv(x) : = v' \rangle \in E_a$ is a transition effect $[t, t'] sv(x) : v \to v'$ if there is a condition $c = \langle [t, t] sv(x) = v \rangle \in C_a$ in the same action. We refer to $c$ as the condition of the transition effect.

The transition pattern is useful in that it allows to identify the value of the state variable immediately before the effect and forbids the presence of any other effect between the condition and the effect (due to the coherence requirement).

**Loop transitions.** We refer to a transition effect $[t, t'] sv(x) : v \to v$, from a value $v$ to the same value $v$ as a *loop transition*. While it may seem counter-intuitive, the interest of this loop transition pattern lies in that it forbids any usage (condition or effect) of the state variable $sv(x)$ over the duration of the effect $[t, t']$. It can thus be used to lock a binary resource over the course of an action.<fnref n="1" />

**Lemma 2.** A loop transition is a useless support for any condition $c \in C_{\Pi}$.

<figure><img src="image_4.png" /><figcaption>**Figure 2.** Domain Transition Graph of the state variable representing the state of a rover's store in the Rovers IPC domain.</figcaption></figure>

*Proof.* Let $e = \langle [t_1, t_2] sv(x) : v \to v \rangle$ be a loop transition. Assume, without loss of generality, that $e$ supports a single condition $c = \langle [t_3, t_4] sv(x) = v \rangle$. For the plan to be a solution, there is necessarily an effect $e'$ that supports the condition $[t_1, t_1] sv(x) = v$. Note that there cannot be any effect besides $e$ between $e'$ and $c$. Thus, if the loop transition effect was to be removed, the condition $c$ supported by $e$ would still be supported by $e'$ whose value would persist until $t_4$. □

**Loop chains.** Now that we have established this result for a single transition let us attempt to generalize it to chains of transitions. A set of transition effects $\{e_1, e_2, \dots, e_n\}$ is said to form a *transition chain* if each effect $e_i$ supports the condition of the next transition $e_{i+1}$ (for $i \in \llbracket 1, n-1 \rrbracket$). We represent such a chain as $sv(x) : v_0 \to v_1 \to \dots \to v_n$ where $v_0$ is the value required by the condition of $e_1$ and each other $v_i$ is the value established by the effect $e_i$.

**Lemma 3.** Consider a transition chain $sv(x) : v_0 \to v_1 \to \dots v_n \to v_0$ of effects $\{e_1, \dots, e_{n+1}\}$ where the value $v_0$ of the last effect is the one required by the first one. If each effect $e_i$ only supports the condition of the next transition $e_{i+1}$, then removing the whole chain would not invalidate any condition support.

*Proof.* (Sketch) For the plan to be a solution, there is necessarily an earlier effect $e_0$ supporting the first condition $sv(x) = v_0$ of the chain. The only effect allowed to support a condition outside the chain is $e_{n+1}$ which may support a later condition $c = \langle [t, t] sv(x) = v \rangle$. Note that there cannot be any effect between $e_0$ and $c$ besides the ones of the chain. If we remove the effects and conditions of the whole chain, the value $v_0$ established by $e_0$ would persist until $t$, thus $c$ would be supported by $e_0$. □

In order to exploit this property, we need to identify useless supports, i.e., transition effects whose support for a condition may only lead to such a loop. For this, we consider the Domain Transition Graph (DTG) of state variables [17]. For a state variable $sv(x)$, its DTG contains a node for each value it may assume and an edge $v \xrightarrow{a} v'$ for each transition effect $[t, t'] sv(x) : v \to v'$ appearing in action template $a$.

We say that a node $v$ of the DTG is an *outside contributor*, if the condition $sv(x) = v$ appears in the goal or in any action template that contains an effect on another state variable $sv'(x)$. This means that the fact $sv(x) = v$ is useful in itself or may be used to establish a fact on another state variable.

Let us first consider the DTG of Figure 2, where outside contributing nodes are denoted by a double circle. This denotes a common binary resource consumption pattern where actions such that *sample-rock* consume the space in internal storage and the producing action *drop* frees up the space for future usage. The pattern that we would like to forbid here is having, e.g., a *sample-rock* action present in the plan only to support a later *drop* action.

**Lemma 4.** If the DTG of a state variable $sv(x)$ has a single *outside contributor* node $v$, then any support of a transition $e = \{[t, t'] sv : v \to v'\}$ to a condition is useless.

<footnote n="1">¹ While the pattern is not directly present in PDDL [13] domains, consider an action $a$ with the start condition $[s_a, s_a] sv(x) = \top$, a start effect $[s_a, s_a + \epsilon] sv(x) := \bot$ and an end effect $[e_a, e_a + \epsilon] sv(x) := \top$. If there is no negative condition on $sv(x)$ on any action, these can be represented with an equivalent transition $[s_a, e_a + \epsilon] sv(x) : \top \to \top$.</footnote>
<figure><img src="image_5.png" /><figcaption>**Figure 3.** Domain Transition Graph of the state variable representing which instrument ($i_1$ or $i_2$) is currently powered in the Satellite IPC domain.</figcaption></figure>

*Proof.* Assume the action instance *a* containing *e* has no other supporting effect. We need to prove that the solution plan $\pi$ is not minimal. Assume otherwise that the plan is minimal. Then it must be the case that all actions have at least one outgoing support. As a consequence, the effect *e* must be the first effect of transition chain *sv*: *v* $\to$ *v'* $\to \dots \to$ *v* that eventually ends in *v* which is the only value allowing external contributions. Note that each effect in the chain may only support the condition of the next transition as no nodes on the path are external contributors. Let us refer to *X* as the set of actions containing the effects of the chain (including *a*). Applying Lemma 3, we are allowed to remove all effects and conditions of the chain. After removing these, no action in *X* would have any outgoing support, meaning that $\pi \setminus X$ is a solution plan. This contradicts our assumption of plan minimality and establishes our result that if *e* is the only effect with outgoing support of *a*, then the plan is not minimal. $\square$

Let us now consider the DTG of Figure 3, representing a common case of resource allocation where a resource (here electric power) may be allocated and deallocated. The behaviour that we would like to forbid here is deallocating a resource (e.g., *turn-off*($i_1$)) only to allow reallocating it (e.g., *power-on*($i_1$))

**Lemma 5.** Consider an outside contributing node *v* of the DTG of the state variable *sv*(*x*) such that *v* is not the initial value of *sv*(*x*). Assume there is a distinct node *v'* that is not an outside contributor. Let *e*₁ = ⟨[*t*₁, *t*'<sub>1</sub>] *sv*: *v* $\to$ *v*'⟩ and *e*₂ = ⟨[*t*₂, *t*'<sub>2</sub>] *sv*: *v'* $\to$ *v*⟩ be two transition effects on *sv*(*x*). Then *e*₁ is a useless support for the condition *c* of *e*₂.

*Proof.* Let us denote as $a_1$ and $a_2$ the actions containing $e_1$ and $e_2$ respectively. As $v'$ is not an outside contributor, $a_2$ is known to only have effect $e_2$ and $e_1$ to only support $c$. The effects form a loop transition chain $sv(x): v \to v' \to v$. Hence, if $a_1$ has no other effect with an outgoing support then both actions could be removed from the solution plan, implying that the plan is not minimal. $\square$

Having established these results, we consider that *useless*(*e*, *c*) is true for an effect *e* ∈ E<sub>Π</sub> and a condition *c* ∈ C<sub>Π</sub> iff they satisfy the conditions of one of Lemmas 2, 4 or 5. Having defined this predicate, we can now use the constraint of Equation (7) to exclude these non-minimal solutions from the search space.

# 6 Evaluation

## 6.1 Implementation

The two contributions have been implemented on top of the ARIES solver [4].<fnref n="2" /> For action-based planning, ARIES implements the algorithm and constraint-based encoding of LCP [3] on which we built our contributions. The resulting CSPs are solved with a dedicated scheduling solver [5] which notably enables optimization of the

makespan of the solutions. Search in the scheduling solver exploits the standard activity-based search of SAT solvers. For planning, it first considers the boolean variables encoding causal support.

## 6.2 Evaluated Planners

We refer to ARIES-SYM-MIN as the solver containing all two contributions, with the original symmetry breaking constraints of LCP substituted by the one proposed. ARIES-SYM, is a version with this enhanced symmetry breaking without the minimality enforcement constraints. ARIES-SYMLEX is a variant of the previous where conditions in symmetry breaking are oredered lexicographically instead of with the abstraction hierarchy of [19].

As a baseline, we consider LCP or more precisely its implementation on top of ARIES. It features exactly the same constraints as the original LCP solver but leverages the internal solver of ARIES. We also consider OPTIC [1] and TFLAP [23] as state-of-the-art state-space temporal planners, selected as they supports temporally expressive problems with required concurrency, timed-initial literals and makespan optimization, all of which are considered in the evaluation. TFLAP was the best performing individual planner of the latest temporal planning competition (IPC 2018).

## 6.3 Domains

We consider several domains from the temporal tracks of past International Planning Competition (IPC). One of the limitations in selecting domains is due to the partial support for PDDL [13] in ARIES, notably the restriction of action durations being integers and limited support for numeric expressions defining the action duration (the lifted representation implies that the durations that depend on action parameters cannot be statically computed when grounding).

Depots, Driverlog, Satellite, Rovers and Zenotravel are the eponymous domains from IPC 2002, in their time-simple-automatic variant. Depots deals with logistics problems involving containers in a harbor. Driverlog requires simultaneous planning of the activities of a fleet of trucks and their drivers. Satellite requires scheduling the activities of a fleet of earth-observation satellites. Rovers deals with the activity planning for planetary exploration rovers. Zenotravel considers planning the transportation of people around with planes. MatchCellar is the temporal-satisficing problem from IPC 2014, that notably requires planners to support required-concurrency between actions [11]. Airport and Satellite-TW are the eponymous problems from IPC 2004, in their temporal-time-windows variant. They use PDDL2.2 [12] and leverage timed-initial literals to impose time windows in which some actions are restricted to occur. In Airport, the objective is the control the ground traffic in airports.

While all domains are defined in PDDL [13], solvers based on ARIES leverage the work of Bernardini et al. to lift predicates into a lifted finite domain representation [2]. This notably allows the identification of state variables such as the ones depicted in Figures 2 and 3. For all domains, the plan quality is evaluated based on the makespan of the plan.

## 6.4 Results

All experiments were conducted on a cluster of machines with Intel E5-2695 v3 2.3G CPUs, limited to one CPU per planner, a limitation of 4 GB of memory and a 1800 seconds wall-time timeout. All planners were run in their anytime configuration for which we only keep the best plan.

<footnote n="2">² https://github.com/plaans/aries, git-tag: paper-ecai25-symmetry</footnote>
<table><caption>**Table 1.** Table of results for each of the considered metrics. The best result for a particular metric over a given domain is highlighted in bold.</caption><thead><tr><th rowspan="2"></th><th colspan="2">LCP<br>(baseline)</th><th colspan="2">ARIES<br>SYMLEX</th><th colspan="2">ARIES<br>SYM</th><th colspan="2">ARIES<br>SYM-MIN</th><th colspan="2">OPTIC<br>(baseline)</th><th rowspan="2">TFLAP<br>(baseline)</th></tr><tr><th>Cov</th><th>IPC</th><th>Cov</th><th>IPC</th><th>Cov</th><th>IPC</th><th>Cov</th><th>IPC</th><th>Cov</th><th>IPC</th></tr></thead><tbody><tr><td>Airport (20)</td><td>9</td><td>7.38</td><td>9</td><td>7.38</td><td>9</td><td>7.37</td><td>9</td><td>7.38</td><td>7</td><td>6.8</td><td><b>20</b> 18.2</td></tr><tr><td>Depots (20)</td><td>7</td><td>6.7</td><td>13</td><td>12.84</td><td>13</td><td>12.42</td><td>13</td><td>12.63</td><td>7</td><td>5.37</td><td><b>20</b> 18.55</td></tr><tr><td>Driverlog (20)</td><td>10</td><td>9.42</td><td>14</td><td>13.68</td><td>14</td><td>13.64</td><td>14</td><td>13.79</td><td>15</td><td>12.78</td><td><b>17</b> 16.87</td></tr><tr><td>MatchCellar (20)</td><td>0</td><td>0.0</td><td><b>20</b></td><td>19.2</td><td><b>20</b></td><td>19.2</td><td><b>20</b></td><td>19.2</td><td>0</td><td>0.0</td><td><b>20</b> 20.0</td></tr><tr><td>Rovers (20)</td><td>13</td><td>12.21</td><td>13</td><td>12.9</td><td>13</td><td>12.39</td><td>14</td><td>13.56</td><td><b>20</b></td><td>18.4</td><td>17 16.05</td></tr><tr><td>Satellite (20)</td><td>5</td><td>3.99</td><td>7</td><td>6.7</td><td><b>20</b></td><td>16.76</td><td><b>20</b></td><td>19.32</td><td>16</td><td>13.39</td><td><b>20</b> 12.79</td></tr><tr><td>Satellite-TW (20)</td><td>3</td><td>2.82</td><td>7</td><td>6.94</td><td><b>14</b></td><td>13.43</td><td><b>14</b></td><td>13.66</td><td>9</td><td>8.7</td><td><b>8</b> 6.89</td></tr><tr><td>Zenotravel (20)</td><td>12</td><td>10.87</td><td>14</td><td>13.69</td><td>15</td><td>13.75</td><td>14</td><td>13.11</td><td>12</td><td>9.78</td><td><b>20</b> 19.11</td></tr><tr><td>Total (160)</td><td>59</td><td>53.39</td><td>97</td><td>93.33</td><td>118</td><td>108.96</td><td>118</td><td>112.65</td><td>86</td><td>75.22</td><td><b>142</b> 128.46</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>**Figure 4.** Number of instances solved by each planner over time, considering only the time to produce the first solution, regardless of quality.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Figure 5.** Difference in IPC score of solutions found by ARIES (ARIES-SYM-MIN) and TFLAP. A blue dot at 0.75 indicates that for this instance, the plan returned by TFLAP had a score of 0.25 (i.e. 4 times longer than the one returned by ARIES).</figcaption></figure>

We consider two metrics. Cov is the number of problems for which the planner returned at least one solution. IPC denotes the score that the planner would have obtained in the *satisficing* track of the IPC. Compared to coverage, a planner is penalized if it did not return the best plan among all competing planners (e.g. its score would be 0.5 if it solved all problems with a solution on average twice as costly as the best found).

The results are presented in Table 1. Let us first consider the performance of ARIES-SYM. Compared to LCP, the performance is drastically increased, with ARIES solving many more problems on most domains. Coverage in particular increases from 37% to 60%, making the enhanced symmetry breaking a game changer in the scalability of constraint-based approaches to temporal planning.

The impact of minimality enforcing constraints (in ARIES-SYM-MIN) is more limited but does provide some additional performance gains, which can be attributed to a reduced search space. Looking at the evolution of the coverage as runtime increases (Figure 4) it can be seen that it tends to solve the hardest instances substantially faster even if it does not translate in an increased coverage for this particular timeout (1800s). In addition to an improved makespan on average, a detailed inspection shows that the final plans contain on average less actions (with up to 20% of useless actions avoided in Rovers and Satellite) which is a desirable property even when they do not impact the makespan and thus the measured quality.

Compared to state-space planners, the complete ARIES variant substantially outperforms OPTIC on these benchmarks while TFLAP maintains a better overall coverage. An analysis on individual instances (Figure 5) shows that the dominance of TFLAP is far from strict: 7 instances are solved by ARIES and not TFLAP and when both find a plan (69% of instances), the plans of TFLAP are on average 16.5% longer.

# 7 Discussion and Conclusion

In this section, we propose to conclude by a discussion of the contributions and of their relationship with notable previous work.

**Symmetry Breaking** The proposed symmetry breaking constraint closes an existing gap between the original Plan-Space Planning (PSP) algorithm [16] and its adaptation to constraint-based solving. Indeed, the PSP algorithm does not suffer from the symmetries highlighted in this paper thanks to the systematicity of its flaw resolution strategy that inserts actions once needed for a causal support. This is unlike earlier non-systematic partial order planners such as TWEAK or UA [8, 20] that traded-off systematicity for better guidance.

Even though LCP is the only recent encoding-based plan-space planner, similar encodings have been proposed in context of plan optimization [7]. Interestingly, the symmetry breaking constraints they propose are equivalent to ones of LCP and it would be interesting to see if they would benefit from our proposal.

While we eliminate symmetries on the causal structure of the plan, additional work could be considered, notably to avoid symmetries in the set of objects and initial state along the work started for lifted classical planning domains [24].

**Minimality** Of the minimality enforcement constraints proposed in the paper, only the most simple one (requiring outgoing support) derives from the PSP algorithm. This lack of minimality enforcement as been for a long time identified as a difficulty for plan-space planners that may cause them to loop over repeated action applications. Several proposals have been proposed to tackle this problem by detecting such loops during search [18, 25]. Our proposal implements a restricted form of these approaches, which is required to keep a constraint encoding of reasonable size. These more general techniques may be ported to constraint-based planners through dedicated constraint propagators. Unlike planners that natively rely on the PSP algorithm, our approach is less sensitive to loops thanks to the bounded size of the considered sub-problems that limits the potential for recursion.
## Acknowledgments

Part of this work has been supported by the HumFleet project ANR-23-CE33-0003. Our work has benefitted from the AI Interdisciplinary Institute ANITI. ANITI is funded by the France 2030 program under the Grant agreement n°ANR-23-IACL-0002.

[25] D. E. Smith and M. A. Peot. Suspending recursion in causal-link planning. In *International Conference on Artificial Intelligence Planning and Scheduling (AIPS)*, 1996.

[26] D. E. Smith, J. Frank, and A. K. Jonsson. Bridging the Gap between Planning and Scheduling. *Knowledge Engineering Review*, 2000.

[27] W. Zhao. *Encoding Lexicographical Ordering Constraints in SAT*. Honors Project, Illinois Wesleyan University, 2017.

## References

[1] J. Benton, A. Coles, and A. Coles. Temporal Planning with Preferences and Time-Dependent Continuous Costs. In *International Conference on Automated Planning and Scheduling (ICAPS)*, 2012.

[2] S. Bernardini, F. Fagnani, and D. E. Smith. Extracting Lifted Mutual Exclusion Invariants from Temporal Planning Domains. *Artificial Intelligence*, 2018.

[3] A. Bit-Monnot. A Constraint-based Encoding for Domain-Independent Temporal Planning. In *International Conference on Principles and Practice of Constraint Programming (CP)*, 2018.

[4] A. Bit-Monnot. Experimenting with Lifted Plan-Space Planning as Scheduling: Aries in the 2023 IPC. In *Proceedings of the 2023 International Planning Competition*, 2023.

[5] A. Bit-Monnot. Enhancing Hybrid CP-SAT Search for Disjunctive Scheduling. In *European Conference on Artificial Intelligence (ECAI)*, 2023.

[6] A. Bit-Monnot, M. Ghallab, F. Ingrand, and D. E. Smith. FAPE: a Constraint-based Planner for Generative and Hierarchical Temporal Planning, 2020.

[7] S. Buser, C. A. A., and B. J. Christopher. Mathematical Programming Models for Optimizing Partial-Order Plan Flexibility. In *Frontiers in Artificial Intelligence and Applications*. IOS Press, 2016.

[8] D. Chapman. Planning For Conjunctive Goals. *Artificial Intelligence*, 1987.

[9] M. Codish, A. Miller, P. Prosser, and P. J. Stuckey. Constraints for symmetry breaking in graph representation. *Constraints*, 2018.

[10] A. Coles, A. Coles, M. Fox, and D. Long. COLIN: Planning with Continuous Linear Numeric Change. *Journal of Artificial Intelligence Research (JAIR)*, 2012.

[11] W. Cushing, S. Kambhampati, Mausam, and D. S. Weld. When is Temporal Planning Really Temporal? In *International Joint Conference on Artificial Intelligence (IJCAI)*, 2007.

[12] S. Edelkamp and J. Hoffmann. PDDL2.2: The Language for the Classical Part of the 4th International Planning Competition. In *International Planning Competition (IPC-2004)*, 2004.

[13] M. Fox and D. Long. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. *Journal of Artificial Intelligence Research (JAIR)*, 2003.

[14] F. Garcia and P. Laborie. Hierarchisation of the Search Space in Temporal Planning. In *European Workshop on Planning (EWSP)*, 1995.

[15] M. Ghallab and H. Laruelle. Representation and Control in IxTeT, a Temporal Planner. In *International Conference on Artificial Intelligence Planning and Scheduling (AIPS)*, 1994.

[16] M. Ghallab, D. S. Nau, and P. Traverso. *Automated Planning: Theory and Practice*. 2004.

[17] M. Helmert. A Planning Heuristic Based on Causal Graph Analysis. In *International Conference on Automated Planning and Scheduling (ICAPS)*, 2004.

[18] S. Kambhampati. Admissible pruning strategies based on plan minimality for plan-space planning. In *International Joint Conference on Artificial Intelligence (IJCAI)*, 1995.

[19] C. A. Knoblock. Automatically Generating Abstractions for Planning. *Artificial Intelligence*, 1994.

[20] S. Minton, J. L. Bresina, and M. E. Drummond. Total-order and partial-order planning: A comparative analysis. *Journal of Artificial Intelligence Research (JAIR)*, 1994.

[21] M. F. Rankooh and G. Ghassem-Sani. ITSAT: An Efficient SAT-Based Temporal Planner. *Journal of Artificial Intelligence Research (JAIR)*, 2015.

[22] J. Rintanen and M. F. Rankooh. Symmetry-breaking constraints for directed graphs. In *Proceedings of the 2018 International Planning Competition (IPC)*, 2018.

[23] O. Sapena, E. Marzal, and E. Onaindia. TFLAP: a temporal forward partial-order planner. In *Proceedings of the 2018 International Planning Competition (IPC)*, 2018.

[24] S. Sievers, G. Röger, M. Wehrle, and M. Katz. Theoretical foundations for structural symmetries of lifted PDDL tasks. In *International Conference on Automated Planning and Scheduling (ICAPS)*, 2019.