Oscar Chavoya Aceves
email: chavoyao@gmail.com

A classical non linear unified field theory

A classical electromagnetic covariant non linear theory of matter is formulated where electric four-current and the total stress-energy tensor are local functions of Faraday's tensor and its derivatives. General covariance is immediate, resulting in a classical unified field theory. If the Lagrangian density is an analytic function of Faraday's tensor and Lorentz invariance corresponds to reality, this theory must be true in the low energy limit.

Introduction

Since the discovery of Coulomb's Law-in fact, since the time Newton successfully presented Kepler's laws as logical consequences of his Universal Law of Gravitation-there was a concern among physicists that the concept of action at a distance was incompatible with that of space as a scenario of physical reality.

According to original atomistic ideas, there is nothing in the physical world but atoms and the void, which is immaterial or not a thing. This raised the objection that nothing cannot be the link between action-reaction pairs of forces. If space in itself is nothing, then an electric charge should, in some way, be aware or know of the presence and position of other electric charges in its neighborhood and figure out how to move, which is untenable. This problem was in part addressed with the introduction of the electric and magnetic fields, by Faraday, which was the starting point of Maxwell's synthesis of an electromagnetic theory.

The theoretical discovery of electromagnetic waves, confirmed by Hertz's experiments, brought up the problem of the system of reference, which was solved by Einstein in 1905, providing a unified description of electric and magnetic fields in terms of Faraday's tensor-which explains not only our failure to detect the motion of earth through the ether, but the fact that we have not observed magnetic mono-poles. However, as Einstein pointed out, the problem of the nature of electric charges remained unsolved.

Our current understanding of the structure of matter involves the concept of electric charge which appears as a physical constant (the electronic charge e) characterizing the interaction of particles and the electromagnetic field. There is an objective difference between positive and negative electric charges as it is evident when we consider that they produce different effects. If electric charges exist independently of the electromagnetic field they produce, this creates some logical difficulties. If positive and negative charges are objectively different they must be different in nature and, therefore, there must exist at least two kinds of substance, corresponding to the two kinds of electricity, a situation which is complicated by the existence of anti-particles like positrons, anti-protons, and other kinds of matter. In addition, the way electric charges are tied to the electromagnetic field they produce remains a mystery. In Einstein's words [1, p. 49] "Maxwell's equations determine the electromagnetic field when the distribution of electric charges and currents is known. But we do not know the laws which govern the currents and charges. We do know, indeed, that electricity consists of elementary particles (electrons, positive nuclei), but from a theoretical point of view we cannot comprehend this. We do not know the energy factors which determine the distribution of electricity in particles of definite size and charge, and all attempts to complete the theory in this direction have failed."

We go a step further: the equations of electromagnetism in a vacuum as they are written in [2, pp. 71 & 79]

∂F ik ∂x l + ∂F kl ∂x i + ∂F li ∂x k = 0, (1)
∂F ik ∂x k = - 4π c j i . (2)
do not include any provision to preclude a four-current for which the material speed of electricity is superluminal.

To illustrate our claim we consider a time dependent one-dimensional density

ρ(x, t) = Q πa cos 2 (σt) 1 + x+b a 2 + sin 2 (σt) 1 + x-b a 2 (3)
For this argument we assume that x and t are measured in the same units, in such manner that c = 1. We also assume that σ > 0, a > 0 and b > 0 are constants.

∞ -∞ ρ(x, t)dx = Q πa ∞ -∞ cos 2 (σt) 1 + x+b a 2 dx + Q πa ∞ -∞ sin 2 (σt) 1 + x-b a 2 dx = Q From the continuity equation ∂ρ ∂t + ∂jx ∂x = 0 or ∂jx ∂x = -∂ρ ∂t ∂j x ∂x = σ sin(2σt)Q πa 1 1 + x+b a 2 - 1 1 + x-b a 2 (4)
we get

j x = σ sin(2σt)Q π tan -1 x + b a -tan -1 x -b a (5)
Using the functions (3) and ( 5) we can define a four-dimensional current with the components: (ρ(x, t)δ(y)δ(z), j x (x, t)δ(y)δ(z), 0, 0) and then, in principle, solve Maxwell's equations. However, the solution will not always correspond to a physical field, not even disregarding the idealization of a linear distribution of charge.

The material velocity of the density of charge at point x is:

v x (x, t) = j x ρ = σa sin(2σt) tan -1 x+b a -tan -1 x-b a cos 2 (σt) 1+( x+b a ) 2 + sin 2 (σt) 1+( x-b a ) 2 (6)
In particular, we have

v x (b, t) = σa sin(2σt) tan -1 (2) cos 2 (σt)/5 + sin 2 (σt)
The maximum value of this function of time is positive and proportional to σa which means that, by increasing σ, a, or both, we can have superluminal material speed of electric charge at x = b which is incompatible with the principle of relativity and the assumption that electric charge is an attribute of material particles. In principle if we consider this four-current density as a four-dimensional vector and transform it accordingly, the continuity equation [2, p. 65] ∂j i ∂x i = 0 is covariant and, by solving equations (1) and (2) we can find the corresponding configuration of electromagnetic field. The Lorentz' force law

mc dµ i ds = q c F ik µ k where µ i = dx i ds (7)
will allow us to find out how an electric charge moves under the action of the corresponding electromagnetic forces. Nevertheless, the whole solution is no more than a mathematical artifact with no physical interpretation compatible with the most fundamental assumptions of special relativity. Maxwell's theory of electromagnetism ascribes a density of energy and momentum to the electromagnetic field. This, the fact highlighted by Einstein, that matter is made of charged particles (electrons and nuclei), and our prior arguments clearly suggest that there is a need to make an effort to "complete the theory in this direction." If electrons are treated as point particles there is the problem of infinite self-energy. On the other side, if an electron is considered as a density of charge inside a finite region of space-which is what Lorentz did in an early attempt to formulate a theory of electrons that could be used to explain the optical and electro-magnetic properties of the different kinds of ordinary matter [3, p. 14]-there are problems to define the motion and therefore the acceleration of an electron as a whole in space [1, p. 47]. Equation 7 is covariant and the problem of defining the world line that represents the motion of a mechanical system as a whole in space has not a satisfactory covariant solution in the domain of special relativity. [START_REF] Dirac | A new classical theory of electrons[END_REF] This world-line is defined in classical mechanics in such manner that it makes the whole theory logically consistent because in classical mechanics time-and simultaneity-is treated as universal and absolute. For the definition of the center of mass of a system of particles in classical mechanics, the simultaneous positions of the parts of the system are considered.

In this paper an attempt is made to generalize Maxwell's theory in empty space, which is a linear theory, including non-linear terms in Farady's tensor and its derivatives, to account for electric currents.

Though "we do not know the laws which govern the currents and charges," we will see that we can advance a reasonable hypothesis on the relation between electromagnetic field and charge & current densities. The concept of particle does not play a fundamental role in this theory and therefore there is no place for a wave-particle duality. Nevertheless, quantization is not discussed.

Action of the field in a vacuum

Maxwell's equations in a vacuum-in the absence of any electric charges-are equivalent to the necessary extreme condition (δS = 0) for the action

S = - 1 16πc Ω F ik F ik dΩ ( 8
)
where Ω is a region of space-time [2, p. 75] and F ij is Faraday's tensor

F ij = ∂A j ∂x i - ∂A i ∂x j (9)
From the expressions for the fields E and H in terms of the electrodynamic potentials [2, p. 65]

F ik =     0 E x E y E z -E x 0 -H z H y -E y H z 0 -H x -E z -Hy -H x 0     , F ik =     0 -E x -E y -E z E x 0 -H z H y E y H z 0 -H x E z -Hy H x 0     (10) The first variation is δS = - 1 8πc Ω F ik δF ik dΩ δS = 1 8πc Ω F ik ∂δA i ∂x k - ∂δA k ∂x i dΩ = 1 4πc Ω F ik ∂δA i ∂x k dΩ
from this it is not difficult to derive the condition

∂F ik ∂x k = 0, (11)
which is equivalent to the second pair of Maxwell's equations in a vacuum. The first pair of Maxwell's equations is obtained from the definition of Faraday's tensor [START_REF] Ketov | Born-infeld non-linear electrodynamics and string theory[END_REF]:

∂F ij ∂x k + ∂F jk ∂x i + ∂F ki ∂x j = 0. ( 12
)
In fact, from the well known relations between the electrodynamic potentials and the electric and magnetic field

E = -∇A 0 - 1 c ∂A ∂t and H = ∇ × A it is easily proved that ∇ × E = - 1 c ∂H ∂t and ∇ • H = 0.
Those equations are the three-dimensional version of (12), while (11) can be written as

∇ • E = 0 and ∇ × H = 1 c ∂E ∂t .
In the presence of an electric current j i equations (11) are replaced by [START_REF] Landau | The classical theory of fields[END_REF].

In [START_REF] Dirac | A new classical theory of electrons[END_REF] Dirac proposed to break the gauge invariance including a term in the lagrangian by imposing an additional condition on the electrodynamic potentials:

A k A k = κ 2
, where κ 2 is a constant. This lead him to the action

S = Ω - 1 16πc F ik F ik + λ A k A k -κ 2 dΩ (13)
including a Lagrangian multiplier λ(x i ). The first variation leads to the equations:

∂F ik ∂x k = - 4πλ c A i (14) A k A k = κ 2 Using (14) λ = - c 4πκ 2 A j ∂F jk ∂x k and then ∂F ik ∂x k = 1 κ ∂F jk ∂x k A i A j (15)
Introducing the condition A k A k = κ 2 is unjustified but for the fact that it allows to achieve the desired goal of establishing an hypothetical connection between current density and field components. Otherwise it is not backed up by any physical or mathematical arguments. Dirac himself, after a remark by Gabor, abandoned this specific formulation of his ideas improving his model in two papers [START_REF] Dirac | A new classical theory of electrons ii[END_REF] [START_REF] Dirac | A new classical theory of electrons iii[END_REF]. Then, in 1962, he published another paper [START_REF] Dirac | An extensible model of an electron[END_REF] where he presented a model of the electron as a charged surface-which is essentially a variation of the idea behind classical string theories-in an attempt to explain muons as excited states of electrons. Those are, as we said, mathematical models and not fundamental theories. The introduction of strings or surfaces is justified only because those models provide extra degrees of freedom that can be used to accommodate excited states and, therefore, a variety of particles.

Dirac's approach, however provides some insight. We notice that the left side of Maxwell's equations comes from the quadratic term in the integral (13). If we assume that the Lagrangian density is an analytic function of the field intensities-Faraday's tensor (F) expressed in terms of the electrodynamic potentials-the action integral is written as

S = Ω L(F)dΩ where L(F) = L 0 + ∂L ∂F i0i1 F i0i1 + 1 2 ∂ 2 L ∂F i0i1 ∂F i2i3 F i0i1 F i2i3 + • • •
Considering that L must be a scalar and explicitly independent of position in space-time, the first not trivial term in this series is the second-order term. The action of Maxwell's electromagnetic field in a vacuum is obtained if all terms of higher order are neglected.

The coefficient

C i0i1i2i3 = 1 2 ∂ 2 L ∂F i0i1 ∂F i2i3
can only be a linear combination of the three fourth-rank independent isotropic tensors

C i0i1i2i3 = λ • δ i0i1 δ i2i3 + µ • δ i0i2 δ i1i3 + ν • δ i0i3 δ i1i2
Given that δ i0i1 δ i2i3 F i0i1 F i2i3 = 0, the last equation can be simplified to

C i0i1i2i3 = µ • δ i0i2 δ i1i3 + ν • δ i0i3 δ i1i2 Next δ i0i2 δ i1i3 F i0i1 F i2i3 = F i0i1 F i0i1 and δ i0i3 δ i1i2 F i0i1 F i2i3 F i0i1 F i1i0 = -F i0i1 F i0i1 . In consequence: C i0i1i2i3 = (µ -ν)F i0i1 F i0i1 ∝ F i0i1 F i0i1 , as announced.
The third-order coefficient (C i0i1i2i3i4i5 ) can only be a linear combination of the following sixth-rank isotropic tensors [START_REF] Kearsley | Linearly independent sets of isotropic cartesian tensors of ranks up to eight[END_REF]:

δ i0i1 δ i2i3 δ i4i5 , δ i0i1 δ i2i4 δ i3i5 , δ i0i1 δ i2i5 δ i3i4 , δ i0i2 δ i1i3 δ i4i5 , δ i0i2 δ i1i4 δ i3i5 δ i0i2 δ i1i5 δ i3i4 , δ i0i3 δ i1i2 δ i4i5 , δ i0i3 δ i1i4 δ i2i5 , δ i0i3 δ i1i5 δ i2i4 , δ i0i4 δ i1i2 δ i3i5 δ i0i4 δ i1i3 δ i2i5 , δ i0i4 δ i1i5 δ i2i3 , δ i0i5 δ i1i2 δ i3i4 , δ i0i5 δ i1i3 δ i2i4 , δ i0i5 δ i1i4 δ i2i3
The terms including δ i0i1 , δ i2i3 , and δ i4i5 do not make any contribution to the sum C i0i1i2i3i4i5 F i0i1 F i2i3 F i4i5 -because Faraday's tensor is antisymmetric. Each one of the remaining terms

δ i0i2 δ i1i4 δ i3i5 F i0i1 F i2i3 F i4i5 , δ i0i2 δ i1i5 δ i3i4 F i0i1 F i2i3 F i4i5 , δ i0i3 δ i1i4 δ i2i5 F i0i1 F i2i3 F i4i5 , δ i0i3 δ i1i5 δ i2i4 F i0i1 F i2i3 F i4i5 δ i0i4 δ i1i2 δ i3i5 F i0i1 F i2i3 F i4i5 , δ i0i4 δ i1i3 δ i2i5 F i0i1 F i2i3 F i4i5 , δ i0i5 δ i1i2 δ i3i4 F i0i1 F i2i3 F i4i5 , δ i0i5 δ i1i3 δ i2i4 F i0i1 F i2i3 F i4i5 can be reduced to ±δ i0i4 F i0i1 F i1i2 F i3i4 . Also F jb F bc F ci = -F jb F cb F ci = -F ic F cb F bj = -F ib F bc F cj Thus, the tensor Π ij = F ib F bc F cj (16) is antisymmetric, δ i0i4 F i0i1 F i1i2 F i3i4 ≡ 0, and
C i0i1i2i3i4i5 F i0i1 F i2i3 F i4i5 ≡ 0.
Therefore, the next term to consider is the fourth-order term. To determine the coefficient C i0i1i2i3i4i5 we have to consider 105 isotropic tensors that are products of four Kronecker Delta tensors and 35 that are products of two Levi-Civita tensors-this set is not linearly independent. (See the Appendix.) Direct computation shows that the fourth-order term can only be a linear combination of

F ab F ab 2 , F a b F b c F c d F d a , F ⋆ ab F ab 2 , F ⋆ ab F bc F ⋆ cd F da ǫ abcd F ae F bf F cg F dh ǫ ef gh
where F ⋆ ab = 1 2 ǫ abcd F cd , F ⋆ab = 1 2 ǫ abcd F cd is the dual of Faraday's tensor:

F ⋆ ik =     0 -H x -H y -H z H x 0 -E z E y H y E z 0 -E x H z -E y E x 0     , F ⋆ik =     0 H x H y H z -H x 0 -E z E y -H y E z 0 -E x -H z -E y E x 0    
(17) The corresponding-approximated-lagrangian density has the form

L 4 = - 1 16πc F ab F ab + α 2 F ab F ab 2 - β 2 F a b F b c F c d F d a (18) + κ F ⋆ ab F ab 2 -2λF ⋆ ab F bc F ⋆ cd F da + σ 2 ǫ abcd F ae F bf F cg F dh ǫ ef gh
where α, β, κ, λ, and σ are constants. Note that our argument is a paraphrase of the argument used in classical mechanics to study the general properties of the simple harmonic oscillator, irrespective of the nature of the mechanical system. Therefore, thought this model depends on unknown constants, our assumptions are essentially more physical than Dirac's purely mathematical ideas. We assume that:

1. The electromagnetic field F ij is an autonomous dynamical system.

2. Its dynamical laws obey the principle of relativity.

3. Those laws can be obtained from the principle of minimum action, using a Lagrangian density that is an analytic function of Faraday's tensor.

If those assumptions correspond to reality, then this is a sound non-linear generalization of Maxwell's linear theory.

In addition, as it is well known from classical field theory, a three-dimensional vector field f can be represented in the form

f = -∇φ + ∇ × A (19)
where the fields φ and A can be determined from ∇ • f and ∇ × f . From this we find it interesting, at least, that Maxwell's equations (precisely) determine the divergence and the curl of the fields E and H, and we ask ourselves if, in some way, those equations are not necessary consequences of a fundamental law. Accordingly, we consider the problem of approximating a vector field f in a region Ω by the gradient of a scalar potential g = ∇φ. As a measure of proximity we use the quadratic norm (with the classical euclidean norm) and we pose a variational problem

δ Ω 1 2 (f i -g i ) 2 -φ ij (g i,j ) dω = 0
where φ ij = -φ ji are some Lagrange multipliers (we must have g i,j -g j,i ≡ 0). The corresponding Euler-Lagrange equations are

f i = g i + ∂φ ij ∂x j
We notice that

∂f i ∂x i = ∂g i ∂x i
and, if ∂f i ∂x i = 0 then g i can be chosen zero and

∂φ ij ∂x j = f i
which has the form of the second pair of Maxwell equations-regardless of the dimension of the space under consideration and/or the specific metric. Thus, from the assumption that electric charge is conserved ∂j i ∂x i = 0 it follows that there is a field with the properties of the Faraday tensor field.

In addition, if x a (τ ) is the worldline of a particle-τ is the corresponding proper time-then µ a µ a = 1, where

µ a = dx a dτ
is the fourvelocity. This means that for any specific worldline we can always write dµ a dτ ∝ φ ij (τ )µ j where φ ij (τ ) is an antisymmetric tensor field defined along the world-line. The last equation is exactly of the form of the Lorentz force. At the said fourth order, the Born-Infeld lagrangian[9]

L = 1 b 2 1 --det (g ij + bF ij )
as well as the lagrangian

L = -T -det (g ij + 2παF ij )
which is used in open strings theory, are particular cases of (18) in the corresponding limit (fourth order in the field intensities).

To facilitate obtaining the Euler-Lagrange equations and the canonical stressenergy tensor we first notice that

δ F ab F ab = 2F ab δF ab = 2F ab (δA b,a -δA a,b ) = -4F ab δA a,b where A a,b = ∂Aa ∂x b ; δ F ab F ab 2 = 2F cd F cd δ F ab F ab = -8F cd F cd F ab δA a,b ; δ F a b F b c F c d F d a = 4F bc F cd F da δF ab = -4F ac F cd F db δF ab -4F ac F cd F db (δA b,a -δA a,b ) = 8F ac F cd F db δA a,b ; δ F ⋆ ab F ab 2 = F ⋆ ab F ab ǫ opqr (F qr δF op + F op δF qr ) = 2 F ⋆ cd F cd F ⋆ab δF ab = -4 F ⋆ cd F cd F ⋆ab δA a,b ; δ F ⋆ ab F bc F ⋆ cd F da = 2 F bc F ⋆ cd F da δF ⋆ ab + F ⋆bc F cd F ⋆da δF ab = -2 F ac F ⋆cd F db δF * ab + F ⋆ac F cd F ⋆db δF ab = -2 1 2 F pc F ⋆cd F dq ǫ pqab + F ⋆ac F cd F ⋆db δF ab = 2 F pc F ⋆cd F dq ǫ pqab + 2F ⋆ac F cd F ⋆db δA a,b ; δ ǫ abcd ǫ ef gh F ae F bf F cg F dh = 4ǫ acde ǫ bf gh F cf F dg F eh δF ab = -8ǫ acde ǫ bf gh F cf F dg F eh δA a,b .
From those relations we get this

∂L 4 ∂A a,b = 1 4πc F ab + α F cd F cd F ab + βF ac F cd F db + κ F cd F ⋆ cd F ⋆ab (20) +λ F pc F ⋆cd F dq ǫ pqab + 2F ⋆bc F cd F ⋆da + σǫ acde ǫ bf gh F cf F dg F eh
The condition δ L 4 dΩ = 0 leads to the tensor equation

∂ ∂x b ∂L 4 ∂A a,b = 1 4πc ∂ ∂x b F ab + α F cd F cd F ab + βF ac F cd F db + κ F cd F ⋆ cd F ⋆ab (21)
+λ

F gc F ⋆cd F df ǫ f gab + 2F ⋆bc F cd F ⋆da + σǫ acde ǫ bf gh F cf F dg F eh = 0 or ∂F ab ∂x b = - 4π c j a , (22)
j a = c 4π ∂ ∂x b α F cd F cd F ab + βF ac F cd F db + κ F cd F ⋆ cd F ⋆ab (23) +λ F gc F ⋆cd F df ǫ f gab + 2F ⋆bc F cd F ⋆da + σǫ acde ǫ bf gh F cf F dg F eh
In addition, the tensor ∂L4 ∂A a,b is antisymmetric. Therefore

∂ 2 ∂x a ∂x b ∂L 4 ∂A a,b = 0,
and, accordingly, the continuity equation ∂ a j a = 0 is an identity. Considering that

∂L 4 ∂x b = ∂L 4 ∂A u,a A u,ab = ∂ ∂x a ∂L 4 ∂A u,a A u,b because ∂ ∂x a ∂L 4 ∂A u,a = 0
(on shell ) the canonical stress-energy tensor

T a b = ∂L 4 ∂A u,a A u,b -δ a b L 4 (24)
satisfies the condition

∂T a b ∂x a = 0, (25)
but it explicitly includes derivatives of the four-potential, which is unacceptable according to our assumptions. From (21):

∂L 4 ∂A u,a A b,u = ∂χ ua b ∂x u (26)
(on shell also) where

χ ua b = ∂L 4 ∂A u,a A b and χ ua b = -χ au b
In consequence, because of (26), the components of T a b can be replaced with

T a b = ∂L 4 ∂A u,a (A u,b -A b,u ) -δ a b L 4 = - ∂L 4 ∂A u,a F ub -δ a b L 4 (27) = ∂L 4 ∂A a,u F ub -δ a b L 4
which is the stress-energy tensor of the electromagnetic field in this theory. Equations ( 22), (23), and ( 27) are the fundamental equations of a unified classical field theory describing electric current, electromagnetic field, and matter in terms of Faraday's tensor. The generalization of this theory to general relativity is straightforward.

Concluding remarks

As aformentioned, if our assumptions that 1. The electromagnetic field F ij is an autonomous dynamical system.

2. Its dynamical laws obey the principle of relativity.

3. Those laws can be obtained from the principle of minimum action, using a Lagrangian density that is an analytic function of Faraday's tensor.

correspond to reality, the non-linear theory presented here must be true-to the fourth order in the field intensities-for appropiate values of the constants α, β, κ, λ, and σ. We must be aware, however, that this approach is not exempt of logical difficulties, because it depends on the soundness of the concept of a fourdimensional continuous space-time which, in turn, is grounded on our everyday experience of the existence of solid rigid bodies-as stressed by Einstein-as well as on the assumption that whatever the electromagnetic field is, it is completely described by the Faraday tensor field. Therefore, the soundness of this approach is granted at a macroscopic level and, at most, at a mesoscopic level, because there are no solid bodies of atomic dimensions.

δ i0i3 δ i1i2 δ i4i5 δ i6i7 , δ i0i3 δ i1i2 δ i4i6 δ i5i7 , δ i0i3 δ i1i2 δ i4i7 δ i5i6 δ i0i3 δ i1i4 δ i2i5 δ i6i7 , δ i0i3 δ i1i4 δ i2i6 δ i5i7 , δ i0i3 δ i1i4 δ i2i7 δ i5i6 δ i0i3 δ i1i5 δ i2i4 δ i6i7 , δ i0i3 δ i1i5 δ i2i6 δ i4i7 , δ i0i3 δ i1i5 δ i2i7 δ i4i6 δ i0i3 δ i1i6 δ i2i4 δ i5i7 , δ i0i3 δ i1i6 δ i2i5 δ i4i7 , δ i0i3 δ i1i6 δ i2i7 δ i4i5 δ i0i3 δ i1i7 δ i2i4 δ i5i6 , δ i0i3 δ i1i7 δ i2i5 δ i4i6 , δ i0i3 δ i1i7 δ i2i6 δ i4i5 δ i0i4 δ i1i2 δ i3i5 δ i6i7 , δ i0i4 δ i1i2 δ i3i6 δ i5i7 , δ i0i4 δ i1i2 δ i3i7 δ i5i6 δ i0i4 δ i1i3 δ i2i5 δ i6i7 , δ i0i4 δ i1i3 δ i2i6 δ i5i7 , δ i0i4 δ i1i3 δ i2i7 δ i5i6 δ i0i4 δ i1i5 δ i2i3 δ i6i7 , δ i0i4 δ i1i5 δ i2i6 δ i3i7 , δ i0i4 δ i1i5 δ i2i7 δ i3i6 δ i0i4 δ i1i6 δ i2i3 δ i5i7 , δ i0i4 δ i1i6 δ i2i5 δ i3i7 , δ i0i4 δ i1i6 δ i2i7 δ i3i5 δ i0i4 δ i1i7 δ i2i3 δ i5i6 , δ i0i4 δ i1i7 δ i2i5 δ i3i6 , δ i0i4 δ i1i7 δ i2i6 δ i3i5 δ i0i5 δ i1i2 δ i3i4 δ i6i7 , δ i0i5 δ i1i2 δ i3i6 δ i4i7 , δ i0i5 δ i1i2 δ i3i7 δ i4i6 δ i0i5 δ i1i3 δ i2i4 δ i6i7 , δ i0i5 δ i1i3 δ i2i6 δ i4i7 , δ i0i5 δ i1i3 δ i2i7 δ i4i6 δ i0i5 δ i1i4 δ i2i3 δ i6i7 , δ i0i5 δ i1i4 δ i2i6 δ i3i7 , δ i0i5 δ i1i4 δ i2i7 δ i3i6 δ i0i5 δ i1i6 δ i2i3 δ i4i7 , δ i0i5 δ i1i6 δ i2i4 δ i3i7 , δ i0i5 δ i1i6 δ i2i7 δ i3i4 δ i0i5 δ i1i7 δ i2i3 δ i4i6 , δ i0i5 δ i1i7 δ i2i4 δ i3i6 , δ i0i5 δ i1i7 δ i2i6 δ i3i4 δ i0i6 δ i1i2 δ i3i4 δ i5i7 , δ i0i6 δ i1i2 δ i3i5 δ i4i7 , δ i0i6 δ i1i2 δ i3i7 δ i4i5 δ i0i6 δ i1i3 δ i2i4 δ i5i7 , δ i0i6 δ i1i3 δ i2i5 δ i4i7 , δ i0i6 δ i1i3 δ i2i7 δ i4i5 δ i0i6 δ i1i4 δ i2i3 δ i5i7 , δ i0i6 δ i1i4 δ i2i5 δ i3i7 , δ i0i6 δ i1i4 δ i2i7 δ i3i5 δ i0i6 δ i1i5 δ i2i3 δ i4i7 , δ i0i6 δ i1i5 δ i2i4 δ i3i7 , δ i0i6 δ i1i5 δ i2i7 δ i3i4 δ i0i6 δ i1i7 δ i2i3 δ i4i5 , δ i0i6 δ i1i7 δ i2i4 δ i3i5 , δ i0i6 δ i1i7 δ i2i5 δ i3i4 δ i0i7 δ i1i2 δ i3i4 δ i5i6 , δ i0i7 δ i1i2 δ i3i5 δ i4i6 , δ i0i7 δ i1i2 δ i3i6 δ i4i5 δ i0i7 δ i1i3 δ i2i4 δ i5i6 , δ i0i7 δ i1i3 δ i2i5 δ i4i6 , δ i0i7 δ i1i3 δ i2i6 δ i4i5 δ i0i7 δ i1i4 δ i2i3 δ i5i6 , δ i0i7 δ i1i4 δ i2i5 δ i3i6 , δ i0i7 δ i1i4 δ i2i6 δ i3i5 δ i0i7 δ i1i5 δ i2i3 δ i4i6 , δ i0i7 δ i1i5 δ i2i4 δ i3i6 , δ i0i7 δ i1i5 δ i2i6 δ i3i4 δ i0i7 δ i1i6 δ i2i3 δ i4i5 , δ i0i7 δ i1i6 δ i2i4 δ i3i5 , δ i0i7 δ i1i6 δ i2i5 δ i3i4
Forty five of the corresponding terms in the sum

C i0i1i2i3i4i5i6i7 F i0i1 F i2i3 F i4i5 F i6i7
include δ i0i1 , δ i2i3 , δ i4i5 , or δ i6i7 and are, therefore, null. Each of the remaining sixty terms can be simplified to ± ab F ab 2 or ±F ab F bc F cd F da . There is another set of thirty five isotropic tensors that are products of Levi-Civita tensors, as shown below. There are three possibilities to consider when simplifying the product of one of those tensors and F i0i1 F i2i3 F i4i5 F i6i7 1. None of the F factors shares both of its indexes with the left factor of the ǫ-product. Those terms can be grouped into a single term that is proportional to ǫ abcd F ae F bf F cg F dh ǫ ef gh 2. One of the F factors shares both indexes with the left factor of the ǫproduct and, accordingly, there is one and only one factor that shares both indexes with the right factor of the ǫ-product. Those terms add up to a single term that is proportional to F ⋆ ab F bc F ⋆ cd F da where

F ⋆ cd = 1 2 ǫ abcd F ab
is the dual of Faraday's tensor.

3. Each of the ǫ factors shares indexes with two of the F factors. Those terms can be grouped into a single term proportional to F ⋆ ab F ab 2 . ǫ i0i1i2i3 ǫ i4i5i6i7 , ǫ i0i1i2i4 ǫ i3i5i6i7 , ǫ i0i1i2i5 ǫ i3i4i6i7 , ǫ i0i1i2i6 ǫ i3i4i5i7 , ǫ i0i1i2i7 ǫ i3i4i5i6 ǫ i0i1i3i4 ǫ i2i5i6i7 , ǫ i0i1i3i5 ǫ i2i4i6i7 , ǫ i0i1i3i6 ǫ i2i4i5i7 , ǫ i0i1i3i7 ǫ i2i4i5i6 , ǫ i0i1i4i5 ǫ i2i3i6i7 ǫ i0i1i4i6 ǫ i2i3i5i7 , ǫ i0i1i4i7 ǫ i2i3i5i6 , ǫ i0i1i5i6 ǫ i2i3i4i7 , ǫ i0i1i5i7 ǫ i2i3i4i6 , ǫ i0i1i6i7 ǫ i2i3i4i5 i0i2i3i4 ǫ i1i5i6i7 , ǫ i0i2i3i5 ǫ i1i4i6i7 , ǫ i0i2i3i6 ǫ i1i4i5i7 , ǫ i0i2i3i7 ǫ i1i4i5i6 , ǫ i0i2i4i5 ǫ i1i3i6i7 ǫ i0i2i4i6 ǫ i1i3i5i7 , ǫ i0i2i4i7 ǫ i1i3i5i6 , ǫ i0i2i5i6 ǫ i1i3i4i7 , ǫ i0i2i5i7 ǫ i1i3i4i6 , ǫ i0i2i6i7 ǫ i1i3i4i5 ǫ i0i3i4i5 ǫ i1i2i6i7 , ǫ i0i3i4i6 ǫ i1i2i5i7 , ǫ i0i3i4i7 ǫ i1i2i5i6 , ǫ i0i3i5i6 ǫ i1i2i4i7 , ǫ i0i3i5i7 ǫ i1i2i4i6 ǫ i0i3i6i7 ǫ i1i2i4i5 , ǫ i0i4i5i6 ǫ i1i2i3i7 , ǫ i0i4i5i7 ǫ i1i2i3i6 , ǫ i0i4i6i7 ǫ i1i2i3i5 , ǫ i0i5i6i7 ǫ i1i2i3i4

Appendix

There are 105 isotropic tensors of rank eight that are products of Kronecker Delta tensors:


Ahmed-Chawki Chaouche
email: ac.chaouche@misc-umc.org

Amal El

Fallah Seghrouchni

Jean-Michel Ilié
email: jean-michel.ilie@lip6.fr

Djamel Eddine Saïdouni
email: saidouni@misc-umc.org

Learning from Situated Experiences for a Contextual Planning Guidance

Keywords: Planning language, BDI agent, ambient system, intention consistency, past-experiences, contextual planning guidance

This paper presents AgLOTOS as an algebraic language dedicated to the specification of agent plans in ambient systems. It offers two levels of plans: Elementary plans which are composed to produce an intention plan ; The intention plans which are, in turn, composed to build an agent plan. The composition relies on several operators such as alternative and concurrency. Consequently, the plans can be built automatically as a system of concurrent processes. At the execution level, our approach helps the agent to select an optimal plan preserving the consistency of its intentions. The selection is based on an original and formal construction called Contextual Planning System (CPS), which presents the potential paths with the associated contexts while removing the inconsistent options. Finally, our CPS is improved by using past-experiences for a better guidance of the agent.

Introduction

Ambient Intelligence (AmI) is the vision of a ubiquitous electronic environment that is non-intrusive and proactive, when assisting people during various activities (??). For the design of such complex systems, Multi-Agent System (MAS) approaches offer interesting frameworks, since their agents are designed to be intelligent, proactive and autonomous (?).

The major problem of an AmI agent is to recognize its context. This includes gathering information on its location and the ability to discover other agents. In (?), it is shown how autonomous Belief-Desire-Intention (BDI) agents (?) can evolve and move within an ambient environment, based on an agent centric approach and context-awareness. The proposed model, called Higher-order Agent (HoA), takes into account the major features and functionalities of AmI. In particular the AmI systems can be open i.e. agents can enter or leave the system. Locations may change, exposing the agent to different surroundings.

This paper introduces an efficient planning management process into the HoA architecture. In particular, we aim to endow each AmI agent with a powerful on the fly predictive service. The plan of a BDI agent can be viewed as a set of intentions produced by the BDI interpreter.

We adopt the formal description language for plans, namely

AgLOTOS, introducing modularity and concurrency aspects for sub-plan composition. Unlike the formal description of ?, the AgLOTOS semantics overpasses the sequential execution of sub-plans. Moreover, the fact that the agent plans are produced automatically from concurrent intentions, formally enforces the consistency of the agent, hence, extends the GraphPlan-based approaches (?).

The formal semantics of AgLOTOS is enriched to automatically produce a Contextual Planning transition System (CPS), which allows to automatically guide the agent over the possible execution of actions in plans. In the CPS structure, the selection of the possible actions is informed by the successes and failures concerning the running pastexperiences of actions. In the literature, the benefits of a learning process have already been studied but under a huge number of iterations (??). Our learning approach is different and adapted to AmI and dynamic systems requiring an efficient activity of the agent even when the knowledge about the past-experiences is very limited.

The paper is organized as follows: Section 2 describes the functional architecture of the planning process, together with its guidance mechanism based on lookahead capability and past experience knowledges. In Section 3, the AgLO-TOS specification language is briefly described and used to build an agent's plans from its intentions (e.g. composition of plans). In Section 4, the Contextual Planning System (CPS) is defined. Section 5 presents our guidance mechanism and a realistic scenario for illustration. In Section 6, we improve the guidance mechanism by exploiting the agent past-experiences to qualify the actions of the CPS. In Section 7, we study the complexity of the proposed approach and we show how decreasing the combinatorial effect within the CPS. Finally, Section 8 discusses our approach with regard to state of the art. The overall agent architecture, we deal with, is standardly based on several processes. Triggered by events expressing the context changes, the mental process is assumed to be highly deductive and rational, based on BDI structures (Beliefs, Desires and Intentions).

Figure 1 brings out a functional view of our planning process, in charge to offer some plan to execute (σ ) from the current set of intentions (I). It is composed of two modules:

-The Plan Factory builds the so-called agent plan which globally corresponds to the current set of intentions. The LibP library is used to exploit the different alternative plans that must be specified for each intention. With respect to the current spatial context of the agent, a Contextual Planning System (CPS) is built. By its traces (paths), the CPS represents all the possible plans that can be realized. -The Guidance module is able to enrich the CPS information taking profit from the past-experiences of actions, that are stored in the so-called Learned Contextual Experiences (LCE) module. This results in a structure called CPS with learning (CPS-L for short), which can be used to searching the optimal trace with respect to the agent context.

The AgLOTOS Specification Language

The behavior of the BDI agent we consider in this paper is carried out by two successive processes, as highlighted in Figure 2. As usual, the Mental process represents the reasoning mechanism, based on the beliefs (B), desires (D), and intentions (I), the instances of which define the BDI states of the agent. Triggered by the perceived events, the mental process manages/updates the B, D and I structures. In order to organize its selected intentions, the mental process is able to schedule them by associating each one a given weight (see Section 3.2).

From the set of intentions, the Planning process is called by the mental process to produce a plan of actions, helped by a library of plans (LibP). In our approach for each BDI state, the Agent plan is composed as follows: (1) the agent plan is made of sub-plans called Intention plan, each one dedicated to achieving a selected intention; (2) each intention plan is an alternate of several sub-plans, called Elementary plans, extracted from the LibP library. This allows one to consider different ways to achieve the associated intention (see Section 3.1). Further, we assume that the LibP library of elementary plans is indexed by the set of all the possible intentions for the agent.

In our approach, the associated notation of the planning language is described in Table 1. Elementary plans are written using the algebraic language AgLOTOS (?). This language extends the LOTOS language (?) in order to deal with the concurrency of actions in plans.

Let O be the (finite) set of observable actions which are viewed as instantiated predicates, ranged over a, b, ... and let L be any subset of O. Let H ⊂ O be the set of the so-called AmI primitives which represent the mobility and communication:

-In AgLOTOS, actions are refined to make the AmI primitives observable: (1) an agent can perceive the entrance and leaving of other agents in the AmI system, (2) it Planning I P P 0 P 1 P j P 0,0 P 0,1 P 0,k E 0,0 process Mental process

I = {i w 0 , i w 1 , ..., i w j } ⊙ E 0,1 E 0,k

Agent plan

Intention plans

Elementary plans

Behavior expressions

⊙ ||| Parallel ≫ Sequence Alternate { Fig. 2 Agent planning structure
can move between the AmI system locations and (3) an agent can communicate with another agent in the system.

-An AgLOTOS expression refers to contextual information with respect to the (current) BDI state of the agent:

(1) Θ is a finite set of space locations, (2) Λ is a set of agents with which it is possible to communicate, and

(3) M is the set of possible messages to be sent and received.

-The agent mobility is expressed by the primitive move( ) which is used to handle the agent move to some location ( ∈ Θ ). The syntax of the communication primitives is inspired by the semantics of the π-calculus primitives. However, contrary to the classical use of the calculus, the communication support is completely dynamic, so there is no need to specify the predefined channels: the expression x!(ν) specifies the emission to the agent x (x ∈ Λ ) of some message ν (ν ∈ M), whereas, the expression x?(ν) means that ν is received from some agent x.

Let Act = O ∪ {τ}, be the set of actions, where τ / ∈ O is the internal action. Let δ / ∈ Act be a particular observable action which features the successful termination of a plan.

The AgLOTOS language specifies for each elementary plan a name to identify it and an AgLOTOS expression to describe its behavior. Consider that the elementary plan's names are ranged over P 1 , P 2 , ... and that the set of all possible behavior expressions is denoted E, ranged over E, F, .... The AgLOTOS expressions are written by composing (observable) actions using LOTOS operators. The syntax of an AgLOTOS elementary plan P is defined inductively as follows:

P ::= E Elementary plan E ::= exit | stop | a; E | E E (a ∈ O) | hide L in E H ::= move( ) (H ⊂ O, ∈ Θ ) | x!(ν) | x?(ν) (x ∈ Λ , ν ∈ M) = { [ ], , [>, |[L]|, ||, ||| }
In this syntax, P ::= E represents an elementary plan identified by P, such that its behavior expression is E. The elementary expression stop specifies a plan behavior without possible evolution and exit represents the successful termination of some plan. The expression a; E denotes an action a prefixing E and the set represents the standard LO-TOS operators and some of them can refer to any subset L of O.

::= E 1 |[b]| E 2 , means that the joint execution of b in E 1 and E 2 is possible only when b is possible in both E 1 and E 2 . -E ::= hide a in (E 1 |[b]| E 2 ) means that the action a is hidden when a is offered in the expression (E 1 |[b]| E 2 ).
In fact, this operator makes all the occurrences of the action a unobservable (replaced by τ) at the semantical level (see Section 4).

The AgLOTOS language is expressive due to its various operators, so that each execution plan is mainly based on the concurrent composition of elementary plans (one for each intention). Unlike LOTOS specification, it is worth noticing that AgLOTOS does not proposed any recursion mechanism based on the two following points:

-The mental attitudes of the agent can simulate a recursion by maintaining some intention, hence the possible associated elementary plans. Further in this paper, this AgLOTOS restriction guarantees that the semantic construction is finite, hence calculable. -The maintainability of intentions is very efficient since an agent can maintain some intentions, even if the other intentions are revised (??),

Building the Agent Plans from Intentions and Elementary Plans

The building of an agent plan requires the specific AgLOTOS operators:

at the agent plan level, the parallel ||| and the sequential composition operators are used to build the agent plan, in line with the intentions of the agent and associated weights.

the alternate composition operator, denoted ♦, allows to specify an alternation of elementary plans. In particular, an intention is satisfied if and only if at least one of the associated elementary plans is successfully terminated.

Let P be the set of names used to identify the possible intention plans: P ∈ P and let P be the set of names qualifying the possible agent plans: P ∈ P. libp : I → 2 P , features the library of elementary plans. It yields, for each intention i ∈ I, a set of instantiated elementary plans dedicated for achieving i. options : I → P, yields for any i ∈ I, an intention plan of the form:

P i = ♦ P∈libp(i) P.
plan : 2 I → P, creates the final agent plan P from the set of intentions I. Depending on how I is ordered, the intention plans yielded by the different mappings P i = options(i) s.t. i ∈ I are composed by using the AgLO-TOS composition operators ||| and .

In order to account for any BDI state of the agent, we propose that the agent can label the different elements of the set I of intentions by using a weight function weight : I → N. This allows us to weight the corresponding intention plans yielded by the mapping options. The ones having the same weight are composed by using the concurrent parallel operator |||. In contrast, the intention plans corresponding to distinct weights are ordered by using the sequential operator .

P P

e P e1 P e2 P m2 E e1 ||| E e2 E m2 P m P g E g P g P m1 P m3 E m1 E m3
≫ Fig. 3 An example of an agent plan structure

For instance, let I = {i 2 g , i 1 e , i 2 m } be the considered set of intentions, such that the superscript information denotes a weight value. As illustrated in Figure 3, let P g , P e , P m be their corresponding intention plans, the constructed agent plan could be viewed as: P ::= ( P g ||| P m ) P e , where P g ::= P g , P m ::= P m1 ♦P m2 ♦P m3 and P e ::= P e1 ♦P e2 . Further, each elementary plan P k is associated with an expression E k describing its behavior.

A Simple AmI Example

Let us consider the AmI University scenario presented in (?) where Alice and Bob are two agents. The proposed problem of Alice is that she cannot make the two following tasks in the same time: (1) to meet Bob in the location 1 , and (2) to get her exam copies from the location 2 . Clearly, Alice's desires are conflictual since Alice cannot be in two distinct locations simultaneously. As illustrated in Table 2, the scenarios of Alice and Bob are specified separately. It is assumed that Bob and Alice may coordinate in order to achieve their intentions, at their mental process levels. The actions in plans are simply expressed using instantiated predicates, like get copies( 2 ). Intention plans are composed from elementary plans which are viewed as concurrent processes, terminated by exit, a la LO-

TOS.

The mental process can order the set of intentions to be considered. For instance, the intention set of Bob I B = {meeting(Alice, 1 ), getting copies( 2 )} is ordered such that weight(meeting(Alice, 1 )) < weight(getting copies( 2)). Regarding the intention set I B , the corresponding agent plan expression of Bob is: P B = get copies( 2 ); Alice!(con f irm getc); exit move( 1 ); meet(Alice); exit, which is built by using the options and plan mappings. The resulting agent plan expression for Bob is thus the following: act two successive processes. First, get the copies locally in 2 and confirm this to Alice (Alice!(con f irm getc)). Second, move to 1 and meet Alice there. Pay attention that some actions can be processed concurrently, so is the case in the Alice' agent plan P A , for the two intention plans meet(Bob); exit and Bob?(con f irm getc); exit.

Contextual Planning Management

The AgLOTOS operational semantics is basically derived from the one of LOTOS. A pair (E, P) represents a process identified by P, such that its behavior expression is E. The semantic rules defining the possible elementary plan changes are detailed in Table 3 which formalize how a process can evolve under the execution of actions. In particular, the (Plan definition) rule specifies how a pair (E, P) is changed to (E , P) under any action a. Actually, P E means to consider any (E, P) source pair and P a -→ E means changing E to E for P under the execution of a. As far as AgLOTOS is concerned, these rules also represent the operational semantics of elementary plans, viewed as processes.

We now describe how the expression of an agent plan is formed compositionally from the expressions of the intention plans of the agent, themselves built from an alternate of elementary plans and their behavior expressions. The state of an agent plan P, also called an agent plan configuration, is denoted [P]. From the plan structure of any agent plan, such configuration is described by associating a behavior expression to each elementary plan, and by composing them according to the used algebraic operators.

The canonical rules of Definition 1, specify how [P] is formed compositionally from some intention plan configurations, like (E, P) (rule 1), themselves built from an alternate of elementary plan configurations, like (E k , P k ) (rule 2) which represents an elementary plan identified by P k , and its behavior expression is E k . Considering the example of Figure 3:

[P] = (E g , P g )|||(E m1 ♦E m2 ♦E m3 , P m ) (E e1 ♦E e2 , P e )
Definition 1 Any plan configuration [P] has a generic representation defined by the following two rules:

1.

P::= P P::=♦ k=1..n P k P k ::=E k [P]::=(♦ k=1..n E k , P) 2.

P::=P

1 P 2 ∈{|||, } [P]::=[P 1 ] [P 2 ]
We will now define the planning state of the agent contextually, taking into account the agent location and a termination information about the different intention plans defined for the agent.

Definition 2 A contextual planning state is a tuple (ps, , T ), where ps is any planning state, corresponds to an expected location for the agent, and T is the subset of intention plans which are terminated. -→ E and P := E, whereas the second one highlights the termination case, keeping trace of the intention plan P that is going to be terminated. By calling PS the set of all the possible intention plan configurations for the agent, the transition relation is a subset of PS × Act × P × PS. For sake of clarity, the transition (ps 1 , a, nil, ps 2 ) is simply denoted ps 1 a -→ ps 2 . Observe that due to the fact we consider a predictive guidance in the CPS, only successful executions are taken into account, thus abstracting that a plan may fail. Moreover, the semantics of the alternate operator is reduced to the simple non-deterministic choice of LOTOS:

♦ k=1..n E k ≡ [ ] k=1.
.n E k in order to take into account every elementary plan for achieving the corresponding intention. Agent plan level: The possible changes of the contextual planning states, like (ps, , T ), are expressed in Table 4. In (Action) rules, the first one exhibits the case of a regular action, whereas the second one specifies the termination case of some intention plan, which is added to T . In (Communication) rules, the action send x!(ν) (resp. receive x?(ν)) is constrained by the visibility of the agent

x in its neighborhood. In (Mobility) rules, the effect of the action move( ) yields the agent to be placed in .

Guidance Mechanism

From any set of intentions in the agent, denoted I, a Contextual Planning System is built by using the rules of Table 4 and taking into account contextual information of three kinds:

(1) the reached location in a planning state, (2) the set

-→ E (Choice) E a -→ E F [ ] E a -→ E E [ ] F a -→ E (Concurrency) E a -→ E a / ∈L∪{δ } E |[L]| F a -→ E |[L]| F E a -→ E a / ∈L∪{δ } F |[L]| E a -→ F |[L]| E E a -→ E F a -→ F a∈L∪{δ } E |[L]| F a -→ E |[L]| F (Hiding) E a -→ E a / ∈L hide L in E a -→ hide L in E E a -→ E a∈L hide L in E τ -→ hide L in E (Sequence) E a -→ E a =δ E F a -→ E F E δ -→ E E F τ -→ F (Interruption) E a -→ E a =δ E [> F a -→ E [> F E δ -→ E E [> F δ -→ E F a -→ F E [> F a -→ F (Relabeling) E a -→ E a / ∈{a 1 ,...,a n } E[b 1 /a 1 ,...,b n /a n ] a - → E [b 1 /a 1 ,...,b n /a n ] E a - → E a=a k 1≤k≤n E[b 1 /a 1 ,...,b n /a n ] b k -→ E [b 1 /a 1 ,...,b n /a n ]
(Plan definition)

P:=E E a -→ E P a -→ E
of intention plans that are terminated when reaching a planning state, and (3), more globally, the set Λ of neighbors currently known by the agent.

Definition 3

The CPS (Contextual Planning System) is a labeled Kripke structure S, s 0 , Tr, L, T where:

-S is the set of contextual planning states, s 0 = (ps, , / 0) ∈ S is the initial contextual planning state of the agent, such that ps = [P]=plan(I) and represents the current location of the agent, -Tr ⊆ S × Act × S is the set of transitions. The transitions are denoted s a -→ s such that s, s ∈ S and a ∈ Act, -L : S → Θ is the location labeling function -T : S → 2 P is the termination labeling function which captures the terminated intention plans.

In a CPS, any transition s a -→ s represents an action to be performed. Like in the STRIPS description language (?), the actions are associated with preconditions and effects. In our approach, the preconditions only concern the contextual information attached to the source state. Let pre(a) be the precondition of any action a, e.g. pre(a( )) = = L(s). In Figure 4, the three actions that are not realizable are represented by dashed transitions from the states s 2 , s 5 and s 9 . From these states, pre(getc( 2 )) = 2 = L(s).

In order to guide the agent efficiently, the planning process can select an execution trace which maximizes the number of intentions that can be achieved. This can be captured over the set Σ ⊆ 2 Tr of all the possible traces of the CPS. We introduce the notion of maximum trace based on the mapping end : Σ → 2 P , used to specify the set end(σ ) of the different terminated intention plans that occur in a trace σ ∈ Σ . Let Σ MAX represent the set of maximum traces of the CPS. For instance, the trace carried out by s 0 → s 2 → s 5 → s 9 in Figure 4, will not be represented because it is not a maximum trace. Hence, there are only 10 maximum traces in this CPS.

From an algorithmic point of view, the configurations having the maximum number of terminated intention plans could be straightforwardly detected by parsing the CPS structure, with regards to the set of terminated intention plans of each built configuration. By labeling these configurations with a specific proposition MAX, the search of maximum traces is reduced to the traces which satisfy the CTL (Computational Tree Logic) property AF(MAX).

The consistency of a set of intentions I can also be checked over some trace σ of the CPS, in particular in two extreme cases:

if |end(σ )| = |I|, meaning that all the intentions of I are consistent, -if |end(σ )| = 0, there is no satisfied intention, so the agent plan P is contextually inappropriate with respect to the set of intentions I. The pairs (E m , P m ) and (E g , P g ) are two intention plan configurations of Bob ; The first one corresponds to the intention meeting(Alice, 1 ) and the second to getting copies( 2 ), such that E m = move( 1 ); meet(Alice); exit and E g = get copies( 2 ); Alice!(con f irm getc); exit.

The Contextual Planning System of Bob, denoted CPS B , is illustrated in Figure 4. It is built from the initial CPS state,

s 0 = ([P B ], 2 , / 0
), taking into account the current location 2 of Bob. In the figure, the dashed edges represent the unrealized transitions from the states s ∈ {s 2 , s 5 , s 8 }, because pre(getc) = 2 ∈ L(s).

An example of maximum trace derived from s 0 is the following, expressing that Bob got the copies before moving to the meeting with Alice:

((E g , P g ) ||| (E m , P m )) getc -----→ ((E g , P g ) ||| (E m , P m ), 2 , / 0) con f irm -----→ ((E g , P g ) ||| (E m , P m ), 2 , / 0) τ ----→ Pg ((E m , P m ), 2 , { P g }) move( 1 ) ------→ ((E m , P m ), 1 , { P g }) meet -----→ ((E m , P m ), 1 , { P g }) τ -----→ Pm ((stop, P m ), 1 , { P g , P m })
6 Planning Guidance from Past-Experiences

Based on the CPS structure, we augment the planning process with a rich learning mechanism dedicated to improve selection of elementary plans in the LibP library and to guide the agent to achieve as many concurrent intentions as possible.

In the CPS structure, the different traces capture both the concurrency of intentions and the choice of an alternative for each of these intentions. These are implicitly expressed through the interleaving of actions that composed the selected elementary plans. In this section, we focus on actions and their performances in order to reinforce the quality of maximum traces that are offered. The agent can keep track of past-experiences obtained when running actions, and can learn the gain of re-using some action in a given context. Instead of the simplest way which consists of considering the actions of each CPS state separately, we propose to evaluate an overall gain for each maximum traces of the CPS, so as to order them.

Figure 5 shows different FIFO queues recording the successes '1' and failures '-1', with respect to some action a. Such structure is generalized to all possible actions and is called the Learned Contextual Experiences structure of the planning process (LCE for short). More precisely, if a cer-

τ m ℓ 1 ℓ 2 ℓ 2 ℓ 1 ℓ 1 ℓ 1 ℓ 1 ℓ 1 , { P m } , { P m } s 6 s 10 τg move s 13 s 15 ℓ 2 , { P g } ℓ 1 , { P g } ℓ 1 , { P g } ℓ 1 , { P g , P m } conf irm conf irm conf irm ℓ 1 , { P m } ℓ 1 ℓ 1 ℓ 2 meet meet meet τg τg τg τ m τ m τ m
Fig. 4 The CPS B corresponding to the plan 5 Learned Contextual Experiences of an action a tain outcome o ∈ {1, -1} is obtained for the performance of an action a in some location , it is pushed in the queue LCE a ( ).

P B ℓ 0 Locations Experiences ℓ 1 ℓ n -1 1 1 -1 -1 -1 1 1 -1 1 1 a 1 2 3 K Fig.
Due to the high dynamicity of AmI systems, we accord with a common heuristics such that the more recent an execution outcome is the more pertinent it is. Each queue for an action is parametrized by a pair ( f , K) where f is a function called pertinence function and K is the maximum size of this queue.

-In order to tackle the data explosion problem when analyzing its past-experiences, the queue is bounded by K experiences and assumed to be finite, hence the pertinence function domain. This implies that an outcome value beyond a maximum position are not pertinent, with respect to the values in the queue. -The pertinence function f : 1..K → R associates a weight for each outcome value stored in a queue. As an interesting case, for any index x of the queue, f (x) = 1 x yields much more importance for any outcome value corresponding to x.

The contextual gain value G a ( ) ∈ [-1, 1] of an action a in some location directly relates to the successes and failures during the past-experiences of a in . From a non empty queue LCE a ( ), G a ( ) is computed by applying the pertinence function on each outcome value, knowing that the size of the queue is 0

< k ≤ K: G a ( ) = ∑ k j=1 (o j * f ( j)) ∑ k j=1 f ( j) (1)
In the case where LCE a ( ) = / 0, G a ( ) is set to '0' corresponding to a middle gain value. This allows characterizing, at the agent level, that the action a in is not already explored. Hence, the non-explored actions can be privileged against the exploited ones having a gain less 0.

By extension, the different G a ( ) values allow us to assign a gain G(tr) to each CPS transition tr = (ps, , T ) a -→ (ps , , T ) ∈ Tr. The quality of each (maximum) trace is computed as follows, in order to guide the agent with the trace of the best quality.

Q(σ ) = ∑ σ tr G(tr) |σ | (2)
Application to the scenario

The Learned CPS B of Bob is highlighted in Figure 6. The dotted transitions do not support any maximum trace (s 0 → s 0

s 2 s 1 s 4 getc move s 3 s 7 conf irm s 5 s 8 s 11 s 9 s 12 s 14 ℓ 1 ℓ 2 ℓ 2 ℓ 1 ℓ 1 ℓ 1 ℓ 1 , { P m } ℓ 1 , { P m } s 6 s 10 τg move s 13 s 15 τg τ m ℓ 2 , { P g } ℓ 1 , { P g } ℓ 1 , { P g } ℓ 1 , { P g , P m } conf irm ℓ 1 , { P m } ℓ 1 ℓ 1 ℓ 2 0.28 -0.64 1.00
1.00 0.33 0.33 meet Fig. 6 The Learned CPS B corresponding to the plan P B s 2 → s 5 → s 9 ), then are neglected during the guidance phase. For the other transitions, their gains are computed. For instance, the values G(s 1 con f irm ----→ s 3 ) = -0.64 and G(s 4 con f irm ----→ s 7 ) = 0.28 are obtained by considering, the LCE of Bob sampled in Table 5, knowing that the action of both transitions is Alice!(con f irm getc) (con f irm for short) and the fact that the respective source locations of these transitions are L(s 1 ) = 2 and L(s 4 ) = 1 . In Figure 6, two maximum traces are highlighted by a bold line, such that the intermediary parts distinguish them. By computing the respective quality of these traces, the bold one appears to be more relevant that the mixed bold/dashed one, and can be offered to the execution process as the optimal trace (σ opt ). ...

K 1 1 -1 1 -1 2 -1 -1 1 move( 1 ) 2 1 -1 exit g 1 1 1 1 2 1 1 1
The given guidance is driven by Algorithm 1, yielding an optimal maximum trace, σ opt , from a set I of intentions. As the planning process acts as a service provider, it must also notify the case where there is no possible maximum trace.

Consequently, this is useful to drive the mental process to revise the agent intentions according to the current context. The hardness of the CPS-L computation mainly comes from the building of the CPS, since the computation of performance information only require to parse the LCE structure linearly. To evaluate a worst case complexity of the CPS-L, our approach consists in studying the concurrent complexity coming from the agent plan structure. To this end, we propose to reduce the operators of an agent plan configuration [P] in order to only focus on the parallel and the sequential compositions, as follows:

-The parallel composition (E 1 ||| E 2 ) is more complex than the interruption one (E 1 [> E 2 ) and the concurrent ones

(E 1 || E 2 and E 1 |[L]| E 2 ), -The sequential composition (E 1 E 2 ) is more complex than the non-deterministic choice one (E 1 [ ] E 2 ).
We deduce that the worst case complexity of [P] can be bounded by the complexity of an expression formed of a parallel composition of sequential components. As far as complexity is concerned, this is analogous to a composition of words, hence a number of traces in the CPS of order:

O (n 1 + n 2 + ... + n k )! n 1 ! * n 2 ! * ... * n k ! (3)
taking into account that [P] can be transformed in a parallel composition of k sequential components (sub-traces) such that n i is the length of the i th sub-trace.

From this result, it is then not surprising that a certain form of combinatorial explosion could appear in the CPS-L, as the number and the length of the (assimilated) parallel components increase. This is in fact a standard result of concurrent systems, however, here limited by the fact that only one agent is concerned and the fact that the real size of the CPS-L decreases by the number of actions whose preconditions cannot be contextually satisfied. Moreover, we consider that the number of intentions to be dealt with at a moment is reasonably small and that the lengths of the intention plans are small. These reasonable criteria tend to constrain the hardness of an agent plan configuration and the corresponding CPS-L.

Discussion and Related Work

We have presented in this paper, a contextual model for ambient agents which provides a mechanism to guide them contextually. In this section, we discuss the different points of view of the proposed approach, about both planning and learning techniques taking into account the guidance mechanism.

Planning

Considering MAS as a distributed systems composed of communicating entities is not new, however the first proposals either do not include any built-in capacity for "lookahead" type of planning or they do it only at the implementation level without a well defined semantics. Many BDI agentcentric approaches have been proposed to cope with the dynamic of the agent's environment. In (?), a hierarchical model (HTN) is proposed to better control the scheduling of plans in BDI agents, following an alternating goal-plan oriented strategy. Later on the same bases, ? showed how to specify and test learning approaches in some particular cases.

Our model is also agent-centric and accords with the principle of tightly controlling plans from the BDI mental attitudes. In contrast with the former works, the achievement of different intentions can be simultaneously considered and concurrently executed, in a higher level planning model. Conflicts are assumed to be solved by the mental process of the agent, however with the help of intention priorities. It is worth noticing that the conflicts which are caused by the contextual information are taken into account when building a CPS from the intention set. Dealing with action dependencies has already been studied in the literature in order to restrain the agent activity. In particular a GraphPlan planner can efficiently produce a global plan as a flow of actions that corresponds to the subset of the desires (i.e. goals) that could be executed concurrently (?). However, Graph-Plan only deals with some of the possible scheduling between actions, since it follows a global time step approach. In contrast, our approach takes all the possible cases into account.

BDI languages

In the literature there are a number of BDI agent programming languages (?), highlighting different aspects or modules developed in agent software like goals, planning and organization, e.g. Jadex (?), Jason (?), JIAC (?) and 2APL (?). Since 2006, BDI agent-centric approaches emerge to cope with the dynamicity of the agent environment. In particular, the work of ? has extended some existing formal specification models dedicated to distributed systems, in order to specify actions in plans while integrating BDI ingredients within plans in a unified way. Nevertheless, our formal algebraic language based on LOTOS, appears to be more expressive in its capacity to represent plans as concurrent processes as well as concurrent actions. It is also possible to handle action and plan failures in the AgLOTOS language and the HoA architecture. Moreover in our approach, a clear separation exists between the mental and planning levels. Actually, our planning process behaves like a service that could be embedded in existing BDI architectures.

Validation

The verification task standardly applied to MAS is mainly driven by a global vision of the system, e.g. in (?). In (?), the reuse of some program checking techniques is proposed, based on a BDI representation of the system state space. Moreover, in order to cope with the well-known combinatorial explosion of states, abstraction/reduction techniques are applied over the BDI states. One could consider introducing similar techniques within AmI agents, however, the high-level dynamics usually effective in an AmI environment could introduce too much states to consider, even after reduction. In our paper, the proposed guidance technique, is agent-centric so can be seen as a reduction of the system combinatorial explosion problem to the contexts handled by the agent.

Learning

Learning is the general approach to improve the behavior of intelligent agents from experimental-based information. It has been involved at different levels of the agents. Learning was first investigated at the mental level of BDI agents either to improve the BDI deliberation from some learned knowledge e.g. (?) or to produce a new plan with respect to some objective e.g. (?). Learning was also used to reinforce the selection of plans among different possible alternatives. In particular, a decision tree was introduced by ? to represent the different contexts in which the agent behaves. Indeed, the behavior of the agent is learned from the successes and failures of the executions of the agent's plans. The idea to take profit from the past execution experiences was adapted in (?) bringing out an on-line technique, based on a hierarchical goal-plan structure, in order to make the selection of some alternative according to the failures of the previous ones.

In this paper, we follow a similar idea, but unlike the former proposals, our approach is not only online but also adaptive: it is driven by the maximization of intention satisfactions, in order to guide the agent through the different paths implied by the concurrency of actions.

The learned CPS can be viewed as a reinforcement learning for the selection of elementary plans but based on the successes and failures of the executed actions. Actually, the selection of a path implies the selection of some alternative for each intention plan. Moreover, as we aim to tackle ambient systems with limited experiences, our relevance function favors a detailed representation of the action past-experiences, instead of an abstract overall view counting successes and failures, generally based on huge number of repetitive actions. The queues recording the past-experiences are bounded in order to tackle the combinatorial complexity introduced by their management. This approach is compatible with the idea of forgetting useless history. Regarding the pertinence function, our technique is in line with earlier propositions like the Q-learning algorithm. The last one learns a quality value for each action taking into account that the known values become deprecated as the time progresses, under a function like ε = 1/t. In our context, the applied forgetting function (1/x) allows us to privilege the most recent pastexperiences according to a logical recording time.

Recently, the work of (?) introduces a reinforcement learning technique dedicated to a domotic ambient system. The proposed platform is able to learn the acts of a human by recording a set of perceptions for each act. It can react instead of the human to the change of perceptions. The fact that this works under approximation, yields some similarities with our work which takes failures into account, however, without considering any plan construction or mental references.

As a learning alternative, other works proposed probabilistic systems in the frame of repetitive scenarios. A Markov Decision Process approach is proposed in (?) to reinforce learning in BDI agents, whereas a probabilistic function is proposed in (?) to introduce a certain capacity to explore new plans, against the use of plans experimentally known as successful. Both approaches are based on a huge number of repetitive experiences, so they could be ineffective in the case of ambient systems where agents must behave in real time, within a dynamic environment. Moreover, as we focus on user assistance, we can claim that each plan is certainly executed only a few times. Our alternative which consists of a history structure for each action seems relevant in the case of ambient systems, since the forgetting function applied to the known experiments can capture the fact that the changes in the agent environment can deprecate some past experiences on some action or plan.

Conclusion

The algebraic language AgLOTOS appears to be a powerful way to express an AmI agent plan as a set of concurrent processes, helped by an adapted plan library describing elementary plans. Based on any current set of intentions, the semantics of AgLOTOS allows to build a Contextual Planning System (CPS), from which all the maximum traces of situated actions can be evaluated, each one representing an execution plan maximizing the satisfaction of the set of intentions.

The main contribution of this paper was to improve the guidance mechanism based on the CPS in order to minimize the risk of a plan failure. To do that, the CPS structure is enriched with learning information extracted from the past-experiences of the executions of actions. This is used to qualify each action contextually, hence to qualify each maximum trace.

We demonstrate in this paper that the complexity of our planning approach mainly comes from the interleaving of the situated actions in the CPS. As discussed in the paper, the combinatorial effect should be reasonably handled, however, we now aim at improving the CPS guidance by introducing partial search techniques. Moreover, observing that the proposed CPS only focuses on spatial information, we aims at enriching the learning techniques with temporal aspects, to propose a spatio-temporal guidance.

Fig. 1

 1 Fig. 1 View of the contextual planning architecture

P

  ::= P | P ♦ P Intention plan P ::= P | P ||| P | P P Agent plan With respect to the set of intentions I of the agent, the agent plan is formed in two steps: (1) by an extraction mechanism of elementary plans from the library, (2) by using the composition functions called options and plan:

  scenario of Section 3 to achieve the intentions of Bob in a concurrent way: [P B ] = ((E g , P g )|||(E m , P m )) is the agent plan configuration considered for Bob.

Table 1

 1 Synthetic presentation of the used notations

	Notation E P P P (E, P) (E, P) [P]	Description Elementary expression Elementary plan Intention plan Agent plan Elementary plan configuration Intention plan configuration Agent plan configuration
	3.1 The Syntax of Elementary Plans

Table 2

 2 Scenarios for Alice and BobAlice's scenario I

A = {meeting(Bob, 1 ), receiving(Bob, con f irm getc)} P A = meet(Bob); exit ||| Bob?(con f irm getc); exit Bob's scenario I B = {meeting(Alice, 1 ), getting copies( 2 )} P B = get copies( 2 ); Alice!(con f irm getc); exit move( 1 ); meet(Alice); exit

Table 4

 4 shows the operational semantic rules defining the possible contextual planning state changes for the agent. These rules are applied to produce a Contextual Planning transition System, called CPS, from an initial contextual planning state, e.g. ([P], , / 0), meaning that the agent is initially at location and the plan configuration [P] represents its planning state. There are two kinds of transition rules: Intention plan level: When an intention plan is assumed to be treated, a transition (ps 1 , a, P, ps 2 ), denoted ps 1

a

-→ P ps 2 , expresses a change of intention configuration, from ps 1 to ps 2 . In table 4 (Intention plan level), the fist rule assumes the execution of the action a from E a

Table 3

 3 Semantic rules of elementary plan configurations

	(Termination) (Action prefix)	exit a;E -→ stop δ a∈O a

Table 4

 4 Semantic rules of intention and agent configurations

	Intention plan level
	(Action)	E (E, P) a -→E a∈Act a -→(E , P)	E (E, P) δ -→E E=exit
	Agent plan level
	(Action)

τ -→ P (E , P)

Table 5

 5 LCE samples for Bob

	con f irm	1	2	3	4


D-E Saїdouni

N Belala

R Boukharrou

A-C Chaouche

A Seraoui

A Chachoua

TIME PETRI NETS WITH ACTION DURATION: A TRUE CONCURRENCY REAL TIME MODEL

Keywords: Real-time systems, DTPN, maximality semantics, Actions duration, Durational Action Timed Automata

The design of real-time systems needs a high-level specification model supporting at the same time timing constraints and actions duration. We introduce in this paper an extension of Petri Nets called Time Petri Nets with Action Duration (DTPN) where time is associated with transitions. In DTPN, the firing of transitions is bound to a time interval and transitions represent actions which have explicit durations. We give an operational semantics for DTPN in terms of Durational Action Timed Automata (DATA). DTPN considers both timing constraints and durations under a true-concurrency semantics with an aim of better expressing concurrent and parallel behaviours of real-time systems.

INTRODUCTION

Petri Nets are a well-established formal model for the specification of distributed and concurrent systems. This model is very attractive by its ability to capture causal and parallel behaviours of these systems. Since its introduction, timed models based on Petri nets have been extensively studied for the specification and verification of real-time systems.

The two main extensions of Petri Nets with time are Timed Petri Nets (TdPN) and Time Petri Nets (TPN) [START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF][START_REF] Merlin | A study of the recoverability of computing systems[END_REF]. In TdPNs, delays were first associated with transitions (T-TdPN) and then to places (P-TdPN) [START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF][START_REF] Sifakis | Use of petri nets for performance evaluation[END_REF]. The two corresponding subclasses namely T-TdPN and P-TdPN are expressively equivalent [START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF][START_REF] Sifakis | Use of petri nets for performance evaluation[END_REF] and are a subclass of TPNs. Thus, a time delay can represent a minimum duration of firing or a minimum residence time of a token in a place. Informally, the TdPN uses the notion of duration as opposed to the notion of period of TPN.

In TPNs, temporal extension is expressed as an interval associated mainly to transitions (T-TPNs), to places (P-TPNs) or arcs (A-TPNs) [START_REF] Merlin | A study of the recoverability of computing systems[END_REF][START_REF] Khansa | Réseaux de Petri Ptemporels : Contribution à l'Etude des Systèmes à Evénements Discrets[END_REF][START_REF] Walter | Timed petri nets for modelling and analyzing protocols with realtime characteristics[END_REF]. Regarding the expressiveness of T-TPN and P-TPN, [START_REF] Khansa | P-time petri nets for manufacturing systems[END_REF] showed that these two models are incomparable. A-TPNs and P-TPNs are similar; however, the only difference concerns the strong semantics of P-TPNs and the lazy semantics of A-TPNs [START_REF] Boyer | Contribution à la modélisation des systèmes à temps constraint et application au multimedia[END_REF]. At last, T-TPNs form a subclass of Time Stream Petri Nets [START_REF] Emerson | Temporal and modal logic[END_REF] that have been introduced to model multimedia applications.

TPNs

are primarily used for performance analysis. In these models the firing of transitions is of null duration. They natively express specifications in time. In explaining beginnings and ends of actions with specification of time progress, they can also express specifications in duration. However, this manner of modelling the action durations has many disadvantages. First, the size of the associated semantic structure is increased. This phenomenon is known as the state space combinatorial explosion problem. Second, the obtained specification structurally keeps out the statement of system to be specified. Third, the underlying semantics, usually the interleaving semantics, supposes structural and temporal atomicity of actions, i.e., actions are indivisible and have null duration. Moreover, this semantics gives abstracts to the parallel execution of actions.

With the assumption that the firing of each transition corresponds to the execution of a divisible action with duration, our goal is to exploit a model which permits expressing trueconcurrency in a natural way without splitting actions into their start and end events. To do this, we propose at first an extension of TPN model called Time Petri Nets with Duration Action (DTPN). In this model, two annotations are associated to each transition, namely its timing constraint that restricts the date at which it can be fired and the duration of its corresponding action. Consequently, DTPNs can be considered as a generalization of Merlin's TPNs, T-TdPNs and P-TdPN [START_REF] Merlin | A study of the recoverability of computing systems[END_REF][START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF][START_REF] Sifakis | Use of petri nets for performance evaluation[END_REF]. Then, we give true-concurrency semantics to DTPN in terms of maximality semantics [START_REF] Devillers | Maximality preservation and the st-idea for action refinement[END_REF][START_REF] Courtiat | Relating maximality-based semantics to action refinement in process algebras[END_REF][START_REF] Saїdouni | Prise en compte des durées d'action dans les algèbres de processus par l'utilisation de la sémantique de maximalité[END_REF][START_REF] Saїdouni | Aggregation of transitions in marking graph generation based on maximality semantics for petri nets[END_REF][START_REF] Saїdouni | Using maximality-based labelled transition system as a model for petri nets[END_REF]. This semantics has been proven necessary and sufficient for the action refinement and for action durations [START_REF] Saїdouni | Sémantique de maximalité : Application au raffinement d'actions en LOTOS[END_REF]. The underlying model is a Durational Action Timed Automaton (DATA) [START_REF] Saїdouni | Actions duration in timed models[END_REF].

DATA provides an abstract model for real-time systems based on true concurrency semantics. It is very near syntactically to Timed Automata [START_REF] Alur | A theory of timed automata[END_REF] on which transitions are specified in terms of two related conditions (guard and deadline) expressing respectively, possibility and forcing of execution by stopping time progress. As a main result, DATA allows the verification of new properties related to simultaneous progress of actions at different states of the system.

The paper is organized as follows. First, we introduce the Time Petri Nets with Action Duration model. Next, we recall Durational Action Timed Automata with its semantics. In the follow section, we show the operational construction of DATA associated to DTPN, illustrative examples and DATA generation algorithm. Then, a case study of multimedia document modelled with DTPN is presented. After, we discuss the advantages of the proposed model. Finally, we give some conclusions and perspectives of our work.

TIME PETRI NETS WITH ACTION DURATION

Syntax

The basic idea of Time Petri Nets with Action Duration (DTPN) is to associate two dates min and max with each transition that define its firing interval (temporal interval). Although the firing of a transition is instantaneous, the execution duration of the action associated to this transition may have non-null duration. For example, let be a transition associated to the action which has a duration . If is the enabling date of then the firing of will be in the time interval . The firing of marks the start of execution of the associated action.

A place of a DTPN corresponds to two sets: a set of available tokens or free tokens and a set of unavailable tokens or bound tokens. Unavailable tokens, put on the right side of a place, are bound to the firing of transitions associated to actions that are currently running. In a DTPN, an unavailable token becomes available if the end of execution of the action associated to the transition that produced this token is reached. A token in place at the time becomes available (in the left side of ) at the time . Thus, the token is bound to the firing of the transition during the interval and it becomes free at the time .

Figure 1. Marked DTPN

In Figure 1.(a), the token in place 1 is not bound to any transition. This token is called free. In the case when the transition would be fired, it could be argued that the action associated to the firing of has started its execution. This is marked by the presence of the token in place (Figure 1.(b)). Thus, the token in place is bound to the firing of , but after completion of the action , i.e. after 3 units of time, this token will become free (Figure 1.(c)). In a place, the set of free tokens will be denoted by FT , while bound tokens set will be denoted by BT.



iii is a function that associates to each action its static duration.

is the set of all intervals of a DTPN such as is the interval associated to the transition . We denote by and two functions which give respectively the lower and upper bound of an interval.

As commonly in use in the literature, we write °t (resp.

) to denote the set of places such that (resp. ), and (resp. ) to represent the set of transitions such that (resp. ).

Semantics

Explicit Actions Durations.

A real-valued clock is associated with each token. This token is called bound when the duration condition associated with it, in the form of where is the associated clock and is the static action duration, is not satisfied. The token becomes free as soon as this duration condition will be satisfied.

Definition2 (Bound token):

A bound token is an element from noted by (or (

)) such that  is the producing transition of this token,



is the clock associated to the start of the action associated to ,



is the duration of this action,  is the ending condition of the action associated to ( is called also duration condition).

A question that arises concerns tokens which are bound to the same transition. To see that, consider the Petri net of Since BT is a set, we consider that bound tokens denoted with the same clock are defined as a tuple of , also denoted n , where n is the number of instances. We denote by the set (possibly empty) of bound tokens. In the previous example, . In what follows, a DTPN with a marking is called configuration which denoted a state.

denotes the total number of tokens in a place . If such that and then with ∑ and ∑ .

Explicit Timing Constraints. In DTPN's, a transition can be fired if its clock value is in the associated firing interval. Therefore, the firing of the transition is conditioned by the satisfaction of the guard . For example, let us observe the DTPN of Figure 4. In the initial configuration, all the tokens are available and the duration conditions are all satisfied. They are defined by where denotes a particular clock created and initialized at the enabling time of the system and which is associated to a particular transition launched at the system start-up. While the firing of the transition will be in the interval , the switch of the configuration shown in Figure 4 is conditioned by the satisfaction of the guard .

Figure 4. Firing of t1

Consider now the example of the DTPN of Figure 5. If we consider that one token in the place is bound to the firing of (

) and the other one is bound to the firing of ( ) then we can fire the transition using the token identified by the clock (resp. ) if and only if the condition (resp.

) is satisfied but in the relative interval . Therefore, the firing of is causally depending on the clock (resp. ) if and only if both the duration condition and the guard (resp. ) are satisfied. By a first firing of , we obtain the configuration (resp. ) of Figure 6 and through a second firing of the same transition, we obtain the configuration . The multienabling of a transition expresses the autoconcurrency, so, starting from and one can reach .

DURATIONAL ACTION TIMED AUTOMATA

The DATA model [START_REF] Saїdouni | Actions duration in timed models[END_REF][START_REF] Belala | Modèles de temps et leur intérét à la vérification formelle des systèmes temps-réel[END_REF]) is a timed model defined by a timed transition system over an alphabet representing actions to be executed. Structural and temporal non-atomicity of actions are supported by DATA. i.e., actions may be divisible and of non-null durations.

The DATA model supports the notions of urgency and deadlines as timing constraints of the system. An action duration is expressed by a duration condition associated to the states of the model. On the other hand, timing constraints due to restrictions on the enabling domain of an action are expressed by the enabling constraint G (for guard) and by urgency constraint D (for deadline) at the level of DATA transitions. In addition, a transition represents only the start of an action, end of execution is captured by the corresponding duration. On the target state of a transition, a timed expression manifests that the action is potentially in execution.

From operational point of view, with each action is associated a clock which is reset at the start of the action. This clock will be used in the construction of the timing constraints as guards of the transitions. This model is illustrated by the example of Figure 7 composed of two states and a transition labelled with an action a of duration 2 units of time. From the initial state of the illustrative DATA, the execution of the action a leads to a reset of the clock associated with it.

The expression in state represents a duration condition on the action and means that is potentially in execution until the clock reaches the value . The action does not wait for the end of any other action, so the clock designated by the enabling domain of this action will be . This enabling domain will be expressed by the guard and the deadline on the clock ( ). is the corresponding deadline which requires, at the moment of its satisfaction, that action a must occur. can be written → .

Formalization

Definition 6 : The semantics of a DATA is defined by associating to it an infinite transitions system over ℝ . A state of (or configuration) is a pair 〈 〉 such that is a state of and is a valuation for . A configuration 〈 〉 is initial if is the initial state of and , . Two types of transitions between configurations are possible, and which correspond respectively to time passing (rules and ) and the launching of a transition from (rule ).

ℝ 〈 〉 〈 〉 ℝ ⊨ 〈 〉 〈 〉 ⊨ 〈 〉 〈 〉
Where is the smallest real quantity of time in which no action occurs [START_REF] Belala | Modèles de temps et leur intérét à la vérification formelle des systèmes temps-réel[END_REF]. In rules, ⋁ where { is the set of all transitions stemming from state . Indeed, whenever a holds, time cannot progress regardless of the other .

Note that if one wants to guarantee that at least a transition could be drawn starting from a state if time cannot progress any more within this state, one requires that the formula be satisfied.

Remark: For urgency domains, we require that deadline can be only of the form or

OPERATIONAL CONSTRUCTION OF DATA ASSOCIATED TO DTPN

In the following paragraph, we give some preliminary definitions that enable us to propose a generation method of a temporal marking graph in the context of the maximality semantics.

Preliminary Definitions

Definition 7: Let be a DTPN with a marking and a transition :

 The set of ending conditions of actions potentially in execution in is the set of all conditions on clocks identifying bound tokens in the marking . Formally, the function will be used to calculate this set. can be defined as  The transition is said to be fired by the marking iff is enabled by this marking and it is not excluded by another transition enabled by i.e., its upper bound of its firing interval is smaller than the lower bounds of all other conflicted transitions. Formally, is fired by the marking iff and B(p', t') and ↑I(t′)<↓I(t)}. The set of all transitions enabled by the marking is noted . Let us consider the example of Figure 8 in which and are two transitions enabled by the same marking. However, by applying the rule of firing, only the transition will be fired. i.e, .  is a function which selects an element of its operand v , i.e., it satisfies for any .

 The guard or timing constraints for the firing of transition by the marking can be defined as is the resulting marking from the addition of tokens bound to to the marking .

{ |⋃ | |⋃ | ⋃ |⋃ | ⋃  Let

Temporal Marking Graph Construction

Let

be a marked and a bounded DTPN with t T, and . The Temporal Marking Graph (TMG) labelled by associated to is a graph in which the states are defined by all reachable markings from the initial marking and the transitions between states are labelled according to the derivation rule of Definition 8. Note that the bound clocks may not be selected. However, a clock which becomes free can be reused.

Property

Proposition1.

Let be a marked DTPN and TMG its finite Temporal Marking Graph built according to Definition 8. The structure is a DATA with



the Temporal Marking Graph associated to such that is the set of states, -is the initial state with , is the set of transitions (derivations) of TMG.

A derivation represents the switch from the state to state , by launching the execution of the action and using the clock .



is the function defined above,



is the finite set of clocks.

Proof. In order to show the coherence of Proposition 1, the following deductions are trivial. At first, let us observe the initial marking of the DTPN which contains only free tokens, therefore . In the other hand, we have in the initial state of DATA no action potentially in execution which implies that this initial state is exactly the initial state of TMG. Furthermore, is the set of states defined by the set of reachable markings obtained from the initial marking . Then, gives conditions on clocks identifying only bound tokens in which present exactly the duration conditions of actions potentially in execution in the corresponding DATA state.

Some Examples

Figure 9 shows some examples of marked DTPNs with their corresponding DATA's.

Figure 10. Example multimedia specification translated into a PND [START_REF] Bornot | Modeling urgency in timed systems[END_REF].

The reader may remark that the transitions of PND are labelled with guards. These guards are calculated on duration intervals with operators of MADEUS language [START_REF] Jourdan | Authoring and presentation environment for interactive multimedia documents[END_REF]. We can summarize this approach in four steps. First, the multimedia description is specified in MADEUS language. Then, the specifier calculates guards. After, this specification is modelled in PND model. Finally, the obtained PND specification is translated to a TAD (Timed Automata with Deadlines), as presented in [START_REF] Bornot | Modeling urgency in timed systems[END_REF].

The result of specifying this example by DTPN is depicted by Figure 11. In our approach, media objects of document DM may be seen as actions having a static durations. Static duration represents the duration of transmitting a media object without any transmission problem like congestion or latency. However, the transmission may delay. The duration of this delay may be specified by a temporal interval, so, all transitions are delayable. For instance, video clip (object A) has as duration units of time and may delay units of time. i.e., defined by the time interval . In the above description, the scene should be started only after the termination of scene . This is conditioned by the firing of transition (all multimedia object of are terminated). Following the same interpretation, the reader may see that the specification translates directly the multimedia example.

Verification. To investigate the verification of real-time systems, we can use algorithms and tools developed for Timed Automata (TA) [START_REF] Alur | A theory of timed automata[END_REF] to check properties on DATA's. For instance, it is possible to check real-time properties expressed in an extension of CTL logic on bounded DTPN's [START_REF] Emerson | Temporal and modal logic[END_REF]. To do this, we construct firstly the DATA structure corresponding to the DTPN specification. Then, the obtained DATA is translated to an equivalent TA which can be used with UPPAAL tool to check efficiently real-time properties (e.g. safety properties) [START_REF] Bornot | Modeling urgency in timed systems[END_REF].

As example, let us check the consistency of the DTPN of Figure 11. By applying the proposed approach, a fragment of the generated DATA vi of this document specification is given by Figure 12. This fragment presents the sequential execution of the two sub-documents and which is modelled by the transition The obtained DATA is translated to the equivalent TA of Figure 13 with some abstractions related to parallel execution of actions present in the state of the DATA. Then, using UPPAAL, we check the reachability of the TA from the initial state. The reachability is expressed by the following CTL formula (

). As result, the final state ( ) is indeed reachable, so the consistency of the specification is verified.

Note that validation techniques can be applied directly on DATA structures using Aggregated Regions Automata (Kitouni, Hachichi, Bouaroudj & Saїdouni, 2012). That is very important for the validation based on formal methods such as model checking using tools like UPPAAL and KRONOS [START_REF] Larsen | UPPAAL in a nutshell[END_REF][START_REF] Guellati | Verification of durational action timed automata using uppaal[END_REF][START_REF] Yovine | KRONOS: a verification tool for real-time systems[END_REF], and model based testing (Hachichi, Kitouni, Bouaroudj & Saїdouni, 2012). The use of DATA structure allows the verification of properties concerning parallel evolution of actions specified at state level of this model. In according to the case study, we conclude that the use of TAD supposes that the specifier is familiar with MADEUS language. Furthermore, as it may be observed in the specification, the obtained guards are not trivial to understand with respect to the system description. Consequently, the problem arises crucially during the verification result interpretation. As it is explained, DTPN overcomes all these inconveniences. Using DTPN makes multimedia documents specification easier, i.e. without a preliminary computing of guards associated to the transitions of the PND and then to its translated model TAD [START_REF] Bornot | Modeling urgency in timed systems[END_REF].

Operational Advantages. Note that the association of two dates minimum and maximum for each transition with fixed duration of the associated action gives us an intuition that DTPN's are a native extension of T-TdPN. However, in a context of semantics that forces the firing of transitions (strong semantics vii ), if we associate the interval [0,+∞[ for any transition of T-TdPN we can see it as a DTPN. Given that timed extensions of Petri nets (T-TdPN and P-TdPN) are equivalent, DTPN's are also a generalization of P-TdPN. If all actions of a DTPN are instantaneous, this model is seen as a T-TPN. Thus, TPNs are simulated by DTPNs, where all actions have null durations. As result, we conclude that DTPNs arise as a generalization of several models which are T-TPN, P-TdPN and T-TdPN. A generalization that does not stipulate changes at the general structure of a Petri nets, the number of places (resp. the number of transitions) remains the same. In this way, DTPN is not more expressive, but, it allows us to represent with more compact manner large classes of real-time systems. This concision is often a determining factor for the verification of real-time systems due to the complexity of model checking approach which is limited by the state space combinatorial explosion.

Technical Advantages. Another advantage concerns the construction of the set of clocks. In our context, a clock is created dynamically during the generation of the marking graph. On the contrary, other models like Timed Automata and Petri Nets with Deadlines [START_REF] Alur | A theory of timed automata[END_REF][START_REF] Bornot | Modeling urgency in timed systems[END_REF]) manage, at the beginning of modelling, a finite and constant number of clocks.

CONCLUSION

This paper proposes a timed extension of Petri Nets model called Time Petri Nets with Action Duration (DTPN). Two concepts have been integrated namely temporal constraints and action durations associated to transitions.

The paper gives true-concurrency semantics for DTPN's in terms of Durational Action Timed Automata (DATA). At first, we defined an operational method for generating DATA associated to DTPN specification. Then, an algorithm is proposed.

Interesting topics for future research include validation of more case studies of realtime systems in order to better benefit of the proposed model. In order to cope with the combinatorial state space explosion problem, it seems interesting to propose a distributed generation of the Durational Action Timed Automata for DTPN.

i We suppose that τ Act (τ indicates invisible action, also known as silent or internal action).

ii We suppose that all nets are finite, i.e. |P T | . iii D can be ℚ or ℝ . iv The reader may see that when bound tokens become free all their related clocks may not be reused until the associated tokens are consumed.

v In practice, we will often use an ordered set, for example E ⊂ , provided with the relation ≤, the function get gives the smallest element of this set. vi The resulting DATA has 36 states and 73 transitions. For this reason, we represent only a fragment of this structure.

vii Note that the strong semantics, which represents T-TPN and P-TPN [START_REF] Merlin | A study of the recoverability of computing systems[END_REF][START_REF] Khansa | Réseaux de Petri Ptemporels : Contribution à l'Etude des Systèmes à Evénements Discrets[END_REF], forces a transition to be fired when it reaches the upper bound of its firing interval. Whereas the lazy semantics, which represents A-TPN and TdPN (T-TdPN, P-TdPN) [START_REF] Walter | Timed petri nets for modelling and analyzing protocols with realtime characteristics[END_REF][START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF][START_REF] Sifakis | Use of petri nets for performance evaluation[END_REF], never forces a transition to be fired, i.e., a token can remain infinitely in a place.

  For example, let us consider DTPN of Figure 2.(a). After the firing of the transition (Figure 2.(b)), the token remains bound to the latter for 3 units of time, so, the set of the bound tokens in is . This token will become free at the moment of the satisfaction of the duration condition .

Figure 2 .

 2 Figure 2. Petri net with explicit actions durations.

  Figure 3.(a). With the firing of the transition , we obtain the derivation of Figure 3.(b). The right side BT of the place contains two tokens bound to the firing , i.e.

Figure 3 .

 3 Figure 3. Petri net with an output arc of a weight greater than 1 Definition 3 (Marking of DTPN): Let be a DTPN, a marking of is a function . Among others, the marking of a place is a pair such that and

Figure 5 .

 5 Figure 5. Identification of consumed tokens.

Figure 6 .

 6 Figure 6. Clocks identifying consumed tokens.

Figure 7 .

 7 Figure 7. Example of DATA.

Figure 8 .

 8 Figure 8. Example of two conflicted transitions.

  , the following derivation is possible:→ such that is the set of clocks associated with actions in which the end is required for the launch of the action related to the firing of

Figure 11 .

 11 Figure 11. Example of multimedia document specification in DTPN

Figure 12 .

 12 Figure 12. Fragment of DATA corresponding to multimedia document specification of Figure 11

Figure 13 .

 13 Figure 13. Fragment of TA correspending to DATA of Figure 12 DISCUSSION AND RELATED WORK In this work, we have given a framework to specify real-time systems. The advantages of the proposed DTPN model are the following : Specification Advantages. DTPN gives us on one hand a natural way of modelling, it natively expresses time specification in terms of time intervals and action durations. On the other hand, it provides a simple manner of reasoning translating directly the description of real time systems.

Definition 1 (DTPN): Let 𝕋 be

					a non-negative
	temporal domain (like ℚ+ or ℝ+) and	be a
	finite set of actions, i.e. an alphabet i . A Time
	Petri Net with Action Duration (DTPN) on 𝕋
	and	of	support		is	a	tuple
				such that
				is a Petri net where P
		is a set of places, T is a set of
		transitions ii such that			.
				is a backward
		incidence function such that
		represents the arc weight from to
		and			is a forward
		incidence function such that
		represents arc weight from to ,
				is a labelling
		function of a DTPN. If			then
		is called observable or external,
			𝕋	𝕋	is a function
		that associates to each transition a static
		firing interval,

CASE STUDY

In order to illustrate the interest of DTPN for designing real-time systems with action duration, we use it for the specification of the multimedia document introduced in [START_REF] Bornot | Modeling urgency in timed systems[END_REF].

Modelling. The building blocks of a multimedia document are media objects representing a piece of information which has to be played continuously for certain duration. As example, we consider the following document specification.

is a document composed of two scenes, that is, two sub-documents and .

is the introduction, composed of four media objects, namely, a video clip A, a sound clip B, a piece of music C and a user button D. The intention is that the video A is played in parallel with its sound B, while at the same time music is heard in the background. The user can stop the music by pressing the button.

is the body of the document, composed of five media objects, namely, a still picture E followed by a video clip F and its sound clip G, which determine the presentation of an animation H and a diagram O. The duration intervals of the objects are as follows: , , C : , , , , , and . An interval associated to an action means that this action takes at least duration and may elapse until duration. The specification of document DM is modelled by the PND (Petri Net with Deadlines) [START_REF] Bornot | Modeling urgency in timed systems[END_REF] shown in Figure 10.