M Hadjioannou

C Douthe

C J Gantes

Influence of cold bending on the resistance of wide flange members

Cold roller bending is commonly used for bending straight members with hot rolled wide-flange sections to create arches. This process induces plastic deformations along the member, so that it can acquire the desired curvature. The resulting residual stress distribution is different from the wellknown residual stress pattern due to hot rolling. Extensive studies have shown that the influence of residual stresses due to hot rolling on the resistance of wide-flange steel sections is non negligible.

On the contrary, the residual stress pattern due to roller bending has been only recently clearly identified and its effects on the elasto-plastic behavior of curved members have not been studied sufficiently. Thus, in this paper the influence of such residual stresses on the resistance of both wideflange sections and corresponding arch members is investigated in detail. Taking into consideration the residual stress pattern due to cold bending, interaction diagrams are developed for combined axial load and bending moment, as well as buckling curves for cold bent steel arches. The results are quantified and compared with those for hot-rolled and stress free members. This will allow designers to appreciate the available margins of safety when using standard residual stress pattern for cold bent members. Furthermore, the results suggest the necessity for the development of buckling curves for curved members including initial imperfections.

Introduction

Roller bending is nowadays the most common and cost-effective way to produce curved members. Such members are generally made from initially straight hot rolled wide-flange profiles and are used in various structural applications such as arched roofs, atriums and bridges. Roller bending, or cold bending as it is also called, is an iterative process. A straight member passes through three rollers (Figure 1). Plastic deformations are induced at the part of the member which is between the two outer rollers. As the member is rolled all over its length, plastic deformations are induced along the entire length of the member so that it gradually becomes an arch. In each subsequent iteration, the roller in the middle moves vertically towards the other two, in order to increase the curvature. The number of iterations depends on the desired final curvature of the arch. In each pass of the member through the roller, its curvature increases only by small amount. The additional curvature that the member can gain after each pass through the machine is limited due to the local buckling that may occur. In general, as wide-flange sections are prone to local buckling, there are limitations on the maximum curvature that the member can acquire with this process. In order to prevent local buckling of the web, two smaller rollers are sometimes used on the tension flange. They also prevent it from transverse bending known as "Brazier effect" or "ovalization" [START_REF] Brazier | On the flexure of thin cylindrical shells and other "thin" sections[END_REF]. A detailed description of the roller bending process has been presented by Bjorhovde [START_REF] Bjorhovde | Cold bending of wide-flange shapes for construction[END_REF]. The tension and compression flanges are denoted in this paper as top and bottom flange, respectively (Figure 1). As mentioned above, initially straight hot rolled wide-flange profiles are used for roller bending. It is well known that, due to their manufacturing process, such profiles are not stress free. They have an internally self-equilibrated stress distribution, the so-called residual stresses. Such residual stresses occur due to uneven cooling of the section, i.e. flange tips and middle part of the web tend to cool faster than the other parts of the section. This results in compressive (-) residual stresses at the flange tips and the middle part of the web and tensile (+) stresses at the web to flange junctions.

The residual stress distribution in straight hot rolled wide flange sections is well documented.

Various pertinent experiments have been carried out, as presented by Huber and Beedle [START_REF] Huber | Residual stress and the compressive strength of steel[END_REF], Beedle and Tall [START_REF] Beedle | Basic column strength[END_REF], Jez-Gala [START_REF] Gala | Residual stresses in rolled I-sections[END_REF], Mas and Massonet [START_REF] Mas | Part prise par la belgique dans les recherches experimentales de la convention europeene des associations de la construction metallique sur la flambement centriques des barres en acier doux[END_REF], Lay and Ward [START_REF] Lay | Residual stresses in steel sections[END_REF], Galambos [START_REF] Galambos | Guide to stability design criteria for metal structures[END_REF], Young [START_REF] Young | Residual stresses in hot rolled members[END_REF], ECCS [START_REF] Stability | System, Ultimate limit state calculations of sway frames with rigid joints[END_REF]. Figure 3 represents the residual stress distribution proposed by Young [START_REF] Young | Residual stresses in hot rolled members[END_REF], assuming a parabolic distribution. Specific stress values for this model in N/mm 2 are:

  =       1 -165 1- 2.4 w c f ht bt σ ,   =       2 -100 1.5- 2.4 w c f ht bt σ ,   =       100 0.7 - 2 w t f ht bt σ (1)
where 1 c σ , 2 c σ and t σ are the compressive stresses at the tips of the flanges and in the middle of the web, and the tension stress at the intersection of the web to the flanges, respectively. Contrary to other residual stress models, this one suggests that the absolute values of residual stresses are independent of yield stress. In Figure 4 a more simplified residual stress distribution proposed by ECCS [START_REF] Stability | System, Ultimate limit state calculations of sway frames with rigid joints[END_REF] is illustrated, where linear variation of stresses is assumed while their values depend on the steel grade.

Figure 3: Residual stress distribution due to hot rolling process [START_REF] Young | Residual stresses in hot rolled members[END_REF] Figure 4: Residual stress distribution due to hot rolling process [START_REF] Stability | System, Ultimate limit state calculations of sway frames with rigid joints[END_REF]

: (a) h/b≤1.2, (b) h/b>1.2
The influence of residual stresses due to hot rolling on the behavior and stability of straight members has been investigated in numerous studies [START_REF]Manual on stability of steel structures[END_REF][START_REF] Fukumoto | Evaluation of column curves based on probabilistic concept[END_REF][START_REF] Sophianopoulos | The Eefect of thermal-induced residual stresses on the elastoplastic behavior and capacity of non-slender steel I-shaped members under combined loading[END_REF][START_REF] Strating | Computer simulation of the E.C.C.S. buckling curve using a monte-carlo method[END_REF] and was shown to be, in general, not negligible. This is reflected by the inclusion of residual stress models and corresponding buckling curves in various construction standards such as Eurocode 3 [START_REF]Compression members, in: Eurocode 3: Design of steel structures -Part 1-1: General rules and rules for buildings[END_REF] and AISC Steel Construction

Manual [START_REF] Construction | Design of members for compression[END_REF].

However, when an initially straight member made of hot rolled wide-flange profile is curved into its desired arch shape, the residual stress pattern due to hot rolling is removed and a new, different residual stress pattern due to curving is induced. Studies on the influence of residual stresses on roller bent steel arches have been performed by Komatsu and Sakimoto [START_REF] Komatsu | Ultimate load carrying capacity of steel arches[END_REF], Sakimoto et al. [START_REF] Sakimoto | Experimental study on the ultimate strength of steel arches[END_REF] and Pi and Trahair [START_REF] Pi | Out-of-plane inelastic buckling and strength of steel arches[END_REF]. However, all these studies were based on a residual stress pattern of straight sections (hot rolling patterns similar to that of Figure 4). However, analytical [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF], experimental [START_REF] Spoorenberg | Experimental investigation of residual stresses in roller bent wide flange steel sections[END_REF] and computational [START_REF] Spoorenberg | Finite element simulations of residual stresses in roller bent wide flange sections[END_REF] studies have shown that this is not the actual residual stress distribution in such members. Even if these studies have shown that the influence of material nonlinearities on the resistance of arches is smaller than that of geometric nonlinearities, it must be verified that this is still true for residual stresses induced by cold bending.

Spoorenberg et al. [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF] have recently proposed a residual stress pattern especially developed for cold bent wide flange sections. This pattern is based on strong evidence, since the results of detailed experimental [START_REF] Spoorenberg | Experimental investigation of residual stresses in roller bent wide flange steel sections[END_REF] and computational [START_REF] Spoorenberg | Finite element simulations of residual stresses in roller bent wide flange sections[END_REF] studies were combined and included in the proposed residual stress model [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF]. However, no studies on the influence of this well defined residual stress model have been performed to evaluate the effects of cold bending in such members. The aim of the present study is hence to evaluate the response of cold bent members with an approach which will be directly applicable to engineering practice. Therefore, the residual stress pattern for cold bent members is used as an initial stress state for an in-depth investigation of the effects of cold bending.

Firstly, interaction diagrams are developed for defining the elastic and plastic domain at a section level, following the classical methodology illustrated in [START_REF] Sophianopoulos | The Eefect of thermal-induced residual stresses on the elastoplastic behavior and capacity of non-slender steel I-shaped members under combined loading[END_REF] for thermally induced residual stresses.

Then, considerations on the tangent stiffness of the arched member taking into account these residual stresses are used to evaluate their influence on the member stability. Therefore, buckling curves for perfect circular members are developed. A comparison with properties of hot rolled members is finally conducted, in order to conclude on the necessity or not for developing specific capacity curves for curved members. The comparison also gives quantified results about the different influence that cold bent residual stresses have in comparison with hot rolled residual stresses, for which excessive studies have been previously performed.

Residual stresses due to cold bending

A residual stresses distribution due to cold bending proposed by Timoshenko [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF], based on the assumption of a bi-linear material law and employing analytical considerations, is shown in Figure 5,

where α is the ratio between the plastic and elastic section modulus, also known as shape factor. A beam model with uniaxial stresses only is used, and therefore no stress gradient is present along the width of the beam and no plate effects are taken into account. A similar model taking into account the curving radius was proposed by the Steel Construction Institute [START_REF] King | Design of curved steel[END_REF].

Figure 5: Residual stress distribution for roller bent I-sections proposed by Timoshenko [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF] Further analytical and experimental investigations of the residual stresses in various types of crosssections have then been carried out by Weng and White [START_REF] Weng | Residual stresses in cold-bent thick steel plates[END_REF], Weng and Pekoz [START_REF] Weng | Residual stresses in cold-formed steel members[END_REF], Tan et al. [START_REF] Tan | On analysis and measurement of residual stresses in the bending of sheet metals[END_REF].

Regarding the residual stresses in wide-flange sections, the available experimental data are limited.

Spoorenberg et al. [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF] have recently carried out an experimental program focusing on the residual stresses due to cold bending on such sections. Using the sectioning method for their measurements, they validated their method by comparing measurements of residual stresses in straight members with the theoretical thermal stresses and reproduced the same method on members after curving.

They further compared their results with detailed finite element simulations of the roller bending process [START_REF] Spoorenberg | Finite element simulations of residual stresses in roller bent wide flange sections[END_REF] by explicitly modeling the whole process. In their models they included full interaction between the machine parts, i.e. rollers, and workpiece, i.e. steel section.

Based on these, they proposed a residual stress model for roller bent wide flange sections [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF]. Their model is generally applicable within a range of bending radii 1 0

/ 4 0 R h ≤ ≤
and is linearly related to the magnitude of the original yield stress for S235 and S355 steel sections. In this model the residual stress gradients over the web and flange thickness are ignored. For the top flange, a linear stress gradient of 0 .2 y f tensile stress at the flange tips to 0 .2 y f compressive stress at the flange center is proposed (Figure 6). For the bottom flange a bi-linear stress pattern is suggested, with a compressive stress of 0.

Figure 6: Residual stress model for roller bent wide flange sections proposed in [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF] Comparing these values with those proposed by Young [START_REF] Young | Buckling of axially loaded welded steel columns[END_REF] for straight members, reproduced in Eq.( 1), it is noted that in both cases the geometric parameter characterizing the amplitude of residual stresses is the ratio between the flange area (2bt f ) and the web area (ht w ), and that the magnitude of the residual stresses increases with the ratio (bt f /ht w ). However, stresses due to hot rolling are compressive at the flange tips and midst of the web and tensile at the midst of top and bottom flanges and ends of the web. On the contrary, in roller bent sections, the pattern is antisymmetric about the center of gravity of the section and the signs in both flanges are opposite.

The residual stress distribution proposed by Spoorenberg et al. [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF] is well defined, supported by both experimental and numerical results, and it is actually the only residual stress model especially developed for roller bent wide flange sections. It is limited to circular arches curved about their strong axis, it is generally applicable for a certain range of bending radii (10≤R/h≤40) and it is linearly related to the yield stress of the material law, which is consistent with the theoretical model of Timoshenko [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF]. The magnitude and variation of stresses in the two models are however different, particularly in the flanges. This is attributed to the different nature of the two models, as Timoshenko's results are based on a beam model while Spoorenberg's results on a three dimensional solid model. In addition, in [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF] the material law is assumed as bilinear and the initial straight member is assumed as stress free. In reality, steel has strain hardening, which is included in the experimental [START_REF] Spoorenberg | Experimental investigation of residual stresses in roller bent wide flange steel sections[END_REF] and computational [START_REF] Spoorenberg | Finite element simulations of residual stresses in roller bent wide flange sections[END_REF] study of Spoorenberg et al.

The "stress jump" at the web-to-flange junctions in [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF], namely the different stress values at the top or bottom of the web from the corresponding ones in the middle of the top or bottom flange, is also a cause for concern, although this simplification eases the applicability of the model when it is employed analytically. Moreover, Timoshenko's theoretical model assumes that there is no stress variation over the width of the flanges, which seems unrealistic. Considering the fact that during bending the section undergoes large strains, the assumption that plane sections remain plane may be violated and there may be small changes in the section wall and thicknesses (about 1 or 2 %).

Also, the interaction between the rollers of the bending machine and the members may vary from a machine or a section to another and lead to some changes in the presented model. For all these reasons, complementary studies seem necessary and measuring campaigns similar to those for cold formed sections or straight members should be conducted.

Limits of the elasto-plastic domain of roller bent wide flange sections

In spite of the concerns discussed in the previous section, the residual stress model proposed by Spoorenberg et al. [START_REF] Spoorenberg | Proposed residual stress model for roller bent steel wide flange sections[END_REF] is currently the best available alternative for roller bent wide flange section, thus their pattern shown in Figure 6 is used in this study as an initial stress state for the investigation of the limits of the elasto-plastic domain at a section level and then for the development of buckling curves at a member level. The residual stress model due to hot rolling [START_REF] Stability | System, Ultimate limit state calculations of sway frames with rigid joints[END_REF] (Figure 4) is used for comparison. It is assumed that the material is elastic-perfectly plastic, neglecting strain hardening as well as material non-linearities that may be induced by the curving process [START_REF] Spoorenberg | Mechanical properties of roller bent wide flange sections -Part 2: Prediction model[END_REF]. Tensile axial forces and moments that tend to open the arch (increase the radius of curvature) and thus act in the opposite direction to the curving moment are denoted as positive (+), while those that tend to close the arch (decrease the radius of curvature) and thus act in the same direction as the curving moment are denoted as negative (-).

Determination of the elastic domain

In the elastic domain, normal stress at any position over the height of the sections is always smaller that the yield stress. Thus, for any combination of normal force N and bending moment M N , the total stress, including residual stress (Figure 6), is smaller than f y :

N rs y M N z f A I σ + + ≤ (3)
A and I are the area and moment of inertia of the cross-section, respectively, z is the distance from the neutral axis (N.A.) of the section, and σ rs is the residual stress depending on the position over the height of the section. As all these stresses are linearly distributed over the section, the yield stress will be first reached at one of the peaks or extreme values of the residual stress patterns. Depending on the magnitude and direction of normal force and moment, the residual stress peaks at either the web or the flanges may govern first yielding.

Determination of the plastic domain

As for the elastic domain also for the plastic domain, the total stress of the fully yielded section under combined bending and axial force (Figure 7(a)) is the sum of stresses due to applied loads (Figure 7(b)) and residual stresses due to cold bending (Figure 7(c)). It is assumed that the central part of the section undertakes the normal force and the external parts the bending moment. The height of the part undertaking the normal force is denoted as y N and is evaluated from the magnitude of the normal force and the geometrical characteristics of the section. To determine this limit analytically, it must thus be distinguished whether y N includes part of the flanges or is restricted into the web. In most practical cases, y N is within the web and hence, for conciseness of the paper, only this subcase is presented in detail. The normal force in the section (Figure 7(d)) is:

2 w N y rs T N t y f dz σ = -∫ (4)
The corresponding moment M N (Figure 7(e)) is:

N N p py rs F M M M zdF σ = - -∫ (5)
where M p is the total plastic moment resistance of the section ((Figure 7 is within the web, these moments are given by:

P y pl M f W = , 2 N py y w N M f t y = (6)
Repeating these calculations for all values of y N , from zero to h, including the residual stresses, the plastic domain of the section can be defined.

Numerical example

In Figure 8 (a,b) the elastic and plastic domains, respectively, of a HE360B section made of S235 steel subjected to combined bending moment about the strong axis and axial force are illustrated, assuming the residual stress distribution due cold bending shown in Figure 6 and following the process described in sections 3.1 and 3.2. Figure 9 shows the part of the plastic interaction diagram for compressive axial force and bending moment which tends to open the arch. For comparison, the elastic and plastic limits of the stress free section, the section with the residual stress distribution suggested by Timoshenko [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF] (Figure 5) as well as the section with the residual stress distribution due to hot rolling process suggested by ECCS [START_REF] Stability | System, Ultimate limit state calculations of sway frames with rigid joints[END_REF] (Figure 4) are also shown. The values of bending moment and normal force are normalized with respect to the total plastic moment capacity and the total axial capacity of the section, respectively. It is noted that the elastic domain, based on the residual stress distribution of Timoshenko (Figure 5), is null since at the middle of the web the stresses have already reached the yield stress f y .

It is observed that cold bending residual stresses have a non negligible influence on the two domains, in particular the elastic one, and that this influence is different from that of the hot rolling For the most common sections of the European steel industry (IPE, HEA, HEB) the non-dimensional parameter β varies considerably. In IPE sections β is smaller varying from 0.60 (IPE600) to 0.84 (IPE80). For HEA/HEB sections this parameter is in general larger, varying from 0.59 (HEA1000) to 1.88 (HEB260). Using the procedure described in sections 3.1 and 3.2, interaction diagrams are developed for both the elastic and the plastic domain for the cases for which β gets its extreme values. Figure 10 and Figure 11 illustrate the elastic and plastic domain for the lowest and highest value of parameter β, respectively. Figure 10 is for an IPE600 section which has the lowest β value (0.60) while Figure 11 is for a HEB260 section which has the highest β value (1.88). In the same figures, the limits of the elastic and plastic domain for these sections including the residual stresses due to hot rolling process are also included. The results can also be compared with those in Figure 8 for a HEB360 section where β=1.58. the aspect ratio h/b of the section as for lower values of this ratio the magnitude of residual stresses is larger (Figure 4). M N /M pl =0.90 in a stress free section and M N /M pl =0.82 in a cold bent section. This represents a reduction of the resistance of the section of about 10%. It can also be observed that the limits of the The above observations can be further quantified by comparing the differences of the capacity of the stress free section, the hot rolled section and the cold bent section for all combinations of (M N /M pl )/(N/N pl ). This ratio is described by means of the angle γ, shown in Figure 12. We denote by χ SF , χ HR , χ CB , the distances OA SF , OA HR , OA CB , respectively, corresponding to the stress free, hot rolled and cold bent sections. These parameters are used for illustrating the differences of the capacity of stress free, hot rolled and cold bent section for certain combinations of (M N /M pl )/(N/N pl ), as shown in Figure 13. The horizontal axis represents the angle γ=tan -1 [(M N /M pl )/(N/N pl )]) and the vertical axis represents the percentage of difference in capacity of hot rolled and cold bent section with respect to the stress free section. It is verified that residual stresses affect the plastic capacity of cold bent sections much more than that of hot rolled sections. Moreover, for cold bent sections the influence of residual stresses reaches a reduction in capacity of up to about 10% for certain combinations of axial force and moment. It is noted that the most significant differences are observed when stresses due to axial forces have relatively high contribution to the total stress. Moreover, as the parameter β increases, the influence on the capacity of the cold bent section increases as well.

The presented interaction diagrams can be directly used by designers to appreciate the available margins of safety of cold bent members or indirectly: for example, they could be advantageously employed for estimating the plastic collapse load of arches instead of the simple bilinear interaction curves of Spoorenberg et al. [START_REF] Spoorenberg | A theoretical method for calculating the collapse load of steel circular arches[END_REF]. They will give a more accurate estimation with few additional computational effort.

Stability of cold bent members

In order to also evaluate the influence of residual stresses due to cold bending on curved member stability, the model of Figure 6 is here used as initial stress state for the development of buckling curves following the general methodology proposed by Beedle and Tall [START_REF] Beedle | Basic column strength[END_REF]. In order to first evaluate separately the influence of residual stresses on the capacity of curved members, initial imperfections and geometric non-linearities are not taken into account here, but this should be addressed in future research, before the buckling curves are actually suitable for design purposes. Nevertheless, existing work on the plastic design of arches [START_REF] Trahair | Plastic Design of Steel Arches[END_REF][START_REF] Pi | In-plane stability of arches[END_REF][START_REF] Pi | Elasto-plastic buckling and postbuckling of arches subjected to a central load[END_REF][START_REF] Pi | In-plane strength and design of fixed steel I-section arches[END_REF] has already shown how hot rolling or Timoshenko like residual stresses affect the behavior of curved members. So, comparing the influence of cold bending residual stress patterns with other patterns on a member without imperfection can offer a good overview of the importance of the phenomenon.

Definition of the elastic buckling load

The member studied here is a perfectly circular arch, curved about its strong axis, supported by two roller supports at its ends and submitted to a uniform radial pressure, as shown in Figure 14. Inplane flexural buckling is considered, but not out-of-plane flexural or flexural torsional buckling, assuming sufficient lateral support of the arch along its length. According to these hypotheses, the arch is under pure compression in the pre-buckling phase and the normal force N in the arch is related to the radial pressure q through the curvature radius R by:

N q R = (7)
Figure 14: Geometry and loading around arch

The arch will thus buckle if the actual compression N exceeds the first critical buckling load. An analytical expression of the buckling loads can be found in [START_REF] Pi | In-plane stability of arches[END_REF]. It is distinguished between shallow and high arches, the first ones having angle θ such that (2θ <90 ο ) and being more sensitive to the member extensibility and axial deformation. Hence, for pinned high arches, the first critical in-plane buckling load N cr is anti-symmetric and given by:

2 , , 1 2 (
)

cr h EI N R π θ = ( 8
)
EI is the bending stiffness along the major principal axis and Rθ represents the half length of the arch. For shallow arches, the type of buckling depends on the slenderness λ about the major principal axis defined by:

2 R r λ θ = , / r I A = (9)
So, if λ >9.38 , then the first buckling is anti-symmetric:

.26 0.74 1 0.63

cr s cr h N N α π λ   ≈ + -       (10)
while if 3.88 < λ ≤9.38 , then the first buckling is symmetric:

2 , , 1 , ,1
(0.15 0.006 )

cr s b cr h N N λ ≈ + (11)
It must be outlined here that, for arches, the slenderness λ depends on the ratio between the radius of curvature of the member, the included angle of the arch and the gyration radius. The slenderness parameter hence combines geometrical aspects of the arch form with inertia aspects of the cross section, which both influence the critical behavior of the member.

Definition of the plastic buckling load

For evaluating the plastic buckling load, one has to take into account that, for a given normal force N lower that the plastic capacity of the section (N<N pl =f y A), the section may have partly yielded and that therefore the bending stiffness of the member in expressions ( 8) to [START_REF]Manual on stability of steel structures[END_REF] has to be reduced. The general methodology consists thus in supposing a certain level of normal force, then determining the yielded parts of the section and calculating the bending stiffness of the remaining elastic parts and finally deducing the maximum allowable slenderness λ associated with the given normal force. If the material is assumed to be elastic perfectly plastic, then the stiffness of the yielded parts of the cross section is null.

Thus, it is first supposed that a uniform compressive stress σ u is applied to a section having residual stresses induced by cold bending. Then, assuming that the material is elastic perfectly plastic, the effective stress σ eff in the section is evaluated:

eff y rs u y eff rs u rs u y f if f if f σ σ σ σ σ σ σ σ = + ≥ = + + < (12)
By integrating the effective stress σ eff over the entire section, the associated normal force N eff is calculated:

eff eff A N dA σ = ∫ (13)
The corresponding average stress is thus given by:

eff avg N A σ = (14)
In the following, these values of average stress σ avg and normal force N eff are used as reference levels to characterize the critical elasto-plastic slenderness of the curved member. Hence, based on the effective stress [START_REF] Fukumoto | Evaluation of column curves based on probabilistic concept[END_REF], the inertia of the elastic parts of the section about the major principal axis is evaluated:

{ } 2 , , / ( , ) el el el eff y A I y dydz A y z y z f σ = = < ∫ (15)
For this level of normal force N eff , the modified slenderness λ of the elasto-plastic member about the major principal axis is then given by: 2 ,

el el el el I R I r r A I θ λ λ λ = = ⇔ = (16)
Introducing then the inertia of the elastic parts [START_REF]Compression members, in: Eurocode 3: Design of steel structures -Part 1-1: General rules and rules for buildings[END_REF] in expressions ( 8) to [START_REF]Manual on stability of steel structures[END_REF] of the buckling loads and using the modified slenderness [START_REF] Construction | Design of members for compression[END_REF], one finds expressions of the plastic buckling loads which depend on the included angle θ of the member, its radius R and on the applied average stress:

el cr h EI N R π θ = 2 , ,1 2 ( )
.26 0.74 1 0.63 for 9.38

cr s a cr h N N π λ λ   ≈ + - >       (18) 2 , ,1 , ,1 (0
Varying the included angle 2θ for a given value of the radius R of the arch the minimum value θ min for which the elasto-plastic in-plane buckling load is equal to the applied normal force (N cr,s,1,a =N eff ) is obtained. The maximum allowable slenderness for that particular radius and particular level of normal force will hence be given by:

2 min max , , 1 min , (
)

cr s a eff el R N N r θ λ θ = = (20)
Thus, the corresponding slenderness λ is given by: m ax

el I I λ λ = (21)

Buckling curves for cold bent members

Plotting for a given radius the variation of the slenderness with the applied average stress gives the desired buckling curve for the elasto-plastic buckling of perfectly circular cold bent members with hinged supports submitted to uniform radial pressure. Typical buckling curves of such cold bent members are shown in Figure 15 to Figure 17. It is noted that all buckling curves shown are developed for a range of slenderness values which correspond to an included angle for the arch of 0 o <2θ ≤180 o , in accordance with most practical cases.

In Figure 15 a comparison of the influence on the buckling resistance of the different residual stress models is shown for a HEB360 section and a radius of curvature R=10m. Comparing the influence of the hot-rolled residual stress distribution [START_REF] Stability | System, Ultimate limit state calculations of sway frames with rigid joints[END_REF] (Figure 4) with the one of the cold bent member [START_REF] Spoorenberg | Finite element simulations of residual stresses in roller bent wide flange sections[END_REF] (Figure 6), it can be observed that the influence of cold bending is larger for slenderness values up to 110. For values larger than this, the influence due to hot rolling process is slightly larger. Using the residual stress model for cold bent members proposed by Timoshenko [START_REF] Timoshenko | Strength of materials: Part II: Advanced theory and problems[END_REF] (Figure 5), the buckling curve does not have a smooth shape due to the uniform residual stress distributions in the flanges.

Its influence on the resistance of such members is larger for values of slenderness up to about 100.

For values larger than 100, the influence of the residual stress pattern of Figure 6 is larger. Similar observations were made for other cross-sections and other curvature radius.

In Figure 16 the buckling curves of a HEB260 (β=1.88) and an IPE270 (β=0.8) section are shown for a radius R=10m. It is noted that both sections have the same radius of gyration (r=11.22 cm). The buckling curve of the stress free case is also shown for comparison. It is observed that the residual stresses due to cold bending influence the buckling curves significantly with respect to those for the stress free members for intermediate values of slenderness. Beyond a certain value of slenderness, in this case approximately λ=150, there is no influence of residual stresses, buckling is perfectly elastic. Regarding the buckling curves for the two different cold bent sections, even though the aspect ratio β is considerably different, its influence on the buckling resistance is practically negligible. This can be explained by the fact that β affects only the level of the residual stresses in the web which does not have a significant contribution to elasto-plastic bending stiffness.

In Figure 17 a comparison of the influence of the curvature radius on the shape of the buckling curves is provided, both for cold bent and for stress free members. A HEB360 section is considered and the radii vary from 10m to 25m, i.e. in a slightly wider range than the validity limits of the residual stress model (10<R/h<40). It is noted that when the radius of curvature decreases, the range of slenderness for which elasto-plastic buckling occurs increases. Nevertheless, the maximum difference between the stress free member and the cold bent one is almost the same for all the radii of curvature. This is also valid for the highest average stress for which pure elastic buckling occurs which depends very little on the curving radius of the cold bent members.

Summary and conclusions

It is a well known fact that residual stresses due to hot rolling have an influence on the elasto-plastic behavior of straight members with wide flange steel sections. The purpose of this paper was hence to investigate their influence on the behavior of curved members obtained by cold bending. An upto-date review of residual stress models for curved members has hence first been presented. Then, relying on the most recent and reliable model, interaction diagrams of cold bent sections and buckling curves of perfectly circular arched members have been developed. The results of this study can be directly applied in engineering design practice to take into consideration the effects of cold bending in wide flange arches.

Since the residual stress model used in this study is not symmetric, it was shown that the residual stresses affect differently the section response depending on the type of loading (positive or negative bending moments and tensile or compressive normal forces). The elastic domain of curved sections is significantly reduced due to the presence of residual stresses. The plastic limit of cold bent sections is reduced by approximately 10% for some combinations of loading involving compression and opening bending moments. A safety margin of this magnitude seems thus reasonable for such sections. It was also observed that the influence of residual stresses increases when the aspect ratio β =bt f /ht w increases. In general, HEA and HEB sections are affected more by the presence of residual stresses than IPE sections, since the β parameter is higher in such sections.

Concerning the buckling resistance, a parametric study has been conducted to investigate the influence of the aspect ratio β and the curving radius R and to determine how it is affected by the residual stress pattern. It was concluded that residual stresses due to cold bending affect the buckling resistance of a wide flange section in a qualitatively similar way as the residual stresses due to hot rolling, however, critical stress may differ up to ±5%, depending on the slenderness. The nondimensional parameter β has no significant influence on the buckling resistance of cold bent members.

This investigation led us to the conclusion that the observed differences between hot rolled straight members with wide flange section and cold bent curved members were significant enough to necessitate the development of buckling curves for curved members. Future work will thus consist of the introduction of initial imperfections and geometric non-linearities as well as non-uniform loading conditions. The investigation of the interaction between these different factors should eventually lead to the development of design buckling curves for cold bent curved members in a format compatible to existing EC3 curves. First in-plane critical buckling load for a high arch N cr,s,1a

Anti-symmetric in-plane buckling load of the elastic member N cr,s,1b

Symmetric in-plane buckling load of the elastic member N eff Normal force after the application of σ u , ,1 cr h

N

First in-plane critical buckling load of the elasto-plastic member Compressive residual stress due to hot rolling process in flange tips σ c2

Compressive residual stress due to hot rolling process in web midst σ eff

Resulting stress in the cross-section after the application of σ u σ rs

Residual stress σ t

Tensile residual stress due to hot rolling process in web to flange junctions σ u

Uniformly applied stress over the entire cross-section σ wrc

Compressive residual stress in the web due to cold bending σ wrt Tensile residual stress in the web due to cold bending χ SF Characteristic radius of plastic domain in the γ direction of the stress free section χ HR Characteristic radius of plastic domain in the γ direction of the hot rolled section χ CB Characteristic radius of plastic domain in the γ direction of the cold bent section

Figure 1 :

 1 Figure 1: Roller bending process

Figure 2 :

 2 Figure 2: Example of cold curving machine (courtesy EMEK S.A., Greece) As mentioned above, initially straight hot rolled wide-flange profiles are used for roller bending. It is

  35 y f at the flange tips and a maximum of 0.70 y f at the flange center. For the web two triangular stress blocks, one tensile and one compressive, are proposed, with the peaks of the triangles , respectively, from the web-to-flange junction of the top flange. Based on equilibrium conditions the values of these peaks for the tensile and the compressive stress block are:

  (f)) and N py M is the plastic moment within the central part of the section which undertakes the normal forces (Figure 7(g)). If y N

Figure 7 :

 7 Figure 7: Decomposition of stresses in a fully yielded wide flange section under strong axis bending and normal force including the residual stresses induced by cold bending

  residual stresses. It is thus considered as appropriate to carry out a parametric study for other crosssections, using only the residual stress pattern proposed by Spoorenberg et al., which is considered more reliable than the one by Timoshenko.

Figure 8 :Figure 9 :

 89 Figure 8: Interaction diagrams for a HE360B section, (a) Elastic domain & (b) Plastic domain

Figure 10 :

 10 Figure 10: Interaction diagrams for IPE600 section with β=0.60, (a) Elastic domain & (b) Plastic domain

Figure 11 :

 11 Figure 11: Interaction diagrams for HE260B section with β=1.88, (a) Elastic domain & (b) Plastic domain

  less affected by the presence of residual stresses due to hot rolling process than from the presence of residual stresses due to cold bending (Figure8(b), Figure 10(b), Figure 11(b)).

Figure 12 :Figure 13 :

 1213 Figure 12: Definitions of characteristic parameters of the interaction diagram

Figure 15 :Figure 16 :Figure 17 :

 151617 Figure 15: Buckling curves of an arch with radius of curvature R=10m for in-plane buckling with different residual stress models (HEB360)

λ

  in-plane buckling load of the elasto-plastic member , ,1 cr s b N Symmetric in-plane buckling load of the elasto-plastic member R Radius of curvature of the arch r el In-plane radius of gyration of the elastic parts of the section r In-plane radius of gyration T Cross-sectional area which undertakes N t f Flange thickness t w Web thickness W pl Plastic modulus y N Ηeight of the section that undertakes the axial force z Distance from the neutral axis α Ratio between the plastic and elastic modulus or shape factor β Non-dimensional parameter bt f /h 0 t w γ Angle characterizing the load combination in the interaction diagram 2θ Included angle of the arch θ min Included angle of the elasto-plastic arch for which buckling occurs λ In-plane slenderness of the elastic member λ In-plane slenderness of the elasto-plastic member max Maximum allowable in-plane slenderness of the elasto-plastic member σ avg Average applied stress over the entire cross section σ c1

  Major principal axis moment of inertia of the section I elMajor principal axis moment of inertia of elastic portions of the section M N Plastic moment resistance with the presence of axial force N M p Total plastic moment resistance of the section for bending about the major principal axis M pyN Plastic moment within the height y N N Axial force N cr,h,1

	Annex 1: (nomenclature)
	A	Cross-section area
	A el	Area of elastic portions of cross section
	b	Width of the flange
	E	Young modulus
	F	Cross-sectional area which undertakes M N
	f y	Yield stress
	h	Height of the section
	h 0	h-t f
	I

Acknowledgement

The authors gratefully acknowledge the support of the European Community under a Marie Curie Intra-European Fellowship for Career Development (Grant agreement number 235196).


Nicolas Durand
email: durand@cena.dgac.fr

Jean-Marc Alliot
email: alliot@dgac.fr

CENA Joseph Noailles
email: noailles@enseeiht.fr

Automatic aircraft conflict resolution using Genetic Algorithms

Keywords:

In this paper, we show how genetic algorithms can be used to solve en-route aircraft conflict automatically to increase Air Traffic Control capacity in high density areas. The ATC✄ background and the model are presented. The complexity of the problem is then discussed. The author then justifies the choice of GAs. After a brief description of genetic algorithms, the author describes the improvements that were used for solving the conflict resolution problem. Several numerical applications are then given justifying the choices that were made and illustrating the interest of the research. Next steps of this work are discussed in the conclusion.

Introduction

Studies on the use of genetic algorithms for conflict resolution and air space sectoring have given promissing results [START_REF] Alliot | Using genetic algorithms for solving ATC conflicts[END_REF][START_REF] Daniel Delahaye | Genetic algorithms for partitioning airspace[END_REF][START_REF] Daniel Delahaye | Genetic algorithms for air traffic[END_REF][START_REF] Durand | Genetic algorithms for optimal air traffic conflict resolution[END_REF][START_REF] Van Kemenade | Evolutionnary computation in air traffic control planning[END_REF]. This paper presents new results for solving conflict☎ between aircraft for En Route ATC in real time situation.

The first part of the paper introduces the problem, its constraints and goals. The choice of the model is discussed in the second part. In the third part, we discuss the complexity of our problem and explain why classical optimization tools such as gradient methods are not adapted to solve aircraft are said to be in conflict if their altitude difference is less than ☛ ☞ ☞ ☞ feet (✌ ☞ ✍ meters) and the horizontal distance between them is less than ✎ nautical miles (☛ ✏ ✎ ☞ ☞ meters). These two distances are respectively called vertical and horizontal standard separation.

it. Part four describes briefly genetic algorithms and the improvements that were used. Part five presents the coding and part six give several numerical applications.

Problem description

As traffic keeps increasing, En Route capacity, especially in Europe, becomes a serious problem. Aircraft conflict resolution, and resolution monitoring, are still done manually by controllers. Solutions to conflicts are empirical and, whereas aircraft are highly automated and optimized systems, tools provided for ATC control are very basic, even out of date. If we compare the current capacity and the standard separation to the size of controlled space, the conclusion is easy to draw: while ATC is overloaded, the sky is empty.

However, conflict resolution is a very complex trajectory optimization problem under constraints. There have been many attempts to try to reach one of the two objectives, automation and optimization. However, most of the time these two objectives were confused (see [START_REF] Niedringhaus | Automated En Route Air Traffic Control Algorithmic Specifications: Flight Plan Conflict Probe[END_REF][START_REF] Zeghal | Vers une thèorie de la coordination d'actions. Application à la navigation aérienne[END_REF][START_REF] Fron | Arc 2000 : Automatic radar control[END_REF]).

The solver we introduce has to handle the following constraints: ✑ Conflict free trajectories must respect both aircraft and pilot performances. Considering the evolution of ATC toward automation [START_REF] Patrick Dujardin | Different paths to automation[END_REF], trajectories must remain simple for controllers to describe as well as for pilots to understand and follow.

✑

Trajectories must take into account uncertainties in aircraft speed✒ .

✑

Maneuvers orders must be given with an advance notice to the pilot. When a maneuver has begun, it must ✓ Aircraft ground speeds can not be forecasted precisely because of winds, and radar precision. Moreover, models to forecast aircraft ground speeds are not reliable enough. Consequently, uncertainty on speeds have to be introduced in the model. not be called into question. A maximum of one maneuver per aircraft should be forecasted for the next twenty minutes.

✑

If possible, conflicts must be solved horizontally for comfort and economical reasons, especially when aircraft are leveled.

We want to achieve the following goals: ✑ find conflict free and optimal trajectories ✑ compute these trajectories in real time ✑ find many different optimal or nearly-optimal solutions, so that in a transition phase to automation, this tool could be used to assist a human operator

Modeling

In this paper we will restrict our problem to aircraft flying at constant level. It could and will be extended to ✔ ✕ conflict resolution. A simple way to do this is to use the horizontal projection of the climbing and descending aircraft and to treat them as leveled aircraft with different speeds. Consequently, our ✖ ✕ modeling can be extended to ✔ ✕ immediately. Furthermore, the complexity of the problem does not increase when extended to ✔ ✕ .

Theoretical results

Durand, Alech, Alliot and Schoenauer showed in [START_REF] Durand | Genetic algorithms for optimal air traffic conflict resolution[END_REF] that for a conflict resolution involving two aircraft : at the optimum, as long as the standard separation constraint is not saturated, aircraft fly in straight line. When saturating, aircraft start turning, and as soon as the separation constraint is freed aircraft fly straight again. This result can easily be extended to the case of ✗ aircraft, with ✗ ✘ ✖ . When moving only one aircraft, it can be proved that trajectories are regular, they do not include discontinuous points. It can be proved [START_REF] Durand | Conflict free trajectory modelling for en route control[END_REF] that the length of the conflict free trajectory increases when :

✑ the angle of incidence between the two aircraft decreases.

✑ the speed ratio gets close to ✙ .

✑ aircraft are getting closer to the conflict point.

It can also be mathematically proved, that if aircraft parameters (speed and heading) are constant at intervals, and if aircraft trajectories don't loop, the set of conflict free trajectories has two connected components. In one of the two sets, one of the aircraft always lets the other one on its right side, whereas in the other set, it lets it on its left side.

The previous mathematical study leads naturally to approximate the conflict free trajectories by a turning point trajectory (figure 1).

It was shown [START_REF] Durand | Conflict free trajectory modelling for en route control[END_REF] that the turning point approximation lengthens the optimal trajectory by less than ✙ ✚ if distance between the aircraft and the conflict point is greater than two standard separations and the angle of incidence between trajectories greater than ✔ ✛ degrees. It can also be proved that the offset modeling (figure 1), which moves an aircraft to put it on a parallel route, is worse, except for conflicts between overtaking aircraft. It has the advantage to linearize the separation constraints. The offset is thus very easy to compute, but separation constraints must be checked during maneuvers and the complexity of the problem remains (see [START_REF] Medioni | Algorithmes génétiques et programmation linéaire appliqués a la résolution de conflits aériens[END_REF]).

Speed uncertainties

In this paper, we will assume that there is an error about the aircraft future location because of speed uncertainties✜ The conflict free trajectory must be robust regarding these uncertainties. When climbing or descending, aircraft follow climbing rates and descending rates that are fixed by technical constraints and on which uncertainties are more important. To take the uncertainty problem into account, and to be able to guarantee to an aircraft a conflict free trajectory for the next ✖ ✛ minutes, we will represent the aircraft by a point at the initial time. The point will become a segment of a line in the uncertainty direction, the speed direction in our case. To check the standard separation at time ✢ , we calculate the distance between the two segments modeling the aircraft positions and compare it to ✣ Aircraft are able to follow a given route at a given altitude, but their speed can not be precisely predicted. Consequently, controllers prefer waiting to be sure two aircraft are involved in a conflict before solving it. the standard separation (see figure 2).

Because of uncertainties, a conflict may be detected twenty minutes before it should occur and finally may not happen. Consequently, deciding to move an aircraft in that case would be useless, and could even generate other conflicts that would not occur if no maneuver had been decided. Consequently, it is very important that the solver makes a decision as late as possible without penalizing the resolution.

Choosing the model

Both offset modeling and turning point modeling must be kept : for overtaking aircraft, offsets are more efficient whereas for other conflicts, turning points are more efficient. However, because of uncertainties, maneuvers must be started as late as possible with respect to the aircraft constraints. This explains the choice of a constant turning point angle (✔ ✛ degrees, for example allows large deviations in very few time). The previous elements leads us to choose the following model (figure 3). A maneuver will be determined by : ✑ the maneuver starting time ✤ .

✑ the duration of the maneuver and its direction ✕ (right or left).

✑ the duration of the offset ✥ (if no offset, this value will be ✛ ).

✤ and ✥ are positive values whereas ✕ will be positive if the aircraft turns on its right and negative if it turns on its left. This model has the great advantage to reduce the size of the problem. For a conflict involving ✗ aircraft, the dimension of the research space is ✔ ✗ . This will allow us to solve very difficult conflicts with many aircraft without investigating a too large space. The lost of optimality on delays is not important if speed uncertainties are large. Even if a ✔ ✛ degrees deviation is ✔ times more penalizing than a ✙ ✛ degrees turning point, the total duration of a ✙ ✛ degrees deviation is more than ✔ times the duration of a ✔ ✛ degrees deviation. Thus, when a ✙ ✛ degrees deviation is started, it will last ✔ times the ✔ ✛ degrees equivalent deviation and it will have to be started earlier, when the probability of conflict is lower. The optimal deviation angle is thus directly depending on the aircraft speed errors and could be reduced in the future.

Real time optimization

The model introduced above is simple enough to be used in a real time optimization program✦ . Let's consider a conflict involving ✗ aircraft and let's choose a time step (✧ minutes for example). Let's imagine we want to recompute all trajectories every ✧ minutes. During the optimization time, aircraft are flying and must know if they must change their route or not. Consequently, for each aircraft, at the beginning of the current optimization, the next ✧ minutes of its flight may not be changed and is fixed by the previous optimization. Because of the constraints described above when a maneuver is started for an aircraft, it can not be changed, but at least the part of the maneuver that is not included in the first ✧ minutes may be changed with respect to the turning point or offset model. On example 4, at ✢ ★ ✛ on the first line, the aircraft trajectory can not be modified before ✢ ★ ✧ . At the end of the first optimization run, at ✢ ★ ✧ , the current position of the aircraft is updated. The maneuver that occured between ✢ ★ ✧ and ✢ ★ ✖ ✧ is kept as a constraint for the second optimization run (on the example, no maneuver is decided)...

On the example given, we can see that the maneuver described on line ✖ (resulting of an optimization at ✢ ★ ✧ ) ✩ Simulating ✡ ☞ minutes of aircraft flight and checking standard separations is very long. Consequently, a simple modeling is necessary to achieve a real time optimization. is more penalizing than the maneuver described on line ✔ (resulting of an optimization at ✢ ★ ✖ ✧ ). This phenomenon occurs because of uncertainties. If uncertainties on speed are important, having a small ✧ will be very helpful to minimize the resolution costs in real time situation.

A combinatorial problem

In this part, we explain why our problem can not be solved by classical methods.

Complexity of the problem

The complexity of the problem is exposed by Medioni, Durand and Alliot in [START_REF] Médioni | Algorithmes génétiques et programmation linéaire appliqués a la résolution de conflits aériens[END_REF]. Let's consider a conflict between two aircraft. If we can easily prove that the minimized function is convex, the set of conflict free trajectories is not. It is not even connected. If trajectories don't loop, the set of conflict free trajectories has two connected components. For a conflict involving ✗ aircraft there may be ✖ ✪ connected components in the free trajectory space which strongly suggests that any method which requires exploring every connected component is NP. It is important to note that this complexity is independent of the modeling chosen. The offset modeling seems to be very attractive, because it linearizes constraints. Nevertheless, each constraint multiplies by two the number of linear programs to solve. Our problem involves ✪ ✫ ✪ ✬ ✄ ✭ ☎ constraints. Moreover, linearizing the minimized function, multiplies by ✖ ✪ the number of linear program to solve (we minimize the sum of each aircraft offset which may be positive or negative). Finally, we will have to solve

✖ ✮ ✯ ✮ ✰ ✱ ✲ ✳ linear pro- grams, each one involving ✪ ✫ ✪ ✴ ✄ ✭ ☎ linear constraints. For ✗ ★
✵ , ✔ ✖ ✶ ✷ ✸ linear programs have to be solved with ✙ ✵ constraints in each program.

A global optimization problem

Using classical methods, such as gradient methods for example, becomes useless for our problem, because of the arbitrary choice of the starting point required by these methods. Each connected component may contain one or several local optima, and we can easily understand that the choice of the starting point in one of these components can not lead by a classical method to an optimum in another component. We can thus expect only a local optimum. Practical attempts done on LANCELOT Large And Nonlinear Constrained Extended Lagrangian Optimization Techniques [START_REF] Conn | A comprehensive description of LANCELOT[END_REF] have confirmed this problem. Furthermore, this approach is not efficient for a real time trajectory planning. The offset modeling linearizes the constraints but the problem remains so combinatorial that we can not expect to find the global optimum efficiently. Moreover, the separation during maneuvers must be checked afterwards. This experiment strongly suggests that classical methods are not well adapted to our problem.

Genetic Algorithms

Principles

We are using classical Genetic Algorithms and Evolutionary Computation principles such as described in the literature [START_REF] Goldberg | Genetic Algorithms[END_REF][START_REF] Michalewicz | Genetic algorithms+data structures=evolution programs[END_REF]; Figure 5 describes the main steps of GAs.

First a population of points in the state space is randomly generated. Then, we compute for each population element the value of the function to optimize, which is called fitness. In a second step we select✹ the best individuals in the population according to their fitness. Afterwards, we randomly apply classical operators of crossover and mutation to diversify the population (they are applied with respective probabilities ✺ ✻ and ✺ ✼ ). At this step a new population has been created and we apply the process again in an iterative way.

Improvements

Simulated Annealing Tournament

GA can be improved by including a Simulated Annealing process after applying the operators [START_REF] Samir | Parallel recombinative simulated annealing: a genetic algorithm[END_REF]. For example, af-✽ Selection aims at reproducing better individuals according to their fitness. We tried two kinds of selection process, "Roulette Wheel Selection" and "Stochastic Remainder Without Replacement Selection", the last one always works out better.

if ✾ ✙ is better than ✺ ✙ then ✾ ✙ is selected.
Else ✾ ✙ will be selected according to a probability which decreases with the generation number. At the beginning of the simulation, ✾ ✙ has a probability of ✿ ✵ to be selected even if its fitness is worse than the fitness of ✺ ✙ and this probability decreases to ✛ ✿ ✛ ✙ at the end of the process. A description of this algorithm is given on figure 6.

Tournament selection brings some convergence theorems from the Simulated Annealing theory. On the other hand, as for Simulated Annealing, the (stochastic) convergence is ensured only when the fitness probability distribution law is stationary in each state point [START_REF] Aarts | Simulated annealing and Boltzmann machines[END_REF].

Sharing

Our problem is very combinatorial and may have many different optimal solutions. In order to find most of these solutions❀ and to avoid local optima, the sharing process introduced by Yin and Germay [START_REF] Yin | A fast genetic algorithm with sharing scheme using cluster analysis methods in multimodal function optimization[END_REF] is used. This sharing process has the great advantage to grow in ✗ ❁ ❂ ❃ ❄ ✗ ❅ (instead of ✗ ☎ for classical sharing) if ✗ is the size of the population.

A sharing process requires introducing a distance between two chromosomes. Defining a distance between two ❆ Finding several solutions is very interesting because the controller can make a choice and negotiate it with pilots. A discrete distance is defined as follow : two chromosomes belong to the same class if each of their aircraft follow the same trajectory types. If not, they belong to different classes. The fitness value of each chromosome is then divided by the number of elements in its class. Results show that sharing was very useful for combinatorial problems. Simulated annealing and sharing process have really improved convergence of GAs and were definitely adopted for the three following applications.

Adapted Crossover and Mutation

GAs seem very powerful because they do not require much information on the fitness function. However, classical operators used by Gruber, Alliot and Schoenauer in [START_REF] Alliot | Using genetic algorithms for solving ATC conflicts[END_REF] did not give good results. Moreover, we know much about the fitness function and it can be very useful to use this information to create adapted crossover and mutation operators. Durand, Alliot and Noailles describe these operators in [START_REF] Durand | Algorithmes genetiques : un croisement pour les problemes partiellement separables[END_REF]. Instead of considering a global fitness value that takes into account the different lengthening of the trajectories and the conflicts between the aircraft, we keep in a ✗ ☎ sized matrix ❇ (where ✗ is the number of aircraft) these values. If ❈ ❉★ ❊ , ❇ ❋ • ❍ measures the conflict between Figure 7: An adapted crossover operator aircraft ❈ and ❊ . It is set to ✛ if no conflict occurs and increases with the seriousness of the conflict. ❇ ❋ • ❋ measures the lengthening of aircraft ❈ trajectory. This fitness matrix contains much more information than the previous scalar global fitness and this will allow us to define more deterministic crossover and mutation operators. We can define for each aircraft :

❋ ★ ✪ ■ ❍ ❏ ✄ ❄ ❇ ❋ • ❍ ❅
The crossover operator is described on figure 7. After choosing ✖ parents ❑ and ▲ , we compare the local fitnesses of their aircraft (These fitnesses are named ❑ ❋ and ▲ ❋ on figure 7). For aircraft ❈ , if ❑ ❋ ▼ ▲ ❋ ◆ ❖ (❖ is a value that modulates the operator's determinism) the ✖ children inherit aircraft ❈ of father ❑ . If ▲ ❋ ▼ ❑ ❋ ◆ ❖ , the ✖ children inherit aircraft ❈ of father ▲ . If none of these two conditions are checked, aircraft ❈ of children ✙ and ✖ are two random combination of aircraft ❈ of the two parents.

The mutation operator is described on figure 8. After choosing a chromosome, an aircraft is mutated (on figure 8 aircraft is chosen). Aircraft having a high fitness (more than ◗ where ◗ modulates the operator's determinism) can be chosen only if every aircraft has a high fitness.

These operators have the great advantage to be rather deterministic at the beginning of the optimization so that a solution without conflict can be very quickly found. When such solutions become sufficiently numerous, these operators are less deterministic and other parts of the research space can be explored.

Two parameters (❖ and ◗ ) where introduced and influence the determinism of the optimization. Because of the determinism of these operators, using sharing (described above) becomes essential.

Improving the result

Genetic algorithms are very efficient to solve global combinatorial optimization problem but are not very efficient to solve local search with a good precision. Consequently, it is very efficient, at the last generation of the genetic algorithm, to use a local optimization method to improve the best solution of each chromosome class defined above. The local method adopted in this study is very simple : we apply a hill-climbing algorithm to the best chromosomes at the end of the GA run..

Coding our problem 5.1 The data

An example of chromosome is given in figure 9. Each value represents a time and is coded by a positive integer. For the deviation duration, this integer can be negative.

The duration of the optimization, the anticipation time, the time step used during the simulation, the horizontal separation must be define for every optimization. Some data must be actualized at each optimization : the position, heading, speed and speed uncertainty| of each Other global data are required : the number of generations, the number of elements, crossover and mutation per-❙ It can depend on its characteristics, its equipment and on the weather conditions.

The fitness

One of the main issues is to know how to compute the fitness of a chromosome. We have a poly criteria problem to solve, in fact the following criteria have to be matched together to give us a single fitness function :

✑

The delay due to a deviation for each aircraft must be as small as possible.

✑

However, the number of aircraft deviated and the total number of maneuvers must be as low as possible (orders are given by the controllers to pilots on the VHF). Thus, instead of sharing the global delay on all the aircraft, some aircraft will support a part of the delay and others not. The sharing process described above is very important to give different equivalent solutions.

✑

The maneuver duration for an aircraft must be as short as possible so that the aircraft is freed as soon as possible for another maneuver.

✑

The trajectories must handle the separation constraints.

The fitness matrix previously described is calculated as follow :

❇ ❋ • ❋ ★ ❚ ❋ ❯ ❱ ❲ ❋ ❇ ❋ • ❍ ★ ❳ ( ❳ ) ❬ ❳ ❋ ✼ ❭ ■ ❳ ❏ ( ❄ ✾ ❳ • ❋ • ❍ ❅
To take into account both the delay and the maneuver duration, we decided to measure the maneuver occupancy surface ❚ (figure 10). This value increases with both the delay and the maneuver duration. It is interesting to note S aircraft i i,i Figure 10: Maneuver Occupancy Surface that controllers currently use this notion of maneuver occupancy surface. To minimize the number of maneuvers, add to ❚ the number of maneuvers ❲ multiplied by a coefficient ❱ (❲ ★ ✛ if no maneuver, ✖ if it is an turning point and ✔ if it is an offset).

At each time step ✢ , we calculate

✾ ❳ • ❋ • ❍
as the difference of the standard separation and the distance between the segments ❈ and ❊ describing aircraft ❈ and ❊ position at time ✢ . These values are added in ❇ ❋ • ❍ and give a measure of the conflict between ❈ and ❊ .

It is obvious that the fitness matrix is symmetric. A triangular matrix could as well be used.

We can now define a global scalar fitness as follow :

) ❄ ❈ ❴ ❊ ❅ ❴ ❈ ❉★ ❊ ❴ ❇ ❋ • ❍ ❉★ ✛ ❵ ❇ ★ ✙ ✖ ❯ ❛ ❋ ❜❏ ❍ ❇ ❋ • ❍ ❝ ❄ ❈ ❴ ❊ ❅ ❴ ❈ ❉★ ❊ ❴ ❇ ❋ • ❍ ★ ✛ ❵ ❇ ★ ✙ ✖ ❯ ✙ ✙ ❯ ❛ ❋ ❇ ❋ • ❋
This fitness function guarantees that if a chromosome value is larger than ✄ ☎ , no conflict occurs. If a conflict remains the fitness does not take into account the delays induced by maneuvers.

Numerical Applications

These applications have been done to justify the model and illustrate the performance of the algorithm.

Model Justification

In this first application, we consider the conflict between two aircraft described on figure 11. The anticipation time is set to ✔ minutes and aircraft speed ( ✛ ✛ knots) are known with an error of ✵ per cent. In this case, if aircraft ✛ real speed is ✔ ✸ ✛ knots and aircraft ✙ real speed is ✖ ✛ knots, because of uncertainty, at last no conflict occurs (the standard separation is nm). However, solutions must be computed "in case". Figures 12 show the result of the genetic algorithm at time minutes, ✶ minutes, ✙ ✛ minutes and ✙ ✔ minutes. The continuous line describes the next ✔ minutes trajectory that can not be changed, the dash line represents the optimal trajectory computed by the genetic algorithm. The parameters of the genetic algorithm were : Because of uncertainties, the initial optimized trajectory is not very good. As times goes on, aircraft are closer to the conflict point and uncertainty decreases so the optimized trajectories give smaller deviations. Finally, at time ✢ ★ ✙ ✔ , the conflict disappears. This example demonstrates the interest of the model because it allows uncertainties and delays maneuvers as long as possible. Thus, the genetic algorithm gives an optimal command for the next ✔ minutes and the optimal trajectory associated.

Long lasting conflicts

In this test, ✵ aircraft are coming from the west and going to the east with different speeds (the furthest has the greatest speed and the nearest the lowest speed). The aircraft are not exactly following the same routes. Figure 13 gives the trajectories of the ✵ with per cent error on speed and ✵ minutes of anticipation time. The size of the population of the genetic algorithm was doubled.

This example was done to show that our model allowed long lasting deviations when they can not be avoided. Here, aircraft ✵ is deviated for more than ✔ ✛ minutes. This example shows the importance of the offset model to solve long lasting conflicts. Solving this problem with turning points would have induced much larger delays and very big deviations (in the example, aircraft ✵ would have been deviated several hundreds of nautical miles away from its trajectory).

Adapted operators and sharing justification

To show the importance of the sharing process and of the adapted operators introduced in the Genetic Algorithm, a conflict involving ✖ ✛ aircraft on a circle (figure 14) was tested. It has very few solutions because all the aircraft are conflicting with each other. Only solutions where all the aircraft (except perhaps one) turn in the same direction are conflict free. Figure 15 gives the result of the optimization with a speed error of ✔ per cent and ✵ minutes anticipation time. The parameters of the genetic algorithm were : number of generations : ✖ ✛ population elements : ✙ ✛ ✛ percentage of crossover : ✷ ✛ percentage of mutation : ✙ ✵ simulated annealing for crossover : yes sharing : yes hill-climbing method : yes The minimum distance between aircraft is ✵ ✿ ✷ nm (the standard separation was fixed at P nm).

order to validate the use of a sharing process combined to adapted operators, P different tests were done on this two examples using : ✑ no sharing process and adapted operators (described previously). For these P tests, the value of the best fitness was measured (figure 16) on the ✖ ✛ generations. "no_sharing_adapted_cross" "sharing_adapted_cross" "no_sharing_classic_cross" "sharing_classic_cross"

Figure 16: Best fitness (aircraft on a circle) First, we can check that adapted operators are very efficient because with classical operators, no conflict free solution is found before generation ✖ ✛ (tests have shown that the first conflict free solution is found after generation ✖ ✛ ✛ ) whereas with adapted operators a conflict free trajectory is always found before generation ✙ ✛ (A solution is conflict free if its fitness is more than ✛ ✿ ✵ ).

Figure 16 show that the sharing process lengthens the growth of the best fitness. However, the final best fitness is as good with a sharing process as it is without. It is even better with a sharing process when the conflict is very difficult to solve. The sharing process has the great advantage to help the genetic algorithm to avoid local minima and to give different conflict free solutions.

These tests were repeated on different examples involving ✖ ✛ aircraft❞ giving the same results and justifying the use of adapted operators with a sharing process for conflict resolution.

Conclusion

Genetic Algorithm have shown their efficiency to solve aircraft conflicts in a real time situation. However, we have shown that improvements are very useful, especially when the dimension of the problem grows. This combinatorial problem has shown that combining local and global optimization methods could help solving real variable combinatorial problems.

The model introduced in this paper is a first step in the resolution of real conflicts with real aircraft. A full simulation on a one day real traffic has been done by Chansou [START_REF] Chansou | Résolution automatisée de conflits en route[END_REF]. Results are very promissing. This work is sponsored since 1992 by the CENA which is the institute in charge of studies and research for improving the French air traffic control systems.

❡

Instead of choosing

The next step consists in developing a graphical user interface to compare human being and computer resolutions. The trajectory forecast model should also be improved.

✆

  Centre d'Etudes de la Navigation Aérienne✝ Ecole Nationale de L'Aviation Civile ✞ Laboratoire d'Informatique et de Mathématiques Appliquées ✟ Air Traffic Control ✠ ✡

Figure 1 :

 1 Figure 1: Turning point and offset approximation.

Figure 2 :

 2 Figure 2: Modeling of speed uncertainties.

Figure 4 :

 4 Figure 4: The model and real time optimization.

Figure 5 :

 5 Figure 5: GA principle

Figure 6 :

 6 Figure 6: GA and SA mixed up

Figure 8 :

 8 Figure 8: An adapted mutation operator

Figure 9 :

 9 Figure 9: Structure of the chromosome

Figure 11 :

 11 Figure 11: ✖ aircraft conflict

Figure 13 :

 13 Figure 12: t=P , ✶ , ✙ ✛ , ✙ ✔ minutes

✑

  a sharing process and adapted operators.

✑

  no sharing process and classical operators.

✑

  a sharing process and classical operators.

Figure 14 :Figure 15 :

 1415 Figure 14: ✖ ✛ aircraft conflict (aircraft on a circle)

✡☞

  aircraft on a circle ☛ ☞ independant conflicts involving ✡ aircraft were used


Nicolas Durand
email: durand@cena.dgac.fr

Jean-Marc Alliot
email: alliot@dgac.fr

Joseph Noailles
email: noailles@enseeiht.fr

Collision avoidance using neural networks learned by genetic algorithms

Keywords: Air Tra c Control, Collision Avoidance, Neural Networks, Genetic Algorithms. 1 Air Tra c Control and Collision Avoidance 3 Large And Nonlinearly Constrained Extended Lagrangian Optimization Techniques 4

As Air Tra c keeps increasing, many research programs focus on collision avoidance techniques. In this paper, a neural network learned by genetic algorithm is introduced to solve con icts between two aircraft. The learned NN is then tested on di erent con icts and compared to the optimal solution. Results are very promising.

As Air Tra c keeps increasing, overloading of the ATC 1 system becomes a serious concern. For the last twenty years, di erent approaches have been tried, and di erent solutions have been proposed. To be short, all theses solutions fall in the range delimited by the two following extreme positions:

On the one hand, it could be possible to imagine an ATC system where every trajectory would be planned and where each aircraft would follow its trajectory with a perfect accuracy. With such a system, no reactive system would be needed, as no con ict 2 between aircraft would ever occur. This solution is close to the Centre d'Etudes de la Navigation A erienne y Ecole Nationale de L'Aviation Civile z Ecole Nationale Sup erieure d'Electronique, d'Electrotechnique, d'Informatique et d'Hydraulique de Toulouse 1 Air Tra c Control 2 2 aircraft are said to be in con ict if their altitude di erence is less than 1000 feet (305 meters) and the horizontal distance between them is less than 8 nautical miles (14800 meters). These two distances are respectively called vertical and horizontal standard separation ARC-2000 hypothesis, which has been investigated by the Eurocontrol Experimental Center 5].

On the other hand, it could also be possible to imagine an ATC system where no trajectories are planned. Each aircraft would ight its own way, and all collisions would have to be avoided by reactive systems. Each aircraft would be in charge of its own security. This could be called a completely free ight system. The free ight hypothesis is currently seriously considered for all aircraft ying \high enough" in a quite near future.

Of course, no ATC system will ever totally rely on only one of these two hypothesis. It is quite easy to understand why. A completely planned ATC is impossible, as no one can guarantee that each and every trajectory would be perfectly followed; there are too many parameters that can not be perfectly controlled: meteorological conditions (storms, winds, etc.), but also breakdowns in aircraft (motor, aps, etc) or other problems (closing of landing runaway on airports, etc.). On the other hand, a completely reactive system looks di cult to handle; it would only perform local optimizations for trajectories. Moreover, in the vicinity of departing and landing areas, the density of aircraft is so high that trajectories generated by this system could soon look like Brownian movements.

An ATC system can be represented by an assembly of lters, or shells. A classical view of the shells in an ATC system could be:

1. Airspace design (airways, control sectors, . . . ), When joining two airports, an aircraft must follow routes and beacons; these beacons are necessary for pilots to know their position during navigation and help controllers to visualize the tra c. As there are many aircraft simultaneously present in the sky, a single controller is not able to manage all of them. So, airspace is partitioned into di erent sectors, each of them being assigned to a controller. This task aims at designing the air network and the associated sectoring. 2. Air Tra c Flow Management (ATFM) (strategic planning, a few hours ahead), With the increasing tra c, many pilots choose the same routes, generating many con icts on the beacons inducing overloaded sectors. Tra c assignment aims at changing aircraft routes to reduce sector congestion, con icts and coordinations. 3. Coordination planning (a few minutes ahead), This task guarantees that new aircraft entering sectors do not overload the sector. 4. Classical control in ATC centers (up to 20 mn ahead), At this level, controllers solve con icts between aircraft. 5. Collision avoidance systems (a few minutes ahead). This level is activated only when the previous one has failed. This level is not supposed to be activated in current situations.

Each level has to limit and organize the tra c it passes to the next level, so that this one will never be overloaded.

In this paper, we present a problem solver that can handle the collision avoidance problem ( lter level 5) with reactive techniques. This problem solver is based on a neural network, which was built by a genetic algorithm.

Existing reactive techniques

The most well known concept on reactive collision avoidance is certainly the ACAS/TCAS concept. It is already implemented in its two rst versions (TCAS-I and TCAS-II). It is a very short term collision avoidance system (less than 60 seconds). It should only be thought as the last security lter of an ATC system. Using TCAS to control aircraft would probably end in serious problems. The TCAS algorithm is based on a the application of a sequence of ltering rules, which give the pilot a resolution advice.

A very simple technique to do reactive control has been investigated by 4]. The idea is to consider each aircraft as positive electric charges, while the destination of the aircraft is a negative charge. This way, each aircraft creates a repulsive force proportional to the inverse of the square of the distance, while the destination behaves like an attractor. This technique has a serious drawback. Symmetries can not be broken. This problem was solved by 9]. This system is slightly more complex, but the general idea is to add non symmetrical force: a force which has the direction of the repulsive force +90 degrees, and a module which is a small fraction of the module of the repulsive force is added to the repulsive force. This system solves the symmetrical problem. However, there are still some drawbacks: the di erent parameters of the attractive and repulsive forces are arbitrarily set, and it is unclear to de ne how to nd optimal values. Moreover, the shape itself of the forces is also arbitrarily set. But the main problem of this system is that it forces aircraft to modify their speed, and not only their heading. Unfortunately, the range of available speeds is very limited for aircraft ying at their requested ight level. Moreover, it is technically very di cult to change aircraft speed with a continuous command, as aircraft engines are easily damaged by this kind of operations.

Our system only allows heading modi cation and solves very complex two aircraft con ict, with almost optimal trajectories. Moreover, the system is very fast, as soon as the neural network has been built. Building neural networks with GA has already been done. An application quite similar was the problem of car parking described in 8]. However, our problem is de nitely more complex.

Modeling the problem

The problem we want to solve is the following. An aircraft ying at a constant speed detects another aircraft ying at the same altitude (more or less 1000 feet) in a 20 nautical miles diameter disk. We want to build a neural network that modi es, when there is a con ict the heading of this aircraft (respecting operational constraint of 45 degrees maximum per 15 seconds). The other aircraft is supposed to have the same embarked system so that it also detects the rst aircraft and reacts using the same neural network with di erent inputs.

The system uses an embarked radar to detect other aircraft. Consequently, all the inputs of the neural network must be given by the radar information.

Using a neural network

In our problem, it seems clear that if no con ict occurs, no neural network is needed to solve it. Consequently, at each time step, we will rst check if both aircraft can connect their destination without changing their heading and without generating con icts. In that case, we do not modify aircraft headings. If we detect a con ict in less than twenty minutes, we compute a new heading for both aircraft with the NN.

4.1

The inputs 7 inputs are used by the neural network (see gure 1) :

The heading of the destination and its absolute value j j (in degrees).

The distance to the other aircraft and its gradient d dt . The bearing of the other aircraft (in degrees)

The converging angle of the trajectories .

A bias set to 1.

4.2

The neural network structure

The neural network structure used is as simple as possible. A 3 layer network is used (see gure 2) and returns a heading change of 45 degrees maximum (for a time step of 15 seconds). The activation function used is the following :

act(s) = 1 1 + e ?s
The rst layer takes the 6 inputs described above plus the bias. The second layer holds 13 units, while the third layer holds the output unit.

Learning the neural network weights

Classical back propagation of gradient can not be used in our case because con ict free trajectories are not known in every con guration. They could be calculated for con icts involving n = 2 aircraft, but the problem is not solvable for n > 2. As we plan to extend our system to more than two aircraft, we decided to use unsupervised learning with GA. However, we will compare the results of our network with optimal trajectories computed by LANCELOT [START_REF] Conn | A comprehensive description of LANCELOT[END_REF] 2] to validate our hypothesis.

Genetic Algorithms

Figure 3 describes the main steps [START_REF] Goldberg | Genetic Algorithms[END_REF] of GAs that were used in this paper: rst a population of points in the state space is randomly generated. Then, we compute for each population element the value of the function to optimize, which we will call tness. Then the selection process reproduces elements according to their tness. Afterwards, some elements of the population are picked at random by pairs. A crossover operator is applied to each pair and the two parents are replaced by the two children generated by the crossover. In the last step, some of the remaining elements are picked Figure 3: GA principle at random again, and a mutation operator is applied, to slightly modify their structure. At this step a new population is been created and we apply the process again in an iterative way. The di erent steps are detailed in the following.

Coding the problem

Here, each neural network is coded by a matrix of real numbers that contains the weights of the neural network.

Selection

A method called "Stochastic Remainder Without Replacement Selection" 3] was used. First, the tness f i of the n elements of the population is computed, and the average a = P f i =n of all the tness is computed. Then each element is reproduced p times in the new population, with p = truncate(n f i =a). The population is then completed using probabilities proportional to f i ? p a=n for each element.

Crossover

The crossover operator we used was the barycentric crossover : 2 parents are recombined by choosing randomly 2 ?0:5; 1:5] and creating child 1 (resp child 2) as the barycentre of some randomly chosen weights of (parent 1 ; ) (resp (parent 1 ; 1 ? )) and (parent 2 ; 1 ? ) (resp (parent 2 ; )). In the further applications, the crossover probability used is 60%.

Mutation

The mutation operator used adds a noise to one of the weights of the neural network. The mutation probability used here is 15%.

Simulated Annealing Tournament

GA can be improved by including a Simulated Annealing process after applying the operators 6]. For example, after applying the crossover operator, we have four individuals (two parents P 1,P 2 and two children C1,C2) with their respective tness. Afterward, those four individuals compete in a tournament. The two winners are then inserted in the next generation. The selection process of the winners is the following: if C1 is better than P 1 then C1 is selected. Else C1 will be selected according to a probability which decreases with the generation number (any cooling scheme used in simulated annealing can be used). At the beginning of the simulation, C1 has a probability of 0:5 to be selected even if its tness is worse than the tness of P 1 and this probability decreases to 0:01 at the end of the process. A description of this algorithm is given on gure 4. Tournament selection brings some convergence theorems from the Simulated Annealing theory. On the other hand, as for Simulated Annealing, the (stochastic) convergence is ensured only when the tness probability distribution law is stationary in each state point 1]. Other global data are required by the Genetic Algorithm such as the number of generations, the number of elements, the percentage of elements to cross and the percentage of elements to mutate.

Computing the tness

One of the main issues is to know how to compute the tness of a chromosome. The constrained problem to solve takes the following criteria into account :

Aircraft trajectories must be con ict free. Delay due to deviation must be as low as possible. To compute the tness, a panel of di erent con ict con gurations is created. The tness is computed as follow : F = 1 D e ?V D is the average delay due to deviations and V is the average number of con ict violations.

The learning examples

To learn the weights of the neural networks, 12 con gurations were created. In each con guration, at t = 0 aircraft are 20 nautical miles distant. in 4 con gurations, aircraft have the same speed and converge with di erent angles (20, 60, 120, 150 degrees, see gure 5). in 4 con gurations, aircraft have di erent speed, their headings are calculated to generate a con ict (one aircraft speed is 500 knots and the other one is 300, 350, 400, and 450 see gure 6). in 2 con gurations, aircraft have opposite headings and the same speed (see gure 7). in 2 con gurations, aircraft have the same heading but di erent speeds (see gure 8). Because of symmetries, these 12 con gurations summarize all the situations that can happen. We will call \positive con guration" (see gure 9) a con guration in which the angle between the slowest aircraft and the fastest is positive. When a \negative con guration" occurs, the symmetrical positive con guration is used in the neural network to calculate the deviation. Therefore, some of the inputs and the output are given the opposite sign.

Numerical results

The neural network was learned using the following parameters : number of generations : 500 population elements : 500 percentage of crossover : 60 percentage of mutation : 15 simulated annealing for crossover : yes Optimal solutions to the di erent con gurations be calculated using gradient method such as LANCELOT LANCELOT has the great advantage to nd the optimal solution to our problems but requires much more time (one hour on HP720). It is then not usable to control aircraft in real time. However, it is interesting to compare optimal solutions found by LANCELOT to solutions learned by the neural network. Learned solutions are obviously less optimal, but the loss of optimality is not signi cant (the delay induced by the neural network is never more than twice the minimal delay, which is generally very small).

The con gurations used to compare the neural network to optimal solutions are not learned con gurations. We want also to validate the capacity of the NN to generalize to non-learned situations : Figure 10 gives an example of con ict at 90 degrees in which aircraft have the same speed. Neural network and optimal solution are similar. Figure 11 gives an example of con ict at 15 degrees in which aircraft have the same speed. Such a con ict is particularly di cult to solve. Solu-Figure 10: Neural network solution (left), optimal solution (right).

tions are di erent, but for such a di cult con ict, the neural network gives a solution that is good and robust. Figure 12 gives an example of aircraft at di erent speeds (400 and 500 knots) with crossing at a small angle (30 degrees). The neural network solution is very similar to the optimal solution. Figure 13 gives an example of aircraft crossing on the same route. This problem is easy to solve and solutions are similar. Figure 14 gives an example of aircraft ying on parallel routes at di erent speeds. This problem is easy to solve and solutions are similar.

Conclusion

Using a simple neural network to solve a con ict between 2 aircraft have given very good results. It was shown above that the neural network could be easily learned by a genetic algorithm without knowing the optimal solutions. The next step of this work will consist in extending the problem to con icts involving more than 2 aircraft. As the problem becomes very combinatory, some hypothesis will probably have to be made to limit the size of the neural network. The third step will be to integrate climbing an descending aircraft in the model and to generate vertical man uvres. The results presented above should be very soon used in a Test Bench to check their validity on real tra c.

Figure 1 :

 1 Figure 1: The neural network inputs of aircraft 1.

Figure 2 :

 2 Figure 2: The neural network structure.

Figure 4 :

 4 Figure 4: GA and SA mixed up

  gurations at the same speed.

Figure 6 : 1 Figure 7

 617 Figure 6: 4 con gurations at the di erent speeds.2 1

Figure 9 :

 9 Figure 8: 2 con gurations of facing aircraft.

Figure 11 :

 11 Figure 11: Neural network solution (left), optimal solution (right).

Figure 12 :

 12 Figure 12: Neural network solution (left), optimal solution (right).

Figure 13 :

 13 Figure 13: Neural network solution (left), optimal solution (right).

Figure 14 :

 14 Figure 14: Neural network solution (down), optimal solution (up).

List of Figures