Mohammed-Tahar Laraba

Sorin Olaru

Silviu-Iulian Niculescu

Franco Blanchini

Giulia Giordano

Daniele Casagrande

Stefano Miani

Guide on Set Invariance for Delay Difference Equations ✩

Keywords: Set invariance, Linear time-delay systems, Discrete time-delay difference equations. 1. Introductory remarks

This paper addresses set invariance properties for linear time-delay systems. More precisely, the first goal of the article is to review known necessary and/or sufficient conditions for the existence of invariant sets with respect to dynamical systems described by linear discrete time-delay difference equations (dDDEs). Secondly, we address the construction of invariant sets in the original state space (also called D-invariant sets) by exploiting the forward mappings. The notion of D-invariance is appealing since it provides a region of attraction, which is difficult to obtain for delay systems without taking into account the delayed states in some appropriate extended state space model.

The present paper contains a sufficient condition for the existence of ellipsoidal D-contractive sets for dDDEs, and a necessary and sufficient condition for the existence of D-invariant sets in relation to linear time-varying dDDE stability. Another contribution is the clarification of the relationship between convexity (convex hull operation) and D-invariance of linear dDDEs. In short, it is shown that the convex hull of the union of two or more D-invariant sets is not necessarily D-invariant, while the convex hull of a non-convex D-invariant set is D-invariant.

Positive invariance is an essential concept in control theory, with applications to constrained dynamical systems analysis, uncertainty handling as well as related control design problems [START_REF] Blanchini | Set invariance in control[END_REF][START_REF] Moussaoui | On bounds of input-output systems. reachability set determination and polyhedral constraints verification[END_REF][START_REF] Hmamed | Positive stabilization of discrete-time systems with unknown delay and bounded controls[END_REF]. It serves as a basic tool in many topics, such as model predictive control [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF][START_REF] Santos | Stable mpc with reduced representation for linear systems with multiple input delays[END_REF][START_REF] Reble | General design parameters of model predictive control for nonlinear time-delay systems[END_REF], fault tolerant control [START_REF] Olaru | Positive invariant sets for fault tolerant multisensor control schemes[END_REF] and reference governor design [START_REF] Stoican | Reference governor design for tracking problems with fault detection guarantees[END_REF]. Furthermore, there exists a close link between classical stability theory and positive invariant sets. It is worth mentioning that, in Lyapunov theory, invariance is implicitly described ✩ A preliminary version of the paper has been presented at the 12 th IFAC Workshop on Time Delay Systems, Ann Arbor (MI), USA, 2015.

Email addresses: mohammed.laraba@lss.supelec.fr (Mohammed-Tahar Laraba), sorin.olaru@lss.supelec.fr (Sorin Olaru), silviu.niculescu@lss.supelec.fr (Silviu-Iulian Niculescu) URL: http://www.supelec.fr/360_p_40423/mohammed-tahar-laraba (Mohammed-Tahar Laraba) by the sub-level sets of a Lyapunov function, which are known to be contractive sets [START_REF] Blanchini | Set-theoretic methods in control[END_REF].

The response of a dynamical system to external excitation is rarely instantaneous, and time-delay models are well suited for describing dynamics related to propagation phenomena and/or communication flows (see, for example, [START_REF] Michiels | Stability and Stabilization of Time-Delay Systems[END_REF][START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF][START_REF] Tarbouriech | Local stabilization of continuous-time delay systems with bounded inputs[END_REF][START_REF] Hennet | A feedback stabilization technique for delay differential systems[END_REF][START_REF] Hmamed | Regulator problem for linear continuous-time delay systems with nonsymmetrical constrained control[END_REF][START_REF] Di Cairano | Refer-ence governor for network control systems subject to variable time-delay[END_REF][START_REF] Gu | Stability of timedelay systems[END_REF][START_REF] Normey-Rico | Control of dead-time processes[END_REF][START_REF] Avila Alonso | A coupled model for healthy and cancer cells dynamics in acute myeloid leukemia[END_REF][START_REF] Miani | Switching controllers for networked control systems with packet dropouts and delays in the sensor channel[END_REF][START_REF] Boussaada | Analysis of drilling vibrations: A time-delay system approach[END_REF][START_REF] Seuret | Lowcomplexity Controllers for Time-delay Systems[END_REF][START_REF] Samanta | Dynamic behaviour for a nonautonomous heroin epidemic model with time delay[END_REF][START_REF] Tarbouriech | Synthesis of controllers for continuous-time delay systems with saturating controls via lmis[END_REF]). In closed loop, the dynamics can be represented by delay differential equations (resp. inclusions) or delay difference equations (resp. inclusions) according to the continuous/discrete framework and the presence of disturbances or uncertainties. In the present paper, we consider autonomous dynamics where the delayed arguments are treated as a state dependence and not as a perturbation signal.

From a mathematical point of view, delay difference equations form an important modeling class, since most modern controllers are implemented via computers or dedicated embedded systems. They have been widely studied in the literature (see [START_REF] Elaydi | An Introduction to Difference Equations[END_REF][START_REF] Fisher | Stability results for delayedrecruitment models in population dynamics[END_REF][START_REF] Tang | Density-dependent birth rate, birth pulses and their population dynamic consequences[END_REF][START_REF] Cooke | On the discretization of a delay differential equation[END_REF]). Difference and differential equations with unbounded random delays have been addressed in [START_REF] Crauel | Difference equations with random delay[END_REF]. Delay difference inclusions DDIs represent also a rich modeling class including networked control systems and uncertain time-delay systems. The relationship between stability of DDIs and the existence of Lyapunov-Krasovskii and Lyapunov-Razumikhin functions has been studied in detail in [START_REF] Gielen | Lyapunov methods for time-invariant delay difference inclusions[END_REF]. Stabilizing controller construction and stability analysis based on Lyapunov-Krasovskii and Lyapunov-Razumikhin functions for DDIs have been proposed therein.

Positive invariance for dynamical systems described by dDDEs has been addressed in [START_REF] Seifert | Positively invariant closed sets for systems of delay differential equations[END_REF]. As hinted before, two main approaches exist in the literature dealing with positive invariant sets for discrete time-delay difference equations. The first approach, referred to as Krasovskii approach, relies on the fact that the discrete-time dDDE allows a finitedimensional extended state space model (this representing a demarcation with respect to the continuoustime counterpart). This extended state space, whose dimension is finite but strongly related to the delay value, leads to an invariant set characterization with respect to an equivalent linear time-invariant model. This concept is well understood and popular in the literature, but it suffers from an increased numerical complexity when delays are relatively large. Lyapunov-Krasovskii and spectral techniques have been also used in [START_REF] Damak | A bridge between Lyapunov-Krasovskii and spectral approaches for stability of difference equations[END_REF] to analyze Lyapunov and asymptotic stability.

The second approach, referred to as Razumikhin approach, has been formulated in the '90s and reinvestigated in the last decade, to obtain an invariant set for the dDDE in the original state space, which is independent of the delay value. This concept is also denoted as D-invariance, and is often conservative as long as the existence conditions are restrictive. It is worth mentioning that a relaxation of the Lyapunov-Razumikhin conditions has been proposed by [START_REF] Gielen | Necessary and sufficient Razumikhin-type conditions for stability of delay difference equations[END_REF]. The proposed conditions, which can be verified by solving an LMI problem for linear dDDEs, prove to be necessary and sufficient for asymptotic stability of dDDEs. Furthermore, the obtained relaxed Lyapunov-Razumikhin functions are useful for constructing invariant sets for dDDEs.

It has been recently recognized that D-invariance can be seen as set factorization of an invariant set in the extended state space [START_REF] Olaru | Low complexity invariant sets for time-delay systems: A set factorization approach[END_REF]. It has been established that the extended state space invariance corresponds to a minimal factorization while D-invariance, under the constraints imposed by the dimension of the dDDE, represents the maximal regular ordered factorization. This interesting result opens the way for factorizations which are in between the two representations, by exploiting non-minimal state space equations. In [START_REF] Laraba | Invariant sets for discrete time-delay systems: Set factorization and state representation[END_REF], the authors have focused on the maximal factorizations. They have proposed a characterization of the link between the Razumikhin and Krasovskii approaches, by using set factorization. The proposed framework yields a fitting trade-off between the conceptual generality of the extended state space approach and the computational convenience of the D-invariance approach. It has been shown that D-invariance represents a particular realization of a broader family of invariant structures. The relationship between these families of invariant sets has been established via set factorization and conjugacy. In [START_REF] Athanasopoulos | On controlled-invariance and stabilization of time-delay systems[END_REF], two specific families of controlled (k, λ)contractive sets in the augmented state space framework have been characterized and the link between these controlled (k, λ)-contractive sets and those of the time-delay system has been established in [START_REF] Raković | Positively invariant families of sets for interconnected and time-delay discrete-time systems[END_REF].

In [START_REF] Lombardi | Cyclic invariance for discrete time-delay systems[END_REF], a new concept of set invariance with respect to discrete-time linear systems subject to delays has been introduced. A family of sets which represent a sequence of cyclically invariant subsets of the state space was defined and characterized. Basically, the existing algebraic conditions for invariance analysis of linear dynamics have been generalized and conditions for the invariance of a given sequences of sets with respect to linear discrete-time dynamics in the presence of delay have been established. The notion of invariant family of sets has been proposed in [START_REF] Raković | Construction of invariant families of sets for linear systems with delay[END_REF][START_REF] Raković | Positively invariant families of sets for interconnected and time-delay discrete-time systems[END_REF] to generalize the cyclic invariance concept.

This paper is an extended version of work published in [START_REF] Laraba | Set invariance for delay difference equations[END_REF], where we addressed the existence of positive invariant sets in the state space of the original dDDE. More precisely, the case of two delays was addressed in the conference paper, while the general case is treated here. D-invariant sets can be seen as invariant sets in both the current and the retarded state space and further related to the stability analysis based on Lyapunov-Razumikhin approach. Sufficient conditions for the existence of a D-invariant set have been first obtained in [START_REF] Dambrine | Feedback control of time-delay systems with bounded control and state[END_REF][START_REF] Goubet-Bartholomeus | Bounded domains and constrained control of linear timedelay systems[END_REF]. Then, a necessary and sufficient characterization for the existence of Dinvariant sets has been provided in [START_REF] Hennet | Stability conditions of constrained delay systems via positive invariance[END_REF][START_REF] Vassilaki | Constrained feedback control of discrete-time systems described by arma models[END_REF]. Particularly, as far as the construction of D-invariant sets is concerned, we can find a series of results in [START_REF] Lombardi | On positive invariance for delay difference equations[END_REF][START_REF] Lombardi | On the polyhedral set invariance conditions for time-delay systems[END_REF], which will be appropriately recalled in the present paper. Recently, [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF] has proposed a computationally efficient numerical routine which is necessary to guarantee the existence of D-invariant sets for the delay difference equations with two delay parameters. This condition covers, for the two delay case, the existing necessary conditions in the literature and proves to reduce considerably the gap with respect to sufficient conditions. In the present work, we provide an interesting example for which the condition in [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF] is verified but the existing algorithms fail to construct a D-invariant set. As discussed in [START_REF] Aleksandrov | Diagonal Lyapunov-Krasovskii functionals for discrete-time positive systems with delay[END_REF], from the stability point of view a pertinent analysis of D-invariance can be made in relationship with delay-independent stability. In short, it has been shown that the existence of a diagonal Lyapunov-Krasovskii functional is necessary and sufficient for delay-independent stability. Polyhedral Lyapunov functions have been used for stability and positive invariance analysis of networked control systems in the presence of bounded delays, constant, unknown or time-varying. The problem of finding stability margins has been proved to reduce to a linear programming problem [START_REF] Bitsoris | Stability, positive invariance and design of constrained regulators for networked control systems[END_REF]. To summarize, the main objectives of the present paper are resumed as follows: i) an overview of necessary and/or sufficient conditions for the existence of D-invariant sets for dDDEs with an arbitrary delay value; ii) a sufficient condition for the existence of ellipsoidal D-invariant sets for dDDEs; iii) the proof of the relationship between time-varying dDDE stability and the existence of D-invariant sets; iv) the proof of two properties related to convexity and convex operations over D-invariant sets. Notably, it is established that a dDDE admits a D-invariant set if and only if it is time-varying delay-independent stable. This paper is structured as follows. Section 2 presents some preliminary mathematical notions and definitions. Basic properties of D-invariance concept are addressed in Section 3. In the same section, we present necessary and sufficient conditions for the existence of non trivial sets. The relationship between D-invariance and stability of dDDEs concludes the section. Algorithmic construction based on set iteration using forward mappings, and some illustrative examples are revisited in Section 4. The concepts of cyclic invariance and the invariant families of sets as well as the relationship with the set factorization are presented in Section 5. Finally Section 6 draws some concluding remarks.

Prerequisites

Notations

We denote by R, R + , Z and Z + sets of real numbers, non-negative reals, integer numbers and nonnegative integers, respectively. For every interval Π of R we define Z Π := Z ∩ Π. For an arbitrary set A ⊆ R n , int(A) denotes the interior of A. B n r (0) denotes the ball of radius r in Euclidean norm, centered in the origin of R n . We denote by 1 n the vector of dimension 'n' with all the entries equal to 1. We denote by D, ∂D, ext(D) the open unit disc, the unit circle and the exterior of the closed unit disc respectively. For the matrix pair (A, B), the set of generalized eigenvalues and the Kronecker product are denoted by γ(A, B) and A ⊗ B, respectively. I n ∈ R n×n and 0 n×m ∈ R n×m denote the identity and the null matrix, respectively. X ⊕ Y denotes the Minkowski sum of sets X and Y, it is defined by:

X ⊕ Y := {z| ∃(x, y) ∈ (X , Y) such that z = x + y} . Definition 1. A set P ⊆ R n is bounded if there ex- ists r ∈ R + such that P ⊂ B n r (0); closed if ∀x / ∈ P, ∃ǫ ∈ R + such that B n ǫ (x) ∩ P = ∅; compact if it is bounded and closed. Definition 2. A set P ⊆ R n is a (proper) C-set if is convex,
compact and includes the origin in its strict interior.

We denote by Com(R n ) and ComC(R n ) the space of compact subsets and the space of C-subsets of R n containing the origin, respectively. The spectrum of a matrix A ∈ R n×n is the set of the eigenvalues of A, denoted by λ(A), while the spectral radius is defined as ρ(A) := max ξ∈λ(A) (|ξ|). The spectral norm will be denoted by σ(A) and is defined as σ(A) := ρ(A T A).

System Dynamics

In the sequel, we will consider discrete time-delay difference equations of the form:

x(k + 1) = d i=0 A i x(k -i) (1)
where x(k) ∈ R n is the state vector at the time k ∈ Z + , d ∈ Z + is the maximal fixed time-delay, the matrices A i ∈ R n×n , for i ∈ Z [0,d] and the initial conditions are considered to be given by x

(-i) = x -i ∈ R n , for i ∈ Z [0,d] .
Definition 3. The null solution of the dDDE:

x(k + 1) = m i=0 A i x(k -d i ) (2)
is asymptotically stable if ∀ǫ > 0, ∃δ > 0 such that whenever

sup j ||x(-j)|| ≤ δ, j = {1, • • • , m}, ||x(k)|| < ǫ, ∀k ∈ Z + and x(k) → 0 when k → ∞. Definition 4. The dDDE (2) is delay-independently stable if its null solution is stable ∀d = [d 0 • • • d m ] ∈ (Z + ) m+1 .
Definition 5. The dDDE with time-varying (positive) delay values:

x(k + 1) = m i=0 A i x(k -d i (k)) (3) is delay-independently stable if its null solution is sta- ble ∀d(k) = [d 0 (k) • • • d m (k)] ∈ (Z + ) m+1 .
It is clear that an extended state space representation can be constructed for any given delay realization. For instance, by setting ξ 1) can be rewritten as:

(k) = x(k) T • • • x(k -d) T T , equation (
ξ(k + 1) = A ξ ξ(k) =      A 0 . . . A d-1 A d I . . . 0 0 . . . . . . . . . . . . 0 . . . I 0      ξ(k), (4)
This class is relevant for modeling several propagation and transmission phenomena. One example is represented by networked control systems (see [START_REF] Heemels | Comparison of overapproximation methods for stability analysis of networked control systems[END_REF]) where the feedback mechanism is affected by communication delays. These delays are known to degrade the performances and eventually affect stability [START_REF] Halanay | Stability and stable oscillations in discrete time systems[END_REF]. We report next, without proof, some well-known results related to asymptotic stability of systems ( 1) and (4) (see e.g [START_REF] Aström | Computer-controlled systems: theory and design[END_REF]).

Lemma 1. The following statements hold:

• System (1) is asymptotically stable if and only if

det zI - d i=0 A i z -i = 0, ∀z ∈ ext(D) ∪ ∂D. (5)
• System (4) is asymptotically stable if and only if:

ρ(A ξ ) < 1. ( 6
)
Theorem 2. The following statements are equivalent:

• The delay difference equation ( 1) is asymptotically stable.

• The system ( 4) is asymptotically stable.

D-INVARIANCE PROPERTIES

Let us first consider the generic (nonlinear) discrete-time dynamical system:

x(k + 1) = f (x(k)) (7)
where x(k) ∈ R n is the state vector at time k ∈ Z + and the function f : R n → R n is continuous. Definition 6. The set P ⊂ R n is said positively invariant for the system ( 7) if for all x(k) ∈ P, x(k + 1) ∈ P for k ∈ Z + . Alternatively, the set P ⊂ R n is positively invariant for (7) if f (P) ⊆ P.

Definition 7. Given a scalar ǫ ∈ R (0,1) , a set P ⊂ R n containing the origin is called ǫ-contractive with respect to system (7) if for any x(k) ∈ P, x(k + 1) ∈ ǫP for k ∈ Z + .

One can notice from Definitions 6 and 7 that positive invariance is a limit case of ǫ-contractivness (it would amount to choosing ǫ = 1 in Definition 7).

In the sequel, we will come back to these notions and detail analogies and particularities of time-delay systems. The D-invariance concept, recalled below, will be widely used throughout this paper for the setcharacterization of dDDEs. The notations by [START_REF] Lombardi | On positive invariance for delay difference equations[END_REF][START_REF] Lombardi | On the polyhedral set invariance conditions for time-delay systems[END_REF] will be mainly used in this endeavor.

Definition 8. A set P ⊆ R n is called D-invariant for the system (1) with initial conditions x -i ∈ P for all i ∈ Z [0,d] if the state trajectory satisfies x(k) ∈ P, ∀k ∈ Z + . Lemma 3. [52]
The following statements are equivalent:

1. P ⊆ R n is D-invariant for system (1).

d i=0

A i P ⊂ P Several properties fix a set of basic relations between D-invariant sets.

Proposition 1. The following properties hold: [START_REF] Blanchini | Set invariance in control[END_REF].

1. If P ⊂ R n is D-invariant then αP is D-invariant for any α ∈ R + . 2. Let P 1 , P 2 ⊂ R n be two D-invariant sets for
Then P 1 ∩ P 2 is a D-invariant set for the same dynamical system. 3. Let P 1 , P 2 ⊂ R n be two D-invariant sets for [START_REF] Blanchini | Set invariance in control[END_REF].

The Minkowski sum P 1 ⊕ P 2 is a D-invariant set for the same dynamical system. 4. If the set P ⊂ R n is D-invariant for the system:

x(k + 1) = d i=0 A i x(k -i) ( 8
)
then P is D-invariant for

x(k + 1) = d i=0 A i x(k -τ i ) (9)
for any τ i ∈ Z + . 5. If the compact set containing the origin P is Dinvariant, then its convex hull Conv(P) is Dinvariant. 6. If P 1 , P 2 ⊂ R n are two D-invariant sets for

(1), their union P 1 P 2 is not necessarily Dinvariant. 7. The convex hull of the union of D-invariant sets is not necessarily D-invariant.

Proof. Properties (1), ( 2) and (4) were proved in [START_REF] Lombardi | Constrained control for time-delay systems[END_REF]. The proof of properties (3) and ( 6) is straightforward. For the proof of property [START_REF] Santos | Stable mpc with reduced representation for linear systems with multiple input delays[END_REF], one can exploit the relationship:

A 1 Conv(P) ⊕ A 2 Conv(P) = Conv(A 1 P) ⊕ Conv(A 2 P) = Conv(A 1 P ⊕ A 2 P).
The first equality is a direct application of the convex hull definition and Minkowski sum properties.

For the second equality, let P 1 , P 2 ⊂ R n , and let x ∈ Conv(P 1 ⊕ P 2 ), then x = λ i (x i + y i ) with x i ∈ P 1 and y i ∈ P 2 , λ i ≥ 0 and

λ i = 1, then x = λ i x i + λ i y i ∈ Conv(P 1 ) ⊕ Conv(P 2 ). Suppose now that x ∈ Conv(P 1 ) ⊕ Conv(P 2 ) then x = λ i x i + β j y j ,with λ i = β j = 1
, and λ i , β j ≥ 0, x i ∈ P 1 , y j ∈ P 2 . since λ i β j = i,j λ i β j = 1 we can write x = i,j λ i β j (x i + y j ), then x ∈ Conv(P 1 ⊕ P 2 ). Note that

A 1 P ⊕A 2 P ⊂ P =⇒ Conv(A 1 P ⊕A 2 P) ⊂ Conv(P)
to conclude that:

A 1 Conv(P) ⊕ A 2 Conv(P) ⊂ Conv(P)
In order to check the property [START_REF] Olaru | Positive invariant sets for fault tolerant multisensor control schemes[END_REF], consider the system:

x(k+1) = 0.2 0.01 0 0.7 x(k)+ 0.6 0 0.005 0.25

x(k-1), (10) then the set

P 1 = x ∈ R 2 | -0.1 -1 ≤ x ≤ 0.1 1
is D-invariant as well as

P 2 = x ∈ R 2 | -1 -0.1 ≤ x ≤ 1 0.1
However, the set obtained as convex hull of the union P 1 P 2 , denoted P = Conv(P 1 , P 2 ), is not D-invariant.

Remark 1. Property (7) of Proposition 1 raises a warning on the convex hull operation applied to the union of two or more D-invariant sets, which is not a closed operation over the class of D-invariant sets. However, property (5) of Proposition 1 points out that for one D-invariant operand, the convex hull operation preserves D-invariance. It becomes clear that under the (unfortunately uncheckable) assumption that a D-invariant set exists, an efficient (convexity based) construction will be able to characterize it.

Remark 2. The property (4) of Proposition 1 holds also for the limit case τ i = ∞. As a consequence, if P ⊆ R n is a D-invariant set containing the origin, then P is positively invariant with respect to the time invariant linear dynamics:

x(k + 1) = A 0 x(k), . . . x(k + 1) = A d x(k). (11)
Equivalently, A 0 P ⊆ P, • • • , A d P ⊆ P. The same result holds for a dDDE represented by a partial sum of [START_REF] Blanchini | Set invariance in control[END_REF]. Note that the second property of Proposition 1 can be generalized. The intersection of a finite or infinite family of D-invariant sets is D-invariant.

The goal of the next subsections is to collect necessary and/or sufficient conditions for the existence of a D-invariant set for dDDEs. The existence of a nondegenerate and bounded D-invariant set1 is related to the stability of the discrete-time dynamical system (1) affected by delay. It is obvious that asymptotic stability is only a necessary condition for the existence of a D-contractive set and stricter conditions have to be imposed for guaranteeing this existence.

In the following we enumerate a series of necessary and/or sufficient conditions available in the literature, to the best of our knowledge; whenever possible, we will link the conditions to classical numerical routines for the eigenvalue problems. [44] Considering the system (1), the existence of a D-invariant C-set P implies that:

1. The spectral radii of the matrices A i are subunitary:

ρ(A i ) ≤ 1, ∀i ∈ Z [0,d] .
2. The spectral radius of the matrix

d i=0
A i is sub-unitary:

ρ d i=0 A i ≤ 1.
3. The spectral radius of the extended state-space matrix is sub-unitary:

ρ (A ξ ) ≤ 1.
Proposition 2 in conjunction with property (4) of Proposition 1 gives a measure of the complexity of establishing necessary and sufficient conditions. Practically, the difficulty is related to the need of testing the spectral radius of the extended state-space matrix for all possible delay realizations.

Alternative algebraic conditions

Alternative necessary conditions were proposed in [START_REF] Gielen | Set-induced stability results for delay difference equations[END_REF] in terms of asymptotic stability of dDDEs, for the existence of a D-contractive set. The main idea is to cover the possible sign combinations for the tuple A i , i ∈ Z [0,d] : a straightforward task for any value of the delay parameter. In order to simplify the notation, let us introduce the set S = {-1, 0, 1} and ∆

= [δ(0), • • • , δ(d)].
ρ d i=0 δ(i)A i ≤ 1, ∀∆ ∈ S d+1 . ( 12
)
If a given dDDE does not satisfy the above condition, then it does not admit a D-contractive set. [START_REF] Gielen | Set-induced stability results for delay difference equations[END_REF] shows that the condition derived in Proposition 3 is not sufficient for the existence of a D-contractive set, numerical examples being available in this sense.

3.1.3. Specific algebraic conditions for 2 delay dDDEs For dDDEs with two delay parameters, in order to decrease the conservativeness of the time-domain methods, [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF] has used the frequency-domain framework. The D-invariance concept was studied, along with its relation to robust asymptotic stability, considered as a strong stability of dDDEs. This notion defines stability with respect to all delay realizations. Due to the incompleteness of the discrete time, the characterization of robust asymptotic stability is not simple. Thus using a more general class of difference equation (precisely the ones that are specified in the continuous-time domain) proved to be useful. In the sequel the concept of strong stability is denoted by delay-independent stability2 and it represents the continuous-time counterpart to robust asymptotic stability.

Recently, [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF] has provided a computationally efficient numerical condition which is necessary to guarantee the existence of Lyapunov-Razumikhin contractive sets. This test is sufficient for the robust asymptotic stability with respect to the delay parameter and can be employed in the D-invariance context. The main result can be summarized in the next theorem. Theorem 4. [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF] Assume that ρ(A 0 + A 1 ) ≤ 1 and that d 0 ∈ R + and d 1 ∈ R + . Then, the system

x(k) = 1 i=0 A i x(k -d i ) ( 13
)
admits a D-contractive set only if γ(U, V ) ∩ ∂D = ∅, where

U = 0 n 2 ×n 2 I n 2 -B 0 -B 1 , V = I n 2 0 n 2 ×n 2 0 n 2 ×n 2 B 2 (14)
B 0 = A 0 ⊗ A T 1 , B 1 = A 0 ⊗ A T 0 + A 1 ⊗ A T 1 -I n 2 , B 2 = A 1 ⊗ A T 0 . (15)
As stated in [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF], the condition of Theorem 4 covers the existing necessary conditions for the two delay parameters case. However, we report here an interesting example which points out the possible limitations of this condition.

Example 1. [START_REF] Laraba | Set invariance for delay difference equations[END_REF] Consider system (1) with d = 1 and:

A 0 = 0.5 0.5 0 0 ; A 1 = 0 0.5 -0.5 0.5 [START_REF] Gu | Stability of timedelay systems[END_REF] For this numerical example, one can compute:

ρ(A 0 + A 1 ) = 0.8660 < 1
and γ(U, V ) = 1.7442 ± 1.9433i, 0.2558 ± 0.2850i, 0, 0, inf, inf.

The necessary condition by [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF] is fulfilled. However, up to the existing constructive routines (see next section) there is no numerical construction able to determine a D-invariant set for this system.

Sufficient conditions for D-invariance

The converse problem of establishing sufficient conditions for the existence of D-invariant sets has been stated in [START_REF] Lombardi | Constrained control for time-delay systems[END_REF] with two tests that we recall here for completeness. Proposition 4. [START_REF] Lombardi | Constrained control for time-delay systems[END_REF] The existence of a D-invariant C-set P is guaranteed for the system (1), if one of the following spectral norm based conditions holds:

1. The sum of the spectral norms of A i , for i ∈ Z [0,d] , is subunitary:

d i=0 σ(A i ) < 1.

In the case of nonsingular matrix

A i for i ∈ Z [0,d] (1 + σ(A -1 0 A 1 ) + • • • + σ(A -1 0 A d ))σ(A 0 ) ≤ 1 . . . (1 + σ(A -1 d A 0 ) + • • • + σ(A -1 d A d-1 ))σ(A d ) ≤ 1.
Remark 3. The sufficient condition (1) can be generalized by replacing the sum of the spectral norms by the sum of any other induced matrix norms.

Proposition 4 concentrates on the spectral norms of the matrices appearing in the dDDE [START_REF] Blanchini | Set invariance in control[END_REF]. A different approach for establishing sufficient conditions is to exploit the structural properties of specific classes of candidate D-invariant sets. We propose next a contribution in this sense with a sufficient condition for the existence of ellipsoidal D-contractive sets for a dDDE. As it is often the case in this framework, the tests are based on LMIs.

Theorem 5. Considering the dynamical system (1), the existence of an ellipsoidal D-invariant set is guaranteed if the following d + 1 LMIs hold for some P = P T ≻ 0:

     A T 0 P A 0 -P A T 0 P A 1 • • • A T 0 P A d A T 1 P A 0 A T 1 P A 1 • • • A T 1 P A d . . . . . . . . . . . . A T d P A 0 A T d P A 1 • • • A T d P A d      ≺ 0 (18a)      A T 0 P A 0 A T 0 P A 1 • • • A T 0 P A d A T 1 P A 0 A T 1 P A 1 -P • • • A T 1 P A d . . . . . . . . . . . . A T d P A 0 A T d P A 1 • • • A T d P A d      ≺ 0 (18b) . . .      A T 0 P A 0 A T 0 P A 1 • • • A T 0 P A d A T 1 P A 0 A T 1 P A 1 • • • A T 1 P A d . . . . . . . . . . . . A T d P A 0 A T d P A 1 • • • A T d P A d -P      ≺ 0 (18c)
Proof. In order to ensure that the set

Ψ = x ∈ R n , x T P x ≤ 1
is D-invariant for the system described by the dDDE (1), one has to show that x k+1 ∈ Ψ,

∀x k , x k-1 , • • • , x k-d ∈ Ψ
, which is equivalent to the simultaneous verification of the d + 1 inequalities:

x T k+1 P x k+1 -x T k P x k < 0 x T k+1 P x k+1 -x T k-1 P x k-1 < 0 . . . x T k+1 P x k+1 -x T k-d P x k-d < 0
Exploiting the dDDE relationship one has:

x T k+1 P x k+1 -x T k P x k = (A 0 x k + A 1 x k-1 + • • • + A d x k-d ) T P (A 0 x k + A 1 x k-1 + • • • + A d x k-d ) -x T k P x k = x T k (A T 0 P A 0 -P )x k + x T k A T 0 P (A 1 x k-1 + • • • + A d x k-d ) + (A 1 x k-1 + • • • + A d x k-d ) T P (A 0 x k + A 1 x k-1 + • • • + A d x k-d ) < 0.
and in the equivalent matrix formulation:

     x k x k-1 . . . x k-d      T      A T 0 P A0 -P A T 0 P A1 • • • A T 0 P A d A T 1 P A0 A T 1 P A1 • • • A T 1 P A d . . . . . . . . . . . . A T d P A0 A T d P A1 • • • A T d P A d           x k x k-1 . . . x k-d      ≺ 0 (20)
Analogously for the second inequality:

     x k x k-1 . . . x k-d      T      A T 0 P A0 A T 0 P A1 • • • A T 0 P A d A T 1 P A0 A T 1 P A1 -P • • • A T 1 P A d . . . . . . . . . . . . A T d P A0 A T d P A1 • • • A T d P A d           x k x k-1 . . . x k-d      ≺ 0 (21)
up to the d + 1 inequality. We can conclude that the existence of a positive definite matrix P = P T is a sufficient condition for the existence of an ellipsoidal D-invariant set, and the proof is complete.

Example 2. For illustration let us consider system (1) with only one delay parameter d = 1 and:

A 0 = 0.35 0.13 0.51 -0.01 , A 1 = 0.51 -0.01 0.03 0.51 . ( 22
)
The condition for the existence of a D-contractive set proposed in Theorem 5 is fulfilled and the Dcontractive set exists as shown in Figure 1. Dashed black lines in Figure 1 represent the state trajectories starting from some points on the boundary of the ellipsoidal D-contractive set with respect to the dDDE (1) with d = 1, A 0 , A 1 given in [START_REF] Samanta | Dynamic behaviour for a nonautonomous heroin epidemic model with time delay[END_REF]. It is interesting to note that the sufficient condition A 0 p + A 1 p ≤ 1 by [START_REF] Hennet | Stability conditions of constrained delay systems via positive invariance[END_REF][START_REF] Lombardi | On positive invariance for delay difference equations[END_REF] does not hold for this numerical example.

Necessary and sufficient algebraic conditions for

Polyhedral D-invariant sets The problem of finding convex D-invariant sets can benefit whenever particular structural properties are enforced. It is the case of polyhedral sets, for which necessary and sufficient conditions exist as resumed by the following theorem. Theorem 6. [START_REF] Hennet | Stability and stabilization of delay differential systems[END_REF] Let a delay difference equation be described by [START_REF] Blanchini | Set invariance in control[END_REF]. There exists P a polyhedral Dcontractive set containing the origin:

P = {x ∈ R n | F x ≤ 1} ( 23
)
with F ∈ R r×n , described by its minimal half space representation, if and only if there exist d + 1 real matrices H i ∈ R r×r , for i = {0, • • • , d}, with nonnegative elements and a positive ǫ < 1, such that:

F A i = H i F (24a) d i=0 H i 1 r ≤ ǫ1 r (24b)
Clearly, if the requirement on ǫ being strictly smaller than 1 relaxed to non-strict inequality, then [START_REF] Elaydi | An Introduction to Difference Equations[END_REF] represents a necessary and sufficient condition for the existence of a D-invariant set.

Relationship between D-invariance and dDDE stability In this subsection we aim at complementing the overview of the necessary and sufficient conditions with a theoretical result that establishes a link between the stability in presence of time-varying delay and the existence of D-invariant sets.

Theorem 7. The dDDE (2) admits a proper Dinvariant set if and only if the time-varying dDDE (3) is delay-independent stable.

Proof. We prove next the case of dDDE with only two delay parameters, x(k + 1) = A 0 x(kd 0 ) + A 1 x(k-d 1 ), the case of finite number of delays (2) being a direct generalization. The proof of the "only if" implication builds on the fact that the existence of a D-invariant set P is equivalent with the set inclusion:

A 0 P ⊕ A 1 P ⊂ P (25)
Thus for initial conditions x(k) ∈ P for k ∈ Z (-∞,0] one has x(1) ∈ P independent of the delay realization d 0 (0), d 1 (0) ∈ N. By induction, given a positive index i ∈ N, if x(k) ∈ P for k ∈ Z (-∞,i] then x(i + 1) ∈ P independent of the delay realization d 0 (i), d 1 (i) ∈ N which implies that the trajectories are bounded x(k) ∈ P, ∀k ∈ N + . Stability for any initial condition follows from property (1) of Proposition 1. By homogeneity, D-invariance is preserved by scaling and as such, there always exists a D-invariant set which contains a given initial condition of the dDDE.

For the "if" part of the proof, consider the initial conditions for the system (3) to be contained a compact set P containing the origin in its interior. Formally, the initial conditions and the time-varying delay realization can be described by the functions:

x - P : Z (-∞,0] → P d 0 : N + → Z (-∞,0] (26)
d 1 : N + → Z (-∞,0] (27)
Having as an objective the construction of the reachable set from P, let us denote the state at time instant k ∈ Z by x(k, x - P , d 0 , d 1 ) as the solution of (3) with respect to the initial conditions x - P and time-varying delay realizations d 0 (•), d 1 (•). With this notation, the reachable set from P via (3) is defined as:

R(P) = x ∈ R n | ∃k ∈ N + , x - P (•), d 0 (•), d 1 (•) s.t. x = x(k, x - P , d 0 , d 1 ) (28)
Coming back to the proof, the objective is to show that P r = P ∪ R(P) is a proper D-invariant set. The fact that the origin is contained in the interior of P r is inherited from the properties of P. The boundedness of the set R(P) is ensured by the stability assumption and will be inherited by P r . What remains to be proved is the invariance of P r . Three possibilities should be discussed:

• x(kd 0 (k)) ∈ P and x(kd 1 (k)) ∈ P: in this case the state x(k + 1) is part of the one step reachable set and subsequently x(k + 1) ∈ R(P) ⊂ P r .

• x(kd 0 (k)) ∈ P and x(kd 1 (k)) ∈ R(P) (with delay indices which can be interchanged): this case corresponds to a reachable state x(kd 1 (k)) ∈ R(P) combined with a large (pseudoinfinite) delay d 0 (k). By consequence the state realizations x(k + 1) will represent a subset of the reachable set and R(P) ⊂ P r .

• x(k -d 0 (k)) ∈ R(P) and x(k -d 1 (k)) ∈ R(P)
(with delay indices which can be interchanged): again, via reachability x(k + 1) ∈ R(P) ⊂ P r with the particular case d 0 (k) = d 1 (k) which deserves a special treatment. Indeed, for the re-

striction d 0 (k) = d 1 (k), the state dynamics (3) reduces to x(k + 1) = (A 0 + A 1 )x(k -d 1 (k))
. But this realization is only a particular case of the general time-varying delay realization

d 0 (k) = d 1 (k) for which x(k-d 0 (k)) = x(k-d 1 (k))
which is covered by the reachable set construction and the proof is complete.

Remark 4. The sets containing the forward trajectories, as those used in the argument of the proof, are non-convex and lead to computationally demanding constructions, from a practical point of view. In the next section we describe the corresponding algorithm and subsequently reinforce the convexity by exploiting property (5) of Proposition 1.

Construction of D-invariant sets based on set iterations

We address now the construction procedures for the case x(k + 1) = A 0 x(k) + A d x(kd) supposing that it admits a D-invariant set. The general form (1) follows similarly. We use the fact that existence of Dinvariant sets is exactly equivalent, by Lemma (3), to the verification of A 0 P ⊕ A d P ⊆ P. To simplify the explanation, we first define the forward mapping :

Φ : Com(R n ) → Com(R n ) Φ(P) = A 0 P ⊕ A d P (29)
and the mapping based on the union:

Ψ : Com(R n ) → Com(R n ) Ψ(P) = (P, Φ(P)). (30)
Note that even if P is convex, Ψ(P) is not necessarily convex.

Remark 5. We enumerate here some useful properties of the mappings defined in (29-30):

1. If a given set P (convex or not) is D-invariant for (1), then Φ(P) ⊆ P. 2. k-iterates over the family of sets is set-wise non decreasing (Ψ k-1 (P) ⊆ Ψ k (P), ∀k ≥ 1) with Ψ k (P) = Ψ(Ψ k-1 (P)) for k > 0 and Ψ 0 (P) = P. 3. If P is D-invariant for (1) then Φ k (P) is set-wise non increasing (Φ k (P) ⊆ Φ k-1 (P), ∀k ≥ 1) .

Basic set-iterates procedure for the construction of D-invariant sets

We describe in this part the basic steps of an iterative construction of D-invariant sets. Under the assumption that such an invariant set exists for the system (1), we can always scale it using property (1) of Proposition ( 1) such that it encompasses the initial set Q. Using the theoretical properties shown above, an algorithmic routine based on non-convex sets mapping is proposed for the computation of D-invariant sets with respect to (1). This algorithm considers as an input argument an arbitrary bounded set Q containing the origin ( [START_REF] Ziegler | Lectures on polytopes[END_REF][START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF]).

R 0 = Q; R 1 = Φ(Q) = A 0 Q ⊕ A d Q; i = 1; while R i ⊂ R i-1 do R i+1 = Ψ(R i ) = (R i , A 0 R i ⊕ A d R i ); i = i + 1; end Return R = R i (Alternatively, R = Conv(R i ) can represent the output if a unique convex set is needed.)
Convergence and finite determinedness analysis: First, it can be proved that Algorithm 1 constructs a non-decreasing sequence that converges to a D-invariant set. Indeed, the algorithm is based on the set mapping R i+1 = Ψ(R i ) which satisfies R i+1 ⊃ R i . Thus the sequence R i is non-decreasing in the sense of set inclusion. On the other hand, since the D-invariance is scalable (using property [START_REF] Blanchini | Set invariance in control[END_REF] of Proposition (1)), the hypothesis of existence of a D-invariant set P containing Q ensures Q ⊂ R i ⊂ P. Since any set R i provided by the algorithm is a subset of P, hence Ψ(R i ) is also a subset of P. In conclusion, the algorithm provides a sequence of sets R i which is non-decreasing by inclusion and limited from above by P. Hence the sequence admits a limit which is D-invariant (by the structure of the algorithm) and proper (because limited from above by P which is a fixed point with respect to the mapping Ψ(•)). Secondly, the finite determinedness can be formally proved. Given the (delay-independent) asymptotic stability of system (1) with matrices A 0 and A d , there exists a finite number of time steps t max such that the trajectories initiated in Q end up in P. The algorithm is collecting the trajectories initiated in Q, which is a subset of P, and thus t max represents an upper bound for the number of iterations. This completes the convergence analysis of the algorithm.

Note that the iterations and the limit set are nonconvex and this is related to the union operation performed by the mapping in Ψ(•).

Convex set-iterates procedure for the construction of D-invariant sets

We describe briefly in this part the main steps of an iterative construction of D-invariant sets while manipulating only convex sets. This algorithmic routine was proposed by [START_REF] Lombardi | On positive invariance for delay difference equations[END_REF], but we recall it here in light of Theorem 7 and Algorithm 1. Let us define the two mappings :

Ω : ComC(R n ) → ComC(R n ) Ω(P) = A 0 P ⊕ A d P (32)
Ξ :

ComC(R n ) → ComC(R n ) Ξ(P) = Conv(P, Ω(P)). ( 33
)
Given a convex set P ∈ ComC(R n ), the sequence Ξ k (P), k > 0 converges toward a convex D-invariant set [START_REF] Lombardi | On positive invariance for delay difference equations[END_REF]. The main objective of this procedure remains the same as the previous one: enlarge the set as much as possible with the Convex hull operation, while keeping it included in a D-invariant superset.

A 0 , A d ∈ R n×n Result: R Convex D-invariant set R 0 = Q; R 1 = Φ(Q) = A 0 Q ⊕ A d Q; i = 1; while R i ⊂ R i-1 do R i+1 = Ξ(R i ) = Conv(R i , A 0 R i ⊕ A d R i ); i = i + 1; end Return R = R i
This algorithm, unlike the previous one, manipulates convex sets with all their computational advantages. At each iteration, the convex hull of the union of the present set and the forward mapping of the same set R i are obtained.

Complexity and speed of convergence

In this section, we point to the possible extension of Algorithms 1-2 in order to improve the convergence speed. Instead of performing one forward mapping in each iteration before checking D-invariance, N forward mappings are performed in each iteration. This seems to be efficient in the sense that we can reduce the complexity and the number of iterations. (

-invariant set R 0 = Q; R 1 = Ω(Q) = A 0 Q ⊕ A d Q; Aux 1 = R 0 ; i = 1; while R i ⊂ R i-1 do for m = 1 : N do Aux m+1 = Φ(Aux m ) end Aux = [Aux 1 , Aux 2 , . . . , Aux N +1 ]; R i = Conv(Aux); R i+1 = Ω(R i ); i = i + 1; Aux 1 = R i ; end Return R = R i
) Let Q =        x ∈ R 2 |     √ 2 - √ 2 - √ 2 √ 2 √ 2 √ 2 - √ 2 - √ 2     x ≤     0.5 1 0.5 1            34
be the initialization set. By applying Algorithm 3 with N = 2 and Algorithm 2, two different Dinvariant sets are obtained for the dynamical system (34) in 2 * (N = 2) and 18 iterations, respectively. Figure 4 presents these sets. Dashed black lines represent the state trajectories starting from the vertices of these sets with respect to the dynamics [START_REF] Laraba | Invariant sets for discrete time-delay systems: Set factorization and state representation[END_REF]. It becomes clear that, under the assumption that a D-invariant set exists, an efficient construction exists. We can also use the algorithmic construction (Algorithm 2) as an induced tool to check if a Dinvariant set can/cannot be obtained, whenever the dDDE satisfies the necessary conditions for the existence of such invariant sets. To illustrate this idea, Example 1, which raises a doubt about the sufficiency of the matrix-pencil based conditions [START_REF] Stanković | Further remarks on asymptotic stability and set invariance for linear delay difference equations[END_REF], will be discussed in the sequel. By computing the set iterations up to strict inclusion into the initial one, convergence/divergence can be inferred. If the initial set Q for Algorithm 2 is the ∞-norm unit ball in R 2 and the dDDE is given by the matrices in Example 1, then after 4 iterations one obtains the sequence in Figure 5. The set iteration can be stopped as long as Q is a strict subset of P 4 . This represents a proof by construction that forward set iterations diverge and the system does not admit a D-invariant set. A pictorial overview of the relation between different kinds of stability and existence of D-invariant sets is given in Figure 6. Solid black lines represent implications that have been proved herein. Solid yellow lines represent previous results and dashed lines with question marks represent open problems. Dashed lines with a cross between two statements show that the first property does not necessarily imply the second.

Extensions of D-invariance

As mentioned in the introduction, two main approaches exist in the literature dealing with positive invariant sets for discrete time-delay difference equations; an invariant set for the dDDE can be computed either in an extended state space, or in the original state space (in this latter case, it is called D-invariant set). The concept of cyclic invariance [START_REF] Lombardi | Cyclic invariance for discrete time-delay systems[END_REF] can be exploited to compute, instead of a rigid set in (R n ) d+1 or R n as in the two aforementioned approaches, a tuple of invariant sets; thus offering a certain degree of flexibility. Definition 9. A (d + 1)-tuple of sets {Ω 0 , . . . , Ω d } is called cyclic D-invariant with respect to (1) if:

A 0 Ω 0 ⊕ A 1 Ω 1 ⊕ • • • ⊕ A d Ω d ⊆ Ω d ; A 0 Ω d ⊕ A 1 Ω 0 ⊕ • • • ⊕ A d Ω d-1 ⊆ Ω d-1 ;
. . .

A 0 Ω 1 ⊕ A 1 Ω 2 ⊕ • • • ⊕ A d Ω 0 ⊆ Ω 0 . (35)
A generalization of the cyclic invariance notion to invariant family of sets was proposed by [START_REF] Raković | Construction of invariant families of sets for linear systems with delay[END_REF][START_REF] Raković | Positively invariant families of sets for interconnected and time-delay discrete-time systems[END_REF].

Definition 10. A family of (d + 1)-tuples of sets F ⊂ n ) d+1 is an invariant family with respect to (1) if for any tuple {Ω 0 , Ω 1 , . . . , Ω d } ∈ F there exists a set Ω * ⊂ R n such that {Ω * , Ω 0 . . . , Ω d-1 } ∈ F and

A 0 Ω 0 ⊕ A 1 Ω 1 ⊕ • • • ⊕ A d Ω d ⊆ Ω * .
The link between the two main representations for discrete time-delay difference equations and their invariant sets has received recently a unifying characterization via set factorization [START_REF] Olaru | Low complexity invariant sets for time-delay systems: A set factorization approach[END_REF]. The reader is referred to this work for geometrical details on the Cartesian product of sets in relationship with positive invariance for time-delay systems.

Conclusion

This paper discusses positive invariance for discrete time-delay systems. Necessary and/or sufficient conditions for the existence of D-invariant sets have been gathered and discussed. The relationship between Dinvariance and stability has been studied for discrete delay difference equations (dDDEs). The construction of D-invariant sets via set iterations has been shown to benefit from set convexification, despite the fact that set forward mappings based on the original dDDE lead to a non-convex D-invariant set. has been member of editorial boards and organizing committees of international journals and conferences and he is currently member of the "IFAC Technical Committee on Robust Control" and Associate Editor for the IEEE Transactions on Automatic Control. His research results, developed in the areas of constrained control, l ∞ disturbance attenuation problems, gain scheduling control, uncertain production-distribution systems via set-valued techniques, and switching controllers, have been published in more than 80 international papers and an international book. Daniele Casagrande was born in Belluno, Italy, in 1973. He received the "Laurea" degree in electronic engineering in 1999 and the PhD in informa-

3. 1 .

 1 Necessary conditions for D-invariance 3.1.1. Basic algebraic conditions Proposition 2.

Proposition 3 .

 3 [START_REF] Gielen | Set-induced stability results for delay difference equations[END_REF] System (1) admits a Dcontractive set only if:

Figure 1 :

 1 Figure 1: D-contractive set for the dDDE (1) with d = 1, A0, A1 given in (22).

Algorithm 1 :

 1 Basic (non-convex) set-iterates procedure. Data: A bounded set Q ∈ R n containing the origin; the matrices A 0 , A d ∈ R n×n describing the system (1) Result: R a D-invariant set

Example 3 .

 3 [START_REF] Laraba | Set invariance for delay difference equations[END_REF] Let us consider the following dynamical system: the initialization set Q as the ∞-norm unit ball in R 2 . A non-convex D-invariant set is obtained iteratively by applying Algorithm 1 with 4 iterations.

Figure 2 :

 2 Figure 2: Graphical illustration of the non convex D-invariant set for the Example 3. The D-invariant set-green (left); the set A0P ⊕ A d P-red (right).

Figure 2

 2 Figure 2 presents this invariant set (the left one), and the image (the right one) of this set by the forward mapping Φ(•).Figure 3 presents the Convex

  Figure 2 presents this invariant set (the left one), and the image (the right one) of this set by the forward mapping Φ(•).Figure 3 presents the Convex

Figure 3 :

 3 Figure 3: Graphical illustration of the convex D-invariant set for the Example 3.

Algorithm 2 :

 2 Convex set-iterates converging to a D-invariant set. Data: A convex set Q ∈ R n containing the origin in the interior; the matrices

Algorithm 3 :

 3 Auxiliary set-iterates procedure. Data: A bounded convex set containing the origin Q ∈ R n ; the matrices A 0 , A d ∈ R n×n ; N the number of forward mappings in one iteration Result: R Convex D

Example 4 .

 4 [START_REF] Laraba | Set invariance for delay difference equations[END_REF] Let us consider the following dynamical system :

Figure 4 :

 4 Figure 4: Graphical illustration of D-invariant sets obtained by Algorithm 2 (left) and Algorithm 3 (right), for the Example 4.

Figure 5 :

 5 Figure 5: Sequence of the forward mappings Conv(P, A0P ⊕ A d P), for the Example 1.

Figure 6 :

 6 Figure 6: Schematic overview of the presented results.

  tion engineering in 2006, both from the University of Trieste, Italy. In 2006 he was research associate at the Institute of Cybernetics of the Tallinn University of Technology, Estonia. Between 2006 and 2007 he was research associate at the Department of Electrical, Electronic and Computer Engineering of the University of Trieste. In 2008 he was research associate at the Department of Electrical and Electronic Engineering of Imperial College London, UK. Since 2008 he is with the Department of Electrical, Managing and Mechanical Engineering of the University of Udine, Italy, where he is currently an assistant professor in optimization. His current research interests are focused on stability of switched system, Hamiltonian systems, LPV stability, nonlinear control and optimization.

It is easy to observe that sets like {0} or R n are D-invariant but they do not satisfy the non-degenerate or boundedness conditions.

also known as stability in the delays.

Acknowledgements

The research leading to these results has benefited from the financial support of the Franco-Italian collaborative research program Galileo 2014. The first three authors gratefully acknowledge financial support from the European Union's 7 th Framework Programme under EC-GA No. 607957 TEMPO -Training in Embedded Predictive Control and Optimization.


Wilawan Inchamnan
email: wilawan.inn@dpu.ac.th

Peta Wyeth
email: peta.wyeth@qut.edu.au

Daniel Johnson
email: dm.johnson@qut.edu.au

A Framework for Analyzing the Creative Potential of Computer Games

Keywords: Videogames, Creative gameplay, Behavioral analysis, Expert review

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The research described in this paper examines the impact that the design of a game has on the potential for that game to engage players in creative activity. Creative thinking is an important aspect of problem solving and a valuable skill to acquire. While existing research demonstrates the effectiveness of some games in facilitating creativity [START_REF] Catala | Exploring tabletops as an effective tool to foster creativity traits[END_REF], this study focuses on the impact that specific game elements (e.g., goals, actions) have on the creative problem solving processes that occur during gameplay. Assessing the creative potential of an experience requires a focus on how an individual responds to particular activities [START_REF] Kaufman | Finding creative potential on intelligence tests via divergent production[END_REF]. This research examines the activities provided within games though specific game elements and analyses how these activities may facilitate creative engagement. It identifies the key specific components of computer games that support creative activity. The outcome of the research is a set of guidelines that can aid game designers in the creation of games to facilitate people's creative thinking skills.

Background

Interactive experiences within a game environment allow people to express their creativity and intentions [START_REF] Sweetser | Player-centered game environments: Assessing player opinions, experiences, and issues[END_REF]. Research on creativity has resulted in multiple definitions, perspectives and models. For example, creativity has been defined to consist of at least four components: (1) the creative process, (2) the creative product, (3) the creative person, and (4) the creative situation [START_REF] Brown | Creativity[END_REF]. It has also been grouped using four definitions: product, person, press (the "press" of the environment), and process [START_REF] Santanen | Toward an understanding of creative solution generation[END_REF].

Our research concentrates on the creative process and, more specifically, the thinking processes employed during creative activity. The creative process is the result of sustained and complex mental effort over time [START_REF] Santanen | Toward an understanding of creative solution generation[END_REF] and consists of a step-by-step sequence of mental activities.

To identify the potential of games to engage players in creative processes, criteria related to activity undertaken need to be clearly understood. While we understand that games have great potential to support creative processes [START_REF] Paras | Game, motivation, and effective learning: An integrated model for educational game design[END_REF], it is not clear how we go about designing for creative activity. We know that creative ideas result from the novel combination of ideas [START_REF] Spearman | [END_REF], that creativity involves a process of convergent and divergent thinking [START_REF] Amabile | Creativity in Context[END_REF], and that critical thinking plays an important role [START_REF] Clark | Convergent and divergent thinking abilities of talented adolescents[END_REF]. To develop interactive experiences that incorporate these valuable, educative processes, we need a clearer understanding of how different game elements may be combined to produce creative potential.

A Creative Potential Game Design Model

The creative potential game design model is based on two distinct studies. The first study was designed to measure the creative processes that occur during gameplay [START_REF] Inchamnan | A method for measuring the creative potential of computer games[END_REF]. The conceptual method that was employed to assess creativity examined the extent to which factors that have been identified as playing an important role in creative processes -task motivation, domain-relevant skills and creativity-relevant skills -are present within gaming experiences. A behavioral and verbal protocol method that has been used previously to measure creativity in structure building activities, collage making and poem writing [START_REF] Ruscio | Looking inside the fishbowl of creativity: Verbal and behavioral predictors of creative performance[END_REF] was employed during this research. The study involved participants being observed while playing the three selected puzzle games: Portal 2, Braid and I-Fluid (Portal 2 is played from a first-person perspective and involves solving puzzles via the placement of portals within the environment; Braid is a platform style game that involves solving puzzles by manipulating time; and I-Fluid is a game where the player controls a drop of water and attempts to solve physics based puzzles). They played each game for 15 minutes. To examine the creative process, participants were video recorded while playing the games and a video coding scheme was used to capture the type and frequency of observable behaviors and participant verbalizations.

The second study [START_REF] Inchamnan | Behavioural Creative Components Analysis of Puzzle Gameplay[END_REF][START_REF] Inchamnan | Motivation during videogame play: analysing player experience in terms of cognitive action[END_REF] examined specific elements of the three games used in study 1 to determine which of these elements are important in fostering creativity. A heuristic checklist forms the basis of this study and experts used the items in this checklist to analyze each of the games. The items are structured into the categories identified as the key components of moment-to-moment gameplay. The three categories -identify goals, perform meaningful action and interpret outcome -map to a model of interaction that is based on cognitive processing. This model provides an important link between specific elements of games and creative problem solving activity. Fig. 1 provides an overview of the Creative Potential Game Design Model that links all of these concepts. To understand the interrelationship between gameplay and creative potential we have interpreted the results of the two studies that have been undertaken.

Analysis of the Play Experience

Our research has identified the extent to which each of the facilitating components of creative potential are present in each of puzzle games examined (Fig. 2). Results demonstrated that Portal 2 was best able to provide the task motivation and domain relevant skills necessary to engage in creative activity. Braid was the worst performer in both of these areas. Conversely, Braid was best able to provide the creativity relevant skills identified as important in creative processes and Portal 2 was least able to facilitate these skills. I-Fluid sat between Portal 2 and Braid for facilitating all three components. Our more detailed analysis indicated that while the games were similar in many respects in relation to their ability to facilitate creative activity, there were areas where differences were evident (Fig. 3). Portal 2 was able to support task motivation through providing a greater number of tools to solve problems, offering more opportunities for players to use and freely manipulate a range of objects and providing options for players to playfully explore the world in their own time. Players had the time and resources to plan their approach and refine solutions to problems. Braid and I-Fluid limited the number of actions available to players and there were fewer pathways available that would lead to success.

Fig. 2. Creative potential components for each game

A game's ability to facilitate domain-relevant skills centered on creating an environment that instilled confidence, providing clear pathways to complete tasks and ensuring that players understand the objectives they're trying to achieve. In the games that didn't perform as well on this component there were clearly times when players were uncertain about how the world would respond to their actions and how they could complete game objectives. Some of the challenges that arose for players related to difficulties working with objects and resources. From a creativity-relevant skills perspective our analysis indicates that overall frequency of players engaging in these types of activities were quite low. Areas identified as important in facilitating creativity-relevant skills included providing greater opportunities for players to take a wide focus when engaging in gameplay. This may be achieved through allowing activity that is future-oriented, letting players work through problems that require more than one step and facilitating interactions that enable players to develop their own goals. Problem solving needs to involve a player striving to achieve an outcome through overcoming challenging obstacles.

A tension has been identified between providing an experience that encourages striving (creativity-relevant skills) and producing gameplay where the player finds it straight-forward to understand what they are required to do and how they might go about doing it (domain-relevant skills). It appears that the ideal conditions for creativity are achieved within challenging environments where objectives are clear and consequences for exploration are positive. Given the focus within puzzle games on logical and conceptual challenges, experiences where players are able to develop their own goals or sub-goals is limited. Design for creativity involves opening up rule-sets, broadening the ways goals might be achieved and providing opportunities for nongoal directed behavior.

Analysis of Gameplay

The player's experience of the game derives directly from their interaction with the game environment and it is this environment that we analyze to determine where differences in creative activity occur. We apply the Seven Stages of Action [START_REF] Norman | User centered system design; new perspectives on human-computer interaction[END_REF], which details the process of executing and evaluating actions to achieve a particular goal, to moment-to-moment gameplay activity. Gameplay consists of the challenges and actions that a game offers the player and central to the experience is how the player addresses these challenges to achieve game objectives [START_REF] Adams | Fundamentals of Game Design[END_REF]. The three key components of game activity -goals and challenges, action and interaction, and interpretationcan be mapped to Norman's seven stages of action. Expert analysis of Portal 2, I-Fluid and Braid provides insight into how each game provides challenges that players must address to achieve goals, the effectiveness of the actions and interactivity available, and the quality the feedback presented so that players can assess their progress [START_REF] Inchamnan | Motivation during videogame play: analysing player experience in terms of cognitive action[END_REF].

To determine how the components of game activity influence creative potential we firstly examined the expert review of Portal 2. Given that Portal 2 performed well in the task motivation and domain-relevant skills categories for creative potential, it is useful to identify the game activity components in which it performed better than Braid and I-Fluid. Analysis demonstrated that Portal 2 most effectively provided mechanisms that allow the player to succeed at particular challenges. Expert review found that the game challenges effectively allowed for cognitive and logical thinking and strategic planning, that there were multiple types of challenges available that players could approach in their own way and at their own pace, the level of challenge was well matched to player skill level, and that narrative mechanisms guided challenges and supported progress towards goals. Portal 2 did well at offering players interesting options and choices, allowing the player to perform a range of actions to address a challenge and the story was particularly well integrated with the gameplay. The game actions provide a good sense of control over interactions and they allow players to feel that they have a significant impact on the game world. The review found that the interface to Portal 2 was easiest to learn, use and master and that the game had good input control. In terms of feedback, analysis of results demonstrated that Portal 2 performed well at providing output that allowed the player to assess the state of gameplay at any given time. The feedback mechanisms provided positive reinforcement which enhanced free-choice and self-awareness.

Fig. 4. Analysis of Game Activity Components for Creative Gameplay

Given that Braid performed slightly better than both I-Fluid and Portal 2 in terms of providing activities to support creativity-relevant skills, it is helpful to examine expert review data for its game activity components. Braid did well at supporting players in recovering from errors and at minimizing errors that are detrimental to gameplay. Compared to the other two games, Braid provides the most effective mechanisms for players to interpret the outcome of actions through mechanisms that give immediate and continuous feedback. Fig. 4 illustrates this analysis of game activity components and identifies areas of strength that may contribute to the ability of a game to facilitate creative activity.

Guidelines for Creating a Game with Creative Potential

As a first step towards producing guidelines that will aid in the development of games that facilitate creative problem solving, we have mapped game activity components (Fig. 4) to the mechanisms identified as facilitating creative potential (Fig. 3). These prelimary guidelines are outlined below, with the creative component facilitated included in brackets:

• Ensure that the game includes open-ended goals that allow players to develop their own sub-goals (wide focus, playful exploration) • Create narrative mechanisms that allow players to understand their progress towards achieving goals and that clearly link to choices in the game (understand what is required, clear pathways to complete tasks) • Create challenges that require logical thinking and strategic planning (complexity in problem solving, planning, refining problem solutions) • Ensure that there is variety in the type of challenges provided and that these challenges can be perceived and approached in different ways by players (wide focus, complexity in problem solving, facilitate striving activity, playful exploration, object use and manipulation, planning) • Implement challenges that develop at an appropriate pace and match a player's skill level (facilitate striving activity, environments that instill confidence) • Implement rules that offer freedom of choice, where players have options about actions to use to solve a problem (wide focus, object use and manipulation, planning) • Ensure that player actions have an impact on and shape the game world (wide focus, object use and manipulation, playful exploration) • Ensure that actions available to the player relate to the overarching story/setting of the game and that feedback makes sense within this context (understand what is required, clear pathways to complete tasks) • Manage player errors by allowing support for recovery from errors and ensuring that the impact is minimal (facilitate striving activity, environments that instill confidence) • Ensure that the player has a sense of control of interactions through creating a game interface that is easy to learn, use and master (environments that instill confidence) • Provide mechanisms that allow players to receive immediate and continuous feedback on their actions (environments that instill confidence, understand what is required, clear pathways to complete tasks, refining problem solutions) • Ensure that feedback provided to the player positively reinforces good choices and allows for free choice and self-awareness (facilitate striving activity, understand what is required, refining problem solutions)

Conclusion

In this paper we map the results of our analysis of players engaging in creative problem solving during puzzle game play to the expert review of the components of these games. We have used data to better understand how in-game activities influence a player's engagement in creative activity. We have developed preliminary guidelines that consider the specific ways we can align game goals and challenges, actions and interactivity and interpretation/feedback mechanisms to support creative problem solving processes. Future work will investigate the applicability of the Creative Potential Game Design Model across different game genres. Furthermore, the guidelines produced will be applied and evaluated in the development of a game to support creative activity.

6

Fig. 1 .

 1 Fig. 1. Creative Potential Game Design Model

Fig. 3 .

 3 Fig. 3. Identified Means of Facilitating Creative Potential

Acknowledgments

The authors would like to thank Games Research and Interaction Design Lab team, Queensland University of Technology for their support and cooperation during this study.


Simone Kriglstein
email: kriglstein@cvast.tuwien.ac.at

Ross Brown
email: r.brown@qut.edu.au

Günter Wallner
email: guenter.wallner@uni-ak.ac.at

Workflow Patterns as a Means to Model Task Succession in Games: A Preliminary Case Study

Keywords: Game Design, Design Tools, Workflow Patterns

Over the last decade, people involved in game development have noted the need for more formal models and tools to support the design phase of games. In this paper we present an initial investigation into whether workflow patterns -which have already proven to be effective for modeling business processes -are a suitable way to model task succession in games. Our preliminary results suggest that workflow patterns show promise in this regard, but some limitations, especially with regard to time constraints, currently restrict their potential.

Introduction

Over the last decade, people involved in game development have repeatedly voiced the need for more formal models and tools for designing games. The traditional, and still used, game design document, a detailed and mostly textual description of all aspects of a game design (cf. [START_REF] Almeida | A systematic review of game design methods and tools[END_REF]) has been criticized for several drawbacks. The design document is time-consuming to create, while at the same time being rarely read by members of the development team (see, e.g., [START_REF] Librande | One page designs[END_REF]) and needs constant maintenance to keep the information up-to-date with highly iterative game development processes (cf. [START_REF] Librande | One page designs[END_REF][START_REF] Dormans | Engineering Emergence: Applied Theory for Game Design[END_REF]). Kreimeier [START_REF] Kreimeier | Game design methods: A 2003 survey[END_REF], in a survey of game design methods, noted that the informal discussion of game design makes it difficult to put individual insight into a context of established knowledge. Therefore, formal visual languages have been proposed to more effectively express, abstract and communicate gameplay concepts or relationships between them (e.g., [START_REF] Librande | One page designs[END_REF][START_REF] Koster | A grammar of gameplay: game atoms: can games be diagrammed? Presentation at the Game Developers Conference[END_REF][START_REF] Bura | A game grammar[END_REF][START_REF] Cook | The chemistry of game design[END_REF]).

In a related context, Nelson and Mateas [START_REF] Nelson | A requirements analysis for videogame design support tools[END_REF] point out that game development lacks tools to visualize and reason about systems of game mechanics on an abstract level. However, game designers agree that prototyping is essential for verifying design ideas (cf. [START_REF] Almeida | A systematic review of game design methods and tools[END_REF][START_REF] Neil | Game design tools: Time to evaluate[END_REF]). Yet, prototyping can be a time-consuming and costly process. On that account, researches have therefore proposed prototyping tools to visually model and simulate different aspects of game design on an abstract level (see, e.g., [START_REF] Dormans | Engineering Emergence: Applied Theory for Game Design[END_REF][START_REF] Araújo | Modeling games with petri nets[END_REF][START_REF] Klint | Micro-machinations: A DSL for game economies[END_REF]).

In this paper we present an investigation into whether the widely supported workflow patterns [START_REF] Van Der Aalst | Workflow patterns[END_REF] are a suitable way to model the succession of tasks players have to perform in a game. In a similar manner to Van Der Aalst et al. [START_REF] Van Der Aalst | Workflow patterns[END_REF], we have sought to use a pattern analysis approach to identifying recurring structures within lists of activities performed by players in computer games. Such a pattern approach provides independence from the underlying game implementation environments, and the underlying theoretical languages used to describe such flows of activities. A workflow patterns approach enables us to specify abstractly the tasks to be performed by players within game environments, as the tasks given to players may share similarities in structure to tasks in business systems. The future benefits of such an approach are thus the ability to define such gameplay activity patterns in a rigorous and formal manner (drawing from the Petri net formalisms of workflow patterns) giving us both the power to deeply analyze their correct execution, and then execute them in Petri net based systems.

Related Work

To date a lot of work has been conducted to establish a common design vocabulary, for instance, in the form of design patterns used to express clearly intentions, analyses, and opinions regarding gameplay [START_REF] Björk | Game design patterns 2.0[END_REF].

While design patterns are usually expressed in natural language, some game researchers have argued for more visual models to more clearly and compactly express and communicate ideas about game design (see the recent survey of Almeida and Silva [START_REF] Almeida | A systematic review of game design methods and tools[END_REF] for a discussion on this subject). For example, Koster [START_REF] Koster | A grammar of gameplay: game atoms: can games be diagrammed? Presentation at the Game Developers Conference[END_REF] presented a graphical notation system as a complement to classic game design documents to better communicate the game design. Bura [START_REF] Bura | A game grammar[END_REF], building upon the work of Koster [START_REF] Koster | A grammar of gameplay: game atoms: can games be diagrammed? Presentation at the Game Developers Conference[END_REF], proposed a visual grammar which was influenced by Petri nets resembling data-flow representations of processes (whereas we are concerned with a control-flow perspective). Araújo and Roque [START_REF] Araújo | Modeling games with petri nets[END_REF] also applied Petri nets to model games and emphasized that the formal semantics of Petri nets can be leveraged to formally analyze and simulate game design elements already in an early design stage (e.g., to detect unwanted behavior).

Recently, Dormans [START_REF] Dormans | Engineering Emergence: Applied Theory for Game Design[END_REF] developed the Machinations tool, a graphical notation framework to express the rules of and simulate game economies in order to balance a game's economy or to prevent dominant strategies. While borrowing concepts from Petri nets, Machinations diagrams are aimed to be less complex and more accessible to designers. The work has been later extended by Klint and van Rozen [START_REF] Klint | Micro-machinations: A DSL for game economies[END_REF] to allow not only for simulation but also for formal analysis of game designs. While the above mentioned works aim at expressing game mechanics, Cook [START_REF] Cook | The chemistry of game design[END_REF] focused on the player experience and proposed skill chain diagrams to visually represent how players learn and acquire skills.

Workflow software technology has been applied to games by Brown et al. [START_REF] Brown | Gameplay workflow: A distributed game control approach[END_REF] who used a workflow language to script game tasks.

Use Cases

For our initial investigation we have chosen two gameplay distinct action games, Need for Speed: The Run and Half Life 2.

Need For Speed: The Run (NFS): NFS is an action racer where the player takes part in a race across the US. The complete race is broken down into stages with each stage again divided into different race events. These events can roughly be divided into: a) checkpoint races, b) sprint races, c) rival races, and d) battle races. In case of a checkpoint race, a sequence of checkpoints has to be crossed. In workflow terms this can be described with a Sequence pattern (Workflow Pattern #1 [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF]). This is illustrated in Fig. 1a.

A bit more complex is the workflow pattern for the sprint race event (see Fig. 1b), where the player has to overtake a number of opponents and to cross the goal line in first position. The task to overtake multiple opponents can be described as a cycle that repeats until the player is on the first place (WP #10 -Arbitrary Cycles [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF]). However, overtaking all opponents and reaching the first place is not enough to win the race, the player also has to maintain the lead until the goal line is reached. This is modeled with a second arbitrary cycle. The Simple Merge pattern (WP #5 [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF]) is used to merge the outgoing branch of the Overtake Opponent node and the false branch of the second arbitrary cycle.

The rival race event is technically the same as the sprint race event except that the player has to race against specific drivers that are part of the storyline. It can therefore be modeled the same way as the sprint race.

The battle race is a slight modification of the sprint race, where the player has to overtake an opponent and keep the lead until a checkpoint is reached after which the player races against another opponent until the next checkpoint. This repeats several times during a single battle race. The basic structure of the workflow pattern for a battle race event is therefore similar to the workflow pattern for a speed/rival race event with the difference that it repeats several times in sequential order (see Fig. 1c).

Half Life 2 (HL2): HL2 is a single player first-person shooter (FPS). Like a number of first person shooters, you acquire weapons and health packs in order to defeat non-player characters (NPCs) and traverse levels. Analysis of the levels in the game indicate a number of workflow patterns. First of all, entrance to a level triggers instancing of gameplay tasks (WP #6 -Multi-Choice [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF] in combination with WP #8 -Multi-Merge [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF]). We group these into three major task types, viz. Kill Agents, Use Resources, Open Doors (see Fig. 2). Kill Agents is the destruction, by whatever means, of other agents in the game. Open Door tasks are a general description of having to remove a physical impediment to progress spatially, for example, opening a door, destroying an oil drum, or killing a blocking NPC. These sequences are embedded within a set of multiple tasks that may be ignored. For example, you do not have to kill all agents to progress through a level. This killing of agents and collection of resources is often up to the discretion of the player. A subset of the tasks require a certain sequence (WP #1 [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF]) for them to be completed.

In the level Routekanal1 there are certain sequences that must be performed before progression can occur. For example, you clear out an area of NPCs with a mounted machine gun (Kill Agents) and come to an oil drum that has to be destroyed (Open Door) before you can traverse to the next location and enter a tunnel. Note, it is possible to avoid shooting the NPCs if you are skilled enough in traversal, but you must shoot the oil drum. Therefore, this is an example of an enforced sequence within multi-choices. Once the level is traversed, a final door opening task is completed to exit the level; left over tasks are removed from the list allocated to the player. You cannot go back to the level to finish the other remaining tasks, you must recommence the level in order to begin again, or, you must go to a save point in the game to recommence the level at the same state. This is an example of the Canceling Discriminator pattern (WP #29 [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF]).

Combining these four workflow patterns together, we construct an overall FPS workflow pattern shown in Fig. 3 (left). We argue that this pattern, in slight variations, forms the structure of a number of FPS games. Thus designs for other FPS games can be configured from an executable form of such a pattern.

In addition, there is further detail in the tasks being performed in the cancellation region. In a similar manner, such tasks may be devolved into a split upon opening a door and entering a region of a level. We define that a level is broken up into regions of gameplay, with door opening choke points, that enforce a sequence, but contain within them multi-choices and merging, as per Fig. 3 (right). Note that this pattern has no cancellation upon entering a new region. So the tasks in the split can be circumvented at the discretion of the player.

Discussion

In the presented use cases we focused on the description of the succession of tasks which players have to perform to successfully complete a level, but we did not consider implications of failure. However, modeling the consequences of failing a task can be equally important in game design (e.g., what happens if a checkpoint in a racing game is not reached). Workflow patterns may also be suitable for this task, for example, the WP #4 -Exclusive Choice [START_REF]Workflow Patterns Initiative: Control-flow patterns[END_REF] can be used to describe branching depending on if the previous tasks were completed successfully or not.

Workflow patterns can be used to describe tasks on different levels of abstraction (e.g., opening a door could be described simply as Open Door or in more detail by modeling what actions are necessary to actually open it, for instance, Pull Lever followed by Turn Knob). Furthermore, a combination of the different abstraction levels can be used, for example, to provide a high-level overview with more detailed descriptions on demand.

One of the biggest limitations of the original control flow workflow patterns [START_REF] Van Der Aalst | Workflow patterns[END_REF] for modeling task succession is perhaps their limited support of time aspects, e.g., time spans or timeouts. However, time aspects play a very important role in games. For example, in the above NFS use case the player has to reach the checkpoints within a predefined time limit. Future work can focus on analyzing how new time-based patterns (e.g., [START_REF] Niculae | Time patterns in workflow management systems[END_REF]) can be used to describe time critical game tasks.

Conclusions

In this paper we investigated the applicability of workflow patterns for modeling task succession in games. For this purpose we have chosen two different games as initial case studies. Our first results suggest that workflow patterns show some promise, but that there are also some limitations that currently constrain their potential in regard to games and which need further investigation, in particular, the ability to model winning and losing conditions and time aspects. Further case studies will be necessary to confirm our preliminary observations.

Fig. 1 .

 1 Fig. 1. The general three workflow patterns for the four main race events of NFS illustrated using the BPMN 2.0 visual grammar [15]: a) Pattern for checkpoint race event, b) pattern for sprint and for rival race event, and c) pattern for battle race event.

Fig. 2 .

 2 Fig. 2. Examples of the major tasks performed in an FPS -from left to right: Kill Agent, Use Resources (ammunition, healing items) and Open Door.

Fig. 3 .

 3 Fig. 3. Left: General FPS workflow pattern for HL2. Right: Exploded BPMN view of tasks in the left image, illustrating how the door opening tasks are key to enforcing particular orderings of tasks in HL2 as an FPS.