Time series clustering of weather observations in predicting climb phase of aircraft trajectories

ABSTRACT

Reliable trajectory prediction is paramount in Air Traffic Management (ATM) as it can increase safety, capacity, and efficiency, and lead to commensurate fuel savings and emission reductions. Inherent inaccuracies in forecasting winds and temperatures often result in large prediction errors when a deterministic approach is used. A stochastic approach can address the trajectory prediction problem by taking environmental uncertainties into account and training a model using historical trajectory data along with weather observations. With this approach, weather observations are assumed to be realizations of hidden aircraft positions and the transitions between the hidden segments follow a Markov model. However, this approach requires input observations, which are unknown, although the weather parameters overall are known for the pertinent airspace. We address this problem by performing time series clustering on the current weather observations for the relevant sections of the airspace.

In this paper, we present a novel time series clustering algorithm that generates an optimal sequence of weather observations used for accurate trajectory prediction in the climb phase of the flight. Our experiments use a real trajectory dataset with pertinent weather observations and demonstrate the effectiveness of our algorithm over time series clustering with a k-Nearest Neighbors (k-NN) algorithm that uses Dynamic Time Warping (DTW) Euclidean distance.

References

1. K. E. Atkinson. An Introduction to Numerical Analysis. John Wiley and Sons, 1978.
2. G. Avanzini. Frenet-based algorithm for trajectory prediction. Journal of Guidance, Control, and Dynamics, 27(1):127--135, January 2004.
3. S. Ayhan and H. Samet. Aircraft trajectory prediction made easy with predictive analytics. In Proc. of the 22nd Intl' Conf. on Knowledge Discovery and Data Mining, San Francisco, August 2016.
4. J. Benavides, J. Kaneshige, S. Sharma, R. Panda, and M. Steglinski. Implementation of trajectory prediction function for trajectory based operations. In AIAA Atmospheric Flight Mechanics Conf., Atlanta, GA, 2014.
5. F. Brabec and H. Samet. Client-based spatial browsing on the world wide web. IEEE Internet Computing, 11(1):52--59, January/February 2007.
6. J. Bronsvoort, G. McDonald, J. Lopez-Leones, and H. Visser. Improved trajectory prediction for air traffic management by simulation of guidance logic and inferred aircraft intent using existing data-link technology. In AIAA GNC Conf. and Exhibit, Minneapolis, MN, August 2012.
7. E. Dimitriadou, A. Weingessel, and K. Hornik. A combination scheme for fuzzy clustering. In Proc. of the 2002 AFSS Intl' Conf. on Fuzzy Systems. Calcutta: Advances in Soft Computing, London, UK, February 2002.
8. C. Esperança and H. Samet. Experience with SAND/Tcl: a scripting tool for spatial databases. Journal of Visual Languages and Computing, 13(2):229--255, April 2002.
9. S. Gao, Y. He, and H. Chen. Wind speed forecast for wind farms based on arma-arch model. In Proc. Int'l Conf. on Sustainable Power Generation and Supply, Nanjing, China, April 2009.
10. C. Guo, H. Jia, and N. Zhang. Time series clustering based on ica for stock data analysis. In Proc. 4th Intl' Conf. on Wireless Communications, Networking and Mobile Computing, China, October 2008.
11. J. Han, M. Kamber, and J. Pei. Data Mining: Concepts and Techniques. Morgan Kaufmann, San Francisco, 2011.
12. P. Hansen and B. Jaumard. Cluster analysis and mathematical programming. Mathematical Programming, 79(1-3):191--215, October 1997.
13. E. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowl. Inf. Syst., 7(3):358--386, March 2005.
14. J. Krozel and D. Andrisani. Intent inference and strategic path prediction. In AIAA GNC Conf. and Exhibit, San Francisco, August 2005.
15. M. Kumar, N. R. Patel, and J. Woo. Clustering seasonality patterns in the presence of errors. In Proc. of the Eighth ACM SIGKDD Intl' Conf. on Knowledge Discovery and Data Mining, Edmonton, Alberta, August 2002.
16. T. W. Liao. Clustering of time series data-a survey. Pattern Recognition, 38(11):1857--1874, November 2005.
17. Y. Liu and X. R. Li. Intent based trajectory prediction by multiple model prediction and smoothing. In AIAA GNC Conf. and Exhibit, New Orleans, LA, January 2015.
18. I. Lymperopoulos, J. Lygeros, and A. Lecchini. Model based aircraft trajectory prediction during takeoff. In AIAA GNC Conf. and Exhibit, Keystone, CO, August 2006.
19. S. Mondoloni. A multiple-scale model of wind-prediction uncertainty and application to trajectory prediction. In 6th AIAA Aviation Technology, Integration and Operations Conf., Wichita, KS, September 2006.
20. S. Nutanong, E. H. Jacox, and H. Samet. An incremental Hausdorff distance calculation algorithm. PVLDB, 4(8):506--517, August 2011.
21. S. Nutanong and H. Samet. Memory-efficient algorithms for spatial network queries. In Proc. of the 29th IEEE Int'l Conf. on Data Engineering, pages 649--660, Brisbane, Australia, April 2013.
22. M. Paglione and R. Oaks. Implementation and metrics for a trajectory prediction validation methodology. In AIAA GNC Conf. and Exhibit, Hilton Head, SC, August 2007.
23. J. Paparrizos and L. Gravano. k-shape: Efficient and accurate clustering of time series. SIGMOD Rec., 45(1):69--76, June 2016.
24. S. Peng, J. Sankaranarayanan, and H. Samet. SPDO: High-throughput road distance computations on spark using distance oracles. In Proc. of the 32nd IEEE Int'l Conf. on Data Engineering, pages 1239--1250, Helsinki, Finland, May 2016.
25. F. Petitjean and P. Gançarski. Summarizing a set of time series by averaging: From steiner sequence to compact multiple alignment. Theory Computer Science, 414(1):76--91, January 2012.
26. H. Samet, H. Alborzi, F. Brabec, C. Esperança, G. R. Hjaltason, F. Morgan, and E. Tanin. Use of the SAND spatial browser for digital government applications. Communications of the ACM, 46(1):63--66, January 2003.
27. J. Sankaranarayanan, H. Alborzi, and H. Samet. Distance join queries on spatial networks. In Proc. of the 14th ACM Int'l Symposium on Advances in Geographic Information Systems, pages 211--218, Arlington, VA, November 2006.
28. J. Sankaranarayanan and H. Samet. Roads belong in databases. IEEE Data Engineering Bulletin, 33(2):4--11, June 2010.
29. C. Schultz, D. Thipphavong, and H. Erzberger. Adaptive trajectory prediction algorithm for climbing flights. In AIAA GNC Conf. and Exhibit, Minneapolis, MN, August 2012.
30. E. Tanin, A. Harwood, and H. Samet. A distributed quadtree index for peer-to-peer settings. In Proc. of the 21st IEEE Int'l Conf. on Data Engineering, pages 254--255, Tokyo, Japan, Apr. 2005.
31. G. Verdoolaege and Y. Rosseel. Activation detection in event-related fmri through clustering of wavelet distributions. In IEEE Intl' Conf. on Image Processing, Hong Kong, September 2010.
32. A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. on Information Theory, 13(2):260--269, April 1967.

Index Terms

• Computing methodologies

  • Machine learning

    • Machine learning algorithms

      • Dynamic programming for Markov decision processes

• Information systems

  • Information systems applications

    • Data mining

      • Clustering

    • Decision support systems

      • Data analytics