Navigation planning can be considered as a combination of searching and executing the most convenient flight path from an initial waypoint to a destination waypoint. Generally the aim is to follow the flight path, which provides minimum fuel consumption for the air vehicle. For dynamic environments, constraints change dynamically during flight. This is a special case of dynamic path planning. As the main concern of this paper is flight planning, the conditions and objectives that are most probable to be used in navigation problem are considered. In this paper, the genetic algorithm solution of the dynamic flight planning problem is explained. The evolutionary dynamic navigation planning algorithm is developed for compensating the existing deficiencies of the other approaches. The existing fully dynamic algorithms process unit changes to topology one modification at a time, but when there are several such operations occurring in the environment simultaneously, the algorithms are quite inefficient. The proposed algorithm may respond to the concurrent constraint updates in a shorter time for dynamic environment. The most secure navigation of the air vehicle is planned and executed so that the fuel consumption is minimum. 1. Introduction Navigation planning requires producing a flight plan to describe a proposed aircraft flight. It involves two safety-critical aspects: minimum fuel consumption and compliance with air traffic control requirements. Navigation planning involves creating a flight plan to guide a point-like object from its initial position to a destination waypoint [1]. Along the way, there may be a set of regions to visit and a set of regions to avoid. Planners wish to reach the destination economically and by minimum risk of mid-air collision. Fuel consumption involves fuel flow rate estimations, so that the relation of fuel flow with air temperature, flight altitude, true airspeed, and gross weight can be defined with an accurate formula [2]. Safety regulations require aircraft to carry fuel beyond the minimum needed to fly from origin to destination, allowing for unforeseen circumstances or for diversion to another airport if the planned destination becomes unavailable. Furthermore, under the supervision of air traffic control, aircraft flying in controlled airspace must follow predetermined routes known as airways, even if such routes are not as economical as a more direct flight [3, 4]. The basis of the flight profile is the route that the aircraft is to fly from the departure airport to the destination airport. Flight planning function
References
[1]
M. A. Al-Jarrah and M. M. Hasan, “HILS setup of dynamic flight path planning in 3D environment with flexible mission planning using Ground Station,” Journal of the Franklin Institute, vol. 348, no. 1, pp. 45–65, 2011.
[2]
Joint Planning and Development Office, “Concept of operations for the next generation air transportation system,” Version 3.0, 2009.
[3]
M. T. De Garmo, “Issues concerning integration unmanned aerial vehicles in civil airspace,” Tech. Rep. MP 04W0000323, MITRE, Va, USA, 2004.
[4]
R. Weibel and R. J. Hansman, “Safety considerations for operation of unmanned aerial vehicles in the national airspace system,” MIT International Center for Air Transportation Report ICAT, 2005-01, ICAT, 2005.
[5]
B. M. Sathyaraj, L. C. Jain, A. Finn, and S. Drake, “Multiple UAVs path planning algorithms: a comparative study,” Fuzzy Optimization and Decision Making, vol. 7, no. 3, pp. 257–267, 2008.
[6]
I. K. Nikolos, N. Tsourveloudis, and K. P. Valavanis, “Evolutionary algorithm based 3-D path planner for UAV navigation,” in Proceedings of the 9th Mediterranean Conference on Control and Automation (CDROM'10), Dubrovnik, Croatia, 2001.
[7]
Y. C. Hui, E. C. Prakash, and N. S. Chaudhari, “Game AI: artifical intelligence for 3D path finding,” in Proceedings of the IEEE Region 10 Conference: Analog and Digital Techniques in Electrical Engineering (TENCON'04), pp. B306–B309, tha, November 2004.
[8]
S. Misra and B. J. Oommen, “Stochastic learning automata-based dynamic algorithms for the single source shortest path problem,” in Proceedings of the 17th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE'04), pp. 239–248, May 2004.
[9]
Q. Li, W. Zhang, Y. Yin, Z. Wang, and G. Liu, “An improved genetic algorithm of optimum path planning for mobile robots,” in Proceedings of the 6th International Conference on Intelligent Systems Design and Applications (ISDA'06), pp. 637–642, October 2006.
[10]
J. Tu and S. X. Yang, “Genetic algorithm based path planning for a mobile robot,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1221–1226, Taiwan, September 2003.
[11]
W. Wu and Q. Ruan, “A gene-constrained genetic algorithm for solving shortest path problem,” in Proceedings of the 7th International Conference on Signal Processing Proceedings (ICSP'04), pp. 2512–2515, September 2004.
[12]
H. Mahjoubi, F. Bahrami, and C. Lucas, “Path planning in an environment with static and dynamic obstacles using genetic algorithm: a simplified search space approach,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC'06), pp. 2483–2489, Vancouver, Canada, July 2006.
[13]
J. Inagaki, M. Haseyama, and H. Kitajima, “Genetic algorithm for determining multiple routes and its applications,” in Proceedings of the 1999 IEEE International Symposium on Circuits and Systems (ISCAS '99), pp. I-137–I-140, June 1999.
[14]
G. Ramalingam and T. Reps, “On the computational complexity of dynamic graph problems,” Theoretical Computer Science, vol. 158, no. 1-2, pp. 233–277, 1996.
[15]
P. G. Franciosa, D. Frigioni, and R. Giaccio, “Semi-dynamic shortest paths and breadth first search in digraphs,” in Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, pp. 33–46, Lübeck, Germany, 1997.
[16]
D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni, “Fully dynamic algorithms for maintaining shortest paths trees,” Journal of Algorithms, vol. 34, no. 2, pp. 251–281, 2000.
[17]
A. Elshamli, H. A. Abdullah, and S. Areibi, “Genetic algorithm for dynamic path planning,” in Proceedings of the Canadian Conference on Electrical and Computer Engineering, pp. 677–680, May 2004.
[18]
D. Catanzaro, M. Labbé, and M. Salazar-Neumann, “Reduction approaches for robust shortest path problems,” Computers and Operations Research, vol. 38, no. 11, pp. 1610–1619, 2011.
[19]
C. Zheng, L. Li, F. Xu, F. Sun, and M. Ding, “Evolutionary route planner for unmanned air vehicles,” IEEE Transactions on Robotics, vol. 21, no. 4, pp. 609–620, 2005.
[20]
G. Xiao, F. Xiao, and C. Da, “A genetic-algorithm-based approach to UA V path planning problem,” in Proceedings of the 5th WSEAS International Conference on Simulation, Modelling and Optimization, pp. 17503–19507, Corfu, Greece, August 2005.
[21]
S. Li, X. Sun, and Y. Xu, “Particle swarm optimization for route planning of unmanned aerial vehicles,” in Proceedings of the IEEE International Conference on Information Acquisition (ICIA'06), pp. 1213–1218, Shandong, China, August 2006.
[22]
G. Wang, Q. Li, and L. Guo, “Multiple UAVs routes planning based on particle swarm optimization algorithm,” in Proceedings of the 2nd International Symposium on Information Engineering and Electronic Commerce (IEEC'10), pp. 150–154, July 2010.
[23]
H. Chitsaz and S. M. LaValle, “Time-optimal paths for a dubins airplane,” in Proceedings of the 46th IEEE Conference on Decision and Control (CDC'07), pp. 2379–2384, New Orleans, La, USA, December 2007.
[24]
R. Dai and J. E. Cochran, “Path planning for multiple unmanned aerial vehicles by parameterized cornu-spirals,” in Proceedings of the American Control Conference (ACC'09), pp. 2391–2396, St. Louis, Mo, USA, June 2009.
[25]
M. Shanmugavel, A. Tsourdos, and B. A. White, “Collision avoidance and path planning of multiple UAVs using flyable paths in 3D,” in Proceedings of the 15th International Conference on Methods and Models in Automation and Robotics (MMAR'10), pp. 218–222, August 2010.
[26]
M. Shanmugavel, A. Tsourdos, B. White, and R. Zbikowski, “Co-operative path planning of multiple UAVs using Dubins paths with clothoid arcs,” Control Engineering Practice, vol. 18, no. 9, pp. 1084–1092, 2010.
[27]
S. P. Bhat and P. Kumar, “A feedback guidance strategy for an autonomous mini-air vehicle,” in Proceedings of the National Conference on Control and Dynamical Systems, IIT Bombay, Bombay, India, January 2005.
[28]
S. Gualandi and B. Tranchero, “Concurrent constraint programming-based path planning for uninhabited air vehicles,” in Proceedings of the SPIE/Defense and Security Symposium on Unmanned Ground, Ocean, and Air Technologies, pp. 12–16, April 2004.
[29]
W. Ren and R. W. Beard, “Constrained nonlinear tracking control for small fixed-wing unmanned air vehicles,” in Proceedings of the American Control Conference (AAC'04), pp. 4663–4668, Boston, Mass, USA, July 2004.
[30]
D. Kingston, Implementation issue of real-time trajectory generation of small UAV [M.S. thesis], Birmingham Young University, 2004.
[31]
R. Beard, D. Kingston, M. Quigley et al., “Autonomous vehicle technologies for small fixed-wing UAVs,” Journal of Aerospace Computing, Information and Communication, pp. 92–108, 2005.
[32]
C. H. Lin, J. L. Yu, J. C. Liu, and C. J. Lee, “Genetic algorithm for shortest driving time in intelligent transportation systems,” in Proceedings of the International Conference on Multimedia and Ubiquitous Engineering (MUE'08), pp. 402–406, Busan, Korea, April 2008.
[33]
B. S. Hasan, M. A. Khamees, and A. S. H. Mahmoud, “A heuristic genetic algorithm for the single source shortest path problem,” in Proceedings of the IEEE/ACS International Conference on Computer Systems and Applications (AICCSA'07), pp. 187–194, May 2007.
[34]
S. Yang, H. Cheng, and F. Wang, “Genetic algorithms with immigrants and memory schemes for dynamic shortest path routing problems in mobile ad hoc networks,” IEEE Transactions on Systems, Man and Cybernetics Part C, vol. 40, no. 1, pp. 52–63, 2010.
[35]
S. Yang, “Population-based incremental learning with memory scheme for changing environments,” in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'05), pp. 711–718, June 2005.
[36]
J. A. Farrell and M. Barth, The Global Positioning System & Inertial Navigation, McGraw Hill, 1999.
[37]
“Aerosim Blockset,” Version 1.2, User's Guide, Unmanned Dynamics, LLC.
[38]
S. Stolle and R. Rysdyk, “Flight path following guidance for unmanned air vehicles with pan-tilt camera for target observation,” in Proceedings of the 22nd Digital Avionics Systems Conference, pp. 8.B.3/1–8.B.3/12, Indianapolis, Ind, USA, October 2003.
[39]
K. Y. Pettersen and E. Lefeber, “Way-point tracking control of ships,” in Proceedings of the 40th IEEE Conference on Decision and Control (CDC'01), pp. 940–945, Orlando, Fla, USA, December 2001.
[40]
R. Rysdyk, “UAV Path Following for constant line-of-sight,” in Proceedings of the 2nd AIAA "Unmanned Unlimited" Systems, Technologies, and Operations Aerospace, Land, and Sea Conference, paper no. 6626, San-Diego, Calif, USA, September 2003.
[41]
T. Back, D. B. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Oxford University Press, London, UK, 1997.
[42]
G. Harik, E. Cantu-Paz, D. E. Goldberg, and B. L. Miller, “The Gambler's ruin problem, genetic algorithms, and the sizing of populations.,” Evolutionary Computation, vol. 7, no. 3, pp. 231–253, 1999.
[43]
C. W. Ahn and R. S. Ramakrishna, “A genetic algorithm for shortest path routing problem and the sizing of populations,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, pp. 566–579, 2002.
[44]
I. Hatzakis and D. Wallace, “Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach,” in Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference (GECCO'06), pp. 1201–1208, July 2006.
[45]
P. A. N. Bosman, “Learning, anticipation and time-deception in evolutionary online dynamic optimization,” in Proceedings of the Workshop on Evolutionary Algorithms for Dynamic Optimization (GECCO'05), Washington, DC, USA, 2005.
[46]
C. Chitra and P. Subbaraj, “Multiobjective optimization solution for shortest path routing problem,” International Journal of Computer and Information Engineering, vol. 4, no. 2, pp. 77–85, 2010.
[47]
R. W. Morrison, Designing Evolutionary Algorithms for Dynamic Environments, Springer, Berlin, Germany, 2004.
