FLIGHT CONFLICT FORECASTING BASED ON CHAOTIC TIME SERIES

Li Shanmei,Xu Xiaohao,Meng Linghang

(1.School of Computer Scienceand Technology,Tianjin University,Tianjin,300072,P.R.China;2.College of Air Traffic Management,Civil Aviation University of China,Tianjin,300300,P.R.China)

INTRODUCTION

There are complex nonlinear relationships causing traffic chaos in air traffic system.At present the domestic and foreign experts and scholars have made some results on traffic chaos[1-3].These studies are focused on ground transportation,and researches on air traffic chaos have not been seen. However, to realize the automation of air traffic management(ATM),the most important is to resolve the complex and chaos questions between certainty and randomness of ATM[4].Air traffic control(ATC)is a major component of ATM,the purpose of which is to prevent collisions between aircrafts and obstacles,and to make an orderly and efficient operation of air traffic[5]. Thus, the most important task of ATCis to prevent flight conflict.The definition of flight conflict is that the flight convergence in temporal-spatial aspects,and the flight separation violates the minimum separation standard.

Currently,researches on conflict detection are mainly focused on the micro level,that is to determine whether aconflict will occur in the near future among two or more aircrafts from engineering point of view[6-8],while researches on conflict forecasting from a macro level have not been seen.The frequency and difficulty of taking operations to avoid conflicts by controllers increase because of uncertainty in air traffic and weather changing, increasing conflicts and airspace restrictions. To forecast potential conflicts can alleviate the controllers′workload and increase the safety.Flight conflicts have two basic conditional characteristics of chaos system:Sensitivity to initial conditions and long-term unpredictability. Therefore it is necessary to study chaos characteristics on flight conflict.

Chaos theory is firstly used to study the physical characteristics of air traffic in this paper.In order to forecast flight conflict amount,chaotic identification of flight conflict time series must be done at first.Flight conflict time series can be defined as the data sequence of flight conflict amount obtained from equal time intervals according to time sequence.The flight conflict here is potential fligh t conflict.

In this paper,the fault tree analysis is firstly used to analyze chaotic characteristics of flight conflict based on the man-machine-environment system engineering theory.Then,the improved chaotic algorithm based on the small-data method and the wavelet de-noising theory is established,which is used to identify and forecast chaotic time series.Lastly,the chaotic forecast algorithm is used to forecast the simulated data and forecasting results are evaluated.

1 CHAOTIC ANALYSIS OF FLIGHT CONFLICT

In 1981,Mr. Qian Xuesen,the famous scientist,proposed a system theory called manmachine-environment system engineering(MMESE)[9]. According to the theory, air traffic system is composed of four factors that construct a closed-loop system with specific features.These factors are man(pilots and controllers),aircraft,environment, and management. They are interdependent,mutual interacted and undivided.Therefore,the air traffic system is a complex dynamic system involving the behavior of man(pilots and controllers)and the air traffic environment.

In this paper,the man-machine-environment system approach is used to analyze flight conflict[10].A fault tree is established,shown in Fig.1.The flight conflict has nonlinear dynamic characteristic due to the highly nonlinear characteristic of human actions, weather conditions and other factors. They have uncertainty,universality,conductivity,invisible and unexpected features. The uncertainty of flight conflict reflects the randomness of chaotic phenomenon.The conductivity and suddenness of flight conflict shows that the results sensitively rely on initial conditions. Therefore, flight conflicts have obvious chaotic features,and their evolution cannot be described by determined mathematical equations.However,it is a good choice to study from data of observablevariables.

2 RECONSTRUCTION OF PHASE SPACE

Based on the reconstructed phase space theory of Packard and Takens theorem, the information used to determine system state is included in the time series evolution of any variables.The state trajectory obtained through embedding single variable time series into a new coordinate system maintains the most important characteristics of the original state trajectory[11].Therefore the main characteristics of flight conflict can be obtained by the single variableflight conflict time series.

Based on this idea,the flight conflict can be forecasted from the space angel. The basic method of reconstructing phase space is to reconstruct time delay coordinate[12-13].That is to construct m-dimensional statevector though delay variable.Make{xi,i=1,2,…,n}be thegiven time series.The m-dimensional phase is reconstructed by delay time f.The phase points of the phase space can be expressed as follows where M is the number of phase points in themdimensional phase space,M=n-(m-1)f,f the time delay,and n the number of samples in the original time series.

3 IMPROVED CHAOTIC ALGORITHM

In order to forecast flight conflict,the chaos identification is must be done at first.Thus in this section,the chaos identification algorithm and the chaos forecasting algorithm are introduced.

3.1 Chaos identif ication algorithm

Lyapunov exponent is an important quantitative indicator to measure the system dynamic characteristic, which represents the average exponential rate of convergence or divergence between adjacent tracks in phase space.The existence of chaos in the system can be determined by whether the maximum Lyapunov exponent is bigger than zero[14].

In this paper,an improved algorithm for the largest Lyapunov exponent based on the smalldata method and the wavelet de-noising theory is established.The specific steps are described as follows:

(1)The time series aregiven in Eq.(3).The sampling interval isΔt.

where n is the number of samples,x(ti)the value of time series.

(2)Remove noises of the original time series by the wavelet threshold de-noising method[15].The new series can be described as follows

(3)Transform the time series by fast Fourier transformation(FFT).The average period is T.

(4)Calculate the optimal delay time and the best embedding dimension of the reconstructed phase space by the autocorrelation method and the Cao algorithm[10].

(5)Reconstruct the phase space according to time delay and embedding dimension of phase space,which can be seen in Step(1).

(6) Find the nearest neighbors of each neighbor in the phase space and limit short-term separation.Y j′is obtained by the minimum distance between the reference points and other points.The minimum distance is described as follows

where‖ Y j-Y j′‖ is the Euclidean norm,and an additional condition is required,i.e.|j-j′|＞ T.

(7)Calculate the distance of Y j′and Y j after the i th discrete time step.

(8)Calculate the average value of ln d j(i),that is

where q is the number of non-zero dj(i),y(i)the average value of accumulation sum of the distance d j(i).

(9)Make the least squares regression line of y(i)curve,the slope of the line is the largest Lyapunov exponentλmax.

(10) Ifλmax＞ 0, there are chaotic characteristics in flight conflict time series.

The improved algorithm increases the signal to noise ratio(SNR)and the reliabilities of data signals through the process of wavelet denoising.The algorithm is reliable for the small size data and thecomputation is not large through small-data method. Therefore the improved algorithm improves the accuracy and the reliability of the largest Lyapunov exponent calculation.The computation is reduced and the efficiency is improved.

3.2 Chaos forecasting algorithm

Lyapunov exponent describes the geometric properties of phase space.It is a good parameter of chaos forecast. Wolf, et al proposed a forecasting method for chaotic time series by the largest Lyapunov exponent[16].The basic idea is to search the similarities from the historical time series.Based on the evolution of the similarities and the physical meaning of the largest Lyapunov exponent,some certain mathematical models are used to forecast time series.

Specific forecasting steps are described as follows:

(1)Based on the algorithm for chaotic identification,let Y N be thecenter,Y nb the nearest point of Y N,d the Euclidean distance of Y N and Y nb,then we have

(2)Y N+1and Y nb+1are theevolutions of Y N and Y nb.Based on the physical meaning of the largest Lyapunov and the similarities in the conflict system,we have

where Y N+1(m)is unknown and the rest numbers are given. Therefore the forecasting value of flight conflict can be described as follows

where″±″is chosen by the angles of space vectors.

4 CHAOS IDENTIFICATION OF FLIGHT CONFLICT TIME SERIES

4.1 Flight conflict time series

Because theactual data of flight conflict time series is very difficult to obtain. An airport approach control is simulated through air traffic control simulator in this paper.Theflight conflict amount is obtained by simulation exercises.

Fig.2 Time series of flight conflict

The sampling interval is taken to be 30 min.A time series of 256 simulated data about conflict amount is obtained,as shown in Fig.2.One action of avoiding conflict is calculated as one conflict.If the conflict is between two aircrafts,the conflict amount is 1.If the conflict is among n aircrafts,the conflict amount is n-1.

4.2 Chaos identification

In order to identify the chaotic characteristic of flight conflict,we must calculate the delay time and the embedding dimension at first.

The delay time is calculated by the autocorrelation method,as shown in Fig.3.The abscissa is delay time f,the vertical axis is the corresponding value of the autocorrelation function.It can be seen that the corresponding function value is minimal when f=7.That is,the correlation between the embedding coordinates is the smallest.Therefore,the delay time is taken to be 7 in this paper.

Fig.3 Delay time of time series

The embedding dimension is calculated by the Cao algorithm.The result is shown in Fig.4.E1(m)tends to be stable with the increase of m.It is used to determine the smallest embedding dimension.E2(m)is used to determine the chaotic feature of time series if its value tends to be 1 with the increase of m.Therefore,in this paper,the embedding dimension of the time series is 7.

The improved algorithm of the largest Lyapunov exponent proposed in this paper is programmed by Matlab. The value of the exponent is the slope of the straight line.The values of the largest Lyapunov exponent under different embedding dimension values are shown in Table 1.Obviously the values are all bigger than zero,which indicates that the flight conflict time series has chaotic characteristic.Therefore the chaos forecasting method can be used to forecast flight conflict.The result of m=7 is shown in Fig.5,where the slope of regression line is 0.002 6.

Fig.4 Embedding dimension

Table 1 Lyapunov exponent of diff erent embedding dimensions

Fig.5 The largest Lyapunov exponent of time series

4.3 Chaos forecasting

The last 50 data of the series are forecasted by the chaotic method and compared with the original data.The result is show n in Fig.6.It can be seen that the trends of original values and forecasted values areidentical.

The forecasting accuracy of the results is tested in order to verify the validity of this forecasting.The idea of performance test in grey system theory is used to determine the evaluation indexes.

Fig.6 Forecasting results of flight conflict

Let x(t)and x″(t)be actual and forecasted values,and e(t)=x″(t)-x(t)is absolute error,then we have

Correlative value of posterior error is

Micro-error probability is

A good forecasting model requires the value of C the smaller the better,the value of P the bigger the better.Generally,the value of C is smaller than 0.35,and its maximum cannot exceed 0.65.Thevalueof P is bigger than 0.95,and its minimum cannot be less than 0.7.

The results of performance test are shown in Table 2.It can be seen that every index meet the requirements of test accuracy. Therefore the forecasted results can reflect the trend of flight conflict amount.The chaos forecasting method has agood effect,which can be used to forecast the flight conflict amount.

Table 2 Results of performance test

5 CONCLUSIONS

(1)Based on the nonlinear characteristic of flight conflict, MMESE theory is used to establish a fault tree which is used to analyze the chaotic characteristics of flight conflict. The criterion of Lyapunov exponent is given in this paper.An improved chaotic algorithm of the largest Lyapunov exponents is proposed based on the small-data method and the wavelet de-noising theory.Finally,the existence of chaos in flight conflict is determined through simulation data.Objectively identifying the chaotic characteristics of flight conflict and analyzing the variation of conflict in hyperspace can help us understand the complex changes in flight conflict.

(2)Based on the chaos analysis and phase space reconstruction,the forecasting method for the largest Lyapunov exponent is used to forecast the flight conflict amount.The evaluation of the forecasting results shows that the method has a better effect.

(3)This paper only studies thereconstructed phase space from a single variable time series,and not very accurately describes the trajectory of state variables.Multivariate time series contains more rich information to construct multi-variable state space model,which is more accurate to grasp thevariation of the system.Thus,the next step of this research is to forecast the future running situation of air traffic through multivariate time series, and discuss the combination of the chaotic method and other forecasting methods.

[1] Dendrinos D S.Traffic-flow dynamics:A search for chaos[J].Chaos Solitons& Fractals,1994,4(4):605-617.

[2] Nagatani T.Chaotic jam and phase transition in traffic flow with passing[J].Physical Review E:Statistical Physics,Plasmas,Fluids,and Related Interdisciplinary Topics,1999,60(2):1535-1541.

[3] Wang J,Shi Q X,Lu H P.The study of short-term traffic flow forecasting based on theory of chaos[C]//IEEE Intelligent Vehicles Symposium Proceedings.Las Vegas,USA:IEEE,2005:869-874.

[4] Shi Heping.New theory of air traffic management[M].Xiamen:Xiamen University Press,2001.(in Chinese)

[5] General Administration of Civil Aviation of China.Air traffic management rules of China′s civil aviation[S].CCAR-93TM-R3,2000.(in Chinese)

[6] Krozel J,Peters M,Hunter G.Conflict detection and resolution for future air transportation management[R].NASA CR-97-205944,1997.

[7] Kuchar JK,Lee C Y.A review of conflict detection and resolution modeling methods[J]. IEEE Transactions on Intelligent Transportation Systems,2000,1(4):179-189.

[8] Prandini M,Hu J,Lygeros J,et al.A probabilistic approach to aircraft conflict detection[J].IEEE Transactions on Intelligent Transportation Systems,2000,1(4):199-220.

[9] Long Shengzhao,Huang Ruisheng.Man-machineenvironment system engineering theory and basic application[M].Beijing: Science Press,2004.(in Chinese)

[10]Zhou Jinyong,Gao Lan,Hua Qing.Prediction of vessel traffic accident based on chaotic theory[C]//The 9th International Conference for Young Computer Scientists.Zhangjiajie,China: ICYCS,2008:2727-2731.

[11]Huang Wenbiao,Shi Shiliang. Identification and empirical study of chaotic characteristics industrial accident time series[J].Journal of Xi′an University of Science and Technology,2010,30(1):24-38.(in Chinese)

[12]Packard N H,Crutchfield J P,Farmer J D,et al.Geometry from a time series[J].Physical Review Letters,1980,45(9):712-716.

[13]Takens F.Detecting strange attractors in turbulence[M].Berlin: Lecture Notes in Mathematics,1981:366-381.

[14]Lu Jinhu,Lu Junan,Chen Shihua.Chaotic time series analysis and its application[M].Wuhan:Wuhan University Press,2002.(in Chinese)

[15]Peng Yuhua. Wavelet transform and application[M].Beijing:Science Press,1999.(in Chinese)

[16]Wolf A.Determing Lyapunov exponents from a time series[J].Physica D,1985,16(3):285-317.