PaperlayerView exact revision on arXiv

Source-linked AI summary

Trajectory Clustering and an Application to Airspace Monitoring

Maxime Gariel, Ashok N. Srivastava, Eric Feron

arXiv:1001.5007v2cs.LG

TL;DR

The paper addresses the need to monitor aircraft behavior and process large volumes of trajectory records despite variability in pilot-controlled flight patterns. It develops two unsupervised trajectory-clustering methods and uses the learned nominal patterns for real-time conformance monitoring. The resulting AirTrajectoryMiner tool monitors SFO landings and supports a conformance-based measure of airspace complexity.

  • Problem

    Large volumes of recorded flights and variability in pilot-controlled patterns create a need for automated analysis of aircraft trajectories and nominal operations.

  • Method

    The paper clusters radar trajectories using waypoint sequences and principal components of resampled trajectories, then compares current flights with learned nominal trajectories.

  • Results

    The paper presents AirTrajectoryMiner, a real-time tool that monitors flight conformance to identified nominal procedures and measures airspace complexity from that conformance.

  • Takeaways & Limitations

    The monitoring tool is presented for SFO landings and can be modified to monitor other traffic patterns by changing its input dataset.

Abstract

from arXiv · show

This paper presents a framework aimed at monitoring the behavior of aircraft in a given airspace. Nominal trajectories are determined and learned using data driven methods. Standard procedures are used by air traffic controllers (ATC) to guide aircraft, ensure the safety of the airspace, and to maximize the runway occupancy. Even though standard procedures are used by ATC, the control of the aircraft remains with the pilots, leading to a large variability in the flight patterns observed. Two methods to identify typical operations and their variability from recorded radar tracks are presented. This knowledge base is then used to monitor the conformance of current operations against operations previously identified as standard. A tool called AirTrajectoryMiner is presented, aiming at monitoring the instantaneous health of the airspace, in real time. The airspace is "healthy" when all aircraft are flying according to the nominal procedures. A measure of complexity is introduced, measuring the conformance of current flight to nominal flight patterns. When an aircraft does not conform, the complexity increases as more attention from ATC is required to ensure a safe separation between aircraft.

INTRODUCTION

The paper addresses increasing air-traffic volume by developing data-driven methods to analyze recorded aircraft trajectories. It applies these methods to Northern California TRACON radar tracks, focusing on SFO landings and their operational context.

  • Motivation: NextGen and SESAR procedures require automated trajectory analysis to assess airspace concepts using large volumes of daily flight records.The paper identifies trajectory-record analysis as a key element for evaluating performance and navigation accuracy.
  • Approach: The framework clusters trajectories using waypoint sequences and principal components of resampled trajectories.The waypoint method identifies turning points, while the second method applies principal components analysis to resampled trajectories.
  • Approach: It monitors current-flight conformance to pre-identified nominal trajectories in real time and proposes a conformance-based airspace-complexity measure.The monitoring tool uses knowledge learned from trajectory clustering rather than flight-plan or aircraft-intent information beyond destination airport.
  • Data: The study uses radar records from the Northern California TRACON, an 80km-radius and 6,000m-high cylinder centered at Oakland International Airport.The dataset covers the first three months of 2006 and includes Oakland, San Francisco, San Jose, and smaller airports.
  • Data: The analysis discards VFR traffic and focuses on SFO landings because SFO is the busiest NCT airport and its arrivals show numerous and varied patterns.Trajectories are sorted by airport and operation type before selecting the study focus.

II. TRAJECTORY CLUSTERING

The trajectory-clustering section combines a waypoint-based method with a principal-components approach for discovering common flight patterns and outliers. The methods exploit structured aircraft motion while accommodating variable trajectory representations.

  • Methods: The paper introduces two clustering techniques: waypoint sequences and principal components analysis of resampled and augmented trajectories.Both methods are presented after reviewing existing trajectory-clustering approaches.
  • Related work: The reviewed literature includes density-based, longest-common-subsequence, and distance-based methods for grouping trajectories with varying geometry, timing, or noise.These methods differ in their representations and distance or similarity functions.
  • Related work: The principal-components approach follows earlier automated flight-track taxonomy work that resamples trajectories and clusters a reduced-order representation.The cited taxonomy used the first two modes because they captured 95% of dataset fluctuations.
  • Waypoint-based clustering: The waypoint method exploits the fact that aircraft usually fly straight with a limited number of turns and often follow waypoint sequences near airports.Turning points are grouped into waypoints, after which trajectories are represented as waypoint sequences and clustered with LCS.
  • Waypoint-based clustering: Published waypoints cannot directly support TRACON monitoring because relatively few waypoints or reporting points are located there.The paper evaluates this limitation by comparing trajectory-clustering results with published waypoints.

1) Turning Points Identification:

The turning-point stage estimates aircraft heading from trajectory samples, filters noise, and detects significant heading changes. It then represents each trajectory as an ordered sequence of turning points for subsequent clustering.

  • Turning-point detection: Aircraft heading is estimated at each trajectory point from neighboring x- and y-coordinate differences.The formulation omits the aircraft index to simplify notation.
  • Turning-point detection: A low-pass filter smooths the heading sequence before turning points are identified.The filter uses a constant α, and the paper reports α = 0.4 as providing good noise filtering without too much delay.
  • Turning-point detection: A turning point is detected when the filtered heading difference exceeds Ψc = 0.025rad = 1.43°.The threshold was chosen experimentally to capture small heading changes while excluding meaningless variations; results were not very sensitive to small threshold changes.
  • Turning-point representation: Consecutive detections during large turns are trimmed so that long turning-point sequences do not represent one maneuver redundantly.For two consecutive detections the first is kept; for three, the middle one is kept.
  • Turning-point representation: Each trajectory is represented by a sequence of turning points, with its first point labeled as a turning point, before the turning-point set is clustered.The paper next applies k-means or DBSCAN to the set of turning points.

2) Algorithms overview:

The paper reviews k-means and DBSCAN as clustering algorithms for turning-point data. k-means alternates assignment and centroid updates, while DBSCAN forms density-based clusters and can identify noise.

  • k-means: k-means partitions observations into k clusters by minimizing within-cluster squared distances to cluster means.The cluster mean is its centroid, and k is the algorithm's user-supplied input.
  • k-means: The assignment step places each observation in the cluster with the closest mean, equivalent to partitioning space by the centroids' Voronoi diagram.Figure 5 presents the resulting clusters and corresponding Voronoi diagram.
  • k-means: The update step recalculates each cluster mean as the centroid of its assigned observations.Assignments and updates alternate until assignments no longer change.
  • k-means: k-means is heuristic: it may depend on initialization and is not guaranteed to reach the global optimum.The paper recommends multiple runs with different starting conditions and retaining the run with the minimum objective value.
  • DBSCAN: DBSCAN clusters points that are close together and sufficiently dense, using ε and MinPts rather than a preset number of clusters.It iteratively collects density-reachable objects and merges clusters when their core objects connect.

3) Turning Points Clustering; creation of waypoints:

The waypoint method clusters aircraft turning points and then clusters waypoint sequences to identify common trajectory flows. It switches between k-means and DBSCAN according to point density, but waypoint-based matching can exclude similar trajectories.

  • Turning-point clustering: Waypoints are defined as planar coordinates of clusters of turning points where many aircraft usually change heading.Sparse turning-point distributions use k-means, while dense distributions use DBSCAN.
  • Turning-point clustering: For sparse data, k-means creates waypoints from turning-point clusters and uses each cluster's center of mass as the waypoint center.This choice avoids a density-based method labeling most sparse points as outliers.
  • Turning-point clustering: For dense data, DBSCAN replaces meaningless distance-based clusters, creating waypoints from the convex hulls of density-based clusters.The reported DBSCAN settings are ε = 350m and minPts = 10; outliers are not depicted.
  • Waypoint-sequence clustering: Each trajectory is converted into a sequence of waypoints by following its original direction and adding waypoints it passes over.Sequence clustering then uses the longest common subsequence; sequences with fewer than 3 points perform poorly, so only sequences containing more than 4 waypoints are retained.
  • Results: The method identifies main landing flows in SFO data, although some trajectories do not fit the expected clusters and quality is assessed visually.The examples include one day's landings and an initial set of 30,000 trajectories; cluster colors differ when indexing is randomized.
  • Limitations: Waypoint matching can exclude trajectories that are slightly offset from waypoints and can retain trajectories with large rerouting periods if they pass over waypoints.Thus, geometric passage over waypoints does not always distinguish closely similar or substantially rerouted trajectories.

C. Trajectory-based clustering via component analysis

The trajectory-based method resamples and augments trajectories, reduces them with PCA, and density-clusters the first five principal components. It is designed to improve on a prior two-component approach and identify outliers without fixing cluster count.

  • C. Trajectory-based clustering via component analysis: The method resamples trajectories to equal length, augments their dimensionality, normalizes and concatenates the data, retains five principal components, and applies density-based clustering.These steps are summarized in Figure 10.
  • C. Trajectory-based clustering via component analysis: Unlike Eckstein's approach, the method clusters projections onto the first five PCs after augmenting trajectory dimensionality.The added dimensions are intended to provide richer trajectory representations before PCA.
  • C. Trajectory-based clustering via component analysis: The density-based algorithm identifies outliers and does not require the number of clusters to be set a priori.This is presented as an advantage over the compared approach.
  • Preprocessing: Resampling is required because trajectories have different numbers of points, but it removes the speed notion originally represented by distances between radar echoes.Trajectories with fewer than 50 points are removed before vector-based clustering.

2) Dimensionality augmentation:

Dimensionality augmentation adds position, distance, curvature, and heading information to each resampled trajectory. The resulting normalized vector represents each flight with 450 components and preserves selected trajectory properties and symmetries.

  • 2) Dimensionality augmentation: The augmented representation adds trajectory coordinates and derived features before clustering.The paper states that dimensionality is increased to improve clustering results.
  • 2) Dimensionality augmentation: The aircraft position vector contains 150 components and is unique to each trajectory.It records Cartesian position at the 50 resampled points.
  • 2) Dimensionality augmentation: Distance-to-center features encode convergence toward the TRACON and can represent trajectories symmetrically around the TRACON center.Distance to a reference corner similarly introduces symmetry around the specified diagonal.
  • 2) Dimensionality augmentation: Curvature-related features distinguish straight trajectories from curved ones through their rate of change and variability.These features do not present symmetry.
  • 2) Dimensionality augmentation: Using sine and cosine avoids angular discontinuities, and the full augmented trajectory vector has 450 components after normalization.Heading is resampled to 50 points; normalization scales each parameter between 0 and 1.

3) Principal Components Analysis:

The method augments and resamples trajectories, projects them onto five principal components, and clusters them with DBSCAN. The resulting centroids represent typical procedures, while outliers reveal atypical operations and their temporal and aircraft-related variation.

  • Principal components analysis: Choosing p = 5 balances computational speed and accuracy while retaining most trajectory information in the first principal components.Added dimensions spread projected trajectories farther apart, making clustering easier.
  • Clustering: DBSCAN clusters projections onto the first five principal components, accommodates arbitrary cluster shapes, identifies outliers, and requires no preset cluster count.The resulting clusters are described as visually clean and clearly differentiated.
  • Cluster interpretation: Cluster centroids represent average trajectories and can be interpreted as standard procedures, although DBSCAN settings may produce minor variations as separate clusters.Some minor clusters differ only slightly from one another.
  • Outlier analysis: 19.5% of all trajectories are outliers, mainly because of holding patterns, large vectoring maneuvers, or direct routes.These patterns are identified through visual inspection of the detected outliers.
  • Outlier analysis: Regional and business aircraft have outlier frequencies of 4% and 5%, respectively, while jets contribute the largest outlier count but a much smaller frequency.The paper suggests aircraft size, speed, maneuverability, and sharper vectoring may explain these differences.
  • Temporal variation: Daily outlier frequencies range from less than 2% to 16%, with weather offered as the most likely explanation.Late fog dissipation or convective weather can reduce runway capacity and prompt vectoring or holding patterns.
  • Temporal variation: Outlier frequency is higher at night, rises again near 11 a.m., and shows another peak at 5 p.m.Nighttime outliers are mostly associated with direct routing, while daytime variation is discussed in relation to traffic density and fog.

III. AIRSPACE MONITORING

The monitoring approach compares current aircraft trajectories with nominal paths learned from clustering rather than relying on filed flight-plan intent. This addresses arrival operations where waypoint sequences can change and published waypoints do not adequately represent observed traffic.

  • III. AIRSPACE MONITORING: The monitoring technique automatically detects when aircraft do not conform to standard procedures derived from cluster centroids.The objective is real-time detection of deviations from nominal paths, while allowing trajectory variability around centroids.
  • A. Literature review and motivation: Intent-based monitoring may fail for arrivals because waypoint sequences can change, waypoints can be skipped or added, and vectoring is often used.Such monitoring requires knowledge of airspace structure, waypoints, and aircraft intent.
  • A. Literature review and motivation: A related conformance framework compares observed states with expected states generated from pilot-intent, aircraft-intent, and aircraft-dynamics models.Its inputs include a conformance basis and surveillance observations.
  • III. AIRSPACE MONITORING: Cluster centroids pass over only a limited number of published waypoints and reporting points, so those points cannot efficiently monitor TRACON traffic.The comparison is illustrated for SFO arrivals in the San Francisco Bay Area.

B. Data formatting

Real-time monitoring requires fragmented nominal trajectories because only past observations are available during operations. The system uses these fragments and learned nominal behavior to evaluate conformance and display aircraft and complexity information for TRACON monitoring.

  • B. Data formatting: Nominal trajectories are split into ten fragments of five points because current real-time trajectories are incomplete.Five points correspond to approximately 84 seconds, motivating an 80-second analysis memory.
  • C. Anomaly detection: Inductive Monitoring System: IMS learns nominal behavior from user-provided training data and detects anomalies using k-means and density-based clustering.The supplied passage describes IMS as a model-free alternative with high-fidelity detection.
  • C. Anomaly detection: Inductive Monitoring System: The training dataset contains 276,040 five-point trajectory segments formed from trajectories identified as nominal.These segments provide the nominal examples used by the monitoring system.
  • D. AirTrajectoryMiner: Monitoring tool: AirTrajectoryMiner takes nominal trajectories and radar tracks as inputs and outputs current-flight conformance and a TRACON complexity measure.The complexity output can be incorporated into Traffic Management Advisor software.
  • D. AirTrajectoryMiner: Monitoring tool: Figure 20 combines a two-dimensional airspace view with a time history of TRACON complexity.Its caption identifies the top frame as conformance to standard procedure and the bottom frame as complexity history.
  • D. AirTrajectoryMiner: Monitoring tool: The display distinguishes SFO-intended aircraft, non-SFO aircraft, conforming and outlier trajectories, and non-SFO traffic that may interfere with SFO arrivals.Green, red, grey, and orange segments encode these operational categories.
  • D. AirTrajectoryMiner: Monitoring tool: Colored cluster-centroid lines represent nominal trajectories, and their displayed lengths correspond to the aircraft’s last 80 seconds of analyzed trajectory.The centroids differ from Figure 13 because clustering was rerun with parameters allowing greater variability and fewer clusters.

E. Measure of complexity

The paper defines airspace complexity as disorder relative to nominal operations, using entropy over aircraft identified as nominal or outliers. Complexity rises with detected outliers and traffic, informing controller workload and arrival-rate management.

  • The proposed metric measures difficulty in steering traffic from nominal operations with initial separation toward degraded operations with increased separation.
  • The metric is based on aircraft compliance with procedures identified as nominal and uses Shannon entropy to quantify deviations from those operations.
  • Outlier aircraft inbound to SFO are modeled as unique and independent categories when calculating their entropy.
  • The complexity C sums the entropy of aircraft inbound to SFO and aircraft not inbound to SFO.
  • Complexity is 0 without detected outliers and increases with both the number of outliers and the number of aircraft.
  • The measure is refreshed every 15 seconds over a 10-minute window; increasing complexity suggests higher controller workload and a reduced aircraft arrival rate.
  • An aircraft may be off nominal because of large controller-required vectoring associated with runway congestion or rerouting caused by weather.

CONCLUSION

The paper presents two trajectory clustering methods and applies them to real-time airspace monitoring. The tool compares current flights with identified nominal procedures and can be adapted beyond SFO landings by changing its input dataset.

  • The monitoring tool compares current flights with identified nominal procedures in real time.
  • The presented version monitors landings at SFO but can be modified for any traffic pattern by changing the input dataset.
  • The paper combines two trajectory clustering methods with an application to airspace monitoring.
Loading 1001.5007v2…