Three-dimensional multi-constraint route planning of unmanned aerial vehicle low-altitude penetration based on coevolutionary multi-agent genetic algorithm

Abstract

To address the issue of premature convergence and slow convergence rate in three-dimensional (3D) route planning of unmanned aerial vehicle (UAV) low-altitude penetration, a novel route planning method was proposed. First and foremost, a coevolutionary multi-agent genetic algorithm (CE-MAGA) was formed by introducing coevolutionary mechanism to multi-agent genetic algorithm (MAGA), an efficient global optimization algorithm. A dynamic route representation form was also adopted to improve the flight route accuracy. Moreover, an efficient constraint handling method was used to simplify the treatment of multi-constraint and reduce the time-cost of planning computation. Simulation and corresponding analysis show that the planning results of CE-MAGA have better performance on terrain following, terrain avoidance, threat avoidance (TF/TA²) and lower route costs than other existing algorithms. In addition, feasible flight routes can be acquired within 2 s, and the convergence rate of the whole evolutionary process is very fast.

Keywords

unmanned aerial vehicle (UAV) / low-altitude penetration / three-dimensional (3D) route planning / coevolutionary multi-agent genetic algorithm (CE-MAGA)

References

[1] YeW., ZhuA.-h., FanH.-da.. Survey of route planning of low altitude penetration [J]. Journal of System Simulation, 2007, 19(10): 2357-2361

[2] LiuL.-f., ZhangS.-qing.. Voronoi diagram and GIS-based 3D path planning [C]. Proceedings of the 17th International Conference on Geoinformatics, 2009, New York, IEEE: 1100-1104

[3] AsseoS. J.. Terrain following/terrain avoidance path optimization using the method of steepest descent [C]. Proceedings of the IEEE 1988 National Aerospace and Electronics Conference, 1988, Dayton, IEEE: 1128-136

[4] ZhouX.-b., CaiZ.-x., SunG.-rong.. Non-smooth environment modeling and global path planning for mobile robots [J]. Journal of Central South University, 2003, 10(3): 248-254

[5] CaiZ.-x., PengZ.-hong.. The application of a novel path encoding mechanism in path planning for a mobile robot [J]. Robot, 2001, 23(3): 230-233

[6] MittalS., DebK.. Three-dimensional offline path planning for UAVs using multiobjective evolutionary algorithms [C]. Proceedings of IEEE Congress on Evolutionary Computation, 2007, Singapore, IEEE: 3195-3202

[7] HasirciogluI., TopcuogluH. R., ErmisM.. 3-D path planning for the navigation of unmanned aerial vehicles by using evolutionary algorithms [C]. Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008, New York, Association for Computing Machinery: 1499-1506

[8] VacherJ. P., GalinhoT., LesageF., CardonA.. Genetic algorithms in a multi-agent system [C]. Proceedings of IEEE International Joint Symposia on Intelligence and Systems, 1998, Rockville, IEEE: 17-26

[9] ZhongW.-c., LiuJ., XueM.-z., JiaoL.-cheng.. A multiagent genetic algorithm for global numerical optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(2): 1128-1141

[10] CaiZ.-x., PengZ.-hong.. Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multi-mobile robot systems [J]. Journal of Intelligent and Robotic Systems, 2002, 33(1): 61-71

[11] NikolosI. K., ValavanisK. P., TsourveloudisN. C., KostarasA. N.. Evolutionary algorithm based offline/online path planner for UAV navigation [J]. IEEE Transactions on Systems, Man and Cybernetics-Part B: Cybernetics, 2003, 33(6): 898-912

[12] PehlivanogluY. V., BaysalO., HaciogluA.. Path planning for autonomous UAV via vibrational genetic algorithm [J]. Aircraft Engineering and Aerospace Technology, 2007, 79(4): 352-359

[13] BeardR. W., MclainT. W., GoodrichM. A., AndersonE. P.. Coordinated target assignment and intercept for unmanned air vehicles [J]. IEEE Transactions on Robotics and Automation, 2002, 18(6): 911-922

[14] ZhengC.-w., YanP., DingM.-y., SunF.-chun.Route planning for air vehicles [M], 2008, Beijing, National Defense Industry Press: 32-34

[15] DebK.. An efficient constraint handling method for genetic algorithms [J]. Computer Methods in Applied Mechanics and Engineering, 2000, 186(2/3/4): 311-338

[16] RussellS., NorvigP.Artificial intelligence: A modern approach [M], 1995, Englewood Cliffs, Alan Apt: 31-52