Systematic vs. Non-Systematic Search for 3D Aircraft Conflict Resolution

Younes Mechqrane, El Houssine Bouyakhf

LIMIARF/FSR, University Mohammed V Agdal, Rabat, Morocco..

DOI: 10.4236/jilsa.2012.43023                

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.

Keywords

Constraint Satisfaction Problem; Systematic Search; Non-Systematic Search; Aircraft Conflict Resolution

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	Joint Planning and Development Office, “Next Generation Air Transportation System Integrated Plan,” Washington DC, 2004.
[3]	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,
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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
[11]	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
[12]	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
[13]	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
[14]	G. Gariel and E. Feron, “3D Conflict Avoidance under Uncertainties,” 28th Digital Avionics Systems Conference, Orlando, 23-29 October 2009, pp. 4.E.3-1-4.E.3-8.
[15]	E. M. Kan1, M. H. Lim, S. P. Yeo, J. S. Ho and Z. Shao, “Contour Based Path Planning with B-Spline Trajectory Generation for Unmanned Aerial Vehicles (UAVs) over Hostile Terrain,” Journal of Intelligent Learning Systems and Applications, Vol. 3, No. 3, 2011, pp. 122-130.
[16]	S. Minton, M. Johnston, A. Philips and P. Laird, “Minimizing Conflicts, A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems,” Artificial Intelligence, Vol. 58, No. 1-3, 1992, pp. 161-205. doi:10.1016/0004-3702(92)90007-K
[17]	P. Morris, “The Breakout Method for Escaping from Local Minima,” 11th National Conference on Artificial Intelligence, Washington DC, 11-15 July 1993, p. 4045.
[18]	A. K. Mackworth, “Consistency in Networks of Relations,” Artificial Intelligence, Vol. 8, No. 1, 1977, pp. 99-118. doi:10.1016/0004-3702(77)90007-8
[19]	F. Boussemart, F. Hemery, C. Lecoutre and L. Sais, “Boosting Systematic Search by Weighting Constraints,” Proceedings of ECAI’04, Valencia, 22-27 August 2004, pp. 146-150.