An efficient hybrid algorithm strategy for UAV obstacle avoidance and path planning
-
摘要: 现有路径规划算法中存在搜索类A*算法高度依赖网格地图、高分辨率下计算内存开销大和采样类RRT算法、RRT*算法搜索效率低、路径规划时间长等问题，提出了一种无人机避障路径混合算法。首先，根据A*算法对网格地图的依赖性提出了全方向可选择性的路径搜索策略；其次，根据采样类算法的强随机性和低搜索效率，提出了全局最佳路径搜索方向以及高效节点选取方式；在障碍物附近采用沿墙算法的思路，避免陷入局部最小值的同时进一步缩短路径规划的运行时间。仿真结果表明：在不同复杂度的障碍物环境中，混合算法相较于传统的A*算法、RRT算法和RRT*算法在路径规划时间方面均缩短96%以上、生成路径长度有不同程度的减少以及平均迭代次数均减少98%以上。因此该算法能够显著提升路径规划的效率，为无人机避障高效自主路径规划提供有力的支撑。Abstract:
Background Among the existing path planning algorithms, the search-based A* algorithm is highly dependent on grid maps and incurs large computational memory overhead at high resolutions. Meanwhile, the sampling-based RRT algorithm and RRT* algorithm suffer from low search efficiency and long path planning time.Purpose Aiming at the shortcomings of existing algorithms and the requirement for real-time path planning, a brand-new hybrid algorithm strategy is proposed.Methods Firstly, based on the A* algorithm’s dependence on grid maps, an omnidirectional optional path search perspective is put forward. Secondly, in view of the strong randomness and low search efficiency of sampling-based algorithms, a global optimal path search direction and a new efficient node selection method are proposed. Near obstacles, the idea of a simple and convenient wall-following algorithm is adopted to avoid falling into local minima while further shortening the running time of path planning.Results Simulation results show that in obstacle environments of different complexities, compared with the traditional A* algorithm, RRT algorithm, and RRT* algorithm, the new hybrid algorithm reduces the path planning time by more than 96%, shortens the generated path length to varying degrees, and decreases the average number of iterations by more than 98%.Conclusions The Mixed algorithm demonstrates excellent adaptability in three typical environments: it can rapidly generate near-optimal paths in open and regular environments; it also achieves high planning efficiency in cluttered but wide-passage environments; and it can efficiently find short paths even in challenging environments with narrow passages. Comparisons with the A*, RRT, and RRT* algorithms further verify that the Mixed algorithm performs outstandingly in terms of both path quality and search efficiency.Therefore, this algorithm can significantly improve the efficiency of path planning and provide strong support for the efficient autonomous path planning of UAV obstacle avoidance.-
Key words:
- path planning /
- hybrid algorithm /
- obstacle avoidance
-
图 2 路径规划实际可运动方向示意图
Figure 2. Schematic diagram of actual movable directions for path planning
图 5 环境a中不同算法的仿真结果图
Figure 5. Simulation result diagrams of different algorithms in environment a
图 6 环境a中不同算法的仿真结果图
Figure 6. Simulation result diagrams of different algorithms in environment b
图 7 环境c中不同算法的仿真结果图
Figure 7. Simulation result diagrams of different algorithms in environment c
表 1 环境a中的仿真数据
Table 1. Simulation data in environment a
algorithm search time/s path length/pixel average number of iterations A* 27.610 714.555 43 294 RRT 1.144 886.891 494 RRT* 88.282 779.150 12 000 mixed 0.04 687.750 8 
下载: 导出CSV
表 2 环境b中的仿真数据
Table 2. Simulation data in environment b
algorithm search time/s path length/pixel average number of iterations A* 108.856 998.950 118 335 RRT 4.985 1328.343 2 585 RRT* 51.332 1149.777 12 000 mixed 0.109 1113.60 27
下载: 导出CSV
表 3 环境c中的仿真数据
Table 3. Simulation data in environment c
algorithm search time/s path length/pixel average number of iterations A* 91.237 886.777 107 907 RRT 8.222 1383.177 4304 RRT* 47.080 1027.518 12 000 mixed 0.255 931.14 40
下载: 导出CSV
-
[1] 刘清云, 游雄, 张欣, 等. 移动机器人路径规划算法综述[J]. 计算机科学, 2025, 52: 240900074 doi: 10.3778/j.issn.1002-8331.2507-0291Liu Qingyun, You Xiong, Zhang Xin, et al. Review of path planning algorithms for mobile robots[J]. Computer Science, 2025, 52: 240900074 doi: 10.3778/j.issn.1002-8331.2507-0291 [2] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910Zhao Xiao, Wang Zheng, Huang Chengkan, et al. Mobile robot path planning based on an improved A* algorithm[J]. ROBOT, 2018, 40(6): 903-910 [3] 郭建, 杨朋, 曾志豪, 等. 融合改进Dijkstra算法和动态窗口法的移动机器人路径规划[J]. 组合机床与自动化加工技术, 2024(3): 36-40Guo Jian, Yang Peng, Zeng Zhihao, et al. Mobile robot path planning based on improved Dijkstra algorithm and dynamic window method[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2024(3): 36-40 [4] 刘冲, 刘本学, 吕桉, 等. 基于改进RRT算法的室内移动机器人路径规划[J]. 组合机床与自动化加工技术, 2023(10): 20-23,29 doi: 10.13462/j.cnki.mmtamt.2025.06.010Liu Chong, Liu Benxue, Lü An, et al. Path planning of indoor mobile robot based on improved RRT algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2023(10): 20-23,29 doi: 10.13462/j.cnki.mmtamt.2025.06.010 [5] 邓冬冬, 许建民, 孟寒, 等. 基于蚁群算法与人工势场法融合的移动机器人路径规划[J]. 仪器仪表学报, 2025, 46(2): 1-16Deng Dongdong, Xu Jianmin, Meng Han, et al. Mobile robot path planning based on the fusion of ant colony algorithm and artificial potential field method[J]. Chinese Journal of Scientific Instrument, 2025, 46(2): 1-16 [6] 许云鹏. 基于深度学习的无人机多场景感知与路径规划技术研究[D]. 北京: 北京邮电大学, 2024Xu Yunpeng. Research on multi-scene perception and path planning for unmanned aerial vehicles based on deep learning[D]. Beijing: Beijing University of Posts and Telecommunications, 2024 [7] 李晓露, 熊禾根, 陶永, 等. 基于改进A*算法的移动机器人全局最优路径规划[J]. 高技术通讯, 2021, 31(3): 306-314 doi: 10.3772/j.issn.1002-0470.2021.03.011Li Xiaolu, Xiong Hegen, Tao Yong, et al. Global optimal path planning for mobile robots based on improved A* algorithm[J]. Chinese High Technology Letters, 2021, 31(3): 306-314 doi: 10.3772/j.issn.1002-0470.2021.03.011 [8] 陈秋莲, 蒋环宇, 郑以君. 机器人路径规划的快速扩展随机树算法综述[J]. 计算机工程与应用, 2019, 55(16): 10-17 doi: 10.3778/j.issn.1002-8331.1905-0061Chen Qiulian, Jiang Huanyu, Zheng Yijun. Summary of rapidly-exploring random tree algorithm in robot path planning[J]. Computer Engineering and Applications, 2019, 55(16): 10-17 doi: 10.3778/j.issn.1002-8331.1905-0061 [9] 丁建军, 梁甲杭, 胡志明, 等. 多向人工势场法引导的RRT-Connect路径规划算法研究[J/OL]. 机电工程, 2025: 1-15. (2025-09-22)[2025-09-17]. https://link.cnki.net/urlid/33.1088.th.20250825.1034.007.Ding Jianjun, Liang Jiahang, Hu Zhiming, et al. RRT-connect path planning algorithm guided by multi-directional artificial potential field[J/OL]. Journal of Mechanical & Electrical Engineering, 2025: 1-15. (2025-09-22)[2025-09-17]. https://link.cnki.net/urlid/33.1088.th.20250825.1034.007 [10] Liu Z R, Jiang S H. Review of mobile robot path planning based on reinforcement learning[J]. Manufacturing Automation, 2019, 41(3): 90-92. [11] 黄友锐, 朱忠涛, 韩涛. SN-BI-RRT*: 基于动态梯度和人工势场的双向探索随机树算法[J/OL]. 计算机工程与应用, 2025: 1-24. (2025-08-14). https://link.cnki.net/urlid/11.2127.tp.20250814.1349.012.Huang Yourui, Zhu Zhongtao, Han Tao. SN-BI-RRT*: a bi-directional exploratory randomized tree algorithm based on dynamic gradient and artificial potential field[J/OL]. Computer Engineering and Applications, 2025: 1-24. (2025-08-14). https://link.cnki.net/urlid/11.2127.tp.20250814.1349.012 [12] 王洋. 基于动态五邻域搜索的改进Astar算法路径规划研究[J]. 中国新技术新产品, 2024(7): 1-4Wang Yang. Research on path planning of improved Astar algorithm based on dynamic five-neighborhood search[J]. New Technology & New Products of China, 2024(7): 1-4 [13] 姚千, 杨洁. 改进A*算法在三维空间中无人机的航迹规划[J]. 传感器与微系统, 2025, 44(3): 143-147,151 doi: 10.13873/J.1000-9787(2025)03-0143-05Yao Qian, Yang Jie. Improved A* algorithm for UAV trajectory planning in 3D space[J]. Transducer and Microsystem Technologies, 2025, 44(3): 143-147,151 doi: 10.13873/J.1000-9787(2025)03-0143-05 [14] 查峰, 肖世德, 冯刘中, 等. 移动机器鼠沿墙导航策略与算法研究[J]. 计算机工程, 2012, 38(6): 172-174 doi: 10.3969/j.issn.1000-3428.2012.06.056Zha Feng, Xiao Shide, Feng Liuzhong, et al. Research on wall-following navigation strategy and algorithm for mobile mechanical mouse[J]. Computer Engineering, 2012, 38(6): 172-174 doi: 10.3969/j.issn.1000-3428.2012.06.056 [15] 王栋耀, 马旭东, 戴先中. 基于声纳的移动机器人沿墙导航控制[J]. 机器人, 2004, 26(4): 346-350,356 doi: 10.3321/j.issn:1002-0446.2004.04.012Wang Dongyao, Ma Xudong, Dai Xianzhong. Wall following navigation control for a sonar based mobile robot[J]. ROBOT, 2004, 26(4): 346-350,356 doi: 10.3321/j.issn:1002-0446.2004.04.012 [16] 华亮, 冯浩, 顾菊平, 等. 基于单超声波传感器的移动机器人沿墙导航策略[J]. 工程设计学报, 2008, 15(3): 206-212 doi: 10.3785/j.issn.1006-754X.2008.03.011Hua Liang, Feng Hao, Gu Juping, et al. Wall following navigation strategy for mobile robot using single ultrasonic sensor[J]. Journal of Engineering Design, 2008, 15(3): 206-212 doi: 10.3785/j.issn.1006-754X.2008.03.011 -
点击查看大图
图(7) / 表(3)
计量
- 文章访问数: 19
- HTML全文浏览量: 9
- PDF下载量: 3
- 被引次数: 0
