Benjamin Cambon

Xavier Leoncini

Michel Vittot

Rémi Dumont

Xavier Garbet

Chaotic motion of charged particles in toroidal magnetic configurations

Keywords: numbers: 05, 45, Ac, 52, 25, Gj

We study the motion of a charged particle in a tokamak magnetic field and discuss its chaotic nature. Contrary to most of recent studies, we do not make any assumption on any constant of the motion and solve numerically the cyclotron gyration using Hamiltonian formalism. We take advantage of a symplectic integrator allowing us to make long-time simulations. First considering an idealized magnetic configuration, we add a non generic perturbation corresponding to a magnetic ripple, breaking one of the invariant of the motion. Chaotic motion is then observed and opens questions about the link between chaos of magnetic field lines and chaos of particle trajectories. Second, we return to an axisymmetric configuration and tune the safety factor (magnetic configuration) in order to recover chaotic motion. In this last setting with two constants of the motion, the presence of chaos implies that no third global constant exists, we highlight this fact by looking at variations of the first order of the magnetic moment in this chaotic setting. We are facing a mixed phase space with both regular and chaotic regions and point out the difficulties in performing a global reduction such as gyrokinetics.

Contrary to old studies, most of recent research dealing with hot magnetized fusion plasmas rely on numerical simulations. In the special case of a tokamak magnetic configuration, the majority of the numerical codes are based on the gyrokinetic theory. One of the assumptions made by this theory is to consider the magnetic moment of the particles moving in the magnetic field as an exact invariant of the motion. The straight consequence is to consider that all particle trajectories are integrable for axisymmetric configuration and no electric field.

This assumption enables to make global reduction of the phase space and allows for faster numerical simulations. In fact, the magnetic moment is often an adiabatic invariant and it can present variations over very large-time scales. These remarks lay the ground for possible presence of Hamiltonian chaos in particle trajectory and a non-constant magnetic moment. In this paper, we solve numerically the motion of charged particles including the cyclotron gyration using Hamiltonian formalism in the sixth dimensional phase space, without using any assumption. We take advantage of a symplectic integrator allowing us to make long-time simulations. First, considering an axisymmetric magnetic configuration, we add a non-generic perturbation corresponding to a specific magnetic ripple, breaking one of the invariant of the motion. Chaotic motion is then observed whereas magnetic field lines are still integrable. So, we underline that the link between the two notions is not automatic. Second, we observe chaos of particle trajectories even in an axisymmetric configuration of the magnetic field. For this purpose, we study the limit case in which the major radius of the tokamak is infinite. The geometry becomes cylindrical. We tune the winding profile of magnetic field lines in order to create a separatrix in the effective Hamiltonian of the cylindrical integrable system. We then perturb the system by adding some curvature and returning back to the toroidal configuration. The main result is that the chaotic region of the phase space of the system grows when the major radius of the "tokamak" decreases. The presence of a chaotic trajectories and mixed phase-space implies that the magnetic moment of the charged particles is not a global constant of the motion. We show its variations and remark that, in the case of a chaotic motion, this variation are significant and entice us to be careful before performing a global gyrokinetic reduction.

I. INTRODUCTION

The motion of charged particles in a magnetic field is a classical issue of dynamical systems and plasma physics, as for instance the fifty years old study made in [START_REF] Bogoliubov | Asymptotic Methods in the Theory of Non Linear Oscillations[END_REF][START_REF][END_REF] , before a time when numerical simulations became mainstream, or more recent approaches as for instance 3,[START_REF] Negrete Del Castillo-Negrete | del-Castillo-Negrete del-Castillo[END_REF] . Usually, the main properties of particle trajectories strongly depend on the form of magnetic field lines, making global features difficult to determine without using basic approximations. That's why, the theory of plasma confinement into a tokamak magnetic field is often studied using gyrokinetic theory. One of the assumptions made by regular codes based on this approach is that the magnetic moment µ of confined particles is constant [5][6][7] . The straight consequence is to consider that particle trajectories are integrable for axisymmetric configuration and no electric field. Indeed, trajectory of a charged particle in a tokamak idealized magnetic field is a six dimensions system in which we can consider two exact invariants, the energy and the angular momentum related to the toroidal invariance of the field. Moreover, the magnetic moment is said to be an adiabatic invariant. So, in good conditions, µ is a quasi-constant on short time but has some variations over very large-time scales (see for instance [8][9][10][11][12] ). Due to Arnold-Liouville Theorem, integrability of charged particle trajectory requires three exact commuting invariants 13 . Suppose that this three quantities commute, which is not obvious, we can transform the original system into an integrable approximation. However this may change the nature of particles trajectories. The link between chaotic motion and variations of the magnetic moment is an important topic 14,15 and these remarks lay the ground for possible presence of Hamiltonian chaos of particle trajectory and a non-constant magnetic moment even in an idealized magnetic case.

In this paper, we integrate the Hamilton equations through a symplectic code to be able to solve on one part the cyclotron motion on short time, and on an other part, to make longtime simulations, without approximations. Moreover, contrary to classical approach based on Runge-Kutta method, the main advantage of the symplectic codes is to keep constant the phase space volume and eventually the invariants of the motion over large-time scales, allowing us to study adiabatic variation of the magnetic moment.

FIG. 1. Toroidal geometry and notations

Using this property, the question we would like to answer is the presence of Hamiltonian chaos in charged particle motion in a toroidal magnetic field, studying two different cases.

First, we consider a non generic magnetic ripple modeling the finite number of coils surrounding the tokamak chamber, and breaking one of the invariant of the motion. In the second case, we want to create chaos to particle trajectories keeping an idealized magnetic field but looking for chaos in a six-dimensional system is not simple. In order to find the chaotic regions of the phase space, we decide to study the limit case in which the aspect ration (major radius vs minor one) of the tokamak tends to infinity. In this limit, the tokamak becomes a cylinder and the motions of the charged particles are integrable. The method is to create a separatrix in this simple system using the fact that the poloidal part of the magnetic field in the tokamak chamber is not a well-known function. Then, we will return to the toroidal case and look at the alteration of the integrability of the particle trajectories around the separatrix. In the same time, this second method highlights variations of the magnetic moment.

II. MODEL A. Basic equations

A schematic view of the toroidal geometry is presented on fig 1. In the (r, θ, ϕ) coordinates, we shall first consider the tokamak magnetic field of the following form 16 :

B = B 0 R ξ (ê ϕ + f (r) êθ ) , (1)
in which ξ = R + r cos(θ), êϕ and êθ are the unit vectors associated respectively to the ϕ and θ directions. The toroidal component along êϕ of the magnetic field is due to external coils around the tokamak chamber whereas the plasma generated current inside the tokamak leads to the creation of the poloidal component êθ . In this approximation the function f (r)

represents the amplitude of the poloidal field as a function of the radius and it is directly connected to the so-called safety factor q of principal importance in tokamak physics :

f = r/qξ ≈ r/qR . (2)
In Eq. ( 2) for simplicity we shall use the approximation in order to simply have q = q(r).

Usually, the amplitude of the poloidal component is estimated at about 10% of the global magnetic field but the safety factor is not an a priori fixed function and can actually be tuned in some machines. So, respecting the flux conservation of the magnetic field ∇ • B = 0, we have the freedom to choose the function f (r). It is easy to show that any smooth function depending only on r satisfies the flux conservation constraint.

Associated to Eq. ( 1), a vector potential can be chosen respecting the Coulomb gauge :

A(r) = B 0 F (r) ξ êϕ -B 0 R log( ξ R ) êz , (3)
where F (r) = r f . This choice of the magnetic field and associated potential vector corresponds to nested circular magnetic surfaces, which is a good approximation in the large aspect ratio limit. In a more realistic situation, we may have for instance to take into account that the magnetic surfaces have a slowly drifting center.

Given the magnetic field we consider the dynamics of a particle with charge e and mass m, in this magnetic field. The Hamiltonian of the system writes

H = (p -eA) 2 2m , (4)
where p = (p x , p y , p z ) and x = (x, y, z) form three pairs of canonically conjugate variables.

The associated equations of motion are :

     ẋ = (p -eA)/m , ṗ = e m (∇A) • (p -eA) . (5)
We readily notice in (5) that the particle velocity ẋ is given by v = (p -eA)/m.

B. Chaos, invariants and Adiabatic approximation

Looking for chaotic aspects of particle motions leads to look at the invariants of this three-dimensional system. Indeed, finding three independent invariants commuting with each other would imply integrability in the sense of Arnold-Liouville 13 . The energy of the particle is an exact invariant equal to H = 1 2 mv 2 . Then in the case of the magnetic field (1), the system is invariant by rotation around the êϕ axis. This entails that the conjugated angular momentum M is a constant of the motion (Noether Theorem). We can define it using the Lagrangian

L = 1 2 mv 2 + e A • v , (6)
by

M = ∂L ∂ dϕ dt . (7)
Using this definition (7) and the value of the vector potential in the proposed gauge, we obtain

M = ζ p • êϕ . (8)
Besides these two exact constants of the motion, we need a third integral in order to get integrable motion. The third constant that is often used is the magnetic moment µ defined at leading order by :

µ = mv 2 ⊥ 2B , (9)
where v ⊥ denotes the component of the velocity v perpendicular to the magnetic field B.

The magnetic moment (9) of a gyrating particle is used as a constant even though it is often only an adiabatic invariant [17][18][19][20] . Assuming that these three integrals are in involution we end up with an integrable system. Besides the involution, it is not obvious that the adiabatic invariant is actually a real invariant, in fact it is likely that depending on the magnetic configuration, this assumptions breaks down in some regions of phase space (see for instance 14,15 ), leading to local Hamiltonian chaos. The breaking of this assumption could be problematic, especially since in the last fifteen years a considerable effort had been devoted to gyrokinetics. Hot magnetized plasmas are usually well described using a Maxwell-Vlasov or Vlasov-Poisson description. This implies working with a time dependent particle density function in six-dimensions. In gyrokinetics theory the adiabatic invariant is used to reduce the dimensionality of phase space. This allows to not only to move to an effective 4 + 1 dimensional phase space, but allows also to avoid resolving in time the fast gyration around field lines (cyclotron frequency), both of these features are very appealing when aspiring at a full fledged numerical simulation of magnetized fusion plasmas in realistic conditions. In this paper we do not consider the consequences of the presence of Hamiltonian chaos on this theory, we however will look for the breaking of the adiabatic invariant. In this spirit we consider so-called fast-particles, meaning in typical tokamak conditions, we consider particles whose energy is from 10keV to around 3.5MeV , which is about the energy of α-particles resulting from the fusion of Deuterium and Tritium nuclei. Looking at the variation of µ given by Eq. ( 9) on time scales shorter than the cyclotron period, we observe a non constant function, which at first approximation looks like a sinusoid with a specific period. Given this fact, in what follows we now consider the average of µ on one or more cyclotron period as the effective adiabatic invariant, but keep the same notation.

In order to look for chaos, a possibility would be to actually find traces of adiabatic chaos, meaning chaos on adiabatic time scales. So, looking for the main characteristics of the motion of the particle, we have to study long-term variations of µ. The requirements for a numerical approach are thus that we must resolve short time variation meaning the fast cyclotron motion but we also have to simulate on very long time to be able to capture possible fluctuations of the magnetic moment. We therefore need to use a symplectic approach.

C. Numerical scheme

It is well known that using a classical Runge-Kutta scheme leads to important long-time errors. Indeed the scheme is usually not symplectic, hence the time steps does not preserve efficiently phase-space volume, in this case long-time studies can lead to the emergence of sinks, sources and attractors, which do not belong to the realm of Hamiltonian chaos see for instance field lines in 21 . In order to avoid this difficulty, numerical simulations have been performed using the sixth order Gauss-Legendre symplectic scheme discussed in 22 . Since we needed pairs of canonically conjugated variables, we remained in Cartesian coordinates.

This symplectic construction ensures the conservation of the symplectic volume and so, the Hamiltonian nature of the purpose. Moreover, we observe on Fig. 1 that this construction ensures also the stability of the energy and the angular momentum of the particle even for very large times and chaotic trajectories (see Sec. IV) Last but not least, in order to minimize numerical errors due truncations we use dimensionless variables. This allows to use variables whose variations remain in a finite range. Our choice is performed as follows, noting r, t and B our new variables. We write :

r = r/r a , (10)
t = ω c t = m eB 0 t , (11)
B = B/B 0 , (12)
where r a is the minor radius (see Fig. 1), ω c is the cyclotron frequency, and B 0 is the typical magnetic intensity at the center of the torus. Thereafter, we will only consider these dimensionless variables, and for clarity and readability we drop the˜and note (r, t, B) the dimensionless variables.

In order to validate the accuracy of our numerical scheme and test our code, we first consider the particular case in which there is no plasma inside the tokamak. In this configuration, the poloidal magnetic field is negligible. This property entails that the magnetic field depends only on ξ. So, in polar coordinates (ξ, ϕ, z), B = Rê ϕ /r a ξ. The application of Newton's second law, which computation is detailed in annex V A, demonstrates the drift of the particle in z-direction (the direction depends on the sign of the charge). In fact the system resumes to an integrable one and we end up with an effective Hamiltonian :

H ef f 0 = ξ2 2 + C 2 2ξ 2 + ln 2 (ξ) 4 + C ′ ln(ξ) , (13)
in which C = ξ 2 φ and C ′ are constants, which depend on the particle's initial conditions. A comparison between the (ξ, ξ) phase portrait obtained by our numerical scheme and the one obtained by resolving the quadrature, using the Hamiltonian ( 13) is shown in Fig. 3. We can notice an excellent agreement between the two curves, which validates our code. To be more specific, the step time is chosen to be δt = 0.01, which means we should have about 100 points to resolve the gyration motion. The records in Fig. 3 cover a period of 4. 10 7

time steps with R = 3, C = 1 and C ′ = 0. Further analysis of the Hamiltonian (13), leads as conclusions that there are no separatrix in phase space and that the equilibrium point corresponds to a linear drift of the particle while all other trajectories are helical. As can be noted in Fig. 3, when we zoom on one curve, we can compare in blue the exact trajectory and in red the motion computed by the integrator. The two methods give the same results with a precision better than our recorded digits, meaning better than 10 -5 . Another check of the numerical accuracy of our computation will be performed in Sect. IV.

III. CHAOTIC PARTICLE TRAJECTORIES USING RIPPLE EFFECT

A. The plasma with cylindrical symmetry first part

In the more general case when a plasma is present in the tokamak, the (ξ, ξ) plane looses its specificity because the magnetic field B also depends on r through the expression of the safety factor. In order to choose a configuration (14), we take a function that satisfies q(0) = 1, that presents a maxima and that respects lim r→∞ q(r) = 0 :

q(r) = 1 + ar 1 + r 2 , (14)
we recover the magnetic profile and the function f (r) using the approximate expression in (2). In the following, we will fix the constant a = 10. It becomes then challenging to visualize trajectories in the sixth-dimensional phase space. Indeed, the existence of two exact first integrals leaves room for possible chaos, moreover the expected cyclotronic motion of charged particles is likely to blur sections. Choosing a good section for visualizing trajectories becomes therefore challenging. The first problem is related to the choice of the initial conditions in a six-dimensional phase space. If we focus on fast particles corresponding to the ashes of fusion, their initial conditions are not explicitly known, however we can consider that their energy (mostly a kinetic one) is more or less known and about 3.5MeV and that their initial location is close to the center of the chamber, where the plasma is dense and hot and fusion reactions take place. However, the direction of the speed is uncertain, leaving us with to two independent parameters, the norm being fixed by a chosen energy. Then we have to find a suitable section in which we can distinguish integrable and chaotic trajectories.

If we only consider a classical section such as the poloidal (ξ, z) plane launching particles with a fixed angle, things are not clear due to the Larmor gyration, we end up with "thick" trajectories for all types of initial conditions. In order to better visualize we have considered two possible options. In a first attempt we computed the time average of µ(t) over a large number gyrations

μ(τ ) = 1 τ τ 0 µ(t ′ )dt ′ . ( 15
)
Typically we computed μ during a given initial time of the trajectory. We then performed a section (ξ, z) and recorded positions each time µ(t) = μ and dµ/dt > 0. We then get clear thin and distinct integrable trajectory. However for some initial conditions and a different type of magnetic field, we noticed a slow drift in µ(τ ) such that we could not record any data for large portions of the trajectory as µ(t) was not crossing the initially computed finite time averageμ. In order to circumvent this last problem and noticing that µ(t) always had a fast oscillating component, we finally settled for the following section: we only record points when reaching local maxima of µ(t), meaning we plot the points when dµ/dt = 0 and d 2 µ/dt 2 < 0. As a consequence, plotted points correspond to one Larmor gyration.

The resulting(ξ, z) section is presented in Fig. 4, where different trajectories are represented and have different values of the energy but the same initial speed direction. On this this section, we see two different types of trajectories: the elliptic ones (corresponding to socalled passing particles) and the bananas, separated by a separatrix. They all appear to be integrable, and looking for Hamiltonian chaos is not easy. Indeed in this setting, because the localization of the separatrix appears to depend on the initial speed direction, we can only represent particles with the same speed directions and location initial conditions on a given section, else we actually end up with a projection and characterized by apparent crossing of trajectories. In order to look for Hamiltonian chaos one of the solutions is to add a perturbation into the magnetic field.

B. The ripple effect

In order to trigger chaos more efficiently, we have introduced so called-ripple effect 23 .

This effect is mainly due to the finite number of coils around the tokamak and leads to the breaking of the toroidal invariance of the magnetic field, with for instance a dependence of the magnetic field on the toroidal angle ϕ. A direct consequence of the symmetry breaking is that the angular momentum M ceases to be an invariant, the accessible phase space becomes larger and chaos can occur even if another "hidden" constant of the motion related to the magnetic moment exists.

In order to remain simple we shall consider a very specific and actually non generic perturbation. This translate into a vector potential modified as: Bottom: zoom of the section near the separatrix, we see the jumps between the passing orbits and the banana ones.

A(r) = F (r) ξ (1 + δ cos(kϕ))ê ϕ -log(ξ)ê z , (16)
in which δ represents the amplitude of the perturbation entailed by the ripple and k the number of coils. In the case of ITER, k = 18 andδ is estimated to 10 -3 (the expression is of the perturbation is though different). As mentioned the breaking of one of the exact invariant of the motion makes easier the search of chaotic motion because the trajectory is now confined in a five dimensional phase space. We show in Fig. 5 the motion of one charged particle in the perturbed magnetic field, but for a perturbation amplitude δ = 0.2. Contrary to the idealized magnetic case, chaos shows up and is characterized by separatrix breaking.

Starting from a banana motion, the particle trajectory is able to cross the separatrix to become an elliptic passing one and vice versa. We though would like to insist that a priori we remain in a situation with mixed phase space. In the sense that if we start at a sufficiently low energy, far from the separatrix with an elliptic trajectory, the motion does not present sign of chaos at least for the length of time during which we computed and observed such trajectories.

C. Link between chaos of magnetic field lines and chaotic trajectories of charged particles

One of the usual cartoons that is used when describing magnetic confinement, is that particles have a fast gyration around magnetic field lines, and if the Larmor radius is small, particles follow more or less field lines. When looking at the previous sections in Fig. 4, we directly see that this is likely not the case. However this remark, lead to numerous studies on the chaoticity of magnetic field lines, having in mind a picture very much like the advection of passive tracers in a stationary three dimensional flows, where passive tracers simply follows velocity field lines 21,[24][25][START_REF] Evans | Nonlinear Dynamics ed T. Evans[END_REF][START_REF] Babiano | [END_REF][28][29][30][31][32][33] . The tokamak being a three dimensional object, it has been shown for a long time that field lines of flux conservative fields are generically chaotic in three dimensions. Assuming particles follow field lines it becomes natural to infer that studying the chaos of field lines would have a direct impact on particles confinement and trajectories. In the ideal tokamak, the magnetic field lines are not chaotic, due to the existence of the invariance by rotation of an angle ϕ. In the chosen magnetic fields, the lines winds helically around a given torus. Breaking the invariance, would lead to a real three dimensional system and chaos of field lines. It is in this sense that the perturbation chosen in Eq. ( 16) is non generic. Indeed in this last expression the magnetic field still does not depend on r, nor has a component along r, hence the magnetic field lines still gently wind around a torus, the variation of intensity is compensated by a non uniform winding, which allows to keep a constant flux across a given disk of radius r. Field lines are therefore still integrable, and a Poincaré section of these lines would not differ from the perfectly invariant case.

We insist therefore on the fact that despite the regularity of the magnetic field lines, we end up with chaotic particle trajectories. The connection between the two being therefore not obvious. Given this remark, we shall reconsider the case with an rotational invariance, and see if we can also find chaotic motion of charged particle. In order to illustrate this we reconsider our point of view and start with a cylindrical plasma tube instead of an empty toroidal solenoid.

IV. IMPACT OF THE TOROIDAL GEOMETRY ON PARTICLE TRAJECTORIES A. Infinite torus

In this section, we use another approach to create chaotic trajectories in a toroidally invariant magnetic field. For this purpose we start with a cylindrical magnetic geometry, which is the limit, when R tends to infinity, of the toroidal system. In this approximation, êϕ becomes a stationary vector and the idealized magnetic field can be rewritten as:

B = B 0 (ê ϕ + f (r)ê θ ) . (17)
A calculation described in appendix V B leads to and integrable system with a new effective Hamiltonian:

H ef f = ṙ2 2 + C ′′2 2r 2 + r 2 8 + F 2 (r) 2 = E c + V 0 (r) + F 2 (r) 2 , (18)
in which

C ′′ = r(v θ + r/2) ( 19
)
is a constant. The potential V 0 (r) tends to infinity when r tends to zero or infinity. Between these limits, it admits a minimum at r 0 = √ 2C ′′ . We can thus tune the function F (r) in order to generate a separatrix in this effective Hamiltonian corresponding to the cylindrical system. For this purpose we create a local maximum of the effective potential energy. We remark that choosing a F (r), corresponds to fixing a specific so called q-profile of the tokamak plasma magnetic confinement. We then perturb the system by returning to a toroidal geometry, decreasing the value of R to a finite value. A possible choice for F can be :

F = ar 2 exp(- r² c² ) , (20)
with a = 30 and c = √ 100. The details of the initial conditions which are fixed by C ′′ and H ef f are explained in appendix V B. Given these choices, the figure 6 shows the phase space FIG. 6. Top: phase space for a particle in the cylindric magnetic field governed by Hamiltonian (18).

Bottom: zoom near the separatrix and comparison between analytical curve solved by quadrature and numerical integration.

(r, ṙ) of the effective system for a proton with the particular condition C ′′ = √ 10 -5 . As expected, the motion depicted on Fig. 6 shows that the particle trajectory in this type of magnetic field is integrable. We visualize the separatrix between two areas corresponding to the potential wells and the rest of the phase space for particles with an energy of about E = 600keV . This gives us another framework to successfully test the accuracy of our numerical integration, especially in the vicinity of the separatrix as described in Fig. 6.

Looking for chaos, we shall now perturb this system going back to the toroidal geometry and study the impact of the curvature onto trajectory properties.

B. Particle trajectories in toroidal geometry

As mentioned we consider the toroidal aspect with finite large radius of the tokamak as a perturbation of the cylindrical system. We now consider finite radius R, and will slowly increase the "perturbation" by decreasing the value of R. We are eager to compare the motion of a charged particle in the cylindrical geometry to the one in the toroidal system.

For this purpose we shall visualize the particle trajectories in the (r, ṙ) plane. In order to perform a clean section, considering the action-angle variables associated to the integrable Hamiltonian (18), section are usually best performed at constant action. Indeed if we only consider a projection on the (r, ṙ) plane, as previously, the Larmor radius causes that we end up with thick trajectories for all trajectories. Since computing the action is not a straightforward task, we shall use the fact that for integrable systems H = H(I), a section at constant I, corresponds to a section at constant energy. For this purpose, we reconsider the effective Hamiltonian H ef f (18), which in the cylindrical case can be rewritten as

H ef f = v 2 r 2 + C ′′2 2r 2 + r 2 8 + v 2 ϕ 2 , (21)
and given the expression of C ′′ (19) we notice it corresponds to the actual kinetic energy of the system up to some constant (2C ′′ ). However for a finite radius this Hamiltonian presents temporal variation and becomes a time dependent function H ef f (t). Its expression does not change but, in the toroidal system, C ′′2 is not a constant anymore. So performing a section at constant action corresponds to perform a section at constant H ef f , which corresponds to a section taken at constant C ′′ , since of course the kinetic energy of a particle is a constant of the motion.

We first start with a small perturbation, namely R = 10000 (in our dimensionless units R is measured in minor radii). Results are displayed in Fig. 7. In fact most of the trajectories remain regular, but when we consider a particle with initial conditions close to separatrix in the integrable cylindrical case, represented in Fig. 7 something happens. In fact, the overall picture has the same aspect as the cylindrical phase space (Fig. 6), except if we zoom around the unstable equilibrium point, there the dynamics becomes very different and we see the emergence of a chaotic region, often dubbed a stochastic layer. As in Sect. III, the chaotic region is created by the breaking of the separatrix, in the current case we remain however with an axisymmetric magnetic field. As such the presence of chaos in the charged particle Hamiltonian separatrix chaos emerges.

trajectory indicates that the system is non-integrable and de facto rules out the existence of a third constant of the motion, for instance one related to the magnetic moment.

In order to have a clearer picture we increase the perturbation and we decrease progressively R from R = 10000 to R = 100. The global picture is displayed in Fig. 8. We consider the same initial condition and display the section of one trajectory, we confirm the expected trend that increasing the perturbation, corresponding to a reduction of the aspect ration R leads to a growth of the chaotic region in the phase space. In order to be more conclusive, we as well display regular trajectories obtained in these three settings using the same initial condition as well. The emergence of chaos is a priori not a numerical artifact. When further decreasing R, we notice that an other phenomenon appears when we pass from R = 100 to R = 10; as can been seen on the section for R = 10 and R = 3 depicted in Fig. 9 and a global apparent increase of chaos in the charged particle trajectory emerges. It is though likely that in this range, the section at constant action is not suitable to correctly describe the system, this is relatively surprising as the perturbation is still relatively small and we are actually reaching the aspect ration of real machines such as the one of ITER for instance.

The problem of creating a good section in this region needs still to be solved, and one of the problems of remaining with section made using the cylindrical action could be related to monodromy issues.

We insist on the fact that in this setting the field lines are integrable and the Poincaré section of the field lines is depicted in Fig. 10. This section should not change with the value of R except maybe for the position of resonant surfaces filled with periodic field lines. We notice that in this magnetic configuration, the field lines are periodic and purely toroidal at r = c, radius for which the orientation of the winding of field lines changes. C. Variation of the magnetic moment µ

As previously discussed the presence of chaos in charged particle trajectory in an axially symmetric system with already two constant of the motion, implies that the system is not integrable and as such it precludes the existence of a third constant of the motion, notably one related to the magnetic momentum. In order to verify this statement we measured the variations of the magnetic momentum using time averages of expression (9). For this purpose we compare three different cases in Fig. 11. In this figure, the average μ are computed on about one hundred cyclotron gyrations. Except for initial kinetic energy, the three cases have identical initial conditions. In the first case (upper plot), we take R = 10000 and FIG. 10. Poloidal section of magnetic field lines. The field is given by Eq. ( 1) and f is obtained from Eq. ( 20). Field lines are purely toroidal and thus periodic at r = c = 0.1, where the winding of the magnetic field lines changes orientation. We insist on the fact that this does not depend on the value of R. For illustration we plotted the section of the particle trajectory with R = 10 depicted in Fig. 9.

an energy of about E = 450keV , this leads to an integrable trajectory, associated to this characteristics, we note that the variations of μ are small and periodic. In the second case (middle plot of Fig. 11) we present the variations of the magnetic moment of a particle when R = 10000 with an energy E = 600 keV , that corresponds to an energy close to the one of the separatrix and a motion in the chaotic layer. As seen in Fig. 7, the motion of this particle is chaotic and we notice in Fig. 11 that the variations of μ are bigger than in the first case, we actually have △μ/μ ≃ 20%. In the third case, (lower plot in Fig. 11), we are considering the situation of the particle moving in a system with the aspect ratios of real tokamaks, namely R = 3 at an energy of E = 600keV . As anticipated by the left plot in Fig. 9, the particle trajectory is chaotic and the variations of μ are important △μ/μ ≃ 60% and unpredictable.

This seems to confirm that in the phase space of such systems, there is no global third constant of the motion. The existence of a constant related to the magnetic moment may be locally true, so we expect the general picture of a mixed phase space with regions of chaos and regions with regular motion. This nevertheless poses the problem of a global reduction performed in for instance gyrokinetics theory in the Maxwell-Vlasov context.

V. CONCLUSION AND POSSIBLE CONSEQUENCES

Looking for chaos of charged particles trajectories evolving under the influence of a magnetic field with a toroidal structure, as for instance an axisymmetric one is not an easy issue.

One of the main difficulties is to visualize trajectories correctly, and the second problem is to explore the phase space. Given these difficulties, in this paper we choose to highlight the presence of chaos of particle trajectory in two specific cases. First, we take into account a ripple effect, and as such we break a symmetry and the associated exact invariant of the motion. This allows to insure an a priori non-integrable system and to localize and visualize chaos more easily. This step allowed us to insist on the fact that the chaotic motion of charged particles is not directly linked to the chaotic nature of magnetic field lines, as indeed we considered a non generic perturbation which kept the regularity of field lines, while generating chaos in particle trajectories. So this simple example allowed to underline the fact that the link between chaos of particle trajectories and chaos of magnetic field lines is not obvious. In the second case, we considered an axisymmetric configuration, with two constants of the motion. We managed to observe chaos by tuning the winding profile of magnetic field lines in order to create a separatrix in the effective Hamiltonian of the cylindrical integrable system and perturbing it slowly by adding some curvature and returning back to the toroidal configuration. We exhibited that the chaotic region increases when the aspect ratio (major radius) of the tokamak decreases. At the same time we measured the fluctuations of the magnetic variations of μ which are also directly correlated with the chaos of the particle trajectories. The presence of chaotic trajectories in the case of an axisymmetric field implies that no third constant of the motion exists as the motion is non-integrable.

This implies therefore that the magnetic moment can not be a global constant over all phase space, and that this system corresponds likely to a system with mixed phase phase space, with regions of regular motion and regions of chaotic motion. We may therefore expect all the zoology and complex transport properties that is present in one and a half degrees of freedom system, such as stickiness and associated memory effects. Another consequence is that one has to be careful when performing gyrokinetic reduction. Indeed usually the support of the particle density function described by the Vlasov-Maxwell system covers the whole phase space. Since there are regions with chaos an non-constant magnetic moment, a straightforward reduction is a priori not possible. A future line of research in this field, where C and C ′ are two constants.

We can then use expression ( 26) and (27) in Eq. ( 23), multiply it by ṙ and integrate to obtain the effective Hamiltonian

We end up with an effective Hamiltonian (28) with one degree of freedom, and this shows that particle trajectory in this simple magnetic field is integrable.

B. Particle trajectory in cylindrical geometry

A very similar calculation can be made in the case of a cylindrical geometry. We recall that the magnetic field is given by

B = B 0 êz + f (r)ê θ . (29)
We apply Newton second law to a charged particle of mass m, charge q, moving in this magnetic field. In polar coordinates (r, θ, z), we obtain:

r -r θ2 = q m (B 0 r θ -f (r) ż) , (30)
r θ + 2 ṙ θ = - qB 0 m ṙ , (31)
z = q m ṙf (r) , (32)
Note that the z-direction corresponds to axes along the constant êϕ (R = ∞), and not the z depicted in Fig. 1. We integrate Eq. (32), and (31) as well multiplying it by r before hand and obtain:

r 2 θ + eB 0 2m r 2 = A , (33)
ż = e m F (r) , ( 34
)
where A is a constant and F (r) = r f (x)dx. Now, using expressions (33) and (34) in Eq. ( 30), which we multiply by ṙ before integration, we end up with:

m ṙ2 2 + mA 2 2r 2 + (qB 0 ) 2 8m r 2 + q 2 m F 2 (r) = H ef f , (35)
in which H ef f is a constant. This system is also integrable, but contrary to the Hamiltonian (28) presents the interest to allow us to create a separatrix by tuning the function F (r), in other words the so called q-profile.

FIG. 2 .

 2 FIG. 2. top: Stability of the energy of the particule in two different cases : one integrable trajectory choosen in the case of f = 0 (full line) and another picked up from a chaotic trajectory (dashed line) in the case R = 3 (see Sec. IV) Bottom : Same comparison with the angular momentum M

FIG. 3 .

 3 FIG.3. Top: phase portrait in (ξ, ξ) coordinates for the simple case without plasma in the tokamak chamber. Bottom: zoom and comparison between a numerically computed trajectory and the analytical one. Numerical integration is performed for 4. 10 7 time steps using a δt = 0.01.

FIG. 4 .

 4 FIG. 4. (ξ, z) section obtained with dµ/dt = 0 with no ripple. Four different trajectories with different energies but same speed directions are displayed. Motion appears as integrable, we notice the presence of a separatrix, distinguishing to types of orbits: so called passing orbits and banana orbits.

FIG. 5 .

 5 FIG. 5. Top: (ξ, z) section obtained with dµ/dt = 0, and one trajectory with ripple and ε = 0.2.

FIG. 7 .

 7 FIG. 7. Top: (r, ṙ) section for H ef f = Constant, R = 10000, E = 600keV . Initial conditions are identical to the ones taken in the cylindrical case near the separatrix in Fig. 6. Bottom: zoom of the trajectory near the unstable fix point, the integrable trajectory is drawn for comparison.

FIG. 8 .

 8 FIG.8. (r, ṙ) sections for H ef f = Constant and R = 10000, 1000, 100 . We see an increase of the stochastic layer as the major radius is reduced. For R = 100, we start to see some problems with the section (see Fig.9). For comparison tori corresponding to identical initial conditions and the different radii are drawn in the regular region. Final time is t = 6 10 4 . For each regular trajectory the initial conditions are:x 0 = R + 0.05, y = 0, z = 0, vy = -F (r(t = 0)), vz = -(C ′′ /(x -R) -(x -R)/2.0), E = 590keV, v = 2E/m, vx = v² -vy² -vz² ,for the chaotic trajectories they are the same but with E = 600keV.

FIG. 9 .Fig. 6 .

 96 FIG.9. Top: (r, ṙ) section for H ef f = Constant, with R = 10, E = 600keV . Initial conditions are identical to the previous cases, meaning the one taken in the cylindrical case near the separatrix in Fig.6. Bottom, same section but with R = 3. We notice in both plots what looks like an increase of chaos, but that also that the sections at constant action appears as non satisfactory anymore.

FIG. 11 .

 11 FIG.11. Fluctuation of the finite-time averaged magnetic momentum versus time. The average is performed over about twenty gyration periods. In the upper plot, the values for regular low energy motion versus time are represented, R = 10 4 , E = 450 keV . We can expect that a third constant of the motion exists. For the middle plot we see fluctuations of about △μ/μ ≃ 20%, we still have R = 10 4 but higher energy E = 600 keV . In the lower plot we have fluctuations about 60%, we are in the case of realistic ratios, R = 3 and E = 600 keV . In this last case, it is difficult to imagine that a modified expression of the magnetic moment µ would become constant.

  Rq m C ′ ln(r) = H ef f 0 ,

ACKNOWLEDGMENTS

We are very grateful to P. J. Morrison for providing useful comments and remarks. This work was carried out within the framework the European Fusion Development Agreement and the French Research Federation for Fusion Studies. It is supported by the European Communities under the contract of Association between Euratom and CEA. The views and opinions expressed herein do not necessarily reflect those of the European Commission.

could be on how to perform the reduction only in specific regions of phase space, and how what remains in the other regions is affecting the dynamics of the reduced distribution. In real case scenarii, it is also likely that regions where the reduction a priori works may be changing with the magnetic and electric fields, leading to possible intermittent reductions, a more thorough study in localizing all these regions in phase space in realistic tokamak like configurations appears therefore as a necessity.

ANNEXE

In these annexes we used Newton's law, but Noether theorem and a Lagrangian formalism can be more elegant.

A. Particle trajectory without plasma

In the simple case in which there is no plasma inside tokamak, we can write the magnetic field as :

We apply Newton second law to a charged particle of mass m, charge q, moving in this magnetic field. In polar coordinates (r, θ, z), we have :

where if we refer to Fig. 1, we actually have used the notations r = ξ and θ = ϕ. We integrate Eq. ( 24) and ( 25) and obtain :


Claudia-Lavinia Ignat
email: ignat@inf.ethz.ch

Moira C Norrie
email: norrie@inf.ethz.ch

Gérald Oster
email: oster@loria.fr

Handling Conflicts through Multi-level Editing in Peer-to-peer Environments

Keywords: multi-level editing, operational transformation, tombstone transformation functions, conflict handling ACM Classification I.7.1 [Document and Text Processing]: Document and Text Editing, H.5.3 [Information Interfaces and Presentation]: Group and Organisation Interfaces -Computer-supported cooperative work, H.1.2 [Models and Principles]: User/machine Systems -Human Factors

The handling of conflicts in collaborative editing over hierarchical documents in peer-to-peer networks is a very important issue. In this paper we show how the multi-level editing approach that recursively applies a tombstone transformational approach over the document levels offers support for flexible conflict definition and resolution.

INTRODUCTION

Collaborative editing systems support a group of people editing a set of documents over a computer network. Documents subject to collaboration can be of various types, such as text, XML and graphical. A hierarchical document model encompasses a wide range of documents and offers support for semantically structured documents and in this paper we analyse collaboration over hierarchical structures of documents.

As we want to allow users to work disconnected from the network we have used, a replicated architecture where users edit copies of the document. Operational transformation [START_REF] Ellis | Concurrency Control in Groupware Systems[END_REF] is a suitable approach for maintaining consistency between copies of the shared document. In [START_REF] Davis | Generalizing Operational Transformation to the Standard General Markup Language[END_REF][START_REF] Molli | Synchronous, Asynchronous, Multi-Synchronous Environments[END_REF][START_REF] Ignat | Customizable Collaborative Editor Relying on treeOPT Algorithm[END_REF] various operational transformation approaches for maintaining consistency over tree structures of the document have been proposed.

Members of a team should have the possibility to synchronise their work between pairs of individuals and, therefore, we wanted to develop a general synchronisation mechanism that works in peer-to-peer networks. Some of the existing operation transformational approaches such as FORCE [START_REF] Shen | Flexible Merging for Asynchronous Collaborative Systems[END_REF] and SAMS [START_REF] Molli | Synchronous, Asynchronous, Multi-Synchronous Environments[END_REF] rely on a central repository where changes done by users are published and a user can synchronise their local changes only against the repository. These approaches are limited to asynchronous collaboration over a shared repository and they cannot be applied for peer-to-peer communication.

Most of the approaches for maintaining consistency adopt an automatic way for merging concurrent changes and they do not deal with conflicts. In FORCE [START_REF] Shen | Flexible Merging for Asynchronous Collaborative Systems[END_REF] a flexible merging approach has been proposed where rules for the detection of conflicts between pairs of operations are specified. However, this approach adopts automatic merging and local changes are adopted if conflict occurs. Users are not allowed to manually choose between changes that are in conflict. Moreover, the FORCE approach is not applicable in peer-to-peer networks.

Approaches for merging hierarchical documents such as SGML [START_REF] Davis | Generalizing Operational Transformation to the Standard General Markup Language[END_REF], XML and CRC (Class, Responsibility, Collaboration) documents [START_REF] Molli | Synchronous, Asynchronous, Multi-Synchronous Environments[END_REF] and the treeOPT approach described in [START_REF] Ignat | Customizable Collaborative Editor Relying on treeOPT Algorithm[END_REF] for merging any hierarchical documents also adopt an automatic solution for merging and do not allow the manual intervention of users. Moreover, some specific rules for the concurrent deletion of a node in the tree and modifications referring to that node are considered. The merging approaches described in [START_REF] Molli | Synchronous, Asynchronous, Multi-Synchronous Environments[END_REF] and [START_REF] Ignat | Customizable Collaborative Editor Relying on treeOPT Algorithm[END_REF] consider that, once a node in the tree is deleted, any concurrent changes referring to that node are discarded. The merging approach in [START_REF] Davis | Generalizing Operational Transformation to the Standard General Markup Language[END_REF] excises the deleted nodes, but keeps them as separate structures. In this way, concurrent operations to the deletion of the node and targeting the deleted node are executed. However, the approach does not explain when and how the excised nodes are reassembled into the initial tree document. We therefore see the need of an approach that keeps the deleted nodes and considers changes performed on them during the merging process. A resolution mechanism would present conflicts to the users and their decision would determine whether or not the delete nodes are reassembled in the initial document.

Dealing with conflicts in an easy manner requires a suitable model of the document. Even if the structure of the document is hierarchical, the operational transformation adopted by most existing approaches [START_REF] Molli | Synchronous, Asynchronous, Multi-Synchronous Environments[END_REF][START_REF] Davis | Generalizing Operational Transformation to the Standard General Markup Language[END_REF] is similar to the approach for linear structures and does not take advantage of the tree structure of the document. The existing operation-based approaches maintain a single history buffer where the executed operations are kept. Operations are not associated with the structure of the document and therefore it is difficult to select which operations refer to which node in the document. This fact has limitations for the definition and resolution of 1 conflicts. For instance, they do not allow the possibility of defining that any operations that refer to the same node are conflicting and the user can later choose one of the versions of the node. To determine which operations from the history buffer refer to which node is very complex, since the structure of the document is dynamically changed with the execution of each operation.

Multi-level editing used in the treeOPT approach [START_REF] Ignat | Customizable Collaborative Editor Relying on treeOPT Algorithm[END_REF] involves logging edit operations that refer to each node. In this way, conflicting operations that refer to the same subtree of the document are easily detected by the analysis of the histories associated with the nodes belonging to the subtree. Therefore, the resolution of conflicts is simplified in comparison to the approaches using a single history buffer.

In this paper we present an extension of the treeOPT approach that handles conflicts in an appropriate way including the ones involving concurrent deletions of nodes and modifications of those nodes. The treeOPT approach recursively applies an operational transformation algorithm working for linear structures over the hierarchical document levels. Our method was to combine treeOPT with a linear operational transformation algorithm that works in peer-topeer networks and maintains the structure of the deleted nodes. As SOCT2 together with the tombstone transformation functions [START_REF] Oster | Proving Correctness of Transformation Functions in Collaborative Editing Systems[END_REF] is an operational transformation algorithm that works in peer-to-peer networks and the tombstone transformational approach deals with tombstone entities, we decided to combine treeOPT with SOCT2 and the tombstone transformational approach. In this paper we show how the multi-level editing approach together with the tombstone transformational approach supports dealing with conflicts.

We start by presenting in the next section the treeOPT approach. We then go on by describing in the third section the operational transformation approach that deals with tombstone entities. The fourth section of this paper presents how the adaptation of the treeOPT approach with the tombstone transformational approach offers users a flexible way of handling conflicts. In the last section we provide some concluding remarks and some future work directions.

THE TREEOPT APPROACH

The treeOPT approach can be applied for maintaining consistency for collaboration over hierarchical structured documents, such as textual [START_REF] Ignat | Customizable Collaborative Editor Relying on treeOPT Algorithm[END_REF] and XML [START_REF] Ignat | Flexible Collaboration over XML Documents[END_REF] documents. XML documents conform to a tree model by definition. Text documents can also be structured using a hierarchical model. A text document is composed of a list of paragraphs, each paragraph as a list of sentences, each sentence as a list of words and each word as a list of characters. A document has associated various levels, such as the document (level 0), paragraph (1), sentence (2), word (3) and character (4) in the case of text documents. Each node in the hierarchical structure will keep a history of operations of insertions and deletions of child nodes. We present in what follows our definition for a node in the tree.

A node N of a document is a structure of the form N =< parent, children, length, history, content >, where

• parent is the parent node for the current node • children is an ordered list [child 1 , ..., child n ] of child nodes • length is the length of the node in terms of the number of leaf nodes,

length = 1, if N is a leaf node n i=1 length(child i ), otherwise • history is an ordered list of operations executed on child nodes • content is the textual content of the node content = aCharacter, if N is a leaf node n i=1 content(child i ), otherwise
We define the level of a node to be the height of the node, i.e. the length of the path from the root to the node.

An operation is specified by its type, position in the tree and its content. The type of an operation can be insertion or deletion. The position of an operation is represented by a vector of indexes specifying the path starting from the root to the node where the operation has been applied. The content of an operation is represented by the node that is inserted or deleted. An operation has associated a state vector [START_REF] Ellis | Concurrency Control in Groupware Systems[END_REF] and the identifier of the site that generated the operation. The level of an operation is the level of the node in whose history the operation is kept.

After its execution, an operation is added to the history of the parent node of the node that is inserted or deleted. Due to the fact that the position of an operation is the path to the node where the operation is applied, we represented the position of an operation stored in a history buffer by the position of the target node relative to its parent. For instance, the operation with the absolute position representation InsertWord(3,2,4,"collaborative") of inserting the word "collaborative" in paragraph 3, sentence 2 as the 4th word, will be kept in the history associated with sentence 2 in paragraph 3 with the relative position representation Insert-Word(4,"collaborative"). We are going to refer to an operation given by its absolute position as a composite operation and to an operation viewed at a certain level as a simple operation. Operations in history buffers are viewed as simple operations at the level of the node to which they belong. But, they can be viewed as composite operations taking into account the position of the node to which they belong. Composite operations are characterised by a position vector, while simple operations are characterised by a position index.

Local operations are immediately executed and added to the corresponding history buffers. For the integration of a remote operation into the corresponding history buffer, the treeOPT approach recursively applies an existing operational transformation algorithm, such as GOT [START_REF] Sun | Achieving Convergence, Causality-preservation, and Intention-preservation in Real-time Cooperative Editing Systems[END_REF], GOTO [START_REF] Sun | Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements[END_REF] or SOCT2 [START_REF] Suleiman | Serialization of Concurrent Operations in a Distributed Collaborative Environment[END_REF], over the hierarchical document structure. In what follows we present the implementation of the treeOPT algorithm using the SOCT2 algorithm. Given a new causally ready composite operation, O, the root node of the hierarchical representation of the local copy of the document, RN, and the number of levels in the hierarchical structure of the document, L, the execution form of O is computed. In the case of text documents structured into paragraphs, sentences, words and characters, L=4 and RN=document. Determining the execution form of a composite operation requires finding the elements of the position vector corresponding to a coarser or equal granularity level than that of the composite operation. For each level of granularity l, starting with paragraph level and ending with the level of the composite operation, the SOCT2 algorithm is applied to find the execution form of the corresponding regular operation. SOCT2 does not perform transformations on composite operations, but rather on simple ones. Therefore, we had to define the function Composite2Simple, that takes as arguments a composite operation, together with the granularity level at which we are currently transforming the operation, and returns the corresponding simple operation [START_REF] Ignat | Tree-based Model Algorithm for Maintaining Consistency in Real-time Collaborative Editing Systems[END_REF]. The operational transformation algorithm is applied to the history of the current node CN whose granularity level is l-1. Recall that, for example, to find the corresponding paragraph position, transformations need to be performed against the operations kept in the document history. The lth element in the position vector will be equal to the position of the execution form of the simple operation. If the current granularity level l is equal to the level of the composite operation, the composite operation is executed and the execution form of the simple operation is stored into the history buffer associated with the current node. Otherwise, the processing continues with the next finer granularity level, with CN being updated accordingly. The function SOCT2(O, HB) takes as parameters a causally-ready regular operation O and a history buffer HB and returns the execution form of O.

TOMBSTONE TRANSFORMATION FUNCTIONS

As previously mentioned, for dealing with conflicts in the face of concurrent delete operations that target nodes of the hierarchical structure, we adapt the treeOPT approach to mark deleted entities as invisible, but do not remove these entities from the structure of the document. To our knowledge, the only existing transformation functions that deal with tombstone entities are those proposed in [START_REF] Oster | Proving Correctness of Transformation Functions in Collaborative Editing Systems[END_REF]. These transformation functions are presented below: Besides their adaptation for maintaining the structure of deleted nodes, these transformation functions have some other advantages. First, the definition of inverses of the forward transformation functions [START_REF] Oster | Proving Correctness of Transformation Functions in Collaborative Editing Systems[END_REF] required by the SOCT2 algorithm is straightforward since they are injective functions. Second, as far as we are aware, these transformation functions are the first ones that satisfy both mandatory consistency properties [START_REF] Suleiman | Serialization of Concurrent Operations in a Distributed Collaborative Environment[END_REF] named C 1 and C 2 . Consequently, our treeOPT-SOCT2 algorithm is the first operational transformation algorithm applicable in peer-to-peer environments that maintains consistency of replicated hierarchical documents.

DEALING WITH CONFLICTS

We define two concurrent operations as being in conflict if they modify the same conflict node or any of its children. Conflict nodes can be defined by specifying a certain level of granularity for conflict in which case all nodes of that granularity level are considered conflict nodes. Certain nodes in the hierarchical structure can also be specified as conflict nodes.

When an operation is integrated into the document structure, the tree is traversed from top to bottom till the level of the operation is reached and the operation can be integrated into its corresponding history buffer. If during this integration a conflict node is encountered, a check is done to see if concurrent operations have been performed on the conflict node. Detection of conflict is done by the analysis of the histories associated with conflict node and all its child nodes. If the history buffers distributed throughout the subtree rooted at the conflict node contain an operation concurrent with the remote operation, a conflict is detected and according to a resolution policy the conflict is resolved. The resolution policy can be automatic or manual. In the automatic resolution policy, the operations that win a conflict are decided according to certain rules. For instance, the operations that win a conflict can be decided according to priorities assigned to the sites that generated the operations. The manual resolution policies require user intervention for choosing between conflicting operations.

If an integration algorithm is chosen that deletes the nodes in the hierarchy once a deletion was performed, conflicts between the deletion and any other operation concurrently performed on the deleted subtree cannot be detected. We therefore adopted a transformation algorithm that does not delete nodes, but marks them for deletion. In what follows we analyse the cases that show the benefit of choosing to mark nodes for deletion instead of their physical deletion. These cases are the ones involving the deletion of a node of the tree and the concurrent insertion inside the node that is deleted. These two cases are distinguished by the order of execution of the two concurrent operations, i.e. insertion followed by deletion or deletion followed by insertion. Suppose that the level of the insertion operation is l 1 and that of the deletion operation is l 2 . The cases that need special attention are the ones where l 1 > l 2 .

We analyse first the case when the deletion operation was executed and the concurrent insertion operation has to be integrated. When deletion is performed, the node targeted by deletion is marked as invisible, but further considered when a remote operation has to be integrated. When a remote insertion operation has to be integrated, ancestors of nodes to be deleted and marked as conflict nodes will be detected during processing, showing that the delete and remote insert are concurrent. If a conflict node is a descendant of the node to be deleted and an ancestor of the node to be inserted, conflict is also detected when the processing reaches the conflict node. Processing is also called for the deleted nodes and when processing reaches the conflict node, conflict is detected as the conflict node is marked as deleted.

The second case to be analysed is the one when the insertion operation is executed first and the concurrent deletion operation has to be integrated. If the conflict node is an ancestor of the node to be deleted, conflict is detected when the conflict node is reached in the processing phase. The insert operation in one of the histories distributed throughout the tree rooted at the conflict node will be detected as being in conflict with the remote delete operation. After a deletion is performed, checking for conflicts has to be performed also on the deleted subtree. Processing is therefore further performed and if a conflict node is detected during processing and the conflict node is an ancestor of the inserted node, the conflict is detected as the insertion operation is performed on a node marked as deleted.

If deleted nodes are removed from the document, concurrent changes performed on the deleted parts of the tree are not considered and therefore no conflicts are presented to the user. By using the tombstone transformational approach, the operations concurrent with deletions of nodes in the document and targeting concurrently deleted parts of the document are performed. In this way, if a conflict node is set that detects the conflict between deletion and the concurrent change, users are presented with the two conflicting versions of the conflict node: first one showing the deleted parts of the document (for e.g. by lines through deleted text) and the second one showing concurrent modifications done on the conflict node.

For the resolution method, an undo mechanism has to be provided to cancel some operations performed. An undo mechanism for the SOCT2 algorithm using the TTF transformation functions has been provided in [START_REF] Weiss | Annulation de groupe dans les éditeurs collaboratifs[END_REF] and we are currently working on the integration of the undo mechanism with treeOPT.

CONCLUSIONS AND FUTURE WORK

In this paper we presented how the application of the tombstone transformational approach recursively over the levels of the document by using the treeOPT approach offers support for conflict handling in peer-to-peer networks. The paper also shows that the tombstone transformational approach is general and can be applied for hierarchical structures. We are currently investigating the multi-level editing undo and building a prototype based on the ideas presented in this paper.

  T(ins(p1 , el 1 , sid 1 ), ins(p 2 , el 2 , sid 2 ){ if (p 1 < p 2 ) return ins(p 1 , el 1 , sid 1 ) else if (p 1 = p 2 and sid 1 < sid 2 ) return ins(p 1 , el 1 , sid 1 ) else return ins(p 1 + 1, el 1 , sid 1 ) } T (ins(p 1 , el 1 , sid 1 ), del(p 2 , sid 2 )) { return ins(p 1 , el 1 , sid 1 ) } T (del(p 1 , sid 1 ), ins(p 2 , el 2 , sid 2 )) { if (p 1 < p 2 ) return del(p 1 , sid 1 ) return del(p 1 + 1, sid 1 ) } T (del(p 1 , sid 1 ), del(p 2 , sid 2 )) { return del(p 1 , sid 1 ) }


Mayeur Basile
email: basile.mayeur@inria.fr

Tao

Riad Akrour
email: riad.akrour@inria.fr

Michele Sebag
email: michele.sebag@inria.fr

Direct Value Learning: a Rank-Invariant Approach to Reinforcement Learning

Taking inspiration from inverse reinforcement learning, the proposed Direct Value Learning for Reinforcement Learning (DIVA) approach uses light priors to generate inappropriate behaviors, and uses the corresponding state sequences to directly learn a value function. When the transition model is known, this value function directly defines a (nearly) optimal controller. Otherwise, the value function is extended to the state-action space using off-policy learning. The experimental validation of DIVA on the mountain car problem shows the robustness of the approach comparatively to SARSA, based on the assumption that the target state is known. The experimental validation on the bicycle problem shows that DIVA still finds good policies when relaxing this assumption.

Introduction

In the last decade, significant advances have been made in reinforcement learning (RL) by exploiting nearly-optimal expert demonstrations in the framework of inverse reinforcement learning [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF], learning by imitation [START_REF] Schaal | Computational approaches to motor learning by imitation[END_REF], or learning from demonstrations [START_REF] Konidaris | Constructing skill trees for reinforcement learning agents from demonstration trajectories[END_REF]. New approaches, referred to as preference-based RL and allegedly requiring less expertise from the teacher, have also been proposed [START_REF] Wilson | A bayesian approach for policy learning from trajectory preference queries[END_REF][START_REF] Akrour | Preference-Based Policy Learning[END_REF][START_REF] Jain | Learning trajectory preferences for manipulators via iterative improvement[END_REF].

In this paper, a new approach based on learning-to-rank and aimed at directly learning the value function, referred to as Direct Value Learning for Reinforcement Learning (DIVA), is presented, together with a theoretical and experimental analysis. After introducing the formal background and the state of the art in section 2, section 3 gives an overview of DIVA. DIVA is empirically validated on the mountain car and the bicycle balancing problems comparatively to the state of the art in section 4. The paper concludes with some perspectives for further study.

Position of the problem

After the standard reinforcement learning background [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF], the RL goal is formalised as a Markov decision problem (MDP) (S, A, p, r), with S and A respectively the state and action spaces, p : S × A × S → IR the transition model, with p(s, a, s ′ ) the probability of reaching state s ′ after selecting action a in state s, and r : S → IR the reward function 1 .

Mainstream RL approaches rely on the notion of value function. Letting π : S → A denote a policy, mapping each state onto an action, the value function V π associates to each state the (expected) 1 In the canonical setting [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF] r : (S, A) → IR 1 discounted cumulative reward gathered by following π:

V π (s) = r(s) + γ s ′ p(s, π(s), s ′ )V π (s ′ )
Value iteration and policy iteration algorithms [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF][START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF] proceed by iterating a two-step process, computing the value function associated to the current policy policy, and computing the greedy policy associated to this value function, such that

π V (s) = argmax a { s ′ p(s, a, s ′ )V (s ′ )}
The limitation of these approaches is twofold. On the one hand, a good reward function requires significant expertise in the domain application and in the underlying optimisation algorithm. On the other hand, the exploration of the state-action search space required to enforce the convergence of the RL process hardly scales up with the size of the state and action space.

The celebrated Inverse Reinforcement Learning (IRL) approach [START_REF] Konidaris | Constructing skill trees for reinforcement learning agents from demonstration trajectories[END_REF][START_REF] Abbeel | Apprenticeship Learning and Reinforcement Learning with Application to Robotic Control[END_REF] addresses both limitations, based on the exploitation of nearly optimal demonstrations provided by the expert. These demonstrations are used to infer the reward function and guide the exploration toward good regions of the state-action pairs. The limiting factor then becomes the expertise of the human teacher. A new setting, the preference-based RL approach [START_REF] Wilson | A bayesian approach for policy learning from trajectory preference queries[END_REF][START_REF] Akrour | Preference-Based Policy Learning[END_REF][START_REF] Jain | Learning trajectory preferences for manipulators via iterative improvement[END_REF] proceeds by asking the user in the loop to rank state-action pairs [START_REF] Knox | Training a robot via human feedback: A case study[END_REF], fragments of behaviors [START_REF] Wilson | A bayesian approach for policy learning from trajectory preference queries[END_REF], or full-length trajectories [START_REF] Akrour | Preference-Based Policy Learning[END_REF][START_REF] Jain | Learning trajectory preferences for manipulators via iterative improvement[END_REF].

All abovementioned approaches critically depend on the available expert knowledge. The expert knowledge is used primarily to represent the problem (state and action spaces). It is further used to specify the target behavior through the reward function, or demonstrations, or preferences. The general trendfrom specifying the reward function to expressing preferences on trajectoriesgoes toward relaxing the expertise requirement, and correspondingly increasing the autonomy of the learner.

Along this line, the new Direct Value Learning for Reinforcement Learning RL approach, only requiring light expert priors, is presented.

Direct Value Learning

This section gives an overview of the DIVA algorithm. Notation In the following, tr(s, a) denotes the (random variable) state observed after executing action a in state s. Letting f : S → IR, the expectation of f (s ′ ) according to distribution p(s, a, s ′ ) is noted E s ′ ∼s,a [f (s ′ )] and by abuse of notation E[f (tr(s, a))]. It will be assumed in the remainder that state space S is a subset of IR d , with tr(s, a) = E s ′ ∼s,a [tr(s, a)] ∈ IR d .

Principle

DIVA is based on the simple idea that, while it requires a significant expertise to demonstrate a good behavior, demonstrating a bad behavior is quite easy in many RL problems, e.g. by random action selection. A bad behavior manifests itself by visiting states with decreasing values; such a sequence of states is referred to as Murphy State Sequence (MSS) in honor of the Murphy's law 2 .

M SS = (s 1 , . . . s T ) s.t. V (s t ) > V (s t+1 )
The core assumption of the DIVA approach is that, if the target state is known, a constant behavior starting from the target state generates a MSS; otherwise, a random behavior starting from a random state generates a MSS. A set of Murphy State Sequences defines a learning to rank problem: Given M SS (1) , . . . M SS (J) , Find U : S → IR s.t. ∀j = 1 . . . J, ∀t ∈ 1 . . . T (j) -1, U (s

(j) t ) > U (s (j) t+1 ) (1)
Pb ( 1) is solved using state-of-art ranking algorithms and its solution is referred to as utility function. By construction, utility function U is only defined up to a monotonous transformation: for any monotonous scalar function g (g : IR → IR, x > x ′ ⇒ g(x) > g(x ′ )), g • U also is solution of (1). Two functions U and U ′ are said to be rank-invariant equivalent, noted U ≡ r U ′ , iff there exists a monotonous scalar function g such that U ′ = g • U .

Model-based setting

In the case of a deterministic transition model, let the greedy policy π U defined from utility function U be defined as π U (s) = argmax a {U (tr(s, a)). It follows immediately that two rank-invariant equivalent utility functions define the same greedy policy:

U ≡ r U ′ ⇒ π (U ) = π (U ′ )
In the case of a stochastic transition model, let tr(s, a) denote the next state expectation upon selecting action a in state s. Let the U -greedy policy π U be defined as:

π U (s) = argmax a {U (tr(s, a)))} (2)
For U a rank-invariant equivalent of value function V , the value loss entailed by following π U instead of π V is bounded under mild assumptions:

Proposition 1 Let S ⊆ IR d .
Let U and V be two rank-invariant equivalent functions mapping S onto IR, with V differentiable and Lipschitz with constant M (∀s,

s ′ ∈ S, |V (s) -V (s ′ )| < M ||s - s ′ ||).
Let us further assume that the transition model noise is bounded 3 , with ∀(s, a) ||tr(s, a)tr(s, a))|| < c. Let a * ,V (s) denote the best action associated to state s with respect to V ,

a * ,V (s) = argmax a {E[V (tr(s, a))]}
If the V-margin of a * ,V (s) w.r.t all other actions is greater than 2M c (E[V (tr(s, a * ,V (s)))] > E[V (tr(s, a ′ ))] + 2M c for all a ′ = a * ,V (s)), then

π U (s) = a * ,V (s)
and therefore greedy policies based on V and U select same action in s.

Otherwise, the V-value loss entailed by following π U (s) instead of selecting a * ,V (s) is at most 2M c.

Proof The proof follows from using Taylor-Lagrange decomposition on V and upper-bounding the remainder.

Algorithm In the case where the transition model is known, the DIVA algorithm learns the utility function U from problem (1), and follows the greedy policy based on U (2).

Discussion Whether utility function U is a rank-invariant equivalent of the optimal value function V * depends on the representativity and noise of the Murphy state sequences. In practice however, what matters is whether U preserves the state ordering defined by V * in the neighborhood of the good trajectories (more on this in section 5).

Model-free setting

When the transition model is unknown, the DIVA approach is extended to learn an approximation of the quality function Q(s, a), by taking inspiration from [START_REF] Ernst | Tree-based batch mode reinforcement learning[END_REF]. Intuitively, given the utility function U and triplets (s 1 , a 1 , s ′ 1 ) and (s 2 , a 2 , s ′ 2 ), one requires that (s 1 , a 1 )

≻ (s 2 , a 2 ) if U (s ′ 1 ) ≻ U (s ′ 2 )
. More formally, model-free DIVA proceeds as follows. A set E of triplets (s, a, s ′ ) is generated, and ordering constraints on S × A are defined with: A Qutility function Q U on S × A is learned from the above ordering constraints, and policy π Q,U is defined as:

∀((s 1 , a 1 , s ′ 1 ); (s 2 , a 2 , s ′ 2 ) in E s.t. U (s ′ 1 ) ≻ U (s ′ 2 ), (s 1 , a 1 ) ≻ (s 2 , a 2 )
π Q,U (s) = argmax a {Q U (s, a)} (3)
It is straightforward to show that if Q and Q ′ are rank-invariant equivalent on S × A, then they induce the same greedy policy:

Proposition 2 If ∀s, ∀(a i , a j ), (U (tr(s, a i )) > U (tr(s, a j )) ⇒ (Q U (s, a i ) > Q U (s, a j )) then argmax a {Q U (s, a)} = argmax a {U (tr(s, a))}
Some care must be exercised to prevent learning trivial quality functions. Typically if s 1 and s 2 have very different utility (U (s 1 ) ≫ U (s 2 )) then the learned quality function Q U hardly reflects the action impact. In practice, pairs of triplets (s 1 , a 1 , s ′ 1 ) and (s 2 , a 2 , s ′ 2 ) are uniformly sampled subject to ||s 1s 2 || < κ with κ a fraction of the state space diameter (typically 5 to 10%), and

ordering constraint (s 1 , a 1 ) ≻ (s 2 , a 2 ) is generated if U (s 1 ) -U (s ′ 1 ) > U (s 2 ) -U (s ′ 2 ).

Experimental Validation

This section reports on the empirical validation of DIVA comparatively to SARSA [START_REF] Sutton | Generalization in reinforcement learning: Successful examples using sparse coarse coding[END_REF]. Utility and Qutility functions are computed using RankingSVM with Gaussian kernel [START_REF] Joachims | Training linear svms in linear time[END_REF] .

The mountain car problem

The mountain car problem is defined with same setting as in [START_REF] Sutton | Generalization in reinforcement learning: Successful examples using sparse coarse coding[END_REF], using a 2D state space (position, speed), and a discrete action space ({backward, neutral position, forward}). The friction coefficient ranges from 0 to .02.

In each run, a single 1,000 time step Murphy state sequence is generated by starting from the target state on the top of the hill and selecting the constant action "neutral" (Fig1(a)), yielding a very

The Bicycle problem

With same setting as [START_REF] Randlov | Learning to drive a bicycle using reinforcement learning and shaping[END_REF], the state space of the bicycle riding problem is IR 4 (the angles of the handlebar and of the bicycle to the vertical; associated angular velocities); the action space is discrete (do nothing, turn the handlebar left or right, lean the rider left or right). The goal is to maintain the bicycle in equilibrium for 30,000 time steps. From the initial (0, 0, 0, 0) state, a random controller will make the bicycle fall after approximately 200 steps.

Model-based setting Murphy state sequences are generated by following a random controller starting from a random state. Due to the temporal discretisation of the transition model [START_REF] Randlov | Learning to drive a bicycle using reinforcement learning and shaping[END_REF], action a t affects the angle values only in step t + 2. Some look-ahead is thus required: policy π U selects the action that maximises the maximum of the Utility at state s t+2 :

π U (s) = â * = argmax a (max a ′ U (tr(tr(s, a), a ′ )))
Fig. 3 shows that 20 MSS of length 5 generated by a random controller yield a competent utility function (keeping the bicycle in equilibrium for over 30,000 steps) with high probability (100 out of 100 runs).

Model-free setting The ordering constraints on the state-action pairs must also account for the temporal discretisation. Formally, considering sequences

(s 1 , a 1 , s ′ 1 , a ′ 1 , s ′′ 1 ) and (s 2 , a 2 , s ′ 2 , a ′ 2 , s ′′ 2 ) (with random a ′ 1 and a ′ 2 ), constraint (s 1 , a 1 ) ≻ (s 2 , a 2 ) is generated if U (s ′′ 1 ) -U (s 1 ) > U (s ′′ 2 ) - U (s 2 ).
5,000 pairs are required to achieve same performances as in the model-based setting (with proximity threshold κ = 1%, as the state-action space is bigger than for the mountain car, R 4 instead of R 2 ).

Discussion and Perspectives

The main contribution of this paper is i) to suggest that utility functions, rank-invariant equivalent of the (nearly) optimal value functions, can support satisfactory policies; ii) to show that such utility functions can be learned from bad behaviors. It is believed that this approach makes a step toward reinforcement learning with light prior knowledge, as generating bad behaviors usually requires much less expertise than good behaviors.

A first limitation of the DIVA approach is some look-ahead can be required to compute the utilitybased policy, depending on the latency of the transition model. A second limitation is that, in some problems e.g. the bicycle driving task, it might be hard to generate bad behaviors. A perspective to alleviate this limitation is to consider bad behaviors with additional constraints. Further work will consider richer state spaces (e.g. robot controllers with some dozen degrees of freedom), and investigate the DIVA scalability. Other ranking approaches with linear complexity will be considered [START_REF] Burges | Learning to rank with non-smooth cost functions[END_REF]. Finally, DIVA will be combined with approximate RL methods by taking inspiration from [START_REF] Kim | Learning from limited demonstrations[END_REF].

  DIVA learnt trajectory (e) DIVA decision map (f) SARSA decision map Figure 1: The mountain car problem: Comparative evaluation of DIVA and SARSA in the model-free setting, on two representative runs (friction = .01). Decision maps report the best action for each state in the 2D (position, speed) space (red: forward, blue: backward, green: neutral)

  number of steps to reach the goal (after learning) level of friction

Figure 2 :

 2 Figure 2: Mountain car: Number of time steps to reach the goal for DIVA and SARSA vs friction value (av. on 20 runs)

Figure 3 :

 3 Figure 3: Bicycle (model-based setting): Fraction of success of DIVA w.r.t. number and length of MSS

If something can go wrong, it will.

While this assumption does not hold for Gaussian noise, it is realistic in e.g. robotic settings, where the distance between two consecutive states is bounded anyway due to mechanical constraints.