基于改进双向A~*和向量场直方图算法的无人机航路规划
|
摘要
现代无人机的行驶环境复杂多变,对无人机的航路规划不仅要求路径最短,同时还要满足实时性以应对突发威胁。提出一种离线规划和在线避障结合的航路规划方法。首先利用改进的双向A*算法对已知环境进行离线规划;并提出基于碰撞检测的动态步长和双向去除冗余点方法。在不影响路径精度的同时,缩短离线规划时间和路径。在无人机按照离线路径行驶过程中,当规划路径中出现突发威胁,利用VFH算法进行实时避障;对避障算法设置子目标,使无人机完成避障后能迅速回到离线轨迹,不影响全局路径的最优性。仿真实验表明;所提方法规划的路径长度短、耗时少;并能有效避开突发威胁,充分结合了双向A*算法路径最优和VFH算法的快速实时避障性的优点。
Modern driving environment for unmanned aerial vehicle( UAV) is complicated and changeable,the path of UAV not only requires the shortest length,but also needs to be real-time in response to sudden threat.A kind of path planning method including off-line path planning and online obstacle avoidance was put forward.Firstly,an improved bidirectional A*algorithm was used to plan the path for the known environment,and the methods of dynamic step based on collision detection and removing the redundant point were put forward,which can shorten the planning time and path length without affecting the precision of path planning. While driving,if UAV finds new threats on the off-line,using vector field histogram( VFH) algorithm for real-time obstacle avoidance; and sub-goals for obstacle avoidance algorithm are set,to ensure UAV returned to the offline path quickly after completing obstacle avoidance,so that the optimality of the global path will not be affected. The simulation results show that the proposed method can plan a shorter path with less time,and can effectively avoid sudden threat,fully combines the the optimal-path of bidirectional A*algorithm and the advantages of rapid real-time obstacle avoidance of VFH algorithm.
Modern driving environment for unmanned aerial vehicle( UAV) is complicated and changeable,the path of UAV not only requires the shortest length,but also needs to be real-time in response to sudden threat.A kind of path planning method including off-line path planning and online obstacle avoidance was put forward.Firstly,an improved bidirectional A*algorithm was used to plan the path for the known environment,and the methods of dynamic step based on collision detection and removing the redundant point were put forward,which can shorten the planning time and path length without affecting the precision of path planning. While driving,if UAV finds new threats on the off-line,using vector field histogram( VFH) algorithm for real-time obstacle avoidance; and sub-goals for obstacle avoidance algorithm are set,to ensure UAV returned to the offline path quickly after completing obstacle avoidance,so that the optimality of the global path will not be affected. The simulation results show that the proposed method can plan a shorter path with less time,and can effectively avoid sudden threat,fully combines the the optimal-path of bidirectional A*algorithm and the advantages of rapid real-time obstacle avoidance of VFH algorithm.
引文
1邬琦,潘广贞,杨江涛.基于Voronoi图和动态自适应蚁群算法的UAV航迹规划[J].计算机测量与控制,2014,22(9):3037-3040Wu Qi,Pan Guangzhen,Yang Jiangtao. Route planning of UAV based on Voronoi diagram and dynamic and adaptive ant colony algorithm[J]. Computer Measurement and Control,2014,22(9):3037-3040
2 Makariye N. Towards shortest path computation using Dijkstra algorithm[C]//2017 International Conference on Io T and Application.New York:IEEE,2017:1-3
3 Pal A,Tiwari R,Shukla A. Modified A*algorithm for mobile robot path planning[M]. Berlin:Springer Berlin Heidelberg,2012:183-193
4 Loong W Y,Long L Z,Hun L C. A star path following mobile robot[C]//International Conference on Mechatronics. New York:IEEE,2011:1-7
5 尹高扬,周绍磊,吴青坡.基于改进RRT算法的无人机航迹规划[J].电子学报,2017,45(7):1764-1769Yin Gaoyang,Zhou Shaolei,Wu Qingpo. An improved RRT algorithm for UAV path planning[J]. Acta Electronica Sinica,2017,45(7):1764-1769
6 陈侠,李光耀.基于改进进化算法的无人机航迹规划[J].科学技术与工程,2018,18(3):79-84Chen Xia,Li Guangyao. Path planning for unmanned aerial vehicles using improved evolutionary algorithm[J]. Science Technology and Engineering,2018,18(3):79-84
7 Roberge V,Tarbouchi M,Labonte G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE Transactions on Industrial Informatics,2013,9(1):132-141
8 崔舒婷,赵成萍,周新志,等.基于马尔科夫生存模型与粒子群算法的动态航路规划[J].四川大学学报(自然科学版)2018,55(3):501-506Cui Shuting,Zhao Chengping,Zhou Xinzhi,et al. Online route planning based on Markov survival model and PSO algorithm[J].Journal of Sichuan University(Natural Science Edition),2018,55(3):501-506
9 Stentz A. The focused D*algorithm for real-time replanning[C]//International Joint Conference on Artificial Intelligence. San Francisco:Morgan Kaufmann Publishers Inc,1995:1652-1659
10 Borenstein J,Koren Y. The vector field histogram-fast obstacle avoidance for mobile robots[J]. IEEE Transactions on Robotics and Automation,1991,7(3):278-288
11 Ulrich I,Borenstein J. VFH*:Local obstacle avoidance with lookahead verification[C]//IEEE International Conference on Robotics and Automation. New York:IEEE,2002:2505-2511
12 杨丽春,顾颖彦,白宇.基于改进人工势场法的无人机在线航路规划算法[J].电子技术应用,2018,44(4):5-9Yang Lichun,Gu Yinyan,Bai Yu. UAV's online route planning algorithm based on improved artificial potential field[J]. Application of Electronic Technique,2018,44(4):5-9
13 黄文刚,张怡,姜文毅,等.变步长稀疏A*算法的无人机航路规划[J].计算机工程与应用,2012,48(29):206-209Huang Wengang,Zhang Yi,Jiang Wenyi,et al. SAS algorithm with changeable steps for route planning of UAVs[J]. Computer Engineering and Applications,2012,48(29):206-209
2 Makariye N. Towards shortest path computation using Dijkstra algorithm[C]//2017 International Conference on Io T and Application.New York:IEEE,2017:1-3
3 Pal A,Tiwari R,Shukla A. Modified A*algorithm for mobile robot path planning[M]. Berlin:Springer Berlin Heidelberg,2012:183-193
4 Loong W Y,Long L Z,Hun L C. A star path following mobile robot[C]//International Conference on Mechatronics. New York:IEEE,2011:1-7
5 尹高扬,周绍磊,吴青坡.基于改进RRT算法的无人机航迹规划[J].电子学报,2017,45(7):1764-1769Yin Gaoyang,Zhou Shaolei,Wu Qingpo. An improved RRT algorithm for UAV path planning[J]. Acta Electronica Sinica,2017,45(7):1764-1769
6 陈侠,李光耀.基于改进进化算法的无人机航迹规划[J].科学技术与工程,2018,18(3):79-84Chen Xia,Li Guangyao. Path planning for unmanned aerial vehicles using improved evolutionary algorithm[J]. Science Technology and Engineering,2018,18(3):79-84
7 Roberge V,Tarbouchi M,Labonte G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE Transactions on Industrial Informatics,2013,9(1):132-141
8 崔舒婷,赵成萍,周新志,等.基于马尔科夫生存模型与粒子群算法的动态航路规划[J].四川大学学报(自然科学版)2018,55(3):501-506Cui Shuting,Zhao Chengping,Zhou Xinzhi,et al. Online route planning based on Markov survival model and PSO algorithm[J].Journal of Sichuan University(Natural Science Edition),2018,55(3):501-506
9 Stentz A. The focused D*algorithm for real-time replanning[C]//International Joint Conference on Artificial Intelligence. San Francisco:Morgan Kaufmann Publishers Inc,1995:1652-1659
10 Borenstein J,Koren Y. The vector field histogram-fast obstacle avoidance for mobile robots[J]. IEEE Transactions on Robotics and Automation,1991,7(3):278-288
11 Ulrich I,Borenstein J. VFH*:Local obstacle avoidance with lookahead verification[C]//IEEE International Conference on Robotics and Automation. New York:IEEE,2002:2505-2511
12 杨丽春,顾颖彦,白宇.基于改进人工势场法的无人机在线航路规划算法[J].电子技术应用,2018,44(4):5-9Yang Lichun,Gu Yinyan,Bai Yu. UAV's online route planning algorithm based on improved artificial potential field[J]. Application of Electronic Technique,2018,44(4):5-9
13 黄文刚,张怡,姜文毅,等.变步长稀疏A*算法的无人机航路规划[J].计算机工程与应用,2012,48(29):206-209Huang Wengang,Zhang Yi,Jiang Wenyi,et al. SAS algorithm with changeable steps for route planning of UAVs[J]. Computer Engineering and Applications,2012,48(29):206-209