改进速度障碍法的无人机局部路径规划算法

doi:10.7527/S1000-6893.2022.27586

Abstract

Abstract:

To solve the real-time and safety problems in UAV local path replanning based on environment awareness， a local path avoidance planning algorithm is proposed based on the improved velocity obstacle method. The traditional velocity obstacle method is extended to the three-dimensional space， and a three-dimensional spatial velocity obstacle model is established to transform the motion uncertainty of maneuvering dynamic obstacles in the velocity space into position uncertainty， with better real-time performance and improved obstacle avoidance level and safety margin. By defining and introducing adaptive threat distance， the utilization rate of the original trajectory of the UAV in the obstacle avoidance process is improved. The optimal speed of spatial autonomous obstacle avoidance is solved using spatial geometric analysis， and dynamic real-time planning of local paths is achieved. The timeliness， feasibility and effectiveness of the algorithm are verified by comparing the simulation results of local path obstacle avoidance planning under three scenarios： encounter， pursuit and crossover.

Key words: path planning, velocity obstacle method, maneuvering obstacle, adaptive threat distance, autonomous obstacle avoidance, optimal velocity

CLC Number:

V249.122+.6

Hua GUO, Xiaohe GUO. Local path planning algorithm for UAV based on improved velocity obstacle method[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(11): 327586-327586.

Figures/Tables 18

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Obstacle initial condition parameters

场景	障碍物起点/m	偏航角/（°）	俯仰角/（°）	速度大小/（ $m ⋅ s - 1$ ）
1	（1 000，800，200）	230	-8.87	12
2	（447，358，89）	51.34	8.88	5
3	（400，600，116）	180	0	12

Table 1

Table 2

Table 3

Fig.8

Fig.9

Fig.10

Table 4

Relevant parameters of UAV obstacle avoidance process considering obstacle maneuverability but not threat distance m

场景	$d s a f e$	UAV飞行状态改变点	半径	最近距离
1	150.13	（462.91，370.38，92.58）	50.09	52.97
2	88.52	（308.61，246.89，61.72）	48.87	49.87
3	137.78	（200.59，160.48，40.12）	50.09	66.55

Table 4

Fig.11

Table 5

Table 6

Table 7

References 24

1	CHEN Y B， LUO G C， MEI Y S， et al. UAV path planning using artificial potential field method updated by optimal control theory［J］. International Journal of Systems Science， 2016， 47（6）： 1407-1420.
2	彭闪，殷苑，田峰，等. 无人机航迹规划算法综述［J］. 数字技术与应用， 2022， 40（4）： 77-79.
	PENG S， YIN Y， TIAN F， et al. Overview of UAV path planning algorithms［J］. Digital Technology & Application， 2022， 40（4）： 77-79 （in Chinese）.
3	徐文钰，敖海跃，刘燕斌. 基于鸽群优化算法的多无人机局部航迹重规划［J］. 战术导弹技术， 2022（1）： 46-52.
	XU W Y， AO H Y， LIU Y B. Local path re-planning of multi-UAVs based on pigeon-inspired optimization［J］. Tactical Missile Technology， 2022（1）： 46-52 （in Chinese）.
4	张宏宏，甘旭升，毛亿，等. 无人机避障算法综述［J］. 航空兵器， 2021， 28（5）： 53-63.
	ZHANG H H， GAN X S， MAO Y， et al. Review of UAV obstacle avoidance algorithms［J］. Aero Weaponry， 2021， 28（5）： 53-63 （in Chinese）.
5	刘祥，叶晓明，王泉斌，等. 无人水面艇局部路径规划算法研究综述［J］. 中国舰船研究， 2021， 16（S1）： 1-10.
	LIU X， YE X M， WANG Q B， et al. Review on the research of local path planning algorithms for unmanned surface vehicles［J］. Chinese Journal of Ship Research， 2021， 16（S1）： 1-10 （in Chinese）.
6	JIN Z， YAN B， YE R. The flight navigation planning based on potential field ant colony algorithm［C］∥Proceedings of the 2018 International Conference on Advanced Control， Automation and Artificial Intelligence （ACAAI 2018）. Paris： Atlantis Press， 2018： 200-204.
7	李二超，王玉华. 改进人工势场法的移动机器人避障轨迹研究［J］. 计算机工程与应用， 2022， 58（6）： 296-304.
	LI E C， WANG Y H. Research on obstacle avoidance trajectory of mobile robot based on improved artificial potential field［J］. Computer Engineering and Applications， 2022， 58（6）： 296-304 （in Chinese）.
8	张建英，刘暾. 基于人工势场法的移动机器人最优路径规划［J］. 航空学报， 2007， 28（S1）： 183-188.
	ZHANG J Y， LIU T. Optimized path planning of mobile robot based on artificial potential field［J］. Acta Aeronautica et Astronautica Sinica， 2007， 28（S1）： 183-188 （in Chinese）.
9	魏瑞轩，周凯. 面向位置环境的无人机障碍规避制导率设计［J］. 系统工程与电子技术， 2015， 25（9）： 2096-2101.
	WEI R X， ZHOU K. Design of UAV Obstacle avoidance guidance rate oriented to location environment［J］. Systems Engineering and Electronic Technology， 2015， 25（9）： 2096-2101 （in Chinese）.
10	宋宇，王志明. 面向无人机三维航迹规划的改进粒子群优化算法［J］. 传感器与微系统， 2019， 38（3）： 144-146.
	SONG Y， WANG Z M. Improved PSO algorithm for UAV 3D track planning［J］. Transducer and Microsystem Technologies， 2019， 38（3）： 144-146 （in Chinese）.
11	黄书召，田军委，乔路，等. 基于改进遗传算法的无人机路径规划［J］. 计算机应用， 2021， 41（2）： 390-397.
	HUANG S Z， TIAN J W， QIAO L， et al. Unmanned aerial vehicle path planning based on improved genetic algorithm［J］. Journal of Computer Applications， 2021， 41（2）： 390-397 （in Chinese）.
12	徐鹏. 基于模拟退火算法的机器人路径规划与研究［J］. 科技广场， 2011（1）： 42-44.
	XU P. Planning and research of robot path based on simulated annealing path［J］. Science Mosaic， 2011（1）： 42-44 （in Chinese）.
13	FIORINI P， SHILLER Z. Motion planning in dynamic environments using the relative velocity paradigm［C］∥ Proceedings IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2002： 560-565.
14	黄永龙，仲训昱. 基于改进速度障碍法的多机器人避碰规划算法［J］. 计算机工程与应用， 2012， 48（32）： 47-51， 207.
	HUANG Y L， ZHONG X Y. Improved velocity obstacles-based collision avoidance algorithm for multiple mobile robots［J］. Computer Engineering and Applications， 2012， 48（32）： 47-51， 207 （in Chinese）.
15	DURAND N， BARNIER N. Does ATM need centralized coordination？ Autonomous conflict resolution analysis in a constrained speed environment［J］. Air Traffic Control Quarterly， 2015， 23（4）： 325-346.
16	HAN S C， BANG H， YOO C S. Proportional navigation-based collision avoidance for UAVs［J］.International Journal of Control， Automation and Systems， 2009， 7（4）： 553-565.
17	王泽坤，吴明功，温祥西. 基于速度障碍法的飞行冲突解脱与恢复策略［J］. 北京航空航天大学， 2019， 45（7）： 1294-1302.
	WANG Z K， WU M G， WEN X X. Flight conflict relief and recovery strategy based on speed obstacle method ［J］. Journal of Beijing University of Aeronautics and Astronautics， 2019， 45（7）： 1294-1302 （in Chinese）.
18	张宏宏，甘旭升，李昂，等. 基于速度障碍法的无人机避障与航迹恢复策略［J］. 系统工程与电子技术， 2020， 42（8）： 1759-1767.
	ZHANG H H， GAN X S， LI A， et al. UAV obstacle avoidance and track recovery strategy based on velocity obstacle method［J］. Systems Engineering and Electronics， 2020， 42（8）： 1759-1767 （in Chinese）.
19	杨秀霞，华伟，孟启源. 基于有限时间速度障碍法的UAV避障研究［J］. 弹箭与制导学报， 2018， 38（5）： 19-22， 26.
	YANG X X， HUA W， MENG Q Y. Study on UAV obstacle avoidance based on finite time velocity obstruction method［J］. Journal of Projectiles， Rockets， Missiles and Guidance， 2018， 38（5）： 19-22， 26 （in Chinese）.
20	许文瑶，贺继林. 基于改进速度障碍法的水下机器人动态避障［J］. 电光与控制， 2021， 28（12）： 86-90.
	XU W Y， HE J L. Dynamic obstacle avoidance for ROV based on improved velocity obstacle method［J］. Electronics Optics & Control， 2021， 28（12）： 86-90 （in Chinese）.
21	杨秀霞，周硙硙，张毅. 三维动态不确定UAV自主避障算法［J］. 电光与控制， 2017， 24（9）： 1-5.
	YANG X X， ZHOU W W， ZHANG Y. A 3-D dynamic autonomous obstacle avoidance algorithm for UAVs［J］. Electronics Optics & Control， 2017， 24（9）： 1-5 （in Chinese）.
22	SNAPE J， VAN DEN BERG J， GUY S J， et al. The hybrid reciprocal velocity obstacle［J］. IEEE Transactions on Robotics， 2011， 27（4）： 696-706.
23	CHAKRAVARTHY A， GHOSE D. Generalization of the collision cone approach for motion safety in 3-D environments［J］. Autonomous Robots， 2012， 32（3）： 243-266.
24	杨健. 无人机集群系统空域冲突消解方法研究［D］. 长沙：国防科学技术大学， 2016： 11-16.
	YANG J. Study on the airspace conflict resolution problem of unmanned aerial vehicle swarm systems［D］. Changsha： National University of Defense Technology， 2016： 11-16 （in Chinese）.

场景	UAV飞行状态改变点/m	期望偏航角/（°）	期望俯仰角/（°）	半径/m
1	（339.47，271.57，67.89）	44.03	7.37	50.09
2	（15.43，12.34，3.09）	54.18	13.16	48.87
3	（77.15，61.72，15.43）	44.91	8.99	50.09

场景	UAV飞行状态改变点	期望偏航角/（°）	期望俯仰角/（°）	半径/m
1	（339.47，271.57，67.89）	54.71	6.65	48
2	（15.43，12.34，3.09）	51.25	5.97	48
3	（77.15，61.72，15.43）	56.97	9.53	48

算法类型	算法求解耗时/s	飞行解脱耗时/s	解脱耗时占比/%
引入威胁距离	0.008 1	11	16.92
未引入威胁距离	0.008 4	20	30.77

算法类型	算法求解耗时/s	飞行解脱耗时/s	解脱耗时占比/%
引入威胁距离	0.008 5	19	29.23
未引入威胁距离	0.008 5	37	56.92

算法类型	算法求解耗时/s	飞行解脱耗时/s	解脱耗时占比/%
引入威胁距离	0.007 1	13	20.31
未引入威胁距离	0.008 6	21	32.31

Local path planning algorithm for UAV based on improved velocity obstacle method

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 24

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Yong XU, Hongtao YAN, Tao JIA, Yue MA, Zehua DENG, Duoneng LIU. Aerial simulation docking technology of fixed-wing clustering UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(5): 326539-326539.
[2]	XUE Zhentao, CHEN Jian, ZHANG Zichao, LIU Xuzan, MIAO Xiansheng, HU Gui. Multi-UAV coverage path planning based on optimization of convex division of complex plots [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(12): 325990-325990.
[3]	ZHOU Bin, GUO Yan, LI Ning, ZHONG Xijian. Path planning of UAV using guided enhancement Q-learning algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(9): 325109-325109.
[4]	HU Xinting, WU Yu. Risk-based discrete multi-path planning method for UAVs in urban environments [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(6): 324383-324383.
[5]	PANG Lei, CAO Zhiqiang, YU Junzhi. A pedestrian-aware collision-free following approach for mobile robots based on A^* and TEB [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524909-524909.
[6]	ZHAO Huan, JIANG Zongmin, DING Han. Tool path planning for profiling grinding of aero-engine blade edge [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(10): 524318-524318.
[7]	WU Kun, TAN Shaochang. Path planning of UAVs based on improved whale optimization algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724286-724286.
[8]	LI Xianqiang, MA Rong, ZHANG Shen, HOU Yanze, PEI Yifei. Improved design of ant colony algorithm and its application in path planning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724381-724381.
[9]	DAI Jian, XU Fei, CHEN Qifeng. Multi-UAV cooperative search on region division and path planning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S1): 723770-723770.
[10]	LI Anti, LI Chenglong, WU Dingjie, WEI Peng. Collision avoidance decision method for UAVs in random search combined with jump point guidance [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(8): 323726-323726.
[11]	LU Yanmei, ZONG Qun, ZHANG Xiuyun, LU Hanchen, ZHANG Ruilong. Formation reconstruction and virtual simulation verification of swarm UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(4): 323580-323580.
[12]	KAN Ping, JIANG Zhaoliang, LIU Yuhao, WANG Zhenwu. Cooperative path planning for multi-sprayer-UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(4): 323610-323610.
[13]	WANG Zhiwei, LIN Xiaojun, SHI Yaoyao, GAO Yuan, ZHANG Yun. A polishing path planning method for blisk with abrasive cloth wheel based on compression deviation constraint [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(2): 623330-623330.
[14]	WANG Jing, LUO Ming, ZHANG Dinghua, CHEN Bing. Simultaneous optimization method for tool contour design and path planning of freeform surface flank milling [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(11): 423720-423720.
[15]	SONG Guilin, WANG Xianfeng, ZHAO Cong, GAO Tiancheng, XUE Ke. Fiber placement trajectory planning and tows increase or decrease algorithm for revolution body [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(11): 423704-423704.