Considering the transformation in roles of existing air traffic management technologies, future flight operations and flight deck systems will need additional avionics and operational procedures that involve adaptive algorithms and advanced decision support tools. The main purpose of this article is to provide a theoretical framework for tactical 4D-trajectory planning and conflict resolution of an aircraft equipped with novel automation tools. The proposed 4D-trajectory-planning method uses recent algorithmic advances in both probabilistic and deterministic methods to fully benefit from both approaches. We have constructed an aircraft performance model based on Base of Aircraft Data 4 with high-level hybrid flight template automatons and low-level flight maneuver automatons. This multi-modal flight trajectory approach is utilized to generate cost-efficient local trajectory segments instead of solving complex trajectory-generation problems globally. The proposed sampling-based trajectory planning algorithm spatially explores the airspace and provides proper separation through local trajectory segments and guarantees asymptotic optimality under certain conditions. Moreover, we have integrated the cross-entropy method, which transforms the sampling problem into a stochastic optimization problem, rapidly converges on the minimum cost trajectory sequence by utilizing available flight plans, and reduces the amount of sampling. The integration of the proposed strategies lets us solve challenging, real-time in-tactical 4D-trajectory planning problems within the current and the envisioned future realm of air traffic management systems.
NextGen JPDO. Concept of operations. Technical Report, Joint Planning and Development Office I Version 3.2, December 2013.
2.
SESAR JU. The Concept of Operations at a glance. Technical Report, SESAR JU Deliverable 3 (DLM-0612-001-02-00), December 2013.
3.
CookATannerGWilliamsV. Dynamic cost indexing – Managing airline delay costs. J Air Transport Manage2009; 15: 26–35.
4.
López-Leonés J, Vilaplana MA, Gallo E, et al. The aircraft intent description language: a key enabler for air-ground synchronization in trajectory-based operations. In: IEEE/AIAA 26th digital avionics systems conference, DASC '07, Dallas, TX, US, 2007, pp.1. D. 4–1–1 to D. 4–12.
5.
Kuchar JK and Yang LC. A review of conflict detection and resolution modeling methods. IEEE Trans Intell Transport Syst 2000; 1(4): 179–189.
6.
Richards A and How JP. Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In: Proceedings of the 2002 American control conference, 2002, Anchorage, AK, US, vol. 3, pp.1936–1941.
7.
ChristodoulouMAKodaxakisSG. Automatic commercial aircraft-collision avoidance in free flight: the three-dimensional problem. IEEE Trans Intell Transport Syst2006; 7: 242–249.
8.
Kochenderfer MJ and Chryssanthacopoulos JP. Partially-controlled Markov decision processes for collision avoidance systems. In: International conference on agents and artificial intelligence, Rome, Italy, 2011.
9.
Kochenderfer MJ and Chryssanthacopoulos JP. Robust airborne collision avoidance through dynamic programming. Massachusetts Institute of Technology, Lincoln Laboratory, Project Report ATC-371, 2011, Washington DC, US.
10.
Winder LF. Hazard avoidance alerting with Markov decision processes. PhD Thesis, Massachusetts Institute of Technology, 2004.
11.
WolfTKochenderferM. Aircraft collision avoidance using Monte Carlo real-time belief space search. J Intell Robotics Syst2011; 64: 277–298.
12.
Chryssanthacopoulos JP and Kochenderfer MJ. Accounting for State Uncertainty in Collision Avoidance. J Guid Control Dyn 2011; 34(4): 951–960.
13.
Kuffner JJ and LaValle SM. RRT-connect: An efficient approach to single-query path planning. In: Proceedings of IEEE international conference on robotics and automation (ICRA), Lexington, MA, US, vol. 2, 2000, pp.995–1001.
14.
LaValleSM. On the relationship between classical grid search and probabilistic roadmaps. Int J Robotics Res2004; 23: 673–692.
15.
LindemanSLaValleSM. Current issues in sampling-based motion planning, Berlin Heidelberg: Springer, 2005, pp. 10.
16.
FrazzoliEKaramanS. Incremental sampling-based algorithms for optimal motion planning. Int J Robotics Res2011; 30(7): 846–894.
17.
LaValle S and Kuffner J. Randomized kinodynamic planning. Proceedings of 1999 IEEE international conference on robotics and automation, Detroit, MI, US, 1999, vol. 1, pp.473–479.
18.
Karaman S and Frazzoli E. Optimal kinodynamic motion planning using incremental sampling-based methods. In: 2010 49th IEEE conference on decision and control (CDC), Atlanta, GA, US, 2010, pp.7681–7687.
19.
Luders BD, Karaman S and How JP. Robust sampling-based motion planning with asymptotic optimality guarantees. AIAA Guid, Boston, MA, US, 2013.
20.
Lindemann SR and LaValle SM. Steps toward derandomizing RRTs. In: Proceedings of the fourth international workshop on robot motion and control, RoMoCo'04, Puszczykowo, Poland, 2004.
21.
Karaman S, Walter MR, Perez A, et al. Anytime motion planning using the RRT*. In: 2011 IEEE international conference on robotics and automation (ICRA), 2011, pp.1478–1483.
22.
ŞucanIKavrakiLE. A sampling-based tree planner for systems with complex dynamics. IEEE Trans Robotics2000; 28: 116–131.
23.
Kurniawati H and Hsu D. Workspace importance sampling for probabilistic roadmap planning. In: Proceedings of 2004 IEEE/RSJ international conference on intelligent robots and systems, 2004 (IROS 2004), 2004, vol. 2, pp.1618–1623.
24.
Burns B and Brock O. Toward optimal configuration space sampling. In: Robotics: Science and systems, Citeseer, 2005, pp.105–112.
25.
Hsu D, Sánchez-Ante G and Sun Z. Hybrid PRM sampling with a cost-sensitive adaptive strategy. In: Proceedings of the 2005 IEEE international conference on robotics and automation, 2005, ICRA 2005, Barcelona, Spain, pp.3874–3880.
26.
Kalisiak M and van de Panne M. Faster motion planning using learned local viability models. In: 2007 IEEE International Conference on Robotics and Automation, 2007, pp.2700–2705.
27.
Li Y and Bekris KE. Balancing state-space coverage in planning with dynamics. In: 2010 IEEE International Conference on Robotics and Automation (ICRA), 2010, pp.3246–3253.
28.
Denny J and Amato NM. Toggle PRM: Simultaneous mapping of C-free and C-obstacle—a study in 2D. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), San Francisco, CA, US, 2011, pp.2632–2639.
29.
KobilarovM. Cross-entropy motion planning. Int J Robotics Res2012; 31: 855–871.
30.
RubinsteinRYKroeseDP. The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning, New York, NY, US: Springer Science & Business Media, 2004.
31.
BrockettRW. Languages for motion description and map making. Proc Symp Appl Math1990; 14: 181–293.
32.
TomlinCPappasGJSastryS. Conflict resolution for air traffic management: A study in multi-agent hybrid systems. IEEE Trans Automat Control1998; 43(4): 509–521.
33.
FrazzoliEDahlehMAFeronE. Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans Robotics2005; 21: 1077–1091.
34.
DeverCMettlerBFeronE. Nonlinear trajectory generation for autonomous vehicles via parameterized maneuver classes. J Guid Control Dyn2006; 29: 289–302.
35.
KoyuncuEUreNKInalhanG. Integration of Path/maneuver planning in complex environments for agile maneuvering UCAVs. J Intell Robotic Syst2010; 57: 143–170.
36.
Koo TJ, Pappas GJ and Sastry S. Multi-modal control of systems with constraints. In: 40th IEEE conference decision and control, Orlando, FL, USA, 2001, pp.2075–2081.
37.
LaValle SM. Planning algorithms. New York, NY: Cambridge University Press, 2006, p.1023.
38.
Nuic A, Poinsot C, Iagaru M, et al. Advanced aircraft performance modeling for ATM: Enhancements to the BADA model. In: The 24th digital avionics systems conference, DASC 2005, Washington DC, US, 2005, pp.2–2.B.4–1.
39.
EUROCONTROL. User manual for the Base of Aircraft Data (BADA) Family 4. EEC TechnicalScientific Report, April 2014, Brussels, Belgium.
40.
EUROCONTROL. Principles for establishing the cost-base for en route charges and the calculation of the unit rates. In: European Organisation for the Safety of Air Navigations, Brussels, Belgium, October 2013, pp.1–54.
41.
AltusS. Effective flight plans can help airlines economize. Boeing Aero2009.
42.
RobersonBPilotSS. Fuel conservation strategies: cost index explained. Boeing Aero Quarterly2007.
Karaman S and Frazzoli E. Incremental sampling-based algorithms for a class of pursuit-evasion games. In: Algorithmic foundations of robotics IX, January 2011, pp.71–87. Berlin, Heidelberg: Springer.
45.
Niederreiter H. Random number generation and quasi-Monte Carlo methods. Philadelphia, PA, US: SIAM, 1992.
46.
RubinsteinRYKroeseDP. The cross entropy method: A unified approach to combinatorial optimization, Monte-Carlo simulation (Information Science and Statistics), Secaucus, NJ: Springer-Verlag, 2004.
47.
ReynoldsDGaussian mixture models. In: LiSZJainA (eds). In: Encyclopedia of biometrics, US: Springer, 2009, pp. 659–663. .
