基于改进A*算法的机器人不平坦地形全局路径规划

doi:10.3778/j.issn.1002-8331.2405-0318

摘要/Abstract

摘要： 针对机器人在非结构化和不平整地形的路径规划问题，提出了一种基于改进A*算法的全局路径规划方法。改进A*算法引入双向搜索策略以提高算法计算速度。通过路径节点过滤克服了双向搜索策略带来的问题并减少了关键节点的数量，增加坡度约束降低了机器人的爬坡角度和侧倾角度，提高了规划路径的安全性，通过Bézier曲线拟合路径使其变得光滑，更有利于机器人的运动控制。在不同地形和障碍密度的高程图上进行实验，验证了改进的有效性。实验结果表明，与传统A*算法相比，改进A*算法在路径长度增加14.6%至37.84%的情况下，计算时间减少了71.05%至82.90%，关键节点数量减少了51.94%至70.53%，并且爬坡角度和侧倾角度显著减少，路径更加平滑。因此，该方法在提高效率的同时能够在非结构化和不平坦的地形下生成安全可靠的路径。

关键词: 路径规划, 不平坦地形, 改进A*算法, 移动机器人

Abstract: Addressing the autonomous path planning problem for robots in unstructured and uneven sites, this paper proposes a global path planning method based on an Improved A* algorithm. The Improved A* algorithm first introduces a bidirectional search strategy to speed up computation. It uses path node filtering to overcome issues caused by bidirectional search and to reduce the number of critical nodes. By adding slope constraints, the robot’s climbing and tilting angles are reduced, improving path safety. Paths are smoothed using Bézier curve fitting, aiding robot motion control. The algorithm’s effectiveness is validated through experiments on elevation maps with varying terrain and obstacle densities. Simulation results show that the Improved A* algorithm reduces computation time by 71.05% to 82.90% and the number of critical nodes by 51.94% to 70.53%, while increasing path length by 14.6% to 37.84%. Climbing and tilting angles are significantly reduced, and paths become smoother. Therefore, the proposed method enhances efficiency while generating safe and reliable paths in unstructured and uneven terrains.

Key words: path planning, uneven terrain, Improved A* algorithm, mobile robot

郭聚刚, 于军琪, 冯春勇, 王凯, 陈易圣, 董振平. 基于改进A*算法的机器人不平坦地形全局路径规划[J]. 计算机工程与应用, 2025, 61(5): 309-322.

GUO Jugang, YU Junqi, FENG Chunyong, WANG Kai, CHEN Yisheng, DONG Zhenping. Global Path Planning for Robots on Uneven Terrain Based on Improved A* Algorithm[J]. Computer Engineering and Applications, 2025, 61(5): 309-322.

参考文献

[1] LI C, HUANG X, DING J, et al. Global path planning based on a bidirectional alternating search A* algorithm for mobile robots[J]. Computers & Industrial Engineering, 2022, 168: 108123.
[2] 于军琪, 陈易圣, 冯春勇, 等. 智能建造机器人局部路径规划研究综述[J]. 计算机工程与应用, 2024, 60(10): 16-29.
YU J Q, CHEN Y S, FENG C Y, et al. Review of research on local path planning for intelligent construction robots[J]. Computer Engineering and Applications, 2024, 60(10): 16-29.
[3] 李逸飞, 王书亭, 熊体凡, 等. 兼顾启停特性和转角时耗的移动机器人路径规划[J]. 西安交通大学学报, 2023, 57(2): 192-202.
LI Y F, WANG S T, XIONG T F, et al. Mobile robot path planning considering start-stop characteristics and corner time consumption[J]. Journal of Xi’an Jiaotong University, 2023, 57(2): 192-202.
[4] BANSAL S, TOLANI V, GUPTA S, et al. Combining optimal control and learning for visual navigation in novel envi-ronments[C]//Proceedings of the Conference on Robot Learning, 2020: 420-429.
[5] KALOGEITON V S, IOANNIDIS K, SIRAKOULIS G C, et al. Real-time active SLAM and obstacle avoidance for an autonomous robot based on stereo vision[J]. Cybernetics and Systems, 2019, 50(3): 239-260.
[6] 王秀丽, 周鹏, 侯静楠, 等. 面向变电站机器人巡检路径规划中的算法研究[J]. 计算机工程与应用, 2021, 57(14): 245-250.
WANG X L, ZHOU P, HOU J N, et al. Research on algorithm of inspection path planning for substation robot[J]. Computer Engineering and Applications, 2021, 57(14): 245-250.
[7] 李文峰, 徐蕾, 杨琳琳, 等. 基于改进蚁群算法的农业机器人多田块路径规划方法与试验[J]. 南京农业大学学报南京农业大学学报, 2024, 47(4): 823-834.
LI W F, XU L, YANG L L, et al. Multi field path planning method and experiment of agricultural robot based on improved ant colony algorithm[J]. Journal of Nanjing Agricultural University, 2024, 47(4): 823-834.
[8] 马小康, 白宗文, 杨延宁, 等. 融合灰狼算法和人工势场法的搜救机器人路径规划研究[J]. 制造业自动化, 2024, 46(4): 48-52.
MA X K, BAI Z W, YANG Y N, et al. Research on path planning for search and rescue robots by fusing grey wolf algorithm and artificial potential field method[J]. Manufacturing Automation, 2024, 46(4): 48-52.
[9] 刘进. 轨道交通车辆吹扫机器人智能路径规划研究[J]. 机械制造与自动化, 2024, 53(4): 245-249.
LIU J. Research on intelligent path planning of purging robot for rail vehicle[J]. Machine Building & Automation, 2024, 53(4): 245-249.
[10] KYPRIANOU G, DOITSIDIS L, CHATZICHRISTOFIS S A. Towards the achievement of path planning with multi-robot systems in dynamic environments[J]. Journal of Intelligent & Robotic Systems, 2022, 104(1): 15.
[11] 黄荣杰, 王亚刚. 基于可视图与改进遗传算法的机器人平滑路径规划[J]. 控制工程, 2024, 31(4): 678-686.
HUANG R J, WANG Y G. Smooth path planning for robot based on visibility graph and improved genetic algorithm[J]. Control Engineering of China, 2024, 31(4): 678-686.
[12] ELHOSENY M, THARWAT A, HASSANIEN A E. Bezier curve based path planning in a dynamic field using modified genetic algorithm[J]. Journal of Computational Science, 2018, 25: 339-350.
[13] 孟浩德, 吴征天, 吴闻笛, 等. 基于改进模拟退火算法的灭火小车多目标路径规划[J]. 计算机与数字工程, 2024, 52(2): 394-398.
MENG H D, WU Z T, WU W D, et al. Multi-objective path planning of fire fighting vehicle based on monotone simulated annealing algorithm and A*algorithm [J]. Computer & Digital Engineering, 2024, 52(2): 394-398.
[14] 毛照昉, 王威, 方侃, 等. 基于模拟退火算法的人机协同装配线平衡问题研究[J]. 控制与决策, 2024, 39(10): 3366-3374.
MAO Z F, WANG W, FANG K, et al. Research on the human-robot collaborative assembly line balancing problem based on simulated annealing algorithm[J]. Control and Decision, 2024, 39(10): 3366-3374.
[15] WU L, HUANG X, CUI J, et al. Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot[J]. Expert Systems with Applications, 2023, 215: 119410.
[16] LUO Q, WANG H, ZHENG Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Neural Computing and Applications, 2020, 32: 1555-1566.
[17] MIAO C, CHEN G, YAN C, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230.
[18] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of the International Conference on Neural Networks, 1995: 1942-1948.
[19] 孔鹏飞. 融合爬山策略的改进粒子群混合路径规划算法[J]. 电光与控制, 2024, 31(9): 6-11.
KONG P F. Improved particle swarm hybrid path planning algorithm with mountain climbing strategy[J]. Electronics Optics & Control, 2024, 31(9): 6-11.
[20] LAVALLE S M, KUFFNER J J. Rapidly-exploring random trees: progress and prospects[J]. Algorithmic and Computational Robotics, 2001: 303-307.
[21] 曹园山, 成月, 郑鹏, 等. 基于多约束的改进RRT*算法三维全局路径规划研究[J]. 舰船科学技术, 2024, 46(8): 14-18.
CAO Y S, CHENG Y, ZHENG P, et al. Research on improved RRT* algorithm based on multiple constraints for 3D global path planning[J]. Ship Science and Technology, 2024, 46(8): 14-18.
[22] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 2022, 1: 269-271.
[23] 闫恩雪, 张石强. 基于Dijkstra算法的搬运车省时路径规划研究[J]. 价值工程, 2024, 43(12): 26-29.
YAN E X, ZHANG S Q, Research on time-saving route planning of truck based on dijkstra algorithm[J]. Value Engineering, 2024, 43(12): 26-29.
[24] SáNCHEZ-IBá?EZ J R, PéREZ-DEL-PULGAR C J, GARCíA-CEREZO A. Path planning for autonomous mobile robots: a review[J]. Sensors, 2021, 21(23): 7898.
[25] 崔冰, 赵辉军, 段景文, 等. 基于改进A*算法的地下自动驾驶铲运机路径规划[J]. 矿业研究与开发, 2024, 44(5): 185-193.
CUI B, ZHAO H J, DUAN J W, et al. Path planning of under ground autonomous LHD machines based on improved A? algorithm[J]. Mining Research and Development, 2024, 44(5): 185-193.
[26] 张方方, 于洪岩, 辛健斌, 等. 基于自适应地图环境改进A*算法的机器人路径规划[J/OL]. 控制工程: 1-10[2024-05-20].https://www.cnki.com.cn/Article/CJFDTotal-JZDF20
240507002.htm.
ZHANG F F, YU H Y, XIN J B, et al. Improved robot path planning based on adaptive map environment A* algorithm[J/OL]. Control Engineering of China: 1-10[2024-05-20]. https://www.cnki.com.cn/Article/CJFDTotal-JZDF20240507002.htm.
[27] 宋卫猛, 王毅. 基于自适应启发函数和逆向寻优策略的改进 A* 移动机器人路径规划算法[J]. 计算机测量与控制, 2025, 33(1): 173-180.
SONG W M, WANG Y. Improved A* algorithm of mobile robot path planning based on adaptive heuristic function and reverse optimization strategy[J]. Computer Measurement & Control, 2025, 33(1): 173-180.
[28] 倪建云, 吴杰, 薛晨阳, 等. 融合改进A*和蚁群算法的机器人路径规划[J]. 天津理工大学学报, 2025, 41(2): 73-80.
NI J Y, WU J, XUE C Y, et al. Robot path planning incorporating improved A* and ant colony optimization[J]. Journal of Tianjin University of Technology, 2025, 41(2): 73-80.
[29] 赖荣燊, 窦磊, 巫志勇, 等. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.
LAI R S, DOU L, WU Z Y, et al. Fusion of Improved A* and dynamic window approach for mobile robot path planning[J]. Journal of System Simulation, 2024, 36(8): 1884-1894.

编辑推荐

Metrics

阅读次数

全文

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	52

	来源	本网站

	次数	52
	比例	100%

摘要

最新录用	在线预览	正式出版

0	0	58