A*初始化的变异灰狼优化的无人机路径规划

doi:10.3778/j.issn.1002-8331.2008-0426

摘要/Abstract

摘要： 无人机（unmanned aerial vehicle，UAV）路径规划问题是无人机任务规划系统的重要组成部分，需要在一个存在威胁区的搜索空间中获得最优路径。为解决灰狼优化算法存在收敛速度慢、容易陷入局部最优等问题，提出了一种基于A*初始化的变异灰狼优化算法。该算法首先将模型离散化，进而使用A*算法进行头狼的初始化，使后续算法有一个较优的起点，随后通过简化后的灰狼优化算法在连续模型上构建和更新种群，在迭代过程中，通过新提出的一种新型修正变异算子优化种群。利用三次B样条平滑后的无人机航迹，符合无人机的性能要求。经实验验证，算法在代价收敛速度、求取的最终路径以及算法稳定性方面均优于粒子群算法（particle swarm optimization，PSO）、灰狼优化算法（gray wolf optimizer，GWO）、共生生物搜索算法（symbiotic organisms search，SOS）算法，在解决无人机路径规划问题上具有较高的应用价值。

关键词: 无人机（UAV）, 路径规划, A*算法, 灰狼优化（GWO）

Abstract: Path planning of UAV（unmanned aerial vehicle） is an important part of UAV mission planning system. It is necessary to obtain the optimal path in a search space with threat area. In order to solve the problems of slow convergence speed and easy to fall into local optimization, a mutation gray wolf optimizer algorithm based on A* initialization is proposed. The algorithm first discretizes the model, and then uses A* algorithm to initialize the wolf, so that the subsequent algorithm has a better starting point. Then, the simplified gray wolf optimizer algorithm is used to build and update the population on the continuous model. In the iterative process, the population is optimized by a new modified mutation operator proposed in the paper. The UAV track smoothed by cubic B-spline meets the performance requirements of UAV. The experimental results show that the algorithm is superior to PSO（particle swarm optimization）, GWO（grey wolf optimizer） and SOS（symbiotic organisms search） algorithms in cost convergence speed, final path and algorithm stability, and has high application value in solving UAV path planning problems.

Key words: unmanned aerial vehicle（UAV）, path planning, A* algorithm, gray wolf optimizer（GWO）

曹建秋, 张广言, 徐鹏. A*初始化的变异灰狼优化的无人机路径规划[J]. 计算机工程与应用, 2022, 58(4): 275-282.

CAO Jianqiu, ZHANG Guangyan, XU Peng. A* Initialized Mutable Gray Wolf Optimizer for UAV Path Planning[J]. Computer Engineering and Applications, 2022, 58(4): 275-282.

参考文献

[1] SANTOSO F，GARRATT M A，ANAVATTI S G.State-of-the-art intelligent flight control systems in unmanned aerial vehicles[J].IEEE Transactions on Automation Science and Engineering，2018，15（2）：613-627.
[2] RAO G，HE C Q，CHEN H L，et al.Use of small unmanned aerial vehicle （sUAV）-acquired topography for identifying and characterizing active normal faults along the Seerteng Shan，North China[J].Geomorphology，2020，359：107168.
[3] 邵文武，杨进程，黄涛.我国民用无人机市场发展现状及存在问题分析[J].沈阳航空航天大学学报，2019，36（6）：61-69.
SHAO W W，YANG J C，HUANG T.Analysis on the development status and existing problems of civil UAV market in China[J].Journal of Shenyang Aerospace University，2019，36（6）：61-69.
[4] QU C Z，GAI W D，ZHANG J，et al.A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle（UAV） path planning[J].Knowledge-Based Systems，2020，194：105530.
[5] 胡中华.基于智能优化算法的无人机航迹规划若干关键技术研究[D].南京：南京航空航天大学，2011.
HU Z H.Research on some key techniques of UAV path planning based on intelligent optimization algorithm[D].Nanjing：Nanjing University of Aeronautics and Astronautics，2011.
[6] LU E，XU L Z，LI Y，et al.A novel particle swarm optimization with improved learning strategies and its application to vehicle path planning[J].Mathematical Problems in Engineering，2019（8）：1-16.
[7] WU J W，BIN D，FENG X B，et al.GA based adaptive singularity-robust path planning of space robot for on-orbit detection[J].Complexity，2018：3702916.
[8] PATLE B K，BABU L G，PANDEY A，et al.A review：on path planning strategies for navigation of mobile robot[J].Defence Technology，2019，15（4）：582-606.
[9] MIRJALILI S，MIRJALILI S M，LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software，2014，69：46-61.
[10] 张晓凤，王秀英.灰狼优化算法研究综述[J].计算机科学，2019，46（3）：30-38.
ZHANG X F，WANG X Y.Comprehensive review of grey wolf optimization algorithm[J].Computer Science，2019，46（3）：30-38.
[11] PRADHAN M，ROY P K，PAL T.Grey wolf optimization applied to economic load dispatch problems[J].International Journal of Electrical Power & Energy Systems，2016，83：325-334.
[12] SHAKARAMI M R，DAVOUDKHANI I F.Wide-area power system stabilizer design based on grey wolf optimization algorithm considering the time delay[J].Electric Power Systems Research，2016，133：149-159.
[13] 李靖，杨帆.基于IGWO-A*算法的无人机农田喷洒航迹规划[J].沈阳农业大学学报，2020，51（2）：231-237.
LI J，YANG F.Route planning of UAV for farmland spraying based on IGWO-A* algorithm[J].Journal of Shenyang Agricultural University，2020，51（2）：231-237.
[14] 袁光辉.基于改进灰狼优化算法的物流配送路径规划[J].荆楚理工学院学报，2019，34（3）：12-19.
YUAN G H.Logistics distribution route planning based on improved gray wolf optimizer[J].Journal of Jingchu University of Technology，2019，34（3）：12-19.
[15] 刘二辉，姚锡凡，刘敏，等.基于改进灰狼优化算法的自动导引小车路径规划及其实现原型平台[J].计算机集成制造系统，2018，24（11）：2779-2791.
LIU E H，YAO X F，LIU M，et al.AGV path planning based on improved grey wolf optimization algorithm and its implementation prototype platform[J].Computer Integrated Manufacturing Systems，2018，24（11）：2779-2791.
[16] XU C，DUAN H，LIU F.Chaotic artificial bee colony approach to uninhabited combat air vehicle（UCAV） path planning[J].Aerospace Science and Technology，2010，14（8）：535-541.
[17] 谭雁英，李洋，周军，等.复杂环境下基于A*算法的无人机路径再规划[J].系统工程与电子技术，2017，39（6）：1268-1273.
TAN Y Y，LI Y，ZHOU J，et al.Path replanning approach for UAV based on A*algorithm in complex environment[J].Systems Engineering and Electrinics，2017，39（6）：1268-1273.
[18] ZHANG S，ZHOU Y，LI Z，et al.Grey wolf optimizer for unmanned combat aerial vehicle path planning[J].Advances in Engineering Software，2016，99：121-136.
[19] 季艳芳.两种智能优化算法及其收敛性分析[D].武汉：华中科技大学，2011.
JI Y F.Two intelligent optimization algorithm and its convergence analysis[D].Wuhan：Huazhong University of Science and Technology，2011.
[20] 马骏.基于灰狼优化算法的改进研究及其应用[D].杭州：杭州电子科技大学，2018.
MA J.Improved research based on grey wolf optimizer algorithm and its application[D].Hangzhou：Hangzhou Dianzi University，2018.
[21] 罗凤鸣，吕方林，侯宗琰.基于精英保留策略与爆炸算子的改进遗传算法[J].西华大学学报（自然科学版），2018，37（3）：83-88.
LUO F M，LYU F L，HOU Z Y.An improved genetic algorithm based on elite retention strategy and explosion operators[J].Journal of Xihua University（Natural Science Edition），2018，37（3）：83-88.
[22] 冯士刚，艾芊.带精英策略的快速非支配排序遗传算法在多目标无功优化中的应用[J].电工技术学报，2007（12）：146-151.
FENG S G，AI Q.Application of fast and elitist non-dominated sorting generic algorithm in multi-objective reactive power optimization[J].Transactions of China Electrotechnical Society，2007（12）：146-151.
[23] 苗发辉.共生生物搜索算法改进及应用研究[D].南宁：广西民族大学，2018.
MIAO F H.Improvement and application of symbiotic organisms search algorithm[D].Nanning：Guangxi University for Nationalities，2018.