RWPSO与马尔科夫链的无人机航路规划
|
摘要
粒子群算法(PSO)是基于种群的全局搜索算法,具有原理简单,搜索稳定高效等特性,在航路规划领域被普遍运用,但是其在陷入局部最优以及收敛速度方面都存在一定的缺陷.本文针对无人机的任务权重值与生存权重值引入随机游走策略,按照一定规律改变粒子的惯性权重值,可以有效的避免上述情况发生,提升无人机在航路规划中找到最优路径的效率.另一方面,为了能够给规划的路径提供优劣性的判断标准或参考依据,需要构建适用于评估无人机飞行路径点上的生存状态概率模型,本文将随机游走粒子群算法(RWPSO)的航路规划模型与马尔科夫链生存状态随机性模型相结合,得到一个可以用来评估路径点生存概率的航路规划问题模型.仿真结果表明,基于任务权重、生存权重、任务生存权重随机游走的RWPSO算法在寻优时比PSO、量子粒子群算法(QPSO)效率更高,并成功结合马尔科夫链得到一个可以描述出无人机生存概率变化的模型.此模型框架还能够扩展应用于有辐射源、武器、电磁干扰等复杂场景中的航路与任务规划.
Particle swarm optimization(PSO) is a global search algorithm based on population, which is characterized by simple principle and stable and efficient search. It is widely used in the field of route planning, but it is defective when falling into local optimum and in convergence speed. In this paper, random walk strategy is introduced to the mission weight and survival weight of UAV. By changing the inertia weight of particles according to certain rules, PSO's defects can be effectively avoided, and UAV's efficiency in finding the optimal path can be improved. On the other hand, in order to provide a criterion or reference to evaluate planned path, it is necessary to construct a survival state probability model to evaluate UAV flight path points. The route planning model of the random walk particle swarm optimization algorithm(RWPSO) was combined with the Markov chain survival state randomness model, thereby building up a route planning model for estimating the survival probability of path points. Simulation results show that RWPSO based on random walk of task weight, survival weight, and task survival weight was more efficient than PSO and quantum particle swarm optimization(QPSO) in optimization. A model describing the change of survival probability of UAV was thus obtained successfully by combining Markov chain with RWPSO. The framework can be extended to route and mission planning in complex scenes with radiation sources, weapons, or electromagnetic interference.
Particle swarm optimization(PSO) is a global search algorithm based on population, which is characterized by simple principle and stable and efficient search. It is widely used in the field of route planning, but it is defective when falling into local optimum and in convergence speed. In this paper, random walk strategy is introduced to the mission weight and survival weight of UAV. By changing the inertia weight of particles according to certain rules, PSO's defects can be effectively avoided, and UAV's efficiency in finding the optimal path can be improved. On the other hand, in order to provide a criterion or reference to evaluate planned path, it is necessary to construct a survival state probability model to evaluate UAV flight path points. The route planning model of the random walk particle swarm optimization algorithm(RWPSO) was combined with the Markov chain survival state randomness model, thereby building up a route planning model for estimating the survival probability of path points. Simulation results show that RWPSO based on random walk of task weight, survival weight, and task survival weight was more efficient than PSO and quantum particle swarm optimization(QPSO) in optimization. A model describing the change of survival probability of UAV was thus obtained successfully by combining Markov chain with RWPSO. The framework can be extended to route and mission planning in complex scenes with radiation sources, weapons, or electromagnetic interference.
引文
[1]NONAMI K.Prospect and recent research & development for civil use autonomous unmanned aircraft as UAV and MAV[J].Journal of System Design & Dynamics,2007.1(2):120.DOI:10.1299/jsdd.1.120
[2]WANG Qiang,ZHANG An,QI Linghui.Three-dimensional path planning for UAV based on improved PSO algorithm[C]//The 26th Chinese Control and Decision Conference (2014 CCDC).IEEE,2014:3981.DOI:10.1109/CCDC.2014.6852877
[3]GENG Qingbo,ZHAO Zheng.A kind of route planning method for UAV based on improved PSO algorithm[C]//2013 25th Chinese Control and Decision Conference (CCDC).IEEE,2013:2328.DOI:10.1109/CCDC.2013.6561326
[4]MARINI F,WALCZAK B.Particle swarm optimization (PSO).A tutorial[J].Chemometrics & Intelligent Laboratory Systems,2015.149:153.DOI:10.1016/j.chemolab.2015.08.020
[5]CHEN Chenyu,CHANG Kuochou,HO S H.Improved framework for particle swarm optimization:Swarm intelligence with diversity-guided random walking[J].Expert Systems with Applications,2011,38(10):12214.DOI:10.1016/j.eswa.2011.03.086
[6]FU Yangguang,DING Mingyue,ZHOU Chengping.Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV[J].IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,2011,42(2):511.DOI:10.1109/tsmca.2011.2159586
[7]CHEN H C,FENG H M,LIN T H,et al.Adapt DB-PSO patterns clustering algorithms and its applications in image segmentation[J].Multimedia Tools and Applications,2016,75(23):15327.DOI:10.1007/s11042-015-2518-4
[8]SHI Y,EBERHART R C.Empirical study of particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat.No.99TH8406).IEEE,1999,3:1945.DOI:10.1109/CEC.1999.785511
[9]ERLANDSSON T,NIKLASSON L.A five states survivability model for missions with ground-to-air threats[C]//Modeling and Simulation for Defense Systems and Applications VIII.International Society for Optics and Photonics,2013,8752:875207.DOI:10.1117/12.2015022
[10]ERLANDSSON T.Route planning for air missions in hostile environments[J].The Journal of Defense Modeling and Simulation:Applications,Methodology,Technology,2015,12(3):289
[11]NEX F,REMONDINO F.UAV for 3D mapping applications:a review[J].Applied Geomatics,2014,6(1):1.DOI:10.1007/s12518-013-0120-x
[12]高芳,崔刚,吴智博,等.求解背包问题的病毒协同进化粒子群算法[J].哈尔滨工业大学学报,2009,41(6):103-107.DOI:10.3321/J.issn:0367-6234GAO Fang,CUI Gang,WU Zhibo,et al.Virus-evolutionary particle swarm optimization algorithm for knapsack problem[J].Journal of Harbin Institute of Technology,2009,41(6):103-107.DOI:10.3321/J.issn:0367-6234
[13]MUELLER M,SMITH N,GHANEM B.A Benchmark and Simulator for UAV Tracking[J].Far East Journal of Mathematical Sciences,2016,2(2):445
[14]MARINAKIS Y,MARINAKI M.A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J].Computers & Operations Research,2010,37(3):432.DOI:10.1016/j.cor.2009.03.004
[15]WANG Gaige,GUO Lihong,DUAN Hong,et al.A bat algorithm with mutation for UCAV path planning[J].The Scientific World Journal,2012,2012:1.DOI:10.1100/2012/418946
[16]GUPTA L,JAIN R,VASZKUN G.Survey of important issues in UAV communication networks[J].IEEE Communications Surveys & Tutorials,2016,18(2):1123.DOI:10.1109/COMST.2015.2495297
[17]HUANG Yu,GUO Feng,LI Yongling,et al.Parameter estimation of fractional-order chaotic systems by using quantum parallel particle swarm optimization algorithm[J].Plos One,2015,10(1):e0114910.DOI:10.1371/journal.pone.0114910
[2]WANG Qiang,ZHANG An,QI Linghui.Three-dimensional path planning for UAV based on improved PSO algorithm[C]//The 26th Chinese Control and Decision Conference (2014 CCDC).IEEE,2014:3981.DOI:10.1109/CCDC.2014.6852877
[3]GENG Qingbo,ZHAO Zheng.A kind of route planning method for UAV based on improved PSO algorithm[C]//2013 25th Chinese Control and Decision Conference (CCDC).IEEE,2013:2328.DOI:10.1109/CCDC.2013.6561326
[4]MARINI F,WALCZAK B.Particle swarm optimization (PSO).A tutorial[J].Chemometrics & Intelligent Laboratory Systems,2015.149:153.DOI:10.1016/j.chemolab.2015.08.020
[5]CHEN Chenyu,CHANG Kuochou,HO S H.Improved framework for particle swarm optimization:Swarm intelligence with diversity-guided random walking[J].Expert Systems with Applications,2011,38(10):12214.DOI:10.1016/j.eswa.2011.03.086
[6]FU Yangguang,DING Mingyue,ZHOU Chengping.Phase angle-encoded and quantum-behaved particle swarm optimization applied to three-dimensional route planning for UAV[J].IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,2011,42(2):511.DOI:10.1109/tsmca.2011.2159586
[7]CHEN H C,FENG H M,LIN T H,et al.Adapt DB-PSO patterns clustering algorithms and its applications in image segmentation[J].Multimedia Tools and Applications,2016,75(23):15327.DOI:10.1007/s11042-015-2518-4
[8]SHI Y,EBERHART R C.Empirical study of particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat.No.99TH8406).IEEE,1999,3:1945.DOI:10.1109/CEC.1999.785511
[9]ERLANDSSON T,NIKLASSON L.A five states survivability model for missions with ground-to-air threats[C]//Modeling and Simulation for Defense Systems and Applications VIII.International Society for Optics and Photonics,2013,8752:875207.DOI:10.1117/12.2015022
[10]ERLANDSSON T.Route planning for air missions in hostile environments[J].The Journal of Defense Modeling and Simulation:Applications,Methodology,Technology,2015,12(3):289
[11]NEX F,REMONDINO F.UAV for 3D mapping applications:a review[J].Applied Geomatics,2014,6(1):1.DOI:10.1007/s12518-013-0120-x
[12]高芳,崔刚,吴智博,等.求解背包问题的病毒协同进化粒子群算法[J].哈尔滨工业大学学报,2009,41(6):103-107.DOI:10.3321/J.issn:0367-6234GAO Fang,CUI Gang,WU Zhibo,et al.Virus-evolutionary particle swarm optimization algorithm for knapsack problem[J].Journal of Harbin Institute of Technology,2009,41(6):103-107.DOI:10.3321/J.issn:0367-6234
[13]MUELLER M,SMITH N,GHANEM B.A Benchmark and Simulator for UAV Tracking[J].Far East Journal of Mathematical Sciences,2016,2(2):445
[14]MARINAKIS Y,MARINAKI M.A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J].Computers & Operations Research,2010,37(3):432.DOI:10.1016/j.cor.2009.03.004
[15]WANG Gaige,GUO Lihong,DUAN Hong,et al.A bat algorithm with mutation for UCAV path planning[J].The Scientific World Journal,2012,2012:1.DOI:10.1100/2012/418946
[16]GUPTA L,JAIN R,VASZKUN G.Survey of important issues in UAV communication networks[J].IEEE Communications Surveys & Tutorials,2016,18(2):1123.DOI:10.1109/COMST.2015.2495297
[17]HUANG Yu,GUO Feng,LI Yongling,et al.Parameter estimation of fractional-order chaotic systems by using quantum parallel particle swarm optimization algorithm[J].Plos One,2015,10(1):e0114910.DOI:10.1371/journal.pone.0114910
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |