无人机航迹规划常用算法综述
|
摘要
为促进航迹规划技术的发展,对航迹规划常用算法进行综述。首先对航迹规划的规划思想和构成进行分析;其次将航迹规划算法分为传统经典算法和现代智能算法两大类,对其中几种常用算法进行分析总结;最后阐述现代智能算法在航迹规划应用中的改进、多重算法的融合改进以及多无人机四维航迹规划算法研究3个研究热点及未来发展趋势。
In order to promote the development of path planning technology,the planning ideas and forms of path planning are analyzed. The path planning algorithms are divided into the traditional classical algorithms and modern intelligent algorithms in two categories,and some commonly used algorithms are analyzed and summarized.And the current research hotspots and future development trends are pointed out from the three aspects of improving the application of modern intelligent algorithms in path planning,amalgamation of multiple algorithms and the research of four-dimensional path planning algorithms for multiple UAVs.
In order to promote the development of path planning technology,the planning ideas and forms of path planning are analyzed. The path planning algorithms are divided into the traditional classical algorithms and modern intelligent algorithms in two categories,and some commonly used algorithms are analyzed and summarized.And the current research hotspots and future development trends are pointed out from the three aspects of improving the application of modern intelligent algorithms in path planning,amalgamation of multiple algorithms and the research of four-dimensional path planning algorithms for multiple UAVs.
引文
[1]郑昌文,严平,丁明跃,等.飞行器航迹规划研究现状与趋势[J].宇航学报,2007,28(6):7-12.ZHENG Changwen,YAN Ping,DING Mingyue,et al. Research Status and Trend of Route Planning for Flying Vehicles[J].Journal of Astronautics,2007,28(6):7-12.
[2]韩攀,陈谋,陈哨东,等.基于改进蚁群算法的无人机航迹规划[J].吉林大学学报:信息科学版,2013,31(1):66-72.HAN Pan,CHEN Mou,CHEN Shaodong,et al. UAV Track Planning Based on Improved Ant Colony Algorithm[J]. Journal of Jilin University:Information Science Edition,2013,31(1):66-72.
[3]王维平,刘娟.无人飞行器航迹规划方法综述[J].飞行力学,2010,28(2):6-10.WANG Weiping,LIU Juan. A Summary of UAV Track Planning Methods[J]. Flight Dynamics,2010,28(2):6-10.
[4]聂俊岚,张庆杰,王艳芬.基于加权Voronoi图的无人飞行器航迹规划[J].飞行力学,2015,33(4):339-343.NIE Junlan,ZHANG Qingjie,WANG Yanfen. Flight Path Planning of UAV Based on Weighted Voronoi Diagram[J]. Flight Dynamics,2015,33(4):339-343.
[5]MEDEIROS F L L,SILVA J D S D. Computational Modeling for Automatic Path Planning Based on Evaluations of the Effects of Impacts of UAVs on the Ground[J]. Journal of Intelligent&Robotic Systems,2011,61(1):181-202.
[6]YAN F,LIU Y S,XIAO J Z. Path Planning in Complex 3D Environments Using a Probabilistic Roadmap Method[J].International Journal of Automation and Computing,2013,10(6):525-533.
[7]李世晓,朱凡,张健,等.改进A*算法的多约束航迹规划[J].电光与控制,2014,21(7):36-40.LI Shixiao,ZHU Fan,ZHANG Jian,et al. Improved Multi-Constraint Track Planning for A*Algorithm[J]. Electro-Optics and Control,2014,21(7):36-40.
[8]程琪,荆涛,于志游.利用三次样条改进蚁群算法的无人机航路规划[J].计算机测量与控制,2016,24(8):272-274.CHENG Qi,JING Tao,YU Zhiyou. UAV Route Planning Using Cubic Spline Improved Ant Colony Algorithm[J]. Computer Measurement&Control,2016,24(8):272-274.
[9]SAHINGOZ O K. Generation of Bezier Curve-Based Flyable Trajectories for Multi-UAV Systems with Parallel Genetic Algorithm[J]. Journal of Intelligent&Robotic Systems,2014,74(1/2):499-511.
[10]HUANG L,QU H,JI P,et al. A Novel Coordinated Path Planning Method Using K-Degree Smoothing for Multi-UAVs[J].Applied Soft Computing,2016,48:182-192.
[11]胡中华,赵敏,姚敏,等.无人机航迹规划技术研究及发展趋势[J].航空电子技术,2009,40(2):24-29.HU Zhonghua,ZHAO Min,YAO Min,et al. Research and Development Trend of UAV Track Planning Technology[J].Avionics Technology,2009,40(2):24-29.
[12]DONG S,ZHU X,LONG G. Cooperative Planning Method For Swarm UAVs Based on Hierarchical Strategy[C]∥International Conference on System Science,Engineering Design and Manufacturing Informatization. Pacific Grove,CA,USA:IEEE,2012:304-307.
[13]MAINI P,SUJIT P B. Path Planning for a UAV with Kinematic Constraints in the Presence of Polygonal Obstacles[C]∥International Conference on Unmanned Aircraft Systems. Arlington,VA,USA:IEEE,2016:62-67.
[14]QU Y,ZHANG Y,ZHANG Y. Optimal Flight Path Planning for UAVs in 3-D Threat Environment[C]∥International Conference on Unmanned Aircraft Systems. Orlando,FL,USA:IEEE,2014:149-155.
[15]CHEN X,ZHANG J. The Three-Dimension Path Planning of UAV Based on Improved Artificial Potential Field in Dynamic Environment[C]∥International Conference on Intelligent Human-Machine Systems and Cybernetics. Tlemcen,Algeria:IEEE,2013:144-147.
[16]王强,张安,吴忠杰.改进人工势场法与模拟退火算法的无人机航路规划[J].火力与指挥控制,2014(8):70-73.WANG Qiang,ZHANG An,WU Zhongjie. UAV Route Planning Based on Improved Artificial Potential Field Method and Simulated Annealing Algorithm[J]. Fire Control&Command Control,2014(8):70-73.
[17]姚远,周兴社,张凯龙,等.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用,2010,27(7):953-959.YAO Yuan,ZHOU Xingshe,ZHANG Kailong,et al. Dynamic Path Planning of Unmanned Aerial Vehicles Based on Sparse A*Search and Improved Artificial Potential Fields[J]. Control Theory and Applications,2010,27(7):953-959.
[18]王伟,王华.基于约束人工势场法的弹载飞行器实时避障航迹规划[J].航空动力学报,2014,29(7):1738-1743.WANG Wei,WANG Hua. Real-Time Obstacle Avoidance Path Planning of Missile-Borne Vehicle Based on Constrained Artificial Potential Field Method[J]. Journal of Aerospace Power,2014,29(7):1738-1743.
[19]罗冠辰,于剑桥,张思宇,等.穿越恶劣天气区域的无人机航迹规划[J].北京理工大学学报,2014,34(10):1054-1059.LUO Guanchen,YU Jianqiao,ZHANG Siyu,et al. Drone Path Planning through Bad Weather Areas[J]. Transaction of Beijing Institute of Technology,2014,34(10):1054-1059.
[20]BEHNCK L P,DOERING D,PEREIRA C E,et al. A Modified Simulated Annealing Algorithm for SUAVs Path Planning[J]. IFAC Papersonline,2015,48(10):63-68.
[21]邱福生,杨建平,邵绪威.基于遗传模拟退火算法的无人机航迹规划[J].沈阳航空航天大学学报,2014,31(1):16-19.QIU Fusheng,YANG Jianping,SHAO Xuwei. Flight Path Planning of UAV Based on Genetic Simulated Annealing Algorithm[J]. Journal of Shenyang Institute of Aeronautical Engineering,2014,31(1):16-19.
[22]占伟伟,王伟,陈能成,等.一种利用改进A*算法的无人机航迹规划[J].武汉大学学报:信息科学版,2015,40(3):315-320.ZHAN Weiwei,WANG Wei,CHEN Nengcheng,et al. UAV Track Planning Using Improved A*Algorithm[J]. Geomatics and Information Science of Wuhan University,2015,40(3):315-320.
[23]杨润洲,丁勇,张承果.基于DTW的改进A*算法在航迹规划中的应用[J].电光与控制,2016,23(6):5-10.YANG Runzhou,DING Yong,ZHANG Chengguo. Application of Improved A*Algorithm Based on DTW in Track Planning[J]. Electro-optics and Control,2016,23(6):5-10.
[24]鱼佳欣,李刚,李东涛,等.改进量子遗传算法在无人机航迹规划中的应用[J].计算机仿真,2015,32(5):106-109.YU Jiaxin,LI Gang,LI Dongtao,et al. Application of Improved Quantum Genetic Algorithm in UAV Flight Path Planning[J]. Computer Simulation,2015,32(5):106-109.
[25]HAMED S,MOJTABA V,BABAK I,et al. Optimal Cooperative Path Planning of Unmanned Aerial Vehicles by a Parallel Genetic Algorithm[J]. Robotica,2016,34(4):823-836.
[26]俞琪,刘新,周成平,等.基于病毒遗传算法的快速航迹规划方法[J].宇航学报,2011,32(4):756-761.YU Qi,LIU Xin,ZHOU Chengping,et al. Fast Track Planning Method Based on Virus Genetic Algorithm[J]. Journal of Astronautics,2011,32(4):756-761.
[27]PEHLIVANOGLU Y V. A New Vibrational Genetic Algorithm Enhanced with a Voronoi Diagram for Path Planning of Autonomous UAV[J]. Aerospace Science&Technology,2012,16(1):47-55.
[28]DUAN H,YU Y,ZHANG X,et al. Three-Dimension Path Planning for UCAV Using Hybrid Meta-Heuristic ACO-DE Algorithm[J]. Simulation Modelling Practice&Theory,2010,18(8):1104-1115.
[29]刘振峰,谢洪森,危水根.基于文化蚁群算法的三维飞行器航路规划[J].计算机仿真,2013,30(5):99-103.LIU Zhenfeng,XIE Hongsen,WEI Shuigen. Route Planning of 3D Aircraft Based on Cultural Ant Colony Algorithm[J].Computer Simulation,2013,30(5):99-103.
[30]TAO J,WANG Y,YANG H,et al. Three-Dimensional Path Planning of Unmanned Aerial Vehicle under Complicated Environment[C]∥Control and Decision Conference. Big Sky,MT,USA:IEEE,2016:6377-6382.
[31]傅阳光,周成平,丁明跃.基于混合量子粒子群优化算法的三维航迹规划[J].宇航学报,2010,31(12):2657-2664.FU Yangguang,ZHOU Chengping,DING Mingyue. Three-Dimensional Path Planning Based on Hybrid Quantum Particle Swarm Optimization Algorithm[J]. Journal of Astronautics,2010,31(12):2657-2664.
[32]吴天爱,吴云玉,别晓峰.采用病毒粒子群优化算法的飞行器航迹规划[J].电光与控制,2014,21(8):102-105.WU Tianai,WU Yunyu,BIE Xiaofeng. Aircraft Path Planning Using Virus Particle Swarm Optimization Algorithm[J].Electro-optics and Control,2014,21(8):102-105.
[33]LIU Y,ZHAN G X,GUAN X,et al. Potential Odor Intensity Grid Based UAV Path Planning Algorithm with Particle Swarm Optimization Approach[J]. Mathematical Problems in Engineering,2016,2016(2):1-16.
[34]杨祖强.生物启发的多无人机协同四维航迹规划方法研究[D].杭州:浙江大学航空航天学院,2016.YANG Zuqiang. Bio-inspired 4D Trajectory Generation for Multi-UAV Cooperation[D]. Hangzhou:School of Aeronautics and Astronautics,Zhejiang University,2016.
[2]韩攀,陈谋,陈哨东,等.基于改进蚁群算法的无人机航迹规划[J].吉林大学学报:信息科学版,2013,31(1):66-72.HAN Pan,CHEN Mou,CHEN Shaodong,et al. UAV Track Planning Based on Improved Ant Colony Algorithm[J]. Journal of Jilin University:Information Science Edition,2013,31(1):66-72.
[3]王维平,刘娟.无人飞行器航迹规划方法综述[J].飞行力学,2010,28(2):6-10.WANG Weiping,LIU Juan. A Summary of UAV Track Planning Methods[J]. Flight Dynamics,2010,28(2):6-10.
[4]聂俊岚,张庆杰,王艳芬.基于加权Voronoi图的无人飞行器航迹规划[J].飞行力学,2015,33(4):339-343.NIE Junlan,ZHANG Qingjie,WANG Yanfen. Flight Path Planning of UAV Based on Weighted Voronoi Diagram[J]. Flight Dynamics,2015,33(4):339-343.
[5]MEDEIROS F L L,SILVA J D S D. Computational Modeling for Automatic Path Planning Based on Evaluations of the Effects of Impacts of UAVs on the Ground[J]. Journal of Intelligent&Robotic Systems,2011,61(1):181-202.
[6]YAN F,LIU Y S,XIAO J Z. Path Planning in Complex 3D Environments Using a Probabilistic Roadmap Method[J].International Journal of Automation and Computing,2013,10(6):525-533.
[7]李世晓,朱凡,张健,等.改进A*算法的多约束航迹规划[J].电光与控制,2014,21(7):36-40.LI Shixiao,ZHU Fan,ZHANG Jian,et al. Improved Multi-Constraint Track Planning for A*Algorithm[J]. Electro-Optics and Control,2014,21(7):36-40.
[8]程琪,荆涛,于志游.利用三次样条改进蚁群算法的无人机航路规划[J].计算机测量与控制,2016,24(8):272-274.CHENG Qi,JING Tao,YU Zhiyou. UAV Route Planning Using Cubic Spline Improved Ant Colony Algorithm[J]. Computer Measurement&Control,2016,24(8):272-274.
[9]SAHINGOZ O K. Generation of Bezier Curve-Based Flyable Trajectories for Multi-UAV Systems with Parallel Genetic Algorithm[J]. Journal of Intelligent&Robotic Systems,2014,74(1/2):499-511.
[10]HUANG L,QU H,JI P,et al. A Novel Coordinated Path Planning Method Using K-Degree Smoothing for Multi-UAVs[J].Applied Soft Computing,2016,48:182-192.
[11]胡中华,赵敏,姚敏,等.无人机航迹规划技术研究及发展趋势[J].航空电子技术,2009,40(2):24-29.HU Zhonghua,ZHAO Min,YAO Min,et al. Research and Development Trend of UAV Track Planning Technology[J].Avionics Technology,2009,40(2):24-29.
[12]DONG S,ZHU X,LONG G. Cooperative Planning Method For Swarm UAVs Based on Hierarchical Strategy[C]∥International Conference on System Science,Engineering Design and Manufacturing Informatization. Pacific Grove,CA,USA:IEEE,2012:304-307.
[13]MAINI P,SUJIT P B. Path Planning for a UAV with Kinematic Constraints in the Presence of Polygonal Obstacles[C]∥International Conference on Unmanned Aircraft Systems. Arlington,VA,USA:IEEE,2016:62-67.
[14]QU Y,ZHANG Y,ZHANG Y. Optimal Flight Path Planning for UAVs in 3-D Threat Environment[C]∥International Conference on Unmanned Aircraft Systems. Orlando,FL,USA:IEEE,2014:149-155.
[15]CHEN X,ZHANG J. The Three-Dimension Path Planning of UAV Based on Improved Artificial Potential Field in Dynamic Environment[C]∥International Conference on Intelligent Human-Machine Systems and Cybernetics. Tlemcen,Algeria:IEEE,2013:144-147.
[16]王强,张安,吴忠杰.改进人工势场法与模拟退火算法的无人机航路规划[J].火力与指挥控制,2014(8):70-73.WANG Qiang,ZHANG An,WU Zhongjie. UAV Route Planning Based on Improved Artificial Potential Field Method and Simulated Annealing Algorithm[J]. Fire Control&Command Control,2014(8):70-73.
[17]姚远,周兴社,张凯龙,等.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用,2010,27(7):953-959.YAO Yuan,ZHOU Xingshe,ZHANG Kailong,et al. Dynamic Path Planning of Unmanned Aerial Vehicles Based on Sparse A*Search and Improved Artificial Potential Fields[J]. Control Theory and Applications,2010,27(7):953-959.
[18]王伟,王华.基于约束人工势场法的弹载飞行器实时避障航迹规划[J].航空动力学报,2014,29(7):1738-1743.WANG Wei,WANG Hua. Real-Time Obstacle Avoidance Path Planning of Missile-Borne Vehicle Based on Constrained Artificial Potential Field Method[J]. Journal of Aerospace Power,2014,29(7):1738-1743.
[19]罗冠辰,于剑桥,张思宇,等.穿越恶劣天气区域的无人机航迹规划[J].北京理工大学学报,2014,34(10):1054-1059.LUO Guanchen,YU Jianqiao,ZHANG Siyu,et al. Drone Path Planning through Bad Weather Areas[J]. Transaction of Beijing Institute of Technology,2014,34(10):1054-1059.
[20]BEHNCK L P,DOERING D,PEREIRA C E,et al. A Modified Simulated Annealing Algorithm for SUAVs Path Planning[J]. IFAC Papersonline,2015,48(10):63-68.
[21]邱福生,杨建平,邵绪威.基于遗传模拟退火算法的无人机航迹规划[J].沈阳航空航天大学学报,2014,31(1):16-19.QIU Fusheng,YANG Jianping,SHAO Xuwei. Flight Path Planning of UAV Based on Genetic Simulated Annealing Algorithm[J]. Journal of Shenyang Institute of Aeronautical Engineering,2014,31(1):16-19.
[22]占伟伟,王伟,陈能成,等.一种利用改进A*算法的无人机航迹规划[J].武汉大学学报:信息科学版,2015,40(3):315-320.ZHAN Weiwei,WANG Wei,CHEN Nengcheng,et al. UAV Track Planning Using Improved A*Algorithm[J]. Geomatics and Information Science of Wuhan University,2015,40(3):315-320.
[23]杨润洲,丁勇,张承果.基于DTW的改进A*算法在航迹规划中的应用[J].电光与控制,2016,23(6):5-10.YANG Runzhou,DING Yong,ZHANG Chengguo. Application of Improved A*Algorithm Based on DTW in Track Planning[J]. Electro-optics and Control,2016,23(6):5-10.
[24]鱼佳欣,李刚,李东涛,等.改进量子遗传算法在无人机航迹规划中的应用[J].计算机仿真,2015,32(5):106-109.YU Jiaxin,LI Gang,LI Dongtao,et al. Application of Improved Quantum Genetic Algorithm in UAV Flight Path Planning[J]. Computer Simulation,2015,32(5):106-109.
[25]HAMED S,MOJTABA V,BABAK I,et al. Optimal Cooperative Path Planning of Unmanned Aerial Vehicles by a Parallel Genetic Algorithm[J]. Robotica,2016,34(4):823-836.
[26]俞琪,刘新,周成平,等.基于病毒遗传算法的快速航迹规划方法[J].宇航学报,2011,32(4):756-761.YU Qi,LIU Xin,ZHOU Chengping,et al. Fast Track Planning Method Based on Virus Genetic Algorithm[J]. Journal of Astronautics,2011,32(4):756-761.
[27]PEHLIVANOGLU Y V. A New Vibrational Genetic Algorithm Enhanced with a Voronoi Diagram for Path Planning of Autonomous UAV[J]. Aerospace Science&Technology,2012,16(1):47-55.
[28]DUAN H,YU Y,ZHANG X,et al. Three-Dimension Path Planning for UCAV Using Hybrid Meta-Heuristic ACO-DE Algorithm[J]. Simulation Modelling Practice&Theory,2010,18(8):1104-1115.
[29]刘振峰,谢洪森,危水根.基于文化蚁群算法的三维飞行器航路规划[J].计算机仿真,2013,30(5):99-103.LIU Zhenfeng,XIE Hongsen,WEI Shuigen. Route Planning of 3D Aircraft Based on Cultural Ant Colony Algorithm[J].Computer Simulation,2013,30(5):99-103.
[30]TAO J,WANG Y,YANG H,et al. Three-Dimensional Path Planning of Unmanned Aerial Vehicle under Complicated Environment[C]∥Control and Decision Conference. Big Sky,MT,USA:IEEE,2016:6377-6382.
[31]傅阳光,周成平,丁明跃.基于混合量子粒子群优化算法的三维航迹规划[J].宇航学报,2010,31(12):2657-2664.FU Yangguang,ZHOU Chengping,DING Mingyue. Three-Dimensional Path Planning Based on Hybrid Quantum Particle Swarm Optimization Algorithm[J]. Journal of Astronautics,2010,31(12):2657-2664.
[32]吴天爱,吴云玉,别晓峰.采用病毒粒子群优化算法的飞行器航迹规划[J].电光与控制,2014,21(8):102-105.WU Tianai,WU Yunyu,BIE Xiaofeng. Aircraft Path Planning Using Virus Particle Swarm Optimization Algorithm[J].Electro-optics and Control,2014,21(8):102-105.
[33]LIU Y,ZHAN G X,GUAN X,et al. Potential Odor Intensity Grid Based UAV Path Planning Algorithm with Particle Swarm Optimization Approach[J]. Mathematical Problems in Engineering,2016,2016(2):1-16.
[34]杨祖强.生物启发的多无人机协同四维航迹规划方法研究[D].杭州:浙江大学航空航天学院,2016.YANG Zuqiang. Bio-inspired 4D Trajectory Generation for Multi-UAV Cooperation[D]. Hangzhou:School of Aeronautics and Astronautics,Zhejiang University,2016.