Research ArticleOpen AccessGoogle Scholar indexed
Systematic vs. Non-Systematic Search for 3D Aircraft Conflict Resolution
LIMIARF/FSR, University Mohammed V Agdal, Rabat, Morocco.
LIMIARF/FSR, University Mohammed V Agdal, Rabat, Morocco.
- 1 LIMIARF/FSR, University Mohammed V Agdal, Rabat, Morocco.
- 2 LIMIARF/FSR, University Mohammed V Agdal, Rabat, Morocco.
Journal of Intelligent Learning Systems and Applications·Volume 04 (2012)·Pages 223–229·Published 30 August 2012·DOI10.4236/jilsa.2012.43023
Copy link · social · email
Abstract
A conflict is an event in which two or more aircraft experience a loss of minimum separation. In this paper, we formulate the problem of solving conflicts arising among several aircraft moving in a shared airspace as a Constraint Satisfaction Problem (CSP). The constraint satisfaction problem being NP-complete, the algorithms developed to solve it have been of two types: non-systematic and systematic search methods. In this paper, we have considered a breakout algorithm as an example of non-systematic search methods and a backtracking procedure that maintains Arc Consistency (MAC) as an example of systematic search methods. The performance of these algorithms was compared experimentally and the Breakout algorithm is shown to be clearly superior.
KeywordsConstraint Satisfaction ProblemSystematic SearchNon-Systematic SearchAircraft Conflict Resolution
- T. S. Perry, “In Search of the Future of Air Traffic Control,” IEEE Spectrum, Vol. 34, No. 8, 1997, pp. 18-35. doi:10.1109/6.609472
- Joint Planning and Development Office, “Next Generation Air Transportation System Integrated Plan,” Washington DC, 2004.
- J. H. Reif and M. Sharir, “Motion Planning in the Presence of Moving Obstacles,” 25th IEEE Symposium on Foundations of Computer Science, Portland, 21-23 October 1985, pp. 144-154,
- J. Kuchar and L. C. Yang, “A Review of Conflict Detection and Resolution Modeling Methods,” IEEE Transactions on Intelligent Transportation Systems, Vol. 1, No. 4, 2000, pp. 179-189.
- G. Chaloulos, J. Lygeros, I. Roussos, K. Kyriakopoulos, E. Siva, A. Lecchini-Visintini and P. Casek, “Comparative Study of Conflict Resolution Methods,”, iFly Project, 2009.
- K. Bilimoria, B. Sridhar and G. Chatterji, “Effects of Conflict Resolution Maneuvers and Traffic Density of Free Flight,” AIAA Guidance, Navigation, and Control Conference, San Diego, 29-31 July 1996.
- B. Carpenter and J. Kuchar, “Probability-Based Collision Alerting Logic for Closely-Spaced Parallel Approach,” Proceedings of the AIAA 35th Aerospace Sciences Meeting and Exhibit, Reno NV, 6-9 January 1997.
- V. Duong, E. Hoffman, L. Floc’hic and J. P. Nicolaon, “Extended Flight Rules to Apply to the Resolution of Encounters in Autonomous Airborne Separation,” Technical Report, EUROCONTROL Experimental Center 1996.
- K. Zeghal, “A Review of Different Approaches Based on Force Fields for Airborne Conflict Resolution,” AIAA Guidance, Navigation, and Control Conference, Boston, 10-12 August 1998, pp. 818-827.
- E. Frazzoli, Z. H. Mao, J. H. Oh and E. Feron, “Aircraft Conflict Resolution via Semi-definite Programming,” AIAA Journal of Guidance, Control, and Dynamics, Vol. 24, No. 1, 2001, pp. 79-86. doi:10.2514/2.4678
- J. Hu, M. Prandini and S. Sastry, “Optimal Coordinated Maneuvers for Three Dimensional Aircraft Conflict Resolution,” AIAA Journal of Guidance, Control and Dynamics, Vol. 25, No. 5, 2002, pp. 888-900. doi:10.2514/2.4982
- A. U. Raghunathan, V. Gopal, D. Subramanian, L. T. Biegler and T. Samad, “Dynamic Optimization Strategies for Three-Dimensional Conflict Resolution of Multiple Aircraft,” Journal of Guidance, Control, and Dynamics, Vol. 27, No. 4, 2004, pp. 586-594. doi:10.2514/1.11168
- L. Pallottino, E. Feron and A. Bicchi, “Conflict Resolution Problems for Air Traffic Management Systems Solved with Mixed Integer Programming,” IEEE Transactions on Intelligent Transportation Systems, Vol. 3, No. 1, 2002, pp. 3-11. doi:10.1109/6979.994791