# When Quality Matters: Constraint Programming for Automated Temporal and Numeric Planning

Roland Godet, Arthur Bit-Monnot, Charles Lesire-Cabaniols

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

## To cite this version:

Roland Godet, Arthur Bit-Monnot, Charles Lesire-Cabaniols. When Quality Matters: Constraint Programming for Automated Temporal and Numeric Planning. International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2025, Athens, Greece. hal-05376434

HAL Id: hal-05376434

https://cnrs.hal.science/hal-05376434v1

Submitted on 21 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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>
# When Quality Matters: Constraint Programming for Automated Temporal and Numeric Planning

Roland Godet

LAAS-CNRS, INSA and DTIS, ONERA

Université de Toulouse, France

rgodet@laas.fr

Arthur Bit-Monnot

LAAS-CNRS, CNRS, INSA

Université de Toulouse, France

abitmonnot@laas.fr

Charles Lesire-Cabaniols

DTIS, ONERA

Université de Toulouse, France

charles.lesire@onera.fr

***Abstract***—Automated planning is a field of Artificial Intelligence interested in finding a set of actions that drives the evolution of the environment from an initial state to a desired goal state. Much of the work of the community has been on so-called domain-independent planning where a solver is expected to produce a plan from an abstract problem, specified in a common description language. This has led the community to produce a number of highly-efficient solvers that can be expected to work on a large variety of domains without any fine-tuning.

Where most of the work has focused on sequential plans over purely symbolic states, we instead propose a constraint-based planner whose focus is on more expressive variants, namely numeric and temporal planning, essential in many practical applications. We extend an existing CP encoding of temporal planning with support for optimization and numeric states and leverage an existing lazy clause generation CP solver to find and optimize plans. Where the most successful automated planners rely on some form of forward-search, we show that constraint-programming can be just as effective in finding satisfiable solutions while substantially improving the quality of the produced plans.

## I. INTRODUCTION & RELATED WORK

Time and resources have played a strong role in the early days of planning technologies. Several approaches historically leveraged constraint programming solvers to reason jointly on the causal, temporal and metric relationship underlying candidates plans [1]–[4]. The introduction of heuristic state-space search however shifted the focus of the community towards an explicit forward exploration of the reachable states, guided by very elaborate heuristics that steer a best-first search algorithm towards the desired goal state [5], [6].

With the definition of PDDL [7] and the International Planning Competition (IPC), state-space search became the de-facto standard for domain-independent automated planning. The introduction of time and numerics in PDDL2.1 [8] did not change this, with the most successful planners extending the key components of state-space search for concurrent actions [9]–[13].

In parallel, a number of compilation-based planners have been introduced for classical [14], [15], temporal [16], [17] and numeric [18]–[20] planning, that have proved efficient in the setting where only provably optimal plans are allowed.

Part of this work has been supported by the HumFleet project ANR-23-CE33-0003 and 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.

Like forward heuristic search planners, those planners rely on a timed-indexed encoding, resulting in an explicit representation of all states traversed by the plan.

On the other hand, the plan-space and timeline approaches from IxTeT [1] or Europa [21], closer in spirit to scheduling solvers and that leveraged constraint programming, have been phased out due to their inability to match the scalability of state-space search in a domain-independent setting. A notable exception is the work on lifted plan-space planning of FAPE [22] and LCP [23], without however support for numeric states or optimization.

The landscape of numeric planning has evolved to encompass different levels of expressiveness. Simple Numeric Planning (SNP) [24] restricts numeric variables to increase and decrease operations with constants, while Linear Numeric Planning (LNP) [25], [26] extends SNP with direct assignment and linear combinations in effect expressions.

In this paper, we *adapt the pure-temporal SMT encoding* of LCP [23], based on chronicles, to an action-based formalism compatible with PDDL2.2 [27]. We *extend the encoding with full support for LNP features and optimization*. This results in an expressive temporal and numeric planner that differs by its *fully lifted-nature* and its exploitation of a *plan-space* search space whose exploration is delegated to a constraint programming solver. The resulting planner is competitive on established temporal and numeric PDDL benchmarks with state-of-the-art state-space planners. Finally, a warm start is used to further improve performance, out-performing state-of-the-art state-space planners in solution quality.

## II. LIFTED ACTION-BASED FORMALISM

In this section, we introduce our lifted action-based formalism used to represent a numeric and temporal planning problem, for the largest part compatible with PDDL2.2 [27].

The *time representation* is assumed to be discrete with a fixed granularity. It is defined from the *temporal origin* (0) to an *horizon* (*H*) by the set of rationals $T = \{0, \varepsilon, 2\varepsilon, \dots, H\}$, where $\varepsilon \in \mathbb{Q}^+$ is the *temporal discretization step*.<fnref n="1" />

The *objects* of the problem's environment (e.g., the robots or locations) are represented by a set of symbols *O*.

As the proposed formalism is lifted, many constructs use *variable parameters*. Each variable parameter is a symbolic variable with a domain $O' \subseteq O$.

<footnote n="1">¹In our implementation, *H* is set to $2^{31} \times \varepsilon$.</footnote>
**Definition 1 (State Variable).** A state variable $sv(x)$ represents a dynamic property of the environment, defined by its name $sv$ and a list of variable parameters $x = [x_1, ..., x_n]$. Its value at time $t \in T$ is denoted as $[t]sv(x)$. There are three types of state variables:

* A boolean state variable is a proposition that can be either true ($\top$), false ($\bot$) or undefined ($\dagger$). The set of boolean state variables is denoted as $SV_B$.

* A symbolic state variable can take any value within a given set of symbols $O' \subseteq O$ or be undefined ($\dagger$). The set of symbolic state variables is denoted as $SV_S$.

* A numeric state variable can take any integer value within a given range $[[lb(sv), ub(sv))]]$ or be undefined ($\dagger$). The integers $lb(sv), ub(sv) \in \mathbb{Z}$ are called the lower and upper bounds of the state variable. The set of numeric state variables is denoted as $SV_N$.

*Remark.* While our formalism uses integers for numeric state variables, this is rarely limiting as values can be scaled to appropriate precision as common in CSP solvers.

**Definition 2 (State).** A state is the representation of the environment at a given time, defined as a total function mapping every ground (variable-free) state variables to an appropriately typed value.

The state variables can be used to build more complex expressions that will be used in subsequent definitions.

**Definition 3 (Symbolic Expression).** A symbolic expression is a symbol that can be evaluated to an object in $O$ or be undefined. It can be either:

* A constant symbol from the set of objects: $o \in O$.

* A symbolic parameter: $p$ with a domain in $O' \subseteq O$.

* A symbolic state variable: $sv(x) \in SV_S$.

**Definition 4 (Numeric Expression).** A numeric expression is a linear sum that can be evaluated to an integer value in $\mathbb{Z}$ or be undefined. It is of the form $\omega_0 + \sum_{i} \omega_i \cdot sv_i(x_i)$ where $\omega_0, \omega_i \in \mathbb{Z}$ are constant integer coefficients and $sv_i(x_i) \in SV_N$ are numeric state variables.

**Definition 5 (Boolean Expression).** A boolean expression is a proposition that can be evaluated to true (it is called *satisfied*), false (*unsatisfied*), or undefined. It can be either:

* A boolean atom: true ($\top$) or false ($\bot$).

* A boolean state variable: $sv(x) \in SV_B$.

* The comparison of a numeric expression $N$ with zero: $N \dashv 0$, where $\dashv \in \{<, \leq, >, \geq, =, \neq\}$.

* The comparison of two symbolic expressions $S_1$ and $S_2$: $S_1 \cong S_2$, with $\cong \in \{=, \neq\}$.

* A propositional formula of other boolean expressions.

For the three types of expressions, the evaluation of the expression $E$ at a given time-point $t \in T$ is done by substituting the state variables by their value at $t$ and is denoted $[t]E$. It is said *undefined* if at least one used state variable is undefined at this time. Finally, the expression is said to be *parametrized* if it contains at least one variable parameter.

**Definition 6 (Effect).** Effects are divided into two categories:

* An *assign effect* $[t]sv(x) := v$ on a state variable $sv(x)$ is the assignment of a new value $v \neq \dagger$ with a compatible type to this state variable.

* An *increase effect* $[t]sv(x) += N$ on a numeric state variable $sv(x) \in SV_N$ is the increase of the current value of $sv(x)$ by the value of a numeric expression $N$. If $sv(x)$ is undefined, the increase effect cannot be applied.

Both effect are said to be executed at a time $t \in T$. As in PDDL2.1, the effect will only establish the value at the next time-point $t + \varepsilon$.

**Definition 7 (Action template).** An action template describes an operation that can be performed in the current environment, defined by the tuple $a = (name_a, P_a, s_a, e_a, C_a, X_a, E_a)$:

* $name_a$ is the unique name of the action.

* $P_a = [p_a^1, ..., p_a^n]$ is its list of variable parameters.

* $s_a, e_a \in T$ are the start and end variable time-points.

* $X_a$ is its set of constraints, each one being a time-independent boolean expression parametrized by $P' \subseteq P_a$. It is common practice to have a constraint on the duration, for instance: $e_a - s_a = k \cdot \varepsilon$, for some $k \in \mathbb{N}$.

* $C_a$ is its set of conditions, each one being a time-dependent boolean expression parametrized by $P' \subseteq P_a$ which must be satisfied at a time-point $t \in [[s_a, e_a]]$.

* $E_a$ is its set of effects, each one being parametrized by $P' \subseteq P_a$ and executed at a time-point $t \in [[s_a, e_a]]$.

An action template is said to be *ground* when its variable parameters have been replaced by symbols in $O$, and its start and end time-points by constants in $T$.

**Definition 8 (Planning Problem).** A planning problem is represented by the tuple $\mathcal{P} = (O, SV, A, s_0, G)$ where:

* $O$ is the set of symbols representing the objects.

* $SV = SV_B \cup SV_N \cup SV_S$ is the set of state variables.

* $A$ is the set of action templates.

* $s_0$ is the initial state, a partial assignment to state variables $SV$ at the temporal origin $0$.

* $G$ is the set of goals, a set of boolean expressions which must be satisfied at the horizon $H$.

From a planning problem, the objective for an automated planner is to derive a plan $\Pi$, i.e., a set of ground actions whose sequenced effects will update the state from $s_0$ to a final state where all goals hold.

The set of effects of a plan $\Pi$ is denoted as $E_{\Pi}$ and is composed of the effects of all actions in the plan. The subset of effects that apply at time $t$ on the state variable $sv(x)$ is denoted as $E_{\Pi}^{[t]sv(x)}$. Because a state variable may only assume a single value at a given time-point, two assign effects cannot simultaneously change the value of the same state variable.

A plan $\Pi$ is said to be *coherent* if all its effects are coherent, i.e., for any $t \in T$ and $sv(x) \in SV$:

$$E_{\Pi}^{[t]sv(x)} = \begin{cases} \emptyset & \text{is empty} \\ \{ := v \} & \text{has only one assign} \\ \{ += N_i \mid 1 \le i \le k \} & \text{has } k \in \mathbb{N} \text{ increases} \end{cases}$$
**Definition 9 (Trace).** A trace is a time-indexed sequence of states that represents the evolution of the environment at each time-point. Given a coherent plan $\Pi$, the evolution over time of a state variable $sv(x)$ is recursively computed from its initial value $[0]sv(x)$, defined in the initial state $s_0$, as follows:

$$[t + \varepsilon]sv(x) = \begin{cases} [t]sv(x) & \text{if } E_{\Pi}^{[t]sv(x)} = \emptyset \\ v & \text{if } E_{\Pi}^{[t]sv(x)} = \{ := v \} \\ [t]sv(x) + \sum_i N_i & \text{if } E_{\Pi}^{[t]sv(x)} = \{ += N_i \} \end{cases}$$

*Remark.* Increase effects are cumulative when applied simultaneously, matching scheduling solvers [28] but differing from PDDL2.1.

**Definition 10 (Solution Plan).** A plan $\Pi$ is a solution of $\mathcal{P}$ iff the following conditions are met: (i) $\Pi$ is coherent. (ii) Numeric state variables are always within their domain or can be undefined. (iii) All actions in $\Pi$ are applicable, i.e., all their conditions are satisfied by the trace. (iv) All goals are satisfied at the horizon $H$. (v) All effects in the plan are executed before $H$.

**Definition 11 (Quality).** A problem can have multiple solutions that can be compared with a *quality metric*, that is either:

* The number of actions in the plan: $|\Pi|$.

* The duration of the plan (*makespan*): $\max\{e_a|a \in \Pi\}$.

* The value of a numeric expression $N$ at the horizon.

Without loss of generality, we will focus only on minimization.

### III. PLANNING AS CONSTRAINT SOLVING

To solve such a planning problem, we adapt the pure-temporal encoding of LCP [23] — which compiles the problem into a series of Constraint Satisfaction Problems (CSPs) solved by a dedicated solver — to our action-based formalism with support for numeric features. The CSP encoding contains both boolean and integer variables, with logical and arithmetic constraints handled through branch-and-bound search and clause learning in the underlying Aries CP solver [29].

CP solvers require a fix-sized encoding in which all variables are known a priori. Just like SAT-based planners, LCP relies on a variable $k \in \mathbb{N}$ that bounds the size of the solution plans currently considered.

Algorithm 1 presents the main loop of the solver, adapted from LCP to support optimization. For a given bound $k \in \mathbb{N}$, the problem is encoded into a CSP ($V_k, \mathcal{X}_k$), where $V_k$ is the set of variables and $\mathcal{X}_k$ is the set of constraints (l. 4). If a solution is already known, an additional constraint imposes an improvement to the cost (l. 6). A CSP solver is invoked to find a satisfying assignment (l. 7). If the solver returns UNSAT, more actions are allowed for the next iteration (l. 9). If a satisfying assignment is found, the corresponding plan is shared with the caller (l. 12), and the search continues with the same bound $k$ with the aim of improving the quality.

This algorithm is able to prove the optimality of the solution only within a given maximum bound $k_{max}$. Completeness can be maintained by setting $k_{max}$ to $\infty$ (the default).

**Algorithm 1** Main algorithm for a planning problem $\mathcal{P}$, producing a sequence of plans of increasing quality within a given maximum bound $k_{max}$.

1: bestPlan $\leftarrow \emptyset$

2: $k \leftarrow 0$

3: **while** $k \le k_{max}$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;($V_k, \mathcal{X}_k$) $\leftarrow$ encode($\mathcal{P}, k$)

5: &nbsp;&nbsp;&nbsp;&nbsp;**if** bestPlan $\ne \emptyset$ **then** $\triangleright$ Require quality improvement

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{X}_k$ $\leftarrow$ $\mathcal{X}_k \cup \{\text{cost}(V_k) < \text{cost}(\text{bestPlan})\}$

7: &nbsp;&nbsp;&nbsp;&nbsp;assignment $\leftarrow$ solveCsp($V_k, \mathcal{X}_k$)

8: &nbsp;&nbsp;&nbsp;&nbsp;**if** assignment $=$ UNSAT **then**

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow k + 1$ $\triangleright$ Allow more actions

10: **else**

11: &nbsp;&nbsp;&nbsp;&nbsp;bestPlan $\leftarrow$ extractPlan(assignment)

12: &nbsp;&nbsp;&nbsp;&nbsp;yield bestPlan $\triangleright$ Notify of new plan

a) **Bounded Problem:** The bound $k$ determines the size of the allowed solution. As in LCP, for a given bound $k$, the solution plan may contain at most $k$ instances of an action. For example, given a bound $k = 2$, a solution to a *Blockworld* problem may contain at most 2 *pickup* actions, at most 2 *putdown* actions, and so on. For a given $k \in \mathbb{N}$, we build the set of action instances $A_k$ by instantiating each action $a \in A$ into $k$ action instances: $A_k = \bigcup_{a_i \in A} \{a_i^1, \dots, a_i^k\}$. Each action instance in $A_k$, represents a potential action of the plan whose participation to the solution as well as its actual parameters and start/end times remain to be determined by the CSP solver.

b) **Plan extraction:** As we will detail in the following sections, the set of variables $V_k$ notably contains for each action instance $a \in A_k$: a boolean variable $\text{pres}(a)$ that is true iff $a$ appears in the solution plan, one variable for each parameter of $a$, and two variables respectively representing the start and end times of $a$. From an assignment $\psi$ to variables $V_k$ produced by a CSP solver, one can thus trivially determine: which action instances participate in the plan as well as their parameters and execution times. More formally the corresponding plan is defined as $\Pi_{\psi} = \{ \psi(a) \mid a \in A_k \text{ s.t. } \psi \models \text{pres}(a) \}$ where $\psi(a)$ denotes the ground action obtained through the substitution of the parameters and time-points of $a$ by their value in $\psi$.

### A. Tokens for Capturing State Evolution

Our problem definition contains several structures that may have similar interpretation despite their different origin. For instance, assignment to state variables may be found in the initial state, and in action instances.

This section introduces the core elements used to provide a unified view of such structures regardless of their origin. These are named *tokens* after the eponymous elements that serve a similar role in timeline-based planning [21]. We distinguish four kinds of tokens, respectively representing (i) the evaluation of a state variable at a given time, (ii) a unified time-independent view of constraints, conditions, and goals, (iii) a unified view of the application of an assignment,
and the initial state, and (iv) the application of an increase effect. They all are associated with the presence variable of the associated action introduced earlier, so the different structures are standalone.

1) **Read Token (new contribution):** A read token is used to reify the value of a state variable at a given time and is of the form: $p : [t]sv(x) = v$. The token states that, if its $p$ is true, then the variable $v$ must take the value of the state variable $sv(x)$ at time $t$. These are primarily used to simplify the problem definition by replacing (nested) expressions with fresh variables. For instance, a condition $[t]free(loc(r))$ appearing in an action instance $a$ would be simplified by introducing two read tokens $pres(a) : [t] loc(r) = \ell$ and $pres(a) : [t] free(\ell) = f$, where $\ell$ and $f$ are two new variables introduced to store the value of the corresponding state variables. Having these two tokens, the condition is now equivalent to stating that $f$ should evaluate to true.

Each time a (potentially nested) state variable expression appears in the problem, a new read token is introduced, and the state variable is replaced by the new variable. The set of read tokens $T_R$ is built from the state variables value used in the action instances, the goals, and the plan quality objective:

$$ T_R = \{ \begin{aligned} & pres(a) : [t]sv(x) = v \mid a \in A, sv(x) \text{ used in } a \\ & \cup \{ \top : [H]sv(x) = v \mid g \in G, sv(x) \text{ used in } g \} \\ & \cup \{ \top : [H]sv(x) = v \mid sv(x) \text{ used in the quality } N \} \end{aligned} \} $$

Note that the scope $p$ limits the reach of tokens. In particular, it specifies that a token originating from an action instance $a$ only needs to be considered when $pres(a)$ holds, while a read token originating from a goal should always be considered.

2) **Condition Token (adapted from LCP):** Each boolean expression $B$ obtained by replacing the state variables by their “read” variables in constraints and conditions is associated with a condition token: $p : B$. The token states that, if it is present ($p = \top$), then $B$ must be satisfied. The set of condition tokens $T_C$ is built from the boolean expressions used in the conditions and constraints of the action instances, and the goals:

$$ T_C = \{ \begin{aligned} & pres(a) : c \mid a \in A, c \in C_a \\ & \cup \{ pres(a) : c \mid a \in A, c \in X_a \} \\ & \cup \{ \top : g \mid g \in G \} \end{aligned} \} $$

3) **Assign Effect Token (adapted from LCP):** Each assign effect $[t]sv(x) := v$ of an action instance is associated with an assign effect token: $p : [t, m]sv(x) := v$. The token states that, if it is present, then $sv(x)$ must be assigned the value $v$ immediately after $t$. Moreover, the time-point variable $m$ (with domain $\mathcal{T}$) is introduced for each assign effect to enforce a mutual exclusion (mutex) period $[t, m]$ where $sv(x)$ cannot be assigned a new value by another assign effect. This will be useful to ensure the coherence of the plan. The set of assign

effect tokens $T_E^A$ is built from the initial state, and the assign effects used in the action instances:

$$ T_E^A = \left\{ \begin{array}{l} \top : [0, m]sv(x) := v \\ \mid v \text{ is the initial value of } sv(x) \end{array} \right\} \\ \cup \left\{ \begin{array}{l} pres(a) : [t, m]sv(x) := v \\ \mid a \in A, [t]sv(x) := v \in E_a \end{array} \right\} $$

4) **Increase Effect Token (new contribution):** Each increase effect $[t]sv(x) += N$ of an action instance is associated with an increase effect token: $p : [t]sv(x) += N$. The token states that, if it is present, then $sv(x)$ must be increased by the value of $N$ immediately after time $t$. The set of increase effect tokens $T_E^I$ is built from the increase effects used in the action instances:

$$ T_E^I = \left\{ \begin{array}{l} pres(a) : [t]sv(x) += N \\ \mid a \in A, [t]sv(x) += N \in E_a \end{array} \right\} $$

## B. Variables used over State Progression

The set of variables $V_k$ used to build the constraints of the CSP are the following:

$$ \begin{aligned} V_k = & \{ pres(a) \mid a \in A_k \} & \text{presence of each action} \\ & \cup \{ p_a^i \mid a \in A_k, p_a^i \in P_a \} & \text{parameters of each action} \\ & \cup \{ s_a \mid a \in A_k \} & \text{start of each action} \\ & \cup \{ e_a \mid a \in A_k \} & \text{end of each action} \\ & \cup \{ v_\kappa \mid \kappa \in T_R \} & \text{value of each read token } \kappa \\ & \cup \{ m_\alpha \mid \alpha \in T_E^A \} & \text{mutex of each assign token } \alpha \end{aligned} $$

## C. Constraints over State Progression

The constraints are used to ensure the consistency of the solution plan, i.e., the constraints and conditions are satisfied, and the effects are coherent. Some constraints are adapted from LCP [23] to support our action-based formalism: (i) the support constraint, (ii) the coherence constraint, and (iii) a part of the structure constraints. They are given for completeness of the paper.

1) **Support Constraint (adapted from LCP):** An assign effect token $\alpha \in T_E^A$ is said to support a non-numeric read token $\kappa \in T_R$ with $sv(x) \in SV \setminus SV_N$ if it assigns a value to $sv(x)$ and maintains this value during the evaluation.

$$ \text{Given } \left\{ \begin{array}{l} \kappa = \langle p_{\kappa} : [t_{\kappa}]sv(x_{\kappa}) = v_{\kappa} \rangle \\ \alpha = \langle p_{\alpha} : [t_{\alpha}, m_{\alpha}]sv(x_{\alpha}) := v_{\alpha} \rangle \end{array} \right. \quad \begin{array}{l} \in T_R \\ \in T_E^A \end{array} $$

The constraint supported-by($\kappa, \alpha$) is defined as:

$$ p_{\alpha} \land t_{\alpha} < t_{\kappa} \land t_{\kappa} \leq m_{\alpha} \land x_{\kappa} = x_{\alpha} \land v_{\kappa} = v_{\alpha} $$

The read token $\kappa$ is said to be supported when it is present and there exists an assign effect token $\alpha$ that supports it. Formally, the constraint supported($\kappa$) is defined as:

$$ p_{\kappa} \implies \bigvee_{\alpha \in T_E^A} \text{supported-by}(\kappa, \alpha) $$

Remark. $x = [x^1, \dots, x^n]$ is a list of variables, therefore, $x_1 = x_2$ is a shorthand for $\bigwedge_{i=1}^n x_1^i = x_2^i$.
2) *Numeric Support Constraint (new contribution)*: An assign effect token $\alpha \in T_E^A$ and a set of increase effect tokens $\Phi \subseteq T_E^I$ are said to *support* a numeric read token $\kappa \in T_R$ with $sv(x) \in SV_N$ if:

* $\alpha$ assigns a value to $sv(x)$ and maintains its mutex period until the evaluation time.

* Each $\varphi_i \in \Phi$ increases the value of $sv(x)$ after $\alpha$ execution and before the evaluation time.

$$ \text{Given} \left\{ \begin{array}{l} \kappa = \langle p_{\kappa} : [t_{\kappa}] sv(x_{\kappa}) = v_{\kappa} \rangle \\ \alpha = \langle p_{\alpha} : [t_{\alpha}, m_{\alpha}] sv(x_{\alpha}) := v_{\alpha} \rangle \\ \Phi = \{ \varphi_i = \langle p_{\varphi}^i : [t_{\varphi}^i] sv(x_{\varphi}^i) += N_{\varphi}^i \} \subseteq T_E^I \end{array} \right. \quad \begin{array}{l} \in T_R \\ \in T_E^A \\ \subseteq T_E^I \end{array} $$

Two intermediates variables are introduced to define the numeric support constraint. Firstly, the variable $\chi_{\alpha}(\kappa, \alpha)$ is constrained to be true iff $\alpha$ assigns a value to $sv(x_{\kappa})$ and maintains its mutex period until the evaluation time:

$$ \chi_{\alpha}(\kappa, \alpha) \iff (p_{\alpha} \wedge t_{\alpha} < t_{\kappa} \wedge t_{\kappa} \leq m_{\alpha} \wedge x_{\kappa} = x_{\alpha}) $$

Secondly, the variable $\chi_{\varphi}(\kappa, \alpha, \varphi_i)$ is constrained to be true iff $\varphi_i$ increases the value of $sv(x_{\kappa})$ after the execution of $\alpha$ and before the evaluation time:

$$ \chi_{\varphi}(\kappa, \alpha, \varphi_i) \iff (p_{\varphi}^i \wedge t_{\alpha} < t_{\varphi}^i \wedge t_{\varphi}^i < t_{\kappa} \wedge x_{\kappa} = x_{\varphi}^i) $$

Lastly, the constraint *num-supported-by* ($\kappa, \alpha, \Phi$) is:

$$ \chi_{\alpha}(\kappa, \alpha) \wedge lb(sv) \leq v_{\kappa} \wedge v_{\kappa} \leq ub(sv) \\ \wedge v_{\kappa} = v_{\alpha} + \sum_{i=1}^{n} [\chi_{\varphi}(\kappa, \alpha, \varphi_i)] \cdot v_{\varphi}^i $$

Where $[P]$ is 1 if $P$ is true, 0 otherwise. This effectively cancels the contribution of any irrelevant increase token $\varphi_i$.

Finally, $\kappa$ is said to be *numerically supported* when it is present and if there exists an assign effect token and a set of increase effect tokens that numerically support it. Formally, the constraint *num-supported* ($\kappa$) is defined as:

$$ p_{\kappa} \implies \bigvee_{\alpha \in T_E^A} \textit{num-supported-by} (\kappa, \alpha, T_E^I) $$

Figure 1 illustrates the numeric support of a state variable *energy*. It shows in green that the read tokens ($\ge$ 20?) are supported by the latest *refuel* action and the consumptions of the *travel* actions that occur since the *refuel* (and prior to the read condition).

<figure><img src="image_3.png" /><figcaption>Fig. 1: Evolution of an *energy* state variable over time, initially set to 40. The *refuel* action sets the value to 100 at the end. The *travel* action consumes some *energy* at the start and checks the value at the end.</figcaption></figure>

3) *Coherence Constraint (adapted from LCP)*: Two distinct assign effect tokens are said to be *coherent* if they do not change the value of the same state variable at the same time.

$$ \text{Given} \left\{ \begin{array}{l} \alpha_1 = \langle p_1 : [t_1, m_1] sv(x_1) := v_1 \rangle \\ \alpha_2 = \langle p_2 : [t_2, m_2] sv(x_2) := v_2 \rangle \end{array} \right. \quad \begin{array}{l} \in T_E^A \\ \in T_E^A \end{array} $$

The constraint *coherent* ($\alpha_1, \alpha_2$) is defined as:

$$ p_1 \wedge p_2 \implies (m_1 \le t_2 \vee m_2 \le t_1 \vee x_1 \ne x_2) $$

Figure 1 also illustrates the mutex periods of the assign effect tokens, represented by the “Mutex Periods” rectangles, and their coherence, represented by the absence of overlap.

Similarly, one assign effect token and one increase effect token are said to be *coherent* if they do not update the same state variable at the same time.

$$ \text{Given} \left\{ \begin{array}{l} \alpha = \langle p_{\alpha} : [t_{\alpha}, m_{\alpha}] sv(x_{\alpha}) := v_{\alpha} \rangle \\ \varphi = \langle p_{\varphi} : [t_{\varphi}] sv(x_{\varphi}) += N_{\varphi} \rangle \end{array} \right. \quad \begin{array}{l} \in T_E^A \\ \in T_E^I \end{array} $$

The constraint *coherent* ($\alpha, \varphi$) is defined as:

$$ p_{\alpha} \wedge p_{\varphi} \implies (t_{\varphi} \neq t_{\alpha} \vee x_{\alpha} \neq x_{\varphi}) $$

4) *Consistency Constraint (from LCP)*: A condition token $\beta \in T_C$ is said to be *consistent* if the boolean expression $B$ is satisfied when the token is present. Given $\beta = \langle p : B \rangle \in T_C$, the constraint *consistent* ($\beta$) is defined as: $p \implies B$

5) *Structure Constraint (partially adapted from LCP)*: Additional constraints are needed to ensure the structure of the actions and effects, i.e., the relation between the start and end time-points of an action, the execution and the mutex (for assignments) time-points of an effect, and the horizon.

$$ \text{Given} \left\{ \begin{array}{l} a = (\text{name}_a, P_a, s_a, e_a, C_a, X_a, E_a) \in \mathbb{A} \\ \alpha = \langle p_{\alpha} : [t_{\alpha}, m_{\alpha}] sv(x_{\alpha}) := v_{\alpha} \rangle \\ \varphi = \langle p_{\varphi} : [t_{\varphi}] sv(x_{\varphi}) += N_{\varphi} \rangle \end{array} \right. \quad \begin{array}{l} \in T_E^A \\ \in T_E^I \end{array} $$

The structure constraints are defined as:

$$ \textit{structure-action} (a) : \textit{pres}(a) \implies 0 \le s_a \le e_a \wedge e_a \le H $$

$$ \textit{structure-assign} (\alpha) : \quad p_{\alpha} \implies t_{\alpha} < H \wedge t_{\alpha} < m_{\alpha} $$

$$ \textit{structure-increase} (\varphi) : \quad p_{\varphi} \implies t_{\varphi} < H $$

## D. Complete Encoding & Properties

The CSP can finally be built from the set of variables $V_k$ and the set of constraints $X_k$ introduced previously:

$$ \begin{align*} V_k &= \{ \text{pres}(a) \mid a \in \mathbb{A}_k \} \cup \{ p_a^i \mid a \in \mathbb{A}_k, p_a^i \in P_a \} \\ &\quad \cup \{ s_a \mid a \in \mathbb{A}_k \} \cup \{ e_a \mid a \in \mathbb{A}_k \} \\ &\quad \cup \{ v_{\kappa} \mid \kappa \in T_R \} \cup \{ m_{\alpha} \mid \alpha \in T_E^A \} \end{align*} $$

$$ \begin{align*} \mathcal{X}_k &= \{ \textit{supported} (\kappa) \mid \kappa \in T_R, sv(x_\kappa) \in SV \setminus SV_N \} \\ &\quad \cup \{ \textit{num-supported} (\kappa) \mid \kappa \in T_R, sv(x_\kappa) \in SV_N \} \\ &\quad \cup \{ \textit{coherent} (\alpha_1, \alpha_2) \mid \alpha_1, \alpha_2 \in T_E^A, \alpha_1 \neq \alpha_2 \} \\ &\quad \cup \{ \textit{coherent} (\alpha, \varphi) \mid \alpha \in T_E^A, \varphi \in T_E^I \} \\ &\quad \cup \{ \textit{consistent} (\beta) \mid \beta \in T_C \} \\ &\quad \cup \{ \textit{structure-action} (a) \mid a \in \mathbb{A}_k \} \\ &\quad \cup \{ \textit{structure-assign} (\alpha) \mid \alpha \in T_E^A \} \\ &\quad \cup \{ \textit{structure-increase} (\varphi) \mid \varphi \in T_E^I \} \end{align*} $$

These definitions complete the encoding step of Algorithm 1. The symmetry breaking constraints of LCP [23] may
be added, but are omitted for the sake of space. Also omitted
are the straightforward constraints for binding the cost of a
solution to a numeric variable (Def. 11).

**Theorem 1 (Completeness).** If the planning problem has a solution, then Algorithm 1 will return a solution plan.

*Proof (Sketch).* For a given solution plan Π, we show that there exists a procedure to determine a bound *k* and an assignment to V_k such that all constraints X_k are satisfied, and the assignment represents the plan Π. See Appendix B for the detailed proof. □

**Theorem 2 (Soundness).** All plans produced by Algorithm 1 are valid with respect to Def. 10.

*Proof (Sketch).* For each of the requirements of Def. 10, one can show that there is a corresponding set of constraints in the CSP whose satisfaction implies that the extracted plan will uphold the requirement. See Appendix C for the detailed proof. □

It follows from Theorem 1 that Algorithm 1 will eventually
find the optimal plan if the instance is satisfiable. However,
Algorithm 1 only proves optimality with respect to a bound *k*
on the number of actions. Automatically computing such upper
bounds remains a difficult task [30] and to the best of our
knowledge not studied for the numeric and temporal classes
of automated planning we consider. In our experience, it is
generally easy to derive tight domain-specific bounds when
facing a particular problem.

IV. EXPERIMENTS

A. ARIES: *Planner Implementation*

For a given planning problem, defined in the PDDL format,
we use the unified-planning library [31] for parsing the
problem into a format compatible to our formalism. The
planner works by encoding the planning problem into a CSP
with the corresponding difference, equality, conjunctive and
disjunctive constraints within a Lazy Clause Generation CP
solver, specialized for scheduling [29]. The high-level loop
proceeds as in Algorithm 1, by increasing the bound *k* on the
number of replicated actions, starting at 0. Once the encoded
problem is shown unsatisfiable or the current solution proven
optimal, the bound is incremented by 1 and process continues.
In practice, *k*<sub>max</sub> is set to infinity, allowing the solver to
explore unbounded solution spaces.

For each bound, the solver is configured to run an activity-
based search (VSIDS), initially restricted to boolean vari-
ables. When optimizing, value selection leverages solution-
guidance [29], where the CP solver will favor the value each
variable has in the best known solution.

B. Planners

We compare the performance of ARIES with two state-of-
the-art automated planners that support PDDL2.2.

**OPTIC** [12] is the most established planner in the space
of temporal and numeric planning. Based on forward state-
space search, partially-ordered plans are built incrementally

from the initial state, using a best-first search strategy guided
by a delete-relaxation heuristic. Consistency of numeric and
temporal variables are handled in a MILP program incremen-
tally updated at each node of the search graph.

**LPG** [32] is a hybrid planner combining a state-space
search for totally ordered plans and a local-search over
partially-ordered plans, both guided by delete-relaxation
heuristics. While LPG in general shows outstanding perfor-
mance, one should keep in mind that it is incomplete with
respect to the semantics of PDDL2.2 as its internal repre-
sentation does not support required-concurrency where two
actions necessarily overlap (as in the Match-Cellar domain of
our benchmarks) [33].

C. Domains

For evaluation, we consider six temporal-numeric domains
from past International Planning Competitions (IPC) and two
adaptations of established scheduling problems.

1) **IPC: Depots, Rovers, and Satellite** are IPC 2002 benchmarks with real numerics rounded to integers and pre-computations for division. **Openstacks** and **UMTS** are from IPC 2008 and 2004 respectively. **Match-Cellar** is a numeric IPC 2011 variant using numeric state variables for matches and fuses.

2) **Scheduling:** We provide scheduling instances as PDDL2.1. **JobShop with Operators** and **RCPSP** optimize makespan with precedence and resource constraints. Action-selection is trivial (all operations are required) but tests temporal/resource optimization. Each activity appears exactly once, so *k* = 0 has no solutions and the solver starts with *k* = 1.

JobShop uses Lawrence [34] instances (3-5 operators).
RCPSP uses PSPLib [35] j30/j60/j120 instances with in-
crease effects for resources. Both use PDDL2.1 with predicates
forcing activity presence and precedence, with resource usage
as increase effects on numeric state variables.

D. Metrics

The planners are run in an anytime configuration, i.e.,
returning plans of increasing quality, over a 600-second period.
They are evaluated based on the following metrics.

The **Coverage** (Cov) is the percentage of instances for which at least one solution was returned.

The IPC score is the one of the satisficing track of the Inter-
national Planning Competition (IPC) and favors high-quality
plans. The score for a solved instance is the ratio between the
quality of the returned plan and the best quality of any returned
plan by any planner for this instance. Quality computation
depends on the problem's metric: for makespan optimization,
it is the plan's total duration; for numeric objectives, it is
the value of the specified numeric expression. For unsolved
instances, it is 0. The final score is the mean of all the previous
scores, multiplied by 100.

E. Results and Discussion

The planners were run on a cluster of machines with
Intel E5-2695 v3 2.3G CPUs, with one CPU per planner,
<table><caption>TABLE I: Performances comparison of the different planners on the different domains. Δ Portfolio indicates the performance increase of the portfolio when ARIES is added.</caption><thead><tr><th rowspan="2"></th><th colspan="2">OPTIC</th><th colspan="2">LPG</th><th colspan="2">ARIES</th><th colspan="2">Δ Portfolio</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></tr></thead><tbody><tr><td>Depots (22)</td><td>54.55</td><td>28.05</td><td><strong>95.45</strong></td><td><strong>92.90</strong></td><td>54.55</td><td>52.65</td><td>0.00</td><td>2.55</td></tr><tr><td>Jobshop (40)</td><td><strong>100</strong></td><td>45.89</td><td><strong>100</strong></td><td>73.21</td><td><strong>100</strong></td><td><strong>93.38</strong></td><td>0.00</td><td>23.81</td></tr><tr><td>Match Cellar (20)</td><td><strong>100</strong></td><td><strong>83.93</strong></td><td>0.00</td><td>0.00</td><td>80.00</td><td>80.00</td><td>0.00</td><td>13.74</td></tr><tr><td>Openstacks (30)</td><td><strong>100</strong></td><td><strong>98.08</strong></td><td><strong>100</strong></td><td>39.62</td><td>83.33</td><td>63.43</td><td>0.00</td><td>1.85</td></tr><tr><td>Rcsp (30)</td><td><strong>100</strong></td><td>59.90</td><td><strong>100</strong></td><td>86.93</td><td><strong>100</strong></td><td><strong>100.00</strong></td><td>0.00</td><td>13.07</td></tr><tr><td>Rovers (20)</td><td>55.00</td><td>37.24</td><td><strong>100</strong></td><td><strong>97.20</strong></td><td>55.00</td><td>47.88</td><td>0.00</td><td>1.75</td></tr><tr><td>Satellite (20)</td><td>75.00</td><td>66.26</td><td><strong>100</strong></td><td><strong>83.40</strong></td><td>95.00</td><td>62.62</td><td>0.00</td><td>1.97</td></tr><tr><td>Umts (50)</td><td><strong>100</strong></td><td>97.50</td><td><strong>100</strong></td><td><strong>100.00</strong></td><td><strong>100</strong></td><td>74.24</td><td>0.00</td><td>0.00</td></tr><tr><td>Average</td><td><u>85.57</u></td><td><u>64.61</u></td><td><u>86.93</u></td><td><u>71.66</u></td><td><u>83.48</u></td><td><u>71.78</u></td><td><u>0.00</u></td><td><u>7.34</u></td></tr></tbody></table>

a limitation of 16GB of memory, a 600 seconds wall-time timeout, and a temporal precision of 0.01 (i.e., $T = \{0, 0.01, 0.02, \dots, H\}$). Problem instances and detailed results are available in an online appendix.<fnref n="2" />

The Table I depicts the performance of the individual planners on the different domains. A first challenge for the solvers is to find a valid plan regardless of its quality. LPG is the most performant at this task, finding at least one valid plan for all problems but one instance of Depots and all instances of Match-Cellar (because of its inability to handle required-concurrency [33]). While this translates to a very high coverage, LPG also produces plans of good quality, comparable to ARIES. On the other hand, OPTIC shows a good coverage but produces plans of lower quality, on average about 7.17% worse than the best alternatives.

ARIES achieves the best plan quality on average, with LPG performing very similarly. A deeper look at the results show different strengths however. On most problems, OPTIC finds quickly a first solution of reasonable quality, which is then only slowly improved as time passes. On the other hand, ARIES in general requires more time to provide a first solution, often of worse quality. From this point on however, the solution quality tends to improve steadily and rapidly. This is somewhat expected from the absence of planning-specific heuristics in the search, until the discovery of the first plan where the solution-guided systematic exploration of the search space works well in practice [29].

A detailed analysis shows that ARIES spends most of its CPU time in proving unsatisfiability or optimality for a given bound $k$, before proceeding to the $k + 1$ bound. This is particularly true for the bound immediately preceding the one where a first solution lies. This is unsurprising as, at this bound, the absence of a solution is not obvious and proving it may be challenging. A similar behavior has been noticed in SAT-based planners for classical planning [14].

To better depict the contribution of ARIES to the planning ecosystem, the right part of the table shows the increase in coverage and plan quality that would result in having ARIES in a portfolio as compared to just LPG and OPTIC. This

portfolio operates as a Virtual Best Solver (VBS), running the three planners (ARIES, OPTIC, LPG) in parallel and returning the best plan found among them. The coverage does not increase, meaning that ARIES does not bring new solutions to instances where none existed. However, the average plan quality increases by 7.34%. This is most notable for the scheduling problems but the contribution is significant in most domains.

## V. WARM STARTING

As seen in the previous experimental results, finding an initial solution for ARIES is in general hard and time consuming, but once a first solution is found it can be rapidly improved. This is a common characteristic of combinatorial optimization solvers based on constraint programming and many of them provide the ability to *warm-start* the solver with an initial solution. The initial solution provides upper bounds on the objective and an assignment to all decision variables that can be used by branching heuristics. While warm-starting is often done with a domain-specific greedy algorithm, in this section we propose to explore the benefits of warm-starting ARIES with the solution provided by other automated planners which allows to maintain domain-independence while benefiting from their velocity at finding initial solutions.

To run a warm-started ARIES$_X$ solver with an initial providing solver $X$, we start by running the solver $X$ until it finds its first solution. It is then immediately stopped and the remaining time is allocated to ARIES, with the plan as input.

Exploiting an initial *warm-start* plan in ARIES is a two steps process. First, we force ARIES to exactly replicate the initial plan. This is done by (i) creating a bounded problem with exactly one action instance per action in the initial plan, and (ii) adding constraints that force each action of the initial plan to match an action instance in the CSP solution (i.e., same parameter and timepoints values). The purpose of this step is to obtain a complete assignment over decision variables in the bounded CSP. Once this first step is completed, the constraints forcing the initial solution are retracted and the solver proceeds normally, i.e., using the previous solution for guidance and increasing the number of actions in the bounded problems once optimality is proven for the current bound.

### A. Experiments

Table II shows the increase in coverage and plan quality of OPTIC and LPG when their first plan is optimized by ARIES.

Coverage increases only on *Match-Cellar* for ARIES$_LPG$ (due to required-concurrency handling), confirming that ARIES does not bring new resolutions compared to the original planner. However, the average plan quality increases by 10.89% for OPTIC, and 5.81% for LPG. This shows that, as expected, ARIES is able to greatly optimize plans when given a starting point. This result confirms and generalizes previous findings on a domain-specific problem [36].

## VI. CONCLUSION

We presented a new lifted formalism for numeric and temporal planning with a planner that adapts an existing

<footnote n="2">²https://github.com/plaans/resources-ictai-25</footnote>
<table><caption>TABLE II: Performances comparison of the different warm-started planners with their standalone counterparts.</caption><thead><tr><th rowspan="2"></th><th colspan="2">OPTIC</th><th colspan="2">ARIES<sub>OPTIC</sub></th><th colspan="2">LPG</th><th colspan="2">ARIES<sub>LPG</sub></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></tr></thead><tbody><tr><td>Depots (22)</td><td>54.55</td><td>28.05</td><td>54.55</td><td>38.34</td><td><strong>95.45</strong></td><td><strong>92.90</strong></td><td><strong>95.45</strong></td><td>81.73</td></tr><tr><td>Jobshop (40)</td><td><strong>100</strong></td><td>45.89</td><td><strong>100</strong></td><td><strong>91.38</strong></td><td><strong>100</strong></td><td>73.21</td><td><strong>100</strong></td><td>89.02</td></tr><tr><td>Match Cellar (20)</td><td><strong>100</strong></td><td>83.93</td><td><strong>100</strong></td><td><strong>93.06</strong></td><td>0.00</td><td>0.00</td><td>80.00</td><td>80.00</td></tr><tr><td>Openstacks (30)</td><td><strong>100</strong></td><td><strong>98.08</strong></td><td><strong>100</strong></td><td>96.99</td><td><strong>100</strong></td><td>39.62</td><td><strong>100</strong></td><td>59.40</td></tr><tr><td>Rcpsp (30)</td><td><strong>100</strong></td><td>59.90</td><td><strong>100</strong></td><td>81.57</td><td><strong>100</strong></td><td><strong>86.93</strong></td><td><strong>100</strong></td><td>84.35</td></tr><tr><td>Rovers (20)</td><td>55.00</td><td>37.24</td><td>55.00</td><td>35.55</td><td><strong>100</strong></td><td><strong>97.20</strong></td><td><strong>100</strong></td><td>60.17</td></tr><tr><td>Satellite (20)</td><td>75.00</td><td>66.26</td><td>75.00</td><td>69.34</td><td><strong>100</strong></td><td><strong>83.40</strong></td><td><strong>100</strong></td><td>66.67</td></tr><tr><td>Umts (50)</td><td><strong>100</strong></td><td>97.50</td><td><strong>100</strong></td><td>97.77</td><td><strong>100</strong></td><td><strong>100.00</strong></td><td><strong>100</strong></td><td>98.44</td></tr><tr><td>Average</td><td><u>85.57</u></td><td><u>64.61</u></td><td><u>85.57</u></td><td><u>75.50</u></td><td><u>86.93</u></td><td><u>71.66</u></td><td><u>96.93</u></td><td><u>77.47</u></td></tr></tbody></table>

CSP encoding for chronicles to our action-based formalism, extended with numeric planning and optimization support.

This results in an original planner in this area dominated by ground state-space search solvers. ARIES exploits a fully lifted representation and delegates plan-space exploration to a clause learning CP solver. Despite its originality, the solver is competitive on PDDL and scheduling benchmarks and excels at finding optimized solutions. Our results show ARIES's bottleneck is finding initial solutions, while it excels at optimization. A warm start approach with plans from other state-of-the-art planners mitigates this limitation, with resulting hybrid planners out-performing originals and competitive with standalone portfolios.

REFERENCES

[1] M. Ghallab and H. Laruelle, "Representation and Control in IxTeT, a Temporal Planner," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 1994.

[2] D. E. Smith, J. D. Frank, and A. K. Jónsson, "Bridging the gap between planning and scheduling," *The Knowledge Engineering Review*, 2000.

[3] J. S. Penberthy and D. S. Weld, "Temporal planning with continuous change," in *AAAI Conference on Artificial Intelligence*, 1994.

[4] V. Vidal and H. Geffner, "Branching and pruning: An optimal temporal pocl planner based on constraint programming," in *Artificial Intelligence*, 2004.

[5] J. Hoffmann and B. Nebel, "The FF planning system: Fast plan generation through heuristic search," *Journal of Artificial Intelligence Research (JAIR)*, 2001.

[6] M. Helmert, "The Fast Downward Planning System," *Journal of Artificial Intelligence Research (JAIR)*, 2006.

[7] D. McDermott, M. Ghallab, A. Howe, C. A. Knoblock, A. Ram, M. Veloso, D. S. Weld, and D. Wilkins, "PDDL-the planning domain definition language," Tech. Rep., 1998.

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

[9] M. B. Do and S. Kambhampati, "Sapa: a multi-objective metric temporal planner," *Journal of Artificial Intelligence Research (JAIR)*, 2003.

[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] K. Halsey, D. Long, and M. Fox, "CRIKEY - a temporal planner looking at the integration of scheduling and planning," in *ICAPS Workshop on Integrating Planning into Scheduling*, 2004.

[12] 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.

[13] A. Valentini, A. Micheli, and A. Cimatti, "Temporal Planning with Intermediate Conditions and Effects," in *AAAI Conference on Artificial Intelligence*, 2020.

[14] J. Rintanen, "Planning as satisfiability: Heuristics," *Artificial Intelligence*, 2012.

[15] D. Höller and G. Behnke, "Encoding Lifted Classical Planning in Propositional Logic," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 2022.

[16] M. F. Rankooh and G. Ghassem-Sani, "ITSAT: an efficient sat-based temporal planner," *Journal of Artificial Intelligence Research (JAIR)*, 2015.

[17] S. Panjkovic and A. Micheli, "Abstract action scheduling for optimal temporal planning via OMT," in *AAAI Conference on Artificial Intelligence*, 2024.

[18] F. Leofante, "Omtplan: A tool for optimal planning modulo theories," *Journal on Satisfiability, Boolean Modeling and Computation*, 2023.

[19] C. Piacentini, M. Castro, A. Cire, and J. C. Beck, "Compiling Optimal Numeric Planning to Mixed Integer Linear Programming," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 2018.

[20] E. Scala, M. Ramírez, P. Haslum, and S. Thiébaux, "Numeric planning with disjunctive global constraints via smt," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 2016.

[21] J. Barreiro, M. Boyce, M. B. Do, J. Frank, M. Iatauro, T. Kichkaylo, P. H. Morris, J. Ong, E. Remolina, T. Smith, and D. E. Smith, "EUROPA: A Platform for AI Planning, Scheduling, Constraint Programming, and Optimization," in *International Competition on Knowledge Engineering for Planning and Scheduling (ICKEPS)*, 2012.

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

[23] A. Bit-Monnot, "A Constraint-Based Encoding for Domain-Independent Temporal Planning," in *Principles and Practice of Constraint Programming*, 2018.

[24] D. Gnad, L.-o. Alon, E. Weiss, and A. Shleyfman, "Pdb5 go numeric: Pattern-database heuristics for simple numeric planning," in *AAAI Conference on Artificial Intelligence*, 2025.

[25] X. Lin, Q. Chen, L. Fang, Q. Guan, W. Luo, and K. Su, "Generalized linear integer numeric planning," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 2022.

[26] A. Shleyfman, R. Kuroiwa, and J. C. Beck, "Symmetry detection and breaking in linear cost-optimal numeric planning," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 2023.

[27] S. Edelkamp and J. Hoffmann, "PDDL2.2: The Language for the Classical Part of the 4th International Planning Competition," Tech. Rep., 2004.

[28] P. Laborie, J. Rogerie, P. Shaw, and P. Vilím, "IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG," *Constraints*, 2018.

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

[30] M. Abdulaziz, "Plan-length bounds: Beyond 1-way dependency," in *AAAI Conference on Artificial Intelligence*, 2019.

[31] A. Micheli, A. Bit-Monnot, G. Röger, E. Scala, A. Valentini, L. Framba, A. Rovetta, A. Trapasso, L. Bonassi, A. E. Gerevini, L. Iocchi, F. Ingrand, U. Köckemann, F. Patrizi, A. Saetti, I. Serina, and S. Stock, "Unified planning: Modeling, manipulating and solving ai planning problems in python," *SoftwareX*, 2025.

[32] A. Gerevini, A. Saetti, and I. Serina, "An approach to efficient planning with numerical fluents and multi-criteria plan quality," *Artificial Intelligence*, 2008.

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

[34] S. Lawrence, "Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement)," *Graduate School of Industrial Administration, Carnegie-Mellon University*, 1984.

[35] R. Kolisch and A. Sprecher, "PSPLIB - A project scheduling problem library: OR software - ORSEP Operations Research Software Exchange Program," *European Journal of Operational Research (EJOR)*, 1997.

[36] K. Booth, M. Do, J. Beck, E. Rieffel, D. Venturelli, and J. Frank, "Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation," in *International Conference on Automated Planning and Scheduling (ICAPS)*, 2018.
# APPENDIX A
## SOLUTION PLAN AND CSP RELATION

In this appendix, we demonstrate a way to build an assignment to the CSP variables such that the encoded plan matches a given solution plan. This is needed as a preliminary to the completeness proof.

For a given solution plan Π, the variables in the CSP are:

$$ \mathcal{V} = \{ \begin{aligned} & p_a^i | a \in A, p_a^i \in P_a \\ & \cup \{ s_a | a \in A \} \cup \{ e_a | a \in A \} \\ & \cup \{ \text{pres}(a) | a \in A \} \\ & \cup \{ v_\kappa | \kappa \in T_R \} \\ & \cup \{ m_\alpha | \alpha \in T_E^A \} \end{aligned} \} $$

There are three groups of variables:

* Variables related to actions: $\{ p_a^i | a \in A, p_a^i \in P_a \} \cup \{ s_a | a \in A \} \cup \{ e_a | a \in A \} \cup \{ \text{pres}(a) | a \in A \}$

* Variables related to readings: $\{ v_\kappa | \kappa \in T_R \}$

* Variables related to assignments: $\{ m_\alpha | \alpha \in T_E^A \}$

### A. CSP Action Variables

For each action instance $a \in A$, if the action is present in the solution plan, then the presence variable $\text{pres}(a)$ is set to true ($\top$). Moreover, the parameters $p_a^i$, the start time $s_a$, and the end time $e_a$ of the action are set to the corresponding values in the solution plan.

However, if the action is not present in the solution plan, then the presence variable $\text{pres}(a)$ is set to false ($\bot$) and the other variables are set to arbitrary values since they are not used in the CSP thanks to implies constraints.

This is graphically summarized in the Figure 2.

<figure><img src="image_4.png" /><figcaption>Fig. 2: Relation between the solution plan actions and the CSP action variables</figcaption></figure>

### B. CSP Reading Variables

For each reading $\kappa \in T_R$, the variable $v_\kappa$ is set to the required value in the solution plan.

For a condition $[t]sv(x) = V$ in an action $a \in A$, a read token $\langle \text{pres}(a) : [t]sv(x) = v \rangle \in T_R$ is created. If the action is present in the solution plan ($\text{pres}(a) = \top$), then the variable $v$ is set to $V$. Otherwise, the variable $v$ is set to an arbitrary value since it is not used in the CSP thanks to implies constraints.

For a condition $[t]sv(x) \bowtie V$, where $\bowtie \in \{ <, \leq, >, \geq \}$, in an action $a \in A$, a read token $\langle \text{pres}(a) : [t]sv(x) = v \rangle \in T_R$ is created. If the action is present in the solution plan ($\text{pres}(a) = \top$), then the variable $v$ is set to $V + k$, with $k \in \mathbb{Z}$ such that the condition is respected. Otherwise, the variable $v$ is set to an arbitrary value since it is not used in the CSP thanks to implies constraints.

This is graphically summarized in the Figure 3.

<figure><img src="image_5.png" /><figcaption>Fig. 3: Relation between the solution plan conditions and the CSP reading variables</figcaption></figure>

### C. CSP Mutex Variables

For each assign effect $\alpha \in T_E^A$, the variable $m_\alpha$ is set to the value of the next assign effect execution time-point affecting the same state variable in the solution plan decreased by $\varepsilon$. However, in the case where the assign effect is the last one affecting the state variable, the variable $m_\alpha$ is set just after the horizon, i.e., $m_\alpha = H + \varepsilon$.

This is graphically summarized in the Figure 4.

<figure><img src="image_6.png" /><figcaption>Fig. 4: Relation between the solution plan assign effects and the CSP mutex variables</figcaption></figure>

### D. Solution Plan from the CSP

The previous relations allow to build an assignment of the CSP variables from a solution plan.

In order to create a solution plan from the CSP variable values, only the relations between the action variables and the solution plan actions are needed. If the presence variable $\text{pres}(a)$ is set to $\top$, then the action is present in the solution plan and the parameters $p_a^i$, the start time $s_a$, and the end time $e_a$ are set to the corresponding values in the CSP. However, if the presence variable $\text{pres}(a)$ is set to $\bot$, then the action is not present in the solution plan and the other variables are ignored.
## APPENDIX B
COMPLETENESS PROOF

In this appendix, we prove the Theorem 1 stating that the proposed encoding is complete, i.e., if the planning problem has a solution, then the generated CSP has a solution.

### A. Solution Plan Definition

Let's consider a solution plan Π to the planning problem. Then, according to the Definition 11 of a solution plan, the following holds:

1) Π is coherent, i.e., for any $t \in T$ and $sv(x) \in SV$, $E_{\Pi}^{[t]sv(x)}$ is either:

a) $E_{\Pi}^{[t]sv(x)} = \emptyset$, empty

b) $E_{\Pi}^{[t]sv(x)} = \{ := v \}$, with a single assign

c) $E_{\Pi}^{[t]sv(x)} = \{ += N_i \mid 1 \le i \le k \}$, with $k$ increases

2) Numerical state variables are always within their bounds: $\forall sv(x) \in SV_N, \forall t \in T, lb(sv) \le [t]sv(x) \le ub(sv)$.

3) All actions $a \in \Pi$ are applicable, meaning all constraints and conditions in $C_a$ are entailed by the trace of Π.

4) All goals $g \in G$ are satisfied at the associated time-point.

5) All effects in the plan are executed before the horizon.

### B. Associated CSP Definition

Let's consider $k$ wide enough for $A_k$ to contain enough action instances to represent the solution plan Π. Then, the associated CSP is the tuple variables / constraints ($V, X$), where:

$$ \mathcal{V} = \{ \begin{aligned} & p_a^i \mid a \in A, p_a^i \in P_a \} \\ & \cup \{ s_a \mid a \in A \} \cup \{ e_a \mid a \in A \} \\ & \cup \{ \text{pres}(a) \mid a \in A \} \\ & \cup \{ v_{\kappa} \mid \kappa \in T_R \} \\ & \cup \{ m_{\alpha} \mid \alpha \in T_E^A \} \end{aligned} \} $$

$$ \mathcal{X} = \{ \begin{aligned} & \text{coherent} (\alpha_1, \alpha_2) \mid \alpha_1, \alpha_2 \in T_E^A, \alpha_1 \neq \alpha_2 \} \\ & \cup \{ \text{supported} (\kappa) \mid \kappa \in T_R, sv(x_\kappa) \in SV \setminus SV_N \} \\ & \cup \{ \text{num-supported} (\kappa) \mid \kappa \in T_R, sv(x_\kappa) \in SV_N \} \\ & \cup \{ \text{consistent} (\beta) \mid \beta \in T_C \} \\ & \cup \{ \text{structure-action} (a) \mid a \in A \} \\ & \cup \{ \text{structure-assign} (\alpha) \mid \alpha \in T_E^A \} \\ & \cup \{ \text{structure-increase} (\varphi) \mid \varphi \in T_E^I \} \end{aligned} \} $$

Let's consider the variable assignments of the CSP described in the Appendix A to prove by absurdity that the CSP has a solution. We therefore assume that the CSP has no solution, i.e., a constraint of $X$ is not verified. The following of the proof is organized by the type of constraint that will be first supposed to be violated, and then the contradiction will be shown.

### C. Coherence Constraints

Let's assume that a coherence constraint is not verified, i.e., there exists a pair of assign effects $\alpha_1, \alpha_2 \in T_E^A$ such that $\alpha_1 \neq \alpha_2$ and coherent ($\alpha_1, \alpha_2$) is not verified:

$$ \begin{aligned} \neg (p_1 \wedge p_2) &\implies (m_1 \le t_2 \lor m_2 \le t_1 \lor x_1 \ne x_2) \\ \Leftrightarrow p_1 \wedge p_2 \wedge m_1 > t_2 \wedge m_2 > t_1 \wedge x_1 = x_2 \end{aligned} $$

$p_1 \wedge p_2 \wedge x_1 = x_2$ means that both assign effects are present in the plan and applied to the same state variable.

Moreover, since $t_1 < m_1$ and $t_2 < m_2$, then $m_1 > t_2 \wedge m_2 > t_1$ means that the two mutex periods overlap. This is a **contradiction with the point 1.(b) of a solution plan**, as $E_{\Pi}^{[t]sv(x)}$ can only contain at most one assign effect for each state variable at each time-point.

Similarly, let's assume that a coherence constraint between an assign effect and an increase effect is not verified, i.e., there exists $\alpha \in T_E^A$ and $\varphi \in T_E^I$ such that coherent ($\alpha, \varphi$) is not verified:

$$ \begin{aligned} \neg (p_{\alpha} \wedge p_{\varphi}) &\implies (t_{\varphi} \neq t_{\alpha} \lor x_{\alpha} \neq x_{\varphi}) \\ \Leftrightarrow p_{\alpha} \wedge p_{\varphi} \wedge t_{\varphi} &= t_{\alpha} \wedge x_{\alpha} = x_{\varphi} \end{aligned} $$

This means that both effects are present and applied to the same state variable at exactly the same time-point. This is a **contradiction with the points 1.(b) and 1.(c) of a solution plan**, as at any time-point, either only assign or only increase effects can apply to a state variable.

Therefore, all **coherence constraints are verified**.

### D. Support Constraints

Let's assume that a support constraint is not verified, i.e., there exists a read token value $\kappa \in T_R$ with a state variable $sv(x_\kappa) \in SV \setminus SV_N$ such that supported ($\kappa$) is not verified:

$$ \begin{aligned} \neg (p_{\kappa} &\implies \bigvee_{\alpha \in T_E^A} \text{supported-by} (\kappa, \alpha) \\ \Leftrightarrow p_{\kappa} \wedge \bigwedge_{\alpha \in T_E^A} &\neg \text{supported-by} (\kappa, \alpha) \\ \Leftrightarrow p_{\kappa} \wedge \bigwedge_{\alpha \in T_E^A} &\left( \begin{array}{l} \neg p_{\alpha} \lor t_{\alpha} \ge t_{\kappa} \lor t_{\kappa} > m_{\alpha} \\ \forall x_{\kappa} \ne x_{\alpha} \lor v_{\kappa} \ne v_{\alpha} \end{array} \right) \end{aligned} $$

This means that the read token value is present in the plan, and each assign effect is either:

* $\neg p_\alpha$: not present in the plan

* $t_\alpha \ge t_\kappa$: executed after the reading

* $t_\kappa > m_\alpha$: ended before the reading

* $x_\kappa \ne x_\alpha$: applied to a different state variable

* $v_\kappa \ne v_\alpha$: assigning a different value

Therefore, there is no assign effect that assigns the required value to the state variable at the time-point of the read token value. This is a **contradiction with the points 3 and 4 of a solution plan**, as all actions are applicable and all goals are satisfied.

Finally, all **support constraints are verified**.

### E. Numerical Support Constraints

Let's assume that a numerical support constraint is not verified, i.e., there exists a read token value $\kappa \in T_R$ with a state variable $sv(x_\kappa) \in SV_N$ such that num-supported ($\kappa$) is not verified:

$$ \begin{aligned} \neg (p_{\kappa} &\implies \bigvee_{\alpha \in T_E^A} \text{num-supported-by} (\kappa, \alpha, T_E^I) \\ \Leftrightarrow p_{\kappa} \wedge \bigwedge_{\alpha \in T_E^A} &\neg \text{num-supported-by} (\kappa, \alpha, T_E^I) \\ \Leftrightarrow p_{\kappa} \wedge \bigwedge_{\alpha \in T_E^A} &\left( \begin{array}{l} \neg \chi_{\alpha} (\kappa, \alpha) \lor lb(sv) > v_{\kappa} \lor v_{\kappa} > ub(sv) \\ \lor \left( v_{\kappa} \ne v_{\alpha} + \sum_{i=1}^{|T_E^I|} [\chi_{\varphi} (\kappa, \alpha, \varphi_i)] \cdot v_{\varphi}^i \right) \end{array} \right) \end{aligned} $$
This means that the read token value is present in the plan, and for each assign effect:

* $\neg \chi_{\alpha}(\kappa, \alpha)$: the assign effect token does not assign a value to the state variable or does not maintains its mutex period until the end of the evaluation time. The reasoning is the same as for the support constraints, and it is a **contradiction with the points 3 and 4** of a solution plan.

* $lb(sv) > v_{\kappa} \lor v_{\kappa} > ub(sv)$: the read value is not within the bounds of the state variable. This is a **contradiction with the point 2** of a solution plan, as all numerical state variables are within their bounds.

* $v_{\kappa} \neq v_{\alpha} + \sum_{i=1}^{T_E^I} [\chi_{\varphi}(\kappa, \alpha, \varphi_i)] \cdot v_{\varphi}^i$: the assign and the increase effects do not assign the required value to the state variable. This is **impossible** based on the construction of the assignment, see Appendix A.

Therefore, all **numerical support constraints are verified**.

## F. Consistency Constraints

Let's assume that a consistency constraint is not verified, i.e., there exists a condition token $\beta \in T_C$ such that consistent ($\beta$) is not verified:

$$ \begin{aligned} & \neg (p_{\beta} \implies B_{\beta}) \\ & \Leftrightarrow p_{\beta} \land \neg B_{\beta} \end{aligned} $$

This means that the condition token is present in the plan, but the associated boolean expression is not satisfied. This is a **contradiction with the point 3 and 4** of a solution plan, as all actions are applicable and all goals are satisfied.

Therefore, all **consistency constraints are verified**.

## G. Action Structure Constraints

Let's assume that a constraint on an action structure is not verified, i.e., there exists an action instance $a \in A$ such that structure-action ($a$) is not verified:

$$ \begin{aligned} & \neg (\text{pres}(a) \implies 0 \leq s_a \leq e_a \land e_a \leq H) \\ & \Leftrightarrow \text{pres}(a) \land (s_a < 0 \lor s_a > e_a \lor e_a > H) \end{aligned} $$

This means that the action instance is present in the plan, but:

* $s_a < 0$: The start time is before the temporal origin, which is a **contradiction with the definition of time representation** where $T = \{0, \varepsilon, 2\varepsilon, \dots, H\}$.

* $s_a > e_a$: The start time is after the end time, which is a **contradiction with the definition of an action**.

* $e_a > H$: The end time is after the horizon, which is a **contradiction with the point 5** of a solution plan.

Therefore, all **constraints on action structure are verified**.

## H. Assign Effect Structure Constraints

Let's assume that a constraint on an assign effect structure is not verified, i.e., there exists an assign effect token $\alpha \in T_E^A$ such that structure-assign ($\alpha$) is not verified:

$$ \begin{aligned} & \neg (p_{\alpha} \implies t_{\alpha} < H \land t_{\alpha} < m_{\alpha}) \\ & \Leftrightarrow p_{\alpha} \land (t_{\alpha} \geq H \lor t_{\alpha} \geq m_{\alpha}) \end{aligned} $$

This means that the assign effect token is present in the plan, but the execution time is after the horizon or the mutex time-point, which is a **contradiction with the point 5** of a solution plan or with the definition of an assign effect.

Therefore, all **constraints on assign effect structure are verified**.

## I. Increase Effect Structure Constraints

Let's assume that a constraint on an increase effect structure is not verified, i.e., there exists an increase effect token $\varphi \in T_E^I$ such that structure-increase ($\varphi$) is not verified:

$$ \begin{aligned} & \neg (p_{\varphi} \implies t_{\varphi} < H) \\ & \Leftrightarrow p_{\varphi} \land t_{\varphi} \geq H \end{aligned} $$

This means that the increase effect token is present in the plan, but the execution time is after the horizon, which is a **contradiction with the point 5** of a solution plan.

Therefore, all **constraints on increase effect structure are verified**.

## J. Conclusion

We have shown by absurdity that all constraints of the CSP are verified when the planning problem has a solution. Therefore, **the proposed encoding is complete**, i.e., if the planning problem has a solution, then the generated CSP has a solution. □
## APPENDIX C
### SOUNDNESS PROOF

In this appendix, we prove the Theorem 2 stating that the proposed encoding is sound, i.e., if the generated CSP has a solution, then the original planning problem has a solution as well.

#### A. CSP Solution Definition

Let's consider a solution to our CSP encoding, i.e., a set of values for the variables in $V$ that satisfies all the constraints in $X$:

$$ 
\begin{align*}
\mathcal{V} &= \{ p_a^i | a \in A, p_a^i \in P_a \} \\
&\cup \{ s_a | a \in A \} \cup \{ e_a | a \in A \} \\
&\cup \{ \text{pres}(a) | a \in A \} \\
&\cup \{ v_\kappa | \kappa \in T_R \} \\
&\cup \{ m_\alpha | \alpha \in T_E^A \} \\
\mathcal{X} &= \{ \text{coherent}(\alpha_1, \alpha_2) | \alpha_1, \alpha_2 \in T_E^A, \alpha_1 \neq \alpha_2 \} \\
&\cup \{ \text{supported}(\kappa) | \kappa \in T_R, sv(x_\kappa) \in SV \setminus SV_N \} \\
&\cup \{ \text{num-supported}(\kappa) | \kappa \in T_R, sv(x_\kappa) \in SV_N \} \\
&\cup \{ \text{consistent}(\beta) | \beta \in T_C \} \\
&\cup \{ \text{structure-action}(a) | a \in A \} \\
&\cup \{ \text{structure-assign}(\alpha) | \alpha \in T_E^A \} \\
&\cup \{ \text{structure-increase}(\varphi) | \varphi \in T_E^I \}
\end{align*}
$$

#### B. Associated Plan Definition

Let's consider a plan $\Pi$ of the planning problem built from the solution to the CSP encoding as described in the Appendix A.

Let's prove that the plan $\Pi$ is a solution to the original planning problem, i.e., the following holds:

1) $\Pi$ is coherent, i.e., for any $t \in T$ and $sv(x) \in SV$, $E_{\Pi}^{[t]sv(x)}$ is either:

a) $E_{\Pi}^{[t]sv(x)} = \emptyset$, empty

b) $E_{\Pi}^{[t]sv(x)} = \{ := v \}$, with a single assign

c) $E_{\Pi}^{[t]sv(x)} = \{ += N_i | 1 \le i \le k \}$, with $k$ increases

2) Numerical state variables are always within their bounds: $\forall sv(x) \in SV_N, \forall t \in T, lb(sv) \le [t]sv(x) \le ub(sv)$.

3) All actions $a \in \Pi$ are applicable, meaning all constraints and conditions in $C_a$ are entailed by the trace of $\Pi$.

4) All goals $g \in G$ are satisfied at the associated time-point.

5) All effects in the plan are executed before the horizon.

#### C. Coherence of the Plan

For all pair of assign effect tokens $\alpha_1, \alpha_2 \in T_E^A$, the constraint coherent $(\alpha_1, \alpha_2)$ is satisfied:

$$ p_1 \wedge p_2 \implies (m_1 \le t_2 \vee m_2 \le t_1 \vee x_1 \neq x_2) $$

If at least one of the assign effects is not present in the plan, the constraint is trivially satisfied. Otherwise, let's consider two assign effects $\alpha_1, \alpha_2 \in T_E^A$ present in the plan. If $m_1 \le t_2 \vee m_2 \le t_1$ holds, then one of the assign effects is executed before the other. If $x_1 \neq x_2$ holds, then the assign effects are on different state variables. Therefore, two assign effects on the same state variable cannot be executed at the same time.

Similarly, for all assign effect token $\alpha \in T_E^A$ and increase effect token $\varphi \in T_E^I$, the constraint coherent $(\alpha, \varphi)$ is satisfied:

$$ p_{\alpha} \wedge p_{\varphi} \implies (t_{\varphi} \neq t_{\alpha} \vee x_{\alpha} \neq x_{\varphi}) $$

If at least one of the effects is not present in the plan, the constraint is trivially satisfied. Otherwise, if $t_\varphi \neq t_\alpha$ holds, then the effects are executed at different times. If $x_\alpha \neq x_\varphi$ holds, then the effects are on different state variables. Therefore, an assign effect and an increase effect on the same state variable cannot be executed at the same time.

Moreover, for all read token $\kappa \in T_R$ related to a numerical state variable, i.e., $sv(x_\kappa) \in SV_N$, the constraint num-supported $(\kappa)$ is satisfied:

$$ p_{\kappa} \implies \bigvee_{\alpha \in T_E^A} \left( \begin{array}{l} \chi_{\alpha}(\kappa, \alpha) \wedge lb(sv) \le v_{\kappa} \wedge v_{\alpha} \le ub(sv) \\ \wedge (v_{\kappa} = v_{\alpha} + \sum_{i=1}^{n} [\chi_{\varphi}(\kappa, \alpha, \varphi_i)] \cdot v_{\varphi}^i) \end{array} \right) $$

This implies that for each increase effect token $\varphi_i \in T_E^I$ present in the plan, there is a read token $\kappa \in T_R$ and an assign effect token $\alpha \in T_E^A$ such that $\chi_\varphi(\kappa, \alpha, \varphi_i)$ holds:

$$ p_{\varphi}^i \wedge t_{\alpha} < t_{\varphi}^i \wedge t_{\varphi}^i \le t_{\kappa} \wedge x_{\kappa} = x_{\varphi}^i $$

* $p_{\varphi}^i$: The increase effect token is present in the plan.

* $t_{\alpha} < t_{\varphi}^i$: The assign effect token is executed strictly before the increase effect token.

* $t_{\varphi}^i \le t_{\kappa}$: The read token is executed at the same time or after the increase effect token.

* $x_\kappa = x_\varphi^i$: The increase effect token is related to the same state variable as the assign effect token because $\chi_\alpha(\kappa, \alpha)$ holds so $x_\varphi^i = x_\kappa = x_\alpha$.

Finally, for all assign and increase effects related to the same state variable, it is impossible to have two assign effects or an increase effect with an assign effect at the same time. Therefore, the plan $\Pi$ is coherent and **the first point of the definition is satisfied**.

#### D. Numerical State Variable Bounds

For all read token $\kappa \in T_R$ related to a numerical state variable, i.e., $sv(x_\kappa) \in SV_N$, the constraint num-supported $(\kappa)$ is satisfied:

$$ p_{\kappa} \implies \bigvee_{\alpha \in T_E^A} \left( \begin{array}{l} \chi_{\alpha}(\kappa, \alpha) \wedge lb(sv) \le v_{\kappa} \wedge v_{\alpha} \le ub(sv) \\ \wedge (v_{\kappa} = v_{\alpha} + \sum_{i=1}^{n} [\chi_{\varphi}(\kappa, \alpha, \varphi_i)] \cdot v_{\varphi}^i) \end{array} \right) $$

In particular, we have $lb(sv) \le v_\kappa \wedge v_\alpha \le ub(sv)$ iff the reading is present in the plan. Therefore, it is impossible for a numerical state variable to be out of bounds and **the second point of the definition is satisfied**.

#### E. Applicability of the Actions

For all condition token $\beta \in T_C$, the constraint consistent $(\beta)$ is satisfied:

$$ p_{\beta} \implies B_{\beta} $$

Therefore, the condition or the constraint is satisfied or absent in the plan. Moreover, for all state variable initially
present in the boolean expression $B_β$, the constraints related supported (.) and num-supported (.) are satisfied.

*Remark.* For simplicity, only the supported (.) constraint will be considered for the rest of this subsection, but the reasoning is the same for the num-supported (.) constraint.

Therefore, for all read token $κ \in T_R$ related to a state variable present in the boolean expression $B_β$, the constraint supported (κ) is satisfied:

$$p_κ \implies \bigvee_{α \in T_E^A} \left( \begin{array}{l} p_α \wedge t_α < t_κ \wedge t_κ \le m_α \\ \wedge x_κ = x_α \wedge v_κ = v_α \end{array} \right)$$

This means that there is an assign effect token $α \in T_E^A$ such that:

* $p_α$: The assign effect token is present in the plan.

* $t_α < t_κ \wedge t_κ \le m_α$: The read token is contained in the interval of the assign effect token.

* $x_κ = x_α$: The read token is related to the same state variable as the assign effect token.

* $v_κ = v_α$: The value read is the value assigned by the assign effect token.

Therefore, there exist assign effects for all read tokens in the boolean expression $B_β$ giving the expected value to the boolean expression. Finally, all actions in the plan are applicable and the third point of the definition is satisfied.

## F. Goal Satisfaction

Because all goals are encoded as conditions, the previous reasoning applies to the goals as well. Therefore, all goals are satisfied at the associated time-point and the fourth point of the definition is satisfied.

## G. Effects Before Horizon

For every assign effect token $α \in T_E^A$, the constraint structure-assign (α) is satisfied:

$$p_α \implies t_α < H \wedge t_α < m_α$$

Therefore, all present assign effects are executed before the horizon. Moreover, for all increase effect token $φ \in T_E^I$, the constraint structure-increase (φ) is satisfied:

$$p_φ \implies t_φ < H$$

Therefore, all present assign and increase effects are executed before the horizon and the fifth point of the definition is satisfied.

## H. Plan Structure Check

For every assign effect token $α \in T_E^A$, the constraint structure-assign (α) is satisfied:

$$p_α \implies t_α < H \wedge t_α < m_α$$

Therefore, all present assign effects have a mutex period $m_α - t_α$ which is positive. Moreover, for all action $a \in A$, the constraint structure-action (a) is satisfied:

$$\text{pres}(a) \implies s_a \le e_a \wedge e_a \le H$$

Therefore, all present actions have a positive duration $e_a - s_a$ and are executed before the horizon. Finally, the actions and the assign effects are valid based on their definition.

## I. Conclusion

We have shown that the structure of the plan Π build from the solution of the CSP is valid and satisfies all the constraints to be a solution to the original planning problem. Therefore, the proposed encoding is sound, i.e., if the generated CSP has a solution, then the original planning problem has a solution as well.

□
In this appendix, we analyze the size of the proposed CSP encoding of the planning problem. The generated CSP is built from the set of variables $V$ and constraints $\mathcal{X}$:

$$ 
\begin{aligned}
\mathcal{V} = & \{ p_a^i | a \in A, p_a^i \in P_a \} \\
& \cup \{ s_a | a \in A \} \cup \{ e_a | a \in A \} \\
& \cup \{ \text{pres}(a) | a \in A \} \\
& \cup \{ v_\kappa | \kappa \in T_R \} \\
& \cup \{ m_\alpha | \alpha \in T_E^A \}
\end{aligned}
$$

$$ 
\begin{aligned}
\mathcal{X} = & \{ \text{coherent} (\alpha_1, \alpha_2) | \alpha_1, \alpha_2 \in T_E^A, \alpha_1 \neq \alpha_2 \} \\
& \cup \{ \text{supported} (\kappa) | \kappa \in T_R, \text{sv}(x_\kappa) \in SV \setminus SV_N \} \\
& \cup \{ \text{num-supported} (\kappa) | \kappa \in T_R, \text{sv}(x_\kappa) \in SV_N \} \\
& \cup \{ \text{consistent} (\beta) | \beta \in T_C \} \\
& \cup \{ \text{structure-action} (a) | a \in A \} \\
& \cup \{ \text{structure-assign} (\alpha) | \alpha \in T_E^A \} \\
& \cup \{ \text{structure-increase} (\varphi) | \varphi \in T_E^I \}
\end{aligned}
$$

A. Number of Variables

The number of parameters in $\{ p_a^i | a \in A, p_a^i \in P_a \}$ is:

$$ \sum_{a \in A} |P_a| = O \left( |A| \cdot \max_{a \in A} |P_a| \right) $$

The other variables related to actions are $s_a$, $e_a$, and $\text{pres}(a)$ for each action instance $a \in A$, i.e., $3 \cdot |A|$ in total. Moreover, the number of read token values is $|T_R|$, and the number of assign effect token mutexes is $|T_E^A|$.

Therefore, the total number of variables is:

$$ 
\begin{aligned}
|\mathcal{V}| &= O \left( (3 + \max_{a \in A} |P_a|) \cdot |A| + |T_R| + |T_E^A| \right) \\
&= O \left( |A| + |T_R| + |T_E^A| \right)
\end{aligned}
$$

B. Number of Constraints

The size of each group of constraints is as follows:

* Coherence (assign-assign): $O(|T_E^A|^2)$

* Coherence (assign-increase): $O(|T_E^A| \cdot |T_E^I|)$

* Support: $|T_R| \cdot \{T_E^A | sv \notin SV_N\}$

* Num Support: $|T_R| \cdot \{T_E^A | sv \in SV_N\} \cdot |T_E^I|$

* Consistency: $|T_C|$

* Structure: $|A| + |T_E^A| + |T_E^I|$

Therefore, the total number of support constraints (including numerical support) is:

$$ 
\begin{aligned}
& |T_R| \cdot \left\{ \begin{array}{l} T_E^A \\ T_E^A \end{array} \right\} \cdot sv \notin SV_N \\
+ & |T_R| \cdot \left\{ \begin{array}{l} T_E^A \\ T_E^A \end{array} \right\} \cdot sv \in SV_N \\
= & O \left( |T_R| \cdot |T_E^A| \cdot \max(1, |T_E^I|) \right)
\end{aligned}
$$

Finally, the total number of constraints is:

$$ |\mathcal{X}| = O \left( \begin{array}{l} |T_E^A|^2 + |T_E^A| \cdot |T_E^I| + |T_C| \\ + |A| + |T_E^A| + |T_E^I| \\ + |T_R| \cdot |T_E^A| \cdot \max(1, |T_E^I|) \end{array} \right) $$