Unmanned air vehicles (UAVs), which have been popular in military context, have recently attracted attention of many researchers because of their potential civilian applications. However, before the UAVs can be used for civilian applications, a systematic integration of UAVs in the National Airspace System (NAS) is needed that can allow safe operation of UAVs along with other manned aircrafts. One of the critical capabilities needed for safe operation of the UAVs in the NAS is the ability of UAV to carry out sense and avoid task which would allow the UAV to amend its path to avoid collision with other aircrafts. Despite recent technological advances, such as availability of automatic dependent surveillance broadcast that can transmit position of an aircraft to others in the vicinity, planning a collision-free path autonomously is still challenging in a dynamic environment. The objective of this paper is to develop a methodology for discovering a path for the UAV that meets mission goals, avoids collision, is optimal in terms of path length and, more importantly, is feasible. The paper formulates the problem of path planning using the mathematical paradigm of mixed integer linear programming and provides a solution strategy for solving this problem in the dynamic sense. The tasks of avoidance of obstacles and waypoint navigation are incorporated as constraints in the MILP problem. The paper presents the solution of the MILP problem and verifies the performance of the proposed methodology with regard to optimality of the solution and computational time requirement via several simulated scenarios of different complexities.
NexFRemondinoF. UAV for 3D mapping applications: A review. Appl Geomat2014; 6: 1–15.
2.
RadmaneshMNematollahiONili-AhmadabadiM. A novel strategy for designing and manufacturing a fixed wing MAV for the purpose of increasing maneuverability and stability in longitudinal axis. J Appl Fluid Mech2014; 7: 435–446.
3.
Holdsworth R. Autonomous in-flight path planning to replace pure collision avoidance for free flight aircraft using automatic dependent surveillance broadcast. Doctoral Dissertation, Swinburne University, Australia, 2003.
4.
Ray I. ADS integration into the flight management computer. In: FAA, The first annual international satellite surveillance and communication symposium, 1991, pp.277–280.
5.
PerryTS. In search of the future of air traffic control. Spectrum1997; 34: 18–35.
6.
NordwallBD. Road map leads FAA to free-flight. Aviat Week Space Technol1995; 143: 34–34.
7.
DalyK. Reaching for free flight. Flight International1997, pp. 31–32.
8.
WilliamsonTSpencerNA. Development and operation of the traffic alert and collision avoidance system (TCAS). Proc IEEE1989; 77: 1735–1744.
9.
SteebRCammarataSHayes-RothFA. Distributed intelligence for air fleet control (No. RAND/R-2728-ARPA), Santa Monica, CA: Rand Corp., 1981.
10.
WuCLCavesRE. Research review of air traffic management. Transport Rev2002; 22: 115–132.
11.
JohnssonL. The cellular CNS concept (CCC) operating concept based on the VHF STDMA data link. Navigation1996; 44: 432–459.
12.
Smith AE and Evers C. Method and apparatus for improving utility of automatic dependent surveillance. Patent 6633259-B1, USA, 2003.
13.
CalvertES. Maneuvers to ensure the avoidance of collision. J Navig1960; 13: 127–137.
14.
SatoYIshiiH. Study of a collision-avoidance system for ships. Control Eng Pract1998; 6: 1141–1149.
15.
WylieFJ. The Calvert Method of maneuvering to avoid collisions at sea. J Navig1960; 13: 455–464.
16.
FordRL. The protected volume of airspace generated by an airborne collision avoidance system. J Navig1986; 39: 139–158.
17.
FordRLPowellDL. A new threat detection criterion for airborne collision avoidance systems. J Navig1990; 43: 391–403.
18.
Rojas RG, Law P and Burnside WD. Simulation of an enhanced TCAS II system in operation (No. NASA-CR-181545 SEMI-ANNUA), 1987.
19.
WilliamsonTSpencerNA. Development and operation of the traffic alert and collision avoidance system (TCAS). Proc IEEE1989; 77: 1735–1744.
20.
Sampath KS, Rojas RG and Burnside WD. Modelling and performance analysis of four and eight element TCAS. Ohio State University, USA, 1990.
21.
AsepRAchaibouAKMora-CaminoF. Automatic collision avoidance based on supervised predictive controllers. Control Eng Pract1996; 4: 1169–1175.
22.
Rekkas C and Rees M. Towards ADS-B implementation in Europe. In: Tyrrhenian international workshop on digital communications-enhanced surveillance of aircraft and vehicles, 2008, pp.1–4. New York: IEEE.
23.
Cedrini V, Zacchei M and Zampognaro V. ADS-B 1090es implementation: The cristal-med project. In: Tyrrhenian international workshop on digital communications-enhanced surveillance of aircraft and vehicles, 2008, pp.1–5. New York: IEEE.
24.
Sampigethaya K and Poovendran R. Security and privacy of future aircraft wireless communications with offboard systems. In: 2011 Third international conference on communication systems and networks (COMSNETS), 2011, pp.1–6. New York: IEEE.
25.
Planning J. Concept of operations for the next generation air transportation system, 2007.
26.
ZhangJWeiLIUYanboZHU. Study of ADS-B data evaluation. Chin J Aeronaut2011; 24: 461–466.
27.
ReynishW. The giant strides of ADS-B. Avionics1999; 23: 22–25.
28.
PritchettAR. Display effects on shaping apparent strategy: A case study in collision detection and avoidance. Int J Aviat Psychol2000; 10: 59–83.
29.
RTCA Special Committee. Minimum aviation system performance standards for Automatic Dependent Surveillance-Broadcast (ADS-B). Technical report, January 1998.
30.
Gazit RY. Aircraft surveillance and collision avoidance using GPS. Stanford University, USA, 1996.
31.
Barfield F. Autonomous collision avoidance: The technical requirements. In: Proceedings of the IEEE national aerospace and electronics conference, 2000, pp.808–813. New York: IEEE.
32.
Mostov KS and Soloviev AA. Fuzzy adaptive stabilization of higher order Kalman filters in application to precision kinematic GPS. In: Proceedings of the 9th international technical meeting of the satellite division of the institute of navigation (ION GPS 1996), 1996, pp.1451–1456.
33.
MiuraAMorikawaHMizumachiM. Aircraft collision avoidance with potential gradient—ground‐based avoidance for horizontal maneuvers. Electron Commun Jpn1995; 78: 104–114.
34.
Reichardt D and Shick J. Collision avoidance in dynamic environments applied to autonomous vehicle guidance on the motorway. In: Proceedings of the IEEE ‘Intelligent Vehicles’ 94 symposium, 1994, pp.74–78.
35.
TomlinCJLygerosJSastrySS. A game theoretic approach to controller design for hybrid systems. Proc IEEE2000; 88: 949–970.
36.
Chiang LE. 3-D CNC trajectory interpolation using Bresenham’s algorithm. In: 1994 IEEE international symposium on industrial electronics, 1994, pp.264–268. New York: IEEE.
37.
Velastin SA and Xu C. Line and circle finding by the weighted Mahalanobis distance transform and extended Kalman filtering. In: 1994 IEEE international symposium on industrial electronics, 1994, pp.258–263. New York: IEEE.
38.
Ulmer B. Vita ii-active collision avoidance in real traffic. In: Proceedings of the ‘Intelligent Vehicles’, 1994, pp.1–6. New York: IEEE.
39.
An PE, Harris CJ, Tribe R, et al. Aspects of neural networks in intelligent collision avoidance systems for Prometheus, 1993.
40.
ClementsJC. The optimal control of collision avoidance trajectories in air traffic management. Transport Res B: Methodol1999; 33: 265–280.
41.
KimYGuDWPostlethwaiteI. Real-time optimal mission scheduling and flight path selection. IEEE Trans Autom Control2007; 52: 1119–1123.
42.
Alighanbari M, Kuwata Y and How JP. Coordination and control of multiple UAVs with timing constraints and loitering. In: Proceedings of American control conference, 2003, pp.5311–5316. IEEE.
43.
GargDPKumarM. Optimization techniques applied to multiple manipulators for path planning and torque minimization. Eng Appl Artif Intell2002; 15: 241–252.
44.
RagiSChongEK. UAV path planning in a dynamic environment via partially observable Markov decision process. IEEE Trans Aerosp Electron Syst2013; 49: 2397–2412.
45.
Sarkar S, Hall EL and Kumar M. Mobile robot path planning using support vector machines. In: ASME 2008 dynamic systems and control conference, 2008, pp.709–715. New York: American Society of Mechanical Engineers.
46.
Bellingham JS, Tillerson M, Alighanbari M, et al. Cooperative path planning for multiple UAVs in dynamic and uncertain environments. In: Proceedings of the 41st IEEE conference on decision and control, 2002, pp.2816–2822. New York: IEEE.
47.
GrøtliEIJohansenTA. Path planning for UAVs under communication constraints using SPLAT! and MILP. J Intell Robot Syst2012; 65: 265–282.
48.
Schouwenaars T, De Moor B, Feron E, et al. Mixed integer programming for multi-vehicle path planning. In: European control conference, vol. 1, pp.2603–2608.
49.
Chaudhry A, Misovec K and D’Andrea R. Low observability path planning for an unmanned air vehicle using mixed integer linear programming. In: 43rd IEEE conference on decision and control, 2004, pp.3823–3829. New York: IEEE.
50.
Kingston DB and Schumacher CJ. Time-dependent cooperative assignment. In: Proceedings of American control conference, 2005, pp.4084–4089. New York: IEEE.
51.
FossenTI. Handbook of marine craft hydrodynamics and motion control, New York: John Wiley & Sons, 2011.
Radmanesh M, Nemati A, Sarim M, et al. Flight formation of quad-copters in presence of dynamic obstacles using mixed integer linear programming. In: ASME 2015 Dynamic systems and control conference, 2015. New York: American Society of Mechanical Engineers.
54.
EarlMGD'AndreaR. Iterative MILP methods for vehicle-control problems. IEEE Trans Robot2005; 21: 1158–1167.
55.
Forsmo EJ, Grøtli EI, Fossen TI, et al. Optimal search mission with unmanned aerial vehicles using mixed integer linear programming. In: 2013 International conference on unmanned aircraft systems (ICUAS), 2013, pp.253–259. New York: IEEE.
56.
RichardsASchouwenaarsTHowJP. Spacecraft trajectory planning with avoidance constraints using mixed-integer linear programming. J Guid Control Dyn2002; 25: 755–764.
57.
Richards A and How JP. Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In: Proceedings of American control conference, 2002, pp.1936–1941. New York: IEEE.
58.
Reinl C and von Stryk O. Optimal control of multi-vehicle-systems under communication constraints using mixed-integer linear programming. In: Proceedings of the 1st international conference on Robot communication and coordination, 2007, p. 3. New York: IEEE Press.
59.
Lofberg J. YALMIP: A toolbox for modeling and optimization in MATLAB. In: 2004 IEEE international symposium on computer aided control systems design, 2004, pp.284–289. New York: IEEE.
