Keywords

1 Introduction

The demand in air traffic has been growing mainly in the Asia-Pacific region, and current air traffic management (ATM) system is under considerable stress. To satisfy the increasing demand, the International Civil Aviation Organization (ICAO) published a new operational concept of global ATM in 2005 [9]. NextGen [5] and SESAR [4], the two major ATM programs initiated by the United States and Europe, respectively, are currently ongoing in order to support the new era of air transportation. In Japan, CARATS [16], the long-term vision for air traffic systems, was also proposed in 2010. In these ATM programs, the automated air traffic control (ATC) systems are necessary to meet future growth in air traffic by facilitating and alleviating the work of ATC. The primary concern of ATC is to maintain safe separation between aircraft, and one of the major safety critical situations is a midair conflict. When the minimum separation standard between aircraft is violated, a conflict occurs. The protected zone of an aircraft is generally defined as follows: the minimum allowed horizontal separation of en route airspace is 5 nm, and the vertical separation requirement is 1,000 ft. Air traffic controllers currently monitor the trajectories of aircraft and whether there are some potential conflicts within a lookahead time horizon.

There are two interconnected procedures to predict a midair conflict, i.e., trajectory prediction and conflict detection. In addition, typically, most of the proposed methods to solve the problems of trajectory prediction and conflict detection can be categorized into two approach, i.e., deterministic and probabilistic [11]. Because all problems in the real world contain uncertainties which arise due to disturbances, modeling and estimation errors, we cannot predict the future position of the aircraft completely. Therefore, in this study, we consider the problem of probabilistic conflict detection and propose the novel stochastic conflict detection algorithm by considering various uncertainties during flight, which is the key element for the realization of the future air traffic systems.

For trajectory prediction and conflict detection in a probabilistic setting, the empirical distribution model of future aircraft’s positions [12, 17, 24], the dynamical model by using stochastic differential equations that describe the aircraft motion [8, 19], or other probabilistic aircraft model [2, 14] is applied to the aircraft’s motion model. In this paper, we model the aircraft dynamics by using stochastic differential equations, and determine the future aircraft’s trajectory by solving the stochastic optimal control problem. The previous work in the area of stochastic optimal control includes the following. Blackmore et al. proposed the particle control method using mixed integer linear programming techniques [1]. However, their proposed approach relies on linear system dynamics, and is therefore difficult to apply to nonlinear aircraft dynamics. Liu and Hwang solved stochastic optimal control problems by discretizing the aircraft’s continuous dynamics to get a controlled Markov chain and then finding an optimal control law [15]. But the problem becomes intractable as the number of discrete states grows. Application of various statistical tools to the stochastic optimization problems is another commonly used approach. Lecchini-Visintini et al. proposed a Markov chain Monte Carlo framework to determine an approximate optimal control input [13]. Kantas et al. applied Bayesian optimal design and sequential Monte Carlo method to automatically generate optimal and safe maneuvers [10]. Prandini et al. also employed the Monte Carlo simulation [19]. However, using these statistical methods takes much computation time, and it is very difficult to implement them in the real applications of ATC. Therefore, to reduce the computational burden, we employ a recently developed computationally efficient method, generalized polynomial chaos (gPC) [22, 23], to solve the stochastic trajectory optimization problems. The gPC method applied to the stochastic trajectory optimization problem by Cottrill and Harmon [3], however their application is limited to a very little number of uncertainties or random variables. Therefore to overcome this disadvantage, we employ other approach which can be used for the larger number of random variables ( ≥ 5), and propose the stochastic optimization method. By using the stochastic trajectory optimization method, the novel conflict detection algorithm is proposed.

The paper is organized as follows. Section 2 presents the stochastic trajectory optimization method for trajectory prediction. In Sect. 3, probabilistic conflict detection algorithm is provided. Section 4 gives the numerical results and the effectiveness of our proposed algorithms is illustrated. Finally, conclusions and future research direction are provided in Sect. 5.

2 Trajectory Prediction

Our proposed stochastic optimization method combines the deterministic optimization method with the gPC method. In this section, we first introduce the deterministic trajectory optimization method, thereafter we propose the computationally efficient stochastic approach.

2.1 Deterministic Optimization Method

The following general continuous-time optimal control problem in Bolza form is considered. Determine the state variables, \(\boldsymbol{x}(t) \in {\mathbb{R}}^{n_{x}}\), the control variables, \(\boldsymbol{u}(t) \in {\mathbb{R}}^{n_{u}}\), the initial time, t 0, and the terminal time, t f , on the time interval, \(t \in [t_{0},t_{f}]\), that minimize the cost function given by:

$$\displaystyle{ J =\phi _{B}(\boldsymbol{x}(t_{0}),\boldsymbol{x}(t_{f})) +\int _{ t_{0}}^{t_{f} }g(\boldsymbol{x}(t),\boldsymbol{u}(t),t)dt }$$
(1)

subject to the dynamic constraints:

$$\displaystyle{ \frac{d\boldsymbol{x}} {dt} = \boldsymbol{f}(\boldsymbol{x}(t),\boldsymbol{u}(t),t) }$$
(2)

the inequality path constraints:

$$\displaystyle{ \boldsymbol{c}_{min} \leq \boldsymbol{c}(\boldsymbol{x}(t),\boldsymbol{u}(t),t) \leq \boldsymbol{c}_{max} \in {\mathbb{R}}^{n_{c} } }$$
(3)

and the boundary conditions:

$$\displaystyle{ \boldsymbol{b}_{min} \leq \boldsymbol{b}(\boldsymbol{x}(t_{0}),\boldsymbol{x}(t_{f})) \leq \boldsymbol{b}_{max} \in {\mathbb{R}}^{n_{b} } }$$
(4)

where ϕ B and g define the Mayer and Lagrange terms in the cost function, respectively, \(\boldsymbol{f}\) is the system dynamics, \(\boldsymbol{c}\) defines the path constraint functions, and \(\boldsymbol{b}\) expresses the boundary condition functions.

In this research, we apply the direct collocation pseudospectral method, which has increased in popularity for solving optimal control problems in recent years. Especially the Radau pseudospectral method [18] is employed to solve the optimal control problems. In the pseudospectral method, the dynamic variables (the state variables, \(\boldsymbol{x}(t)\), and the control variables, \(\boldsymbol{u}(t)\)), which depend on time, are approximated and parameterized using Lagrange polynomials. The cost function (Eq. (1)) and the constrains (Eqs. (2)–(4)) are also discretized using a quadrature rule, and the continuous-time optimal control problem is discretized and transcribed into a nonlinear programming (NLP) problem, then an NLP solver, such as sequential quadratic programming (SQP), is applied to determine the optimal solution.

In this paper, we employ the General Pseudospectral Optimization Software (GPOPS) [20], which is performed in MATLAB and using SNOPT [7] as the NLP solver. Using GPOPS, the continuous-time optimal control problem is transformed into the NLP problem for SNOPT NLP solver which finds the optimal solution. Therefore, GPOPS is employed as the deterministic solver in the gPC algorithm described in the next subsection.

2.2 Stochastic Optimization Method

Uncertainties during flight are considered as random variables, and the aircraft’s motion is described as stochastic differential equations. One of the most commonly used methods for solving stochastic differential equations is Monte Carlo method, or one of its variants such as the quasi Monte Carlo method. Monte Carlo method generates random samples of random variables based on their prescribed probability density function. Each random sample is inserted into the stochastic differential equations, and the stochastic problem is transformed into the deterministic problem that can be solved using deterministic methods. Using a set, or ensemble, of deterministic solutions, the statistical information (e.g., expected value (mean), variance and covariance) can be calculated. The Monte Carlo method is straightforward to implement because it only requires repetitive application of deterministic solvers. However, it is well known that the mean converges slowly and a large number of executions are needed for accurate results, which implies excessive computational burden.

The gPC method is also easy to implement by using sample points of the random variables and repetitive executions of deterministic simulations as in the Monte Carlo method. However, to reduce the computational burden, the gPC algorithm uses the collocation points as the sample points and a polynomial approximation to determine the solution as described in detail later. By the gPC method, the stochastic solutions are expressed as orthogonal polynomials of the random variables, and the different types of orthogonal polynomials, such as Hermite and Legendre, can be chosen to achieve better convergence.

There are two main methods of the gPC algorithm, i.e., the Galerkin and the stochastic collocation. With respect to the implementation, a disadvantage of the Galerkin method is that it can be cumbersome and difficult to implement for complex and nonlinear systems [23]. In contrast, the stochastic collocation approach is straightforward and easier to implement because it can be solved by using the deterministic numerical solvers [22]. Therefore, in this paper, the stochastic collocation form of the gPC method is employed. The stochastic collocation form of the gPC algorithm is explained as follows.

By the gPC method, the solution \(\boldsymbol{z}(\boldsymbol{p})\) is approximated by the summation of the orthogonal polynomial of independent random variables \(\boldsymbol{p} = (p_{1},\ldots,p_{N}) \in {\mathbb{R}}^{N}\). The Mth order approximation of the solution \(\boldsymbol{z}_{M}(\boldsymbol{p})\) is written as the following equation.

$$\displaystyle{ \boldsymbol{z}_{M}(\boldsymbol{p}) =\sum _{ m=1}^{M}\boldsymbol{C}_{ m}\varPhi _{m}(\boldsymbol{p}) }$$
(5)

where \(\boldsymbol{C}_{m}\) is the coefficient, and \(\varPhi (\boldsymbol{p})\) represents the N-dimensional orthogonal polynomial basis function obtained from the one-dimensional basis function of each random variable ϕ(p i ) (i = 1, …, N) by the tensor product rule.

$$\displaystyle{ \varPhi _{m}(p_{1},\ldots,p_{N}) =\prod _{ i=1}^{N}\phi _{ i}^{l_{i} }(p_{i})\ (m = 1,\ldots,M,\ l_{i} = 1,\ldots,P) }$$
(6)

where P is the total degree of one-dimensional bases \({\phi }^{l_{i}}\), and M is the total number of tensor product basis functions and determined by the following binomial coefficient.

$$\displaystyle\begin{array}{rcl} M = \left (\begin{array}{c} N + P\\ N\\ \end{array} \right )& &{}\end{array}$$
(7)

In this paper, the normalized orthogonal polynomial basis is used by satisfying the following orthogonality condition.

$$\displaystyle{ E{[\phi }^{j}{(p_{ i})\phi }^{k}(p_{ i})] {=\int \phi }^{j}{(p_{ i})\phi }^{k}(p_{ i})\rho _{i}(p_{i})dp_{i} =\delta _{jk} }$$
(8)

where δ jk is the Kronecker delta function, and \(\rho _{i}(p_{i})\) is the probability density function corresponding to the ith random variable p i .

In addition, the coefficient \(\boldsymbol{C}_{m}\) in Eq. (5) is determined by the following equation.

$$\displaystyle{ \boldsymbol{C}_{m} = E[\boldsymbol{z}(\boldsymbol{p})\varPhi _{m}(\boldsymbol{p})] =\int \boldsymbol{z}(\boldsymbol{p})\varPhi _{m}(\boldsymbol{p})\rho (\boldsymbol{p})d\boldsymbol{p} }$$
(9)

where \(\rho (\boldsymbol{p})\) is the joint probability density function given by:

$$\displaystyle{ \rho (\boldsymbol{p}) =\prod _{ i=1}^{N}\rho _{ i}(p_{i}) }$$
(10)

Applying the stochastic collocation method, the integral in Eq. (9) can be approximated by using Gaussian quadrature. A set of collocation points and quadrature weights is chosen based on the quadrature rule. Though the N-dimensional quadrature is derived from the one-dimensional quadrature by the tensor product rule in the research by Cottrill [3], we employ the sparse grid quadrature based on extensions of one-dimensional or univariate Gaussian quadrature [6]. In general, as the number of random variables gets larger, the tensor product grid suffers the curse of dimensionality. However, the sparse grid with Q collocation points \({\boldsymbol{p}}^{j}\ (j = 1,\ldots,Q)\) and associated weights α j (j = 1, …, Q) consists of a very small number of the collocation points, and it can reduce the computational burden and increase the number of random variables or uncertainties. As in the Monte Carlo method, the stochastic problem is transformed into the deterministic problem on each collocation point, and can be solved by repetitive application of the deterministic method.

The approximation of Eq. (9) based on the quadrature rule is given by the following equation.

$$\displaystyle{ \boldsymbol{C}_{m} \approx \sum _{j=1}^{Q}\boldsymbol{z}({\boldsymbol{p}}^{j})\varPhi _{ m}{({\boldsymbol{p}}^{j})\alpha }^{j} }$$
(11)

where \(\boldsymbol{z}({\boldsymbol{p}}^{j})\) denotes the deterministic solution using the jth collocation point \({\boldsymbol{p}}^{j}\) of the random variables.

The approximate stochastic solution is determined by Eqs. (5) and (11) as the orthogonal polynomials of the random variables. The stochastic solution is a distribution function of the random variables and can be evaluated for any given random inputs. In addition, the statistical information of the stochastic solution can be calculated by using the coefficients given by Eq. (11), and evaluates how the solution varies with the random variables. The expected value of the solution is described as the following equation.

$$\displaystyle{ E[\boldsymbol{z}(\boldsymbol{p})] \approx E[\boldsymbol{z}_{M}(\boldsymbol{p})] =\int \left [\sum _{m=1}^{M}\mathbf{C}_{ m}\varPhi _{m}(\boldsymbol{p})\right ]\rho (\boldsymbol{p})d\boldsymbol{p} = C_{1} }$$
(12)

The variance is calculated by the following equation.

$$\displaystyle\begin{array}{rcl} var[\boldsymbol{z}(\boldsymbol{p})] = E[{(\boldsymbol{z}(\boldsymbol{p}) - E[\boldsymbol{z}(\boldsymbol{p})])}^{2}]& \approx & E[{(\boldsymbol{z}_{ M}(\boldsymbol{p}) - E[\boldsymbol{z}_{M}(\boldsymbol{p})])}^{2}] \\ & =& \int {\left [\sum _{m=1}^{M}\boldsymbol{C}_{ m}\varPhi _{m}(\boldsymbol{p}) - C_{1}\right ]}^{2}\rho (\boldsymbol{p})d\boldsymbol{p} \\ & =& \sum _{m=2}^{M}{\left [\boldsymbol{C}_{ m}\right ]}^{2} {}\end{array}$$
(13)

By the theory of the gPC method, the stochastic solution including the statistical information (expected value and variance) is approximated and determined. Using the gPC algorithm mentioned above, in this paper, the gPC method with GPOPS as the deterministic trajectory optimization solver is applied to the stochastic trajectory optimization problems.

2.3 Stochastic Trajectory Prediction Algorithm

In this study, the time of arrival at the waypoint from the aircraft’s current position is predicted by using our proposed stochastic optimization algorithm. The procedures of the algorithm are listed as follows.

  1. 1.

    Generate a set of collocation points \({\boldsymbol{p}}^{j}\ (j = 1,\ldots,Q)\) and associated weights α j (j = 1, …, Q).

  2. 2.

    Calculate the values of the orthogonal polynomial basis functions \(\varPhi _{m}({\boldsymbol{p}}^{j})\ (m = 1,\ldots,M,\ j = 1,\ldots,Q)\).

  3. 3.

    Solve the Q deterministic trajectory optimization problems using the Q collocation points \({\boldsymbol{p}}^{j}\ (j = 1,\ldots,Q)\), and determine the solution \(\boldsymbol{z}({\boldsymbol{p}}^{j})\ (j = 1,\ldots,Q)\) (z is the time of arrival or the terminal time t f of the trajectory optimization problem in this paper).

  4. 4.

    Calculate the coefficients \(\boldsymbol{C}_{m}\ (m = 1,\ldots,M)\).

  5. 5.

    Calculate the statistics of the approximate solution, the expected value \(E[\boldsymbol{z}(\boldsymbol{p})]\) and the variance \(var(\boldsymbol{z}(\boldsymbol{p}))\), from the coefficients \(\boldsymbol{C}_{m}\).

2.4 Numerical Simulation

In this subsection, numerical simulation is conducted to verify the effectiveness and performance of our proposed stochastic trajectory optimization method.

2.4.1 Problem Setting

We consider the aircraft flying in two-dimensional plane, the ξ and η coordinate frame as shown in Fig. 1. The state variables are defined as \(\boldsymbol{x}(t) = {(\xi,\eta,\psi )}^{T}\) where ψ is the heading angle, and the control variable u(t) is the bank angle. The control variable is bounded as | u(t) | ≤ 35∘. The aircraft dynamics are described in the following equations.

$$\displaystyle\begin{array}{rcl} \dot{\xi }& =& v\cos \psi + w_{\xi } \\ \dot{\eta }& =& v\sin \psi + w_{\eta } \\ \dot{\psi }& =& \frac{g} {v}\tan u {}\end{array}$$
(14)

where g is the acceleration of gravity: 9. 8 m∕s2, v is the airspeed (true airspeed), and (w ξ , w η ) are the wind velocities in the ξ and η directions. v is assumed to be the constant speed of 480 knots.

As shown in Fig. 1, the initial and terminal conditions (t f is the terminal time) are as follows.

$$\displaystyle\begin{array}{rcl} \boldsymbol{x}(0)& =& {(0,0,0)}^{T} \\ \boldsymbol{x}(t_{f})& =& {(40,0,0)}^{T}{}\end{array}$$
(15)

For solving the optimal control problems, the cost function J is minimized and given by the following equation.

$$\displaystyle{ J = 1{0}^{-4} \cdot t_{ f} +\int _{ 0}^{t_{f} }{u(t)}^{2}dt }$$
(16)
Fig. 1
figure 1

Problem setting for trajectory prediction

Full size image

Furthermore, as the uncertainties during flight or random variables for the gPC method, the wind prediction error, the airspeed measurement error, and the current position estimation error are considered. In this paper, we consider the aircraft flying in two-dimensional horizontal plane, and the wind prediction error and the current position estimation error are divided into two components, i.e., the longitude and latitude directions. Then, we consider five random variables. In addition, we assume that these uncertainties are modeled as the standard deviations of the Gaussian distributions, and the values are 5. 17 m∕s for the wind prediction errors, 2. 57 m∕s for the airspeed measurement error and 50 m for the current position estimation errors [2, 17, 21, 24]. The wind prediction error represents uncertainty in the meteorological prediction, and for simplicity the only wind prediction error is considered. Because the Gaussian distributions are used for the uncertainties in this paper, Hermite polynomial basis functions collocated at Gauss-Hermite quadrature points are selected for the gPC method as suggested in the paper by Xiu [22].

The stochastic solution of the terminal time t f is calculated by using our proposed stochastic approach. In addition, to verify the effectiveness and performance of our proposed method, the stochastic solution is computed by using Monte Carlo method, one of the most commonly used methods for solving stochastic differential equations, and compared with the solution that is calculated by using our proposed approach.

2.4.2 Simulation Results

Table 1 shows the expected value E[t f ] and standard deviation \(\sqrt{var[t_{f } ]}\) (derived from the variance var[t f ]) of the terminal time t f by using the gPC and Monte Carlo methods. The estimated solutions given by the gPC and Monte Carlo methods (i.e., E[t f ] and \(\sqrt{ var[t_{f}]}\)) closely match each other. It indicates that the gPC algorithm can estimate a reasonable solution. In addition, as shown in Table 1, by using the Monte Carlo method, the estimation of the solution converges after 20,000 iterations, requiring about five and a half hours. On the other hand, the gPC method requires only 51 collocation points for five random variables by using the sparse grid quadrature. The total number of multidimensional bases M and one-dimensional bases P are 56 and 3, respectively. Computation time is approximately 45 s for solving the 51 trajectory optimization problems and determining the solution by constructing the gPC approximation. Our proposed algorithm performs much faster than the Monte Carlo method does. Therefore our proposed gPC method provides an accurate approximate solution of the stochastic trajectory optimization problem while dramatically reducing computational cost.

Table 1 Comparison between gPC and Monte Carlo methods
Full size table

3 Conflict Detection

By using the trajectory prediction algorithm described in Sect. 2, we propose the estimation method of the conflict probability between aircraft in this section. First, the conflict probability between aircraft is defined, thereafter the estimation method of the conflict probability is described.

3.1 Conflict Prediction

In this study, the specific conflict scenarios, the merging situations at the waypoint (merging point), are considered. As described in Sect. 2, the time of arrival at the merging point from the aircraft’s current position can be predicted. Based on this trajectory prediction algorithm for two or multiple aircraft, a possible conflict between aircraft is detected. A conflict (not a collision) is defined as a situation where two or more aircraft come within the required minimum separation standard between each other. We consider multiple aircraft flying at the same altitude, and the required minimum separation is set to 5 nm horizontally. For simplicity, it is assumed that all aircraft pass at the merging point at the same speed of V knots. Therefore, the minimum distance separation can be transcribed into the minimum time separation \(\varDelta T_{sep} = 5 \cdot 3600/V\) s.

The purpose of the conflict prediction is to compute the probability that any two aircraft will be in conflict at the merging point. By using the stochastic trajectory prediction algorithm, the expected value and variance (or standard deviation) of the time of arrival at the merging point are calculated. The probability distribution of the time of arrival is assumed to be the Gaussian distribution. Therefore, we can determine the Gaussian distributions of the two aircraft, labeled A and B, P A (t) and P B (t), respectively. The conflict probability between the two aircraft can be determined by using these Gaussian distributions. The estimation method of the conflict probability is described in the next subsection.

3.2 Conflict Probability Estimation

We use the convolution integral to estimate the conflict probability. The conflict probability CP A−B between the aircraft A and B is given by the following equations.

$$\displaystyle\begin{array}{rcl} CP_{A-B}& =& \int _{-\varDelta T_{sep}}^{\varDelta T_{sep} }P_{A-B}(\tau )d\tau {}\end{array}$$
(17)
$$\displaystyle\begin{array}{rcl} P_{A-B}(\tau )& =& \int _{-\infty }^{\infty }P_{ A}(t)P_{B}(t+\tau )dt{}\end{array}$$
(18)

where P A−B (τ) given by Eq. (18) expresses the conflict probability when the time separation (the time difference of the time of arrival) at the merging point between the aircraft A and B is τ. Therefore, by using Eq. (18), the conflict probability is described in Eq. (17), because the conflict occurs when τ satisfies the following condition: −Δ T sep  ≤ τ ≤ Δ T sep .

By the theory of the convolution integral, P A−B (τ) given by Eq. (18) is expressed as the Gaussian distribution. Therefore, by using Eqs. (17) and (18), the conflict probability between any two aircraft can be estimated.

4 Numerical Simulation

In this section, numerical simulation is conducted to verify the effectiveness and performance of our proposed stochastic approach to detect conflicts. We consider various conflict scenarios, especially merging situations, between two or multiple aircraft.

4.1 Problem Setting

We consider the aircraft flying in two-dimensional horizontal plane. The two cases are considered: the meteorological prediction for the aircraft dynamics is not considered in Case 1, and considered in Case 2. The meteorological prediction data are provided by the Japan Meteorological Agency as a grid format of longitude and latitude. Therefore, to obtain the required wind predictions, linear and bilinear interpolations are applied. In addition, because the meteorological prediction data are provided as a grid format of longitude and latitude, the longitude θ and latitude ϕ coordinate frame is considered in Case 2, whereas the ξ and η coordinate frame is considered in Case 1. The state variables are defined as \(\boldsymbol{x}(t) = {(\xi,\eta,\psi )}^{T}\) in Case 1 and \(\boldsymbol{x}(t) = {(\theta,\phi,\psi )}^{T}\) in Case 2, and the control variable u(t) is the bank angle. The control variable is bounded as | u(t) | ≤ 35∘. The aircraft dynamics in Case 1 are given by Eq. (14), and the dynamics in Case 2 are described in the following equations.

$$\displaystyle\begin{array}{rcl} \dot{\theta }& =& \frac{v\cos \psi + w_{\theta }} {(R + h)cos\phi } \\ \dot{\phi }& =& \frac{v\sin \psi + w_{\phi }} {R + h} \\ \dot{\psi }& =& \frac{g} {v}\tan u {}\end{array}$$
(19)

where R is the Earth’s radius: 6. 37 × 106 m, h is the altitude, and (w θ , w ϕ ) are the wind velocities in θ and ϕ directions. The altitude is assumed to be a constant 35, 000 ft.

Fig. 2
figure 2

Problem setting for conflict detection in Case 1

Full size image

As the uncertainties during flight, the wind prediction error, the airspeed measurement error, and the current position estimation error are also considered as described in Sect. 2.4.1. In addition, Hermite polynomial basis functions collocated at Gauss-Hermite quadrature points are chosen for the gPC method. Furthermore, for solving the optimal control problems, the cost function J given by Eq. (16) is minimized.

For the gPC method, the number of collocation points for five random variables is set to 51 by using the sparse grid quadrature, and the deterministic trajectory optimization problems are solved repetitively. In addition, the total number of multidimensional bases M and one-dimensional bases P are 56 and 3, respectively. The solutions including the statistical information such as the expected value and variance (or standard deviation) are calculated. The merging situations in Case 1 and 2 are explained as follows.

4.1.1 Merging Scenario in Case 1

As illustrated in Fig. 2, we consider the merging scenarios of the two aircraft, labeled A and B, flying at the same altitude and the same speed of V = 480 knots (true airspeed). The distance between the position of the aircraft A and the merging point is set to D nm, and the distance between the position of the aircraft B and the merging point is longer and set to D + d sep  (d sep  ≥ 0) nm. The initial and terminal conditions of the aircraft A and B are as follows.

$$\displaystyle\begin{array}{rcl} \boldsymbol{x}_{A}(0)& =& {(-D,0,0)}^{T} \\ \boldsymbol{x}_{A}(t_{fA})& =& {(0,0,0)}^{T} \\ \boldsymbol{x}_{B}(0)& =& {(0,-(D + d_{sep}),\pi /2)}^{T} \\ \boldsymbol{x}_{B}(t_{fB})& =& {(0,0,\pi /2)}^{T} {}\end{array}$$
(20)

where t fA and t fB are the terminal time (or the time of arrival at the merging point) of the aircraft A and B, respectively.

We can generate various merging situations with various combinations of D and d sep . In this paper, D is set to 80 and 160 nm and d sep is set to 5 and 10 nm, and the total number of the merging scenarios is four. For each combination, the conflict probability is estimated and evaluated by using our proposed stochastic method described in Sect. 3.

4.1.2 Merging Scenario in Case 2

As shown in Fig. 3, the merging scenario of the three aircraft, labeled A, B, and C, flying at the same altitude (35, 000 ft) and the same speed of V = 450 knots (true airspeed) is considered. The initial and terminal conditions of the aircraft A, B, and C are as follows.

$$\displaystyle\begin{array}{rcl} \boldsymbol{x}_{A}(0)& =& {(138.5,34.75,0)}^{T} \\ \boldsymbol{x}_{A}(t_{fA})& =& {(140,35.5,\pi /2)}^{T} \\ \boldsymbol{x}_{B}(0)& =& {(139,34.25,0)}^{T} \\ \boldsymbol{x}_{B}(t_{fB})& =& {(140,35.5,\pi /2)}^{T} \\ \boldsymbol{x}_{C}(0)& =& {(139.5,34.25,0)}^{T} \\ \boldsymbol{x}_{C}(t_{fC})& =& {(140,35.5,\pi /2)}^{T}{}\end{array}$$
(21)

where t fA , t fB , and t fC are the terminal time (or the time of arrival at the merging point) of the aircraft A, B, and C, respectively.

Using our proposed stochastic approach described in Sect. 3, the conflict probability between the pairwise aircraft is estimated and evaluated.

Fig. 3
figure 3

Problem setting for conflict detection in Case 2

Full size image

4.2 Simulation Results

In Case 1, Figs. 4 and 5 show the probability distributions of the time of arrival at the merging point for the combinations of D and d sep . Table 2 indicates the conflict probabilities for the combinations of D and d sep . As shown in Table 2, when d sep is 10 nm, the conflict probability is lower than that of when d sep is 5 nm due to the longer time separation between the aircraft A and B. When d sep is 10 nm, as D becomes larger, the conflict probability becomes much higher. On the other hand, when d sep is 5 nm, the conflict probability of when D is 160 nm is not much different from that of when D is 80 nm. The reasons of this are as follows. As shown in Figs. 4 and 5, when D becomes larger, the standard deviation of the time of arrival gets larger and the probability distribution grows wider. Accordingly, when d sep is 10 nm, the range in which the two probability distributions overlap each other is much larger. In contrast, when d sep is 5 nm, the range of when D is 80 nm is not much different from that of when D is 160 nm. As a result, when d sep is 10 nm, the conflict probability of when D is 160 nm is higher than that of when D is 80 nm. On the other hand, when d sep is 5 nm, the conflict probability of when D is 160 nm is not much different from that of when D is 80 nm.

Fig. 4
figure 4

Probability distribution of time of arrival in Case 1 (D = 80 nm) (mean value: 600.49 (A), 638.02 (B (d sep  = 5 nm)), 675.55 (B (d sep  = 10 nm)), standard deviation: 14.07 (A), 14.95 (B (d sep  = 5 nm)), 15.83 (B (d sep  = 10 nm)))

Full size image
Fig. 5
figure 5

Probability distribution of time of arrival in Case 1 (D = 160 nm) (mean value: 1200.97 (A), 1238.50 (B (d sep  = 5 nm)), 1276.03 (B (d sep  = 10 nm)), standard deviation: 28.14 (A), 29.02 (B (d sep  = 5 nm)), 29.90 (B (d sep  = 10 nm)))

Full size image
Table 2 Conflict probability in Case 1
Full size table

In addition, the computation time for calculating the time of arrival and each conflict probability is about 1 min. Our proposed probabilistic approach can provide reasonable solutions while dramatically reducing computational cost.

In Case 2, Fig. 6 shows the probability distributions of the time of arrival at the merging point for the three aircraft. The position of the aircraft C is nearest to the merging point among the three aircraft and the mean value of the time of arrival of the aircraft C is the smallest as shown in Fig. 6. On the other hand, the position of the aircraft B is farthest to the merging point and the mean value of the time of arrival of the aircraft B is the longest. As shown in Fig. 6 and Table 3, the distributions of the three aircraft and the conflict probabilities are effectively calculated. In addition, the computation time for calculating the time of arrival is approximately 1 min. In Case 2, the conflict probabilities and the time of arrival can be calculated by using our proposed computationally efficient method.

Fig. 6
figure 6

Probability distribution of time of arrival in Case 2 (mean value: 674.55 (A), 736.66 (B), 641.28 (C), standard deviation: 15.01 (A), 17.27 (B), 14.94 (C))

Full size image
Table 3 Conflict probability in Case 2
Full size table

Therefore, through the numerical simulations in Case 1 and 2, we can confirm the effectiveness and performance of our probabilistic algorithm for detecting possible conflicts by using the computationally efficient gPC method.

5 Conclusions and Future Work

In this paper, we proposed the gPC method for solving the stochastic trajectory optimization problem and estimating the conflict probability. As the sample problems, the numerical simulation for the trajectory prediction demonstrated that our proposed computationally efficient method can generate the accurate approximation of the solution of the stochastic trajectory optimization problem by determining and characterizing the statistical information, i.e., the expected value and variance. In addition, we estimated and evaluated the conflict probability between the pairwise aircraft in two merging scenarios by using the stochastic trajectory prediction algorithm. Through the numerical simulations for trajectory prediction and conflict detection, the performance and effectiveness of our novel probabilistic approach was evaluated and verified.

The purpose of trajectory prediction and conflict detection is to resolve an impending conflict. For conflict resolution, we need to decide the time to initiate a resolution maneuver and select the maneuver to execute. For solving the problem of conflict resolution, knowledge of the conflict probability help to establish the optimal time to initiate the resolution maneuver as well as the characteristics of the maneuver. Further research will focus on applying stochastic trajectory optimization for conflict resolution problems. Besides, for improving our stochastic algorithms, our proposed stochastic method is currently being extended for three-dimensional aircraft dynamics. In addition, the random variables will be assumed to have the different kinds of probability density function, and it will lead to a mix of the different kinds of polynomials in the gPC method. Furthermore, we will consider the time-varying random variables such as time-varying wind prediction error. By introducing the time-varying random variables, the number of random variables and computational burden will be increased, however, our stochastic approach has a potential for solving such a difficult problem.