STABLE PARTITION OF TRAJECTORIES SET INTO ASYMPTOTICALLY CONVERGED BEAMS

A system and method for data tracking, processing, and analysis of multidimensional space trajectories of moving objects. The method is particularly applicable for moving objects having closely spaced final targets, such as aircraft landing at airport runways. The method may be used for air space sectorization. The method is provided for determining the number of asymptotically converged beams of the trajectories in 3D-space. Points of the trajectory sample are scattered into a set of independent points of the trajectories. Two-dimensional orthogonal projection of the set of points is considered and the most likelihood orthogonal linear regression of the points is defined. Such linear regression represents an asymptote tangential to a beam. Certain beam of trajectories is separated in reverse transition into original data space.

PRIORITY STATEMENT

This application claims the benefit of Russian Patent Application No. 2015139739.

FIELD OF INVENTION

The present invention generally relates to the field of data mining, data track mining and, specifically, to the processing and analysis of multidimensional space trajectories of moving objects with common targets and close final space coordinates, as, in particular, aircraft intent trajectories in airport runways.

BACKGROUND OF THE INVENTION

Currently, due to increasing data volume, it is important to design methods and tools for rapid and automatic processing of large data sets. New approaches are required for analysis of large data sets (like unsupervised data mining or other machine learning technics), that can recognize hidden patterns of motion and identify moving objects with similar characteristics and/or the same final targets.

In many areas, particularly, in aviation, it is necessary to process huge sets of trajectory data for monitoring, control or other purposes. Aircraft trajectory is represented by four-dimensional description of the aircraft states with time, where state may include a position of aircraft center of mass and other characteristics of the motion, like velocity, attitude and weight. So, in general, the space trajectory is a multidimensional description of moving object path.

According to statistical data, the large number of avionics incidents takes place in extended airport area due to increased work load of air traffic management (ATM) systems. While air traffic is permanently increased, modernization and optimization of ATM systems are needed to maintain high level of safety.

Automation system TRACON (Terminal Radar Approach Control) [1,2] disclosed in U.S. Pat. No. 6,393,358 is used for simplifying of activity of traffic control services, ensuring air traffic control and reducing workload of air space within the extended airport area. The systems as described allow ensuring of air traffic control within air space and increase airspace capacity. TRACON is used for establishing a spacing reference geometry, predicting spatial locations of a plurality of aircraft at a predicted time of intersection of a path of a first of said plurality of aircraft with the spacing reference geometry, and determining spacing of each of the plurality of aircraft based on the predicted spatial locations.

Aircraft trajectories' analysis is essential for optimization of air traffic control operations, minimization of losses in air traffic efficiency, airspace corridor design, space sectorization, creation of unmanned aerial vehicles, etc. For example, US 20140019033 A1 describes a method of air traffic planning that includes defining an arrival network of nodes and legs, used for optimization of schedule of arrived aircrafts.

Data mining methods are widely used in investigations on work load optimization in extended airport area. The methods are, in particular, used for air space sectorization, i.e. space partitioning into the sectors or zones of different controllers' responsibility. Air space sectorization should be done taking into account regular flows of motion that are described by the samples of aircraft trajectories.

Up to date sectorization problem is solved in considering 2D-projection of the aircrafts' trajectories by its' clustering [3] or space partitioning into the regions like Voronoi-diagrams [4].

Development of the 3D-sectorization algorithm is at initial stage and associated with the problem of trajectory beams revealing (separation) in 3D-space. Trajectory beams are corresponding to the groups of 3D-trajectories with similar characteristics. For trajectory sample partitioning into the beams such methods as PCA [5], nonparametric approach based on Dynamic Bayesian Networks [6], spectral clustering [7] are used. The methods are based on reduction of analyzed data space dimensions.

In analyzing the sets of multidimensional space movement trajectories, their special features like multiple intersections, curvature and torsion (seeFIG. 1a) should be taken into account. So, it is desirable to use a similarity measure that would allow to distinguish the trajectories with similar shape even if they are mutually spaced. The similarity measure should reflect likeness (or distinction) of trajectory shapes in 3D-space.

If the objects move to common (defined, given) targets and their final coordinates are close, the object trajectories form converged beams of multidimensional space trajectories of motion, like in the case of intent trajectories of aircrafts landing on the same runway (SeeFIG. 1b). Generally, the trajectories in such beams may have multiple intersections. Beam convergence is defined by a threshold parameter. Threshold parameter for aircraft trajectories' beams does not exceed a runway width.

In the present invention a new approach [8] to analysis of multidimensional trajectories of moving objects with common targets and close in coordinates is proposed. The present invention permits to separate asymptotically converged beams of trajectories and is based on determination of geometric asymptote tangent to multidimensional trajectory beam in the lower dimension space. Then trajectory beam is separated in the result of reverse transition to the original data space. Such approach, while being applied to the analyses of real data (like radar data), allows getting stable results.

DETAILED DESCRIPTION OF THE INVENTION

Assessment of Beam's Asymptote

Trajectory beam Nk, k=1,K0(K0is empirical parameter) is considered as asymptotically converged with a threshold parameter ε, if for all vectors {x[i]∈R3×L, i∈Nk} in the beam Nk, k=1,K0, a condition of asymptotic convergence of the beam is fulfilled

where (∀i∈Nk, x[Li;i] are coordinates of final trajectory points on a runway. Parameters Li, i∈Nkare subject to determination, ∥. . . ∥2is Euclidean distance metric in three-dimensional coordinate space R3, ε is a cutoff parameter with value of no more than runway width. In considering the claimed approach to determination of the number of asymptotically converged beams, it should be taken into account that the trajectories in the beams have some typical form (profile) and specific geometric asymptote in the region of convergence (1). Geometric asymptote in converged beam of multidimensional aircraft intent trajectories is a line in R3that meets the requirement (1). Trajectories in asymptotically converged beam have tangent line in area around the final points ∀i∈Nk, x[Li;i]. So, asymptotically converged trajectory beams can be identified by determination of their tangential geometric asymptotes in the points of their focuses.

Because discrete points of beam trajectories are tightly located around its' asymptote, to determine the number of asymptotically converged beams a sample of trajectory vectors {x[i]∈R3×L, i=1, N} is scattered into set of the trajectories' points

Set of the points (2) has to be sorted according to the values of one of the coordinates (in ascending or descending order). At that, other coordinates of points, representing converged trajectory beam of certain profile, are also ordered. Then, for the scattered three-dimensional data {zi=(xi, yi, zi), i=1,L·N} (2); orthogonal linear regression models

are analyzed by RANSAC (Random Sample and Consensus) algorithm Here symbolis conjunction, θ={a1,b1,c1,d1, a2,b2,c2,d2} is vector of the parameters of the models (3), that is determined under given cutoff of Euclidian distance ρ⊥(z,M(θ)) calculated by orthogonal projection of point z=(x, y, z) from the set (2) onto a line M (θ). By such a way the model (3) is symmetrical relatively to the coordinates x, y, z . Any pair of the points from (2) is sufficiently to put forward a hypothesis about the model of orthogonal linear regression (3). Final model (3) is proved by the greatest relative quantity (percent) of scattered data {zi=(xi, yi, zi), i=1,L·N} (2). Algorithm MLESAC (Maximum Likelihood Estimation Sample Consensus) [12], that is probabilistic modification of RANSAC [11] algorithm, may be used for these purposes. The algorithm estimates likelihood of the model (3), in representing distance distribution of scattered data {zi=(xi, yi, zi), i=1, L·N} from the model M(θ) (3) as a mixture of data distributions some of which support the model (3) (inliers), while the rest ones reject it (outliers). Considering the scattered data Z (2) as independent, we obtain a relation for logarithm of likelihood as following

where γ is mixing parameter. Distribution of the distances to the data, supporting the model (3), is represented by Gaussian distribution

where σ is standard deviation. Distribution of distances to the data, rejecting the model (3), is described by uniform distribution

where ρmaxis maximal distance to data (it is defined by the context). Likelihood logarithm (4) minimization allows to evaluate vector of the parameters θ and mixing parameter γ. Estimation of the parameters is traditionally done using EM-algorithm [13].

It is obvious for the specialist, that apart from the algorithms considering at the present work in determining of the geometric asymptote M(θ)[k], k=1,K(3) of one of the beams under condition (1), other methods can be used.

The most likely linear regression of the scattered data of trajectory sample defines geometric asymptote M(θ)[k], k=1, K(3) of one of samples' beams under (1). The geometric asymptote received in such a manner meets the requirement

Separation of Trajectory Beam

Beams of the trajectories tangential to the geometric asymptotes are defined as the result of minimization of a cost function

where {r[i;k]∈{0,1}, k=1,K}, i=1,Nis set of binary indicator variables (e.g. if vector x[i] was attributed to the beam k , then r[i;k]=1 and r[i;k]=0, otherwise). Distance between each geometric asymptote and the sample's trajectories is calculated according to cosine measure

After elimination of the points, representing the trajectories of separated beam, from the scattered data (2), the procedure of geometrical asymptote detection is repeated and the next trajectory beam is separated. In this case, remained scattered data (2) are sorted with respect to another space coordinate (different from the previous one), as the model determination should be symmetric relatively to the coordinates x, y, z. Possible dependence of result (3) from the coordinate directions is obviated by changing direction of data ordering in (2) from ascending to descending order or vice versa. Analysis of trajectory sample is completed, when all beams in the sample are separated (seeFIG. 4h).

In general, the approach described in the claimed invention consists of two stages. Sufficient reduction of data dimensions at the first stage simplifies the revealing of data specific features. In considering 2D-projection of scattered points of 3D trajectories, the most likelihood orthogonal linear regression of the scattered data which corresponds to geometrical asymptote of one of the beams in analyzed sample of the trajectories is defined. At the second stage of the approach, after reverse transferring into the original dimensional space, a certain beam is separated from the analyzed trajectory sample in accordance with proximity (by cosine measure) to defined asymptote. Thus, due to such approach no information about original data is lost. Detailed scheme of the claimed invention is shown inFIG. 5.

REFERENCES