Aircraft Trajectory Prediction Made Easy with Predictive Analytics

ABSTRACT

At the heart of Air Traffic Management (ATM) lies the Decision Support Systems (DST) that rely upon accurate trajectory prediction to determine how the airspace will look like in the future to make better decisions and advisories. Dealing with airspace that is prone to congestion due to environmental factors still remains the challenge especially when a deterministic approach is used in the trajectory prediction process. In this paper, we describe a novel stochastic trajectory prediction approach for ATM that can be used for more efficient and realistic flight planning and to assist airspace flow management, potentially resulting in higher safety, capacity, and efficiency commensurate with fuel savings thereby reducing emissions for a better environment. Our approach considers airspace as a 3D grid network, where each grid point is a location of a weather observation. We hypothetically build cubes around these grid points, so the entire airspace can be considered as a set of cubes. Each cube is defined by its centroid, the original grid point, and associated weather parameters that remain homogeneous within the cube during a period of time. Then, we align raw trajectories to a set of cube centroids which are basically fixed 3D positions independent of trajectory data. This creates a new form of trajectories which are 4D joint cubes, where each cube is a segment that is associated with not only spatio-temporal attributes but also with weather parameters. Next, we exploit machine learning techniques to train inference models from historical data and apply a stochastic model, a Hidden Markov Model (HMM), to predict trajectories taking environmental uncertainties into account. During the process, we apply time series clustering to generate input observations from an excessive set of weather parameters to feed into the Viterbi algorithm. Our experiments use a real trajectory dataset with pertaining weather observations and demonstrate the effectiveness of our approach to the trajectory prediction process for ATM.

References

1. Action plan 16: Common trajectory prediction capability. https://acy.tc.faa.gov/cpat/tjm/TP_Requirements_Engineering_Methodology.pdf.
2. Aircraft operating expenses. http://www.opshots.net/2015/04/aircraft-operating-series-aircraft-operating-expenses/.
3. Aircraft situation display to industry. http://www.fly.faa.gov/ASDI/asdi.html.
4. Definition of an aircraft trajectory by icao. http://ap16.atmrt.org/.
5. Google earth. https://www.google.com/earth//.
6. Grib2 documentation. http://www.nco.ncep.noaa.gov/pmb/docs/grib2/grib2_doc.shtml.
7. Ncep wmo grib2 documentation. http://www.nco.ncep.noaa.gov/pmb/docs/grib2/grib2_doc.shtml.
8. G. Avanzini. Frenet-based algorithm for trajectory prediction. Journal of Guidance, Control, and Dynamics, 27(1):127--135, January 2004.
9. S. Ayhan and H. Samet. Diclerge: Divide-cluster-merge framework for clustering aircraft trajectories. In Proceedings of the 8th ACM SIGSPATIAL IWCTS, Seattle, WA, November 2015.
10. 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 Conference, Atlanta, GA, 2014.
11. 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 Conference and Exhibit, Minneapolis, MN, August 2012.
12. E. Casado, C. Goodchild, and M. Vilaplana. Identification and initial characterization of sources of uncertainty affecting the performance of future trajectory management automation systems. In Proceedings of the 2nd Int'l Conference on ATACCS, pages 170--175, Toulouse, France, May 2012.
13. G. Chatterji. Short-term trajectory prediction methods. In AIAA GNC Conference and Exhibit, Portland, OR, August 1999.
14. P. Y. Choi and M. Hebert. Learning and predicting moving object trajectory: a piecewise trajectory segment approach. Technical report, Carnegie Mellon University School of Computer Science, Pittsburgh, PA, August 2006.
15. E. Crisostomi, A. Lecchini-visintini, and J. Maciejowski. Combining monte carlo and worst-case methods for trajectory prediction in air traffic control: A case study. Journal of Guidance, Control and Dynamics, 43(4), 2008.
16. A. de Leege, M. van Paassen, and M. Mulder. A machine learning approach to trajectory prediction. In AIAA GNC Conference and Exhibit, Boston, MA, August 2013.
17. 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.
18. C. Gong and D. McNally. A methodology for automated trajectory prediction analysis. In AIAA GNC Conference and Exhibit, Providence, RI, August 2004.
19. R. H. Güting and M. Schneider. Realm-based spatial data types: The rose algebra. The VLDB Journal, 4(2):243--286, April 1995.
20. E. Jacox and H. Samet. Metric space similarity joins. ACM Transactions on Database Systems, 33(2):7, June 2008.
21. E. Keogh and C. A. Ratanamahatana. Exact indexing of dynamic time warping. Knowl. Inf. Syst., 7(3):358--386, March 2005.
22. J. Krozel and D. Andrisani. Intent inference and strategic path prediction. In AIAA GNC Conference and Exhibit, San Francisco, CA, August 2005.
23. Y. Liu and X. R. Li. Intent based trajectory prediction by multiple model prediction and smoothing. In AIAA GNC Conference and Exhibit, New Orleans, LA, January 2015.
24. I. Lymperopoulos, J. Lygeros, and A. Lecchini. Model based aircraft trajectory prediction during takeoff. In AIAA GNC Conference and Exhibit, Keystone, CO, August 2006.
25. S. Mondoloni. A genetic algorithm for determining optimal flight trajectories. In AIAA GNC Conference and Exhibit, Boston, MA, August 1998.
26. S. Mondoloni. A multiple-scale model of wind-prediction uncertainty and application to trajectory prediction. In 6th AIAA Aviation Technology, Integration and Operations Conference, Wichita, KS, September 2006.
27. K. T. Mueller, J. A. Sorensen, and G. J. Couluris. Strategic aircraft trajectory prediction uncertainty and statistical sector traffic load modeling. In AIAA GNC Conference and Exhibit, Monterey, CA, August 2012.
28. H. K. Ng, S. Grabbe, and A. Mukherjee. Design and evaluation of a dynamic programming flight routing algorithm using the convective weather avoidance model. In AIAA GNC Conference and Exhibit, Chicago, IL, August 2009.
29. S. Nutanong, E. H. Jacox, and H. Samet. An incremental Hausdorff distance calculation algorithm. PVLDB, 4(8):506--517, August 2011.
30. S. Nutanong and H. Samet. Memory-efficient algorithms for spatial network queries. In Proceedings of the 29th IEEE Int'l Conference on Data Engineering, pages 649--660, Brisbane, Australia, April 2013.
31. M. Paglione and R. Oaks. Implementation and metrics for a trajectory prediction validation methodology. In AIAA GNC Conference and Exhibit, Hilton Head, SC, August 2007.
32. S. Peng, J. Sankaranarayanan, and H. Samet. SPDO: High-throughput road distance computations on spark using distance oracles. In Proceedings of the 32nd IEEE Int'l Conference on Data Engineering, pages 1239--1250, Helsinki, Finland, May 2016.
33. L. R. Rabiner. Readings in speech recognition. chapter A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, pages 267--296. Morgan Kaufmann, San Francisco, CA, 1990.
34. H. Ryan and M. Paglione. State vector based near term trajectory prediction. In AIAA GNC Conference and Exhibit, Honolulu, HI, 2008.
35. 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.
36. J. Sankaranarayanan, H. Alborzi, and H. Samet. Efficient query processing on spatial networks. In Proceedings of the 13th ACM Int'l Symposium on Advances in Geographic Information Systems, pages 200--209, Bremen, Germany, November 2005.
37. J. Sankaranarayanan, H. Alborzi, and H. Samet. Distance join queries on spatial networks. In Proceedings of the 14th ACM Int'l Symposium on Advances in Geographic Information Systems, pages 211--218, Arlington, VA, November 2006.
38. J. Sankaranarayanan and H. Samet. Distance oracles for spatial networks. In Proceedings of the 25th IEEE Int'l Conference on Data Engineering, pages 652--663, Shanghai, China, March 2009.
39. J. Sankaranarayanan and H. Samet. Query processing using distance oracles for spatial networks. IEEE Transactions on Knowledge and Data Engineering, 22(8):1158--1175, August 2010.
40. J. Sankaranarayanan and H. Samet. Roads belong in databases. IEEE Data Engineering Bulletin, 33(2):4--11, June 2010.
41. J. Sankaranarayanan, H. Samet, and H. Alborzi. Path oracles for spatial networks. PVLDB, 2(1):1210--1221, August 2009.
42. C. Schultz, D. Thipphavong, and H. Erzberger. Adaptive trajectory prediction algorithm for climbing flights. In AIAA GNC Conference and Exhibit, Minneapolis, MN, August 2012.
43. T. Stewart, L. Askey, and M. Hokit. A concept for tactical reroute generation, evaluation and coordination. In 12th AIAA ATIO Conference and 14th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Indianapolis, IN, September 2012.
44. T. Stewart, J. DeArmon, and D. Chaloux. Using flight information to improve weather avoidance predictions. In Aviation Technology, Integration, and Operations Conference, Los Angeles, CA, August 2013.
45. S. Swierstra. Common trajectory prediction capability for decision support tools. In Proceedings of ATM 2003, 5th USA/Europa R&D Seminar, Budapest, Hungary, June 2003.
46. C. P. Taylor and C. Wanke. Improved dynamic generation of operationally acceptable reroutes using network optimization. Journal of Guidance, Control, and Dynamics, 34(4):961--975, August 2011.
47. C. Tomlin, G. J. Pappas, and S. Sastry. Conflict resolution for air traffic management: A study in multiagent hybrid systems. IEEE Transactions on Intelligent Transportation Systems, 43(4):509--521, April 1998.
48. A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 13(2):260--269, April 1967.
49. L. F. Winder and J. K. Kuchar. Hazard Avoidance Alerting with Markov Decision Processes. PhD thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, August 2004.
50. J. L. Yepes, I. Hwang, and M. Rotea. An intent-based trajectory prediction algorithm for air traffic control. In AIAA GNC Conference and Exhibit, San Francisco, CA, August 2005.
51. J. L. Yepes, I. Hwang, and M. Rotea. New algorithms for aircraft intnet inference and trajectory prediction. Journal of Guidance, Control, and Dynamics, 30(2):370--382, March 2007.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Aerospace

• Computing methodologies

  • Machine learning

    • Machine learning algorithms

      • Dynamic programming for Markov decision processes

• Information systems

  • Information systems applications

    • Decision support systems

      • Data analytics