改进A*与APF的移动机器人路径规划算法研究

doi:10.3778/j.issn.1002-8331.2501-0092

摘要/Abstract

摘要： 针对A*路径规划算法在复杂环境中存在搜索效率受限及动态避障能力不足的问题，提出了一种改进A*算法与人工势场法相结合的路径规划方法。对静态障碍物进行预处理获取可视化通行节点，进而建立在空旷区域和障碍物区域分别采用三角形边界和三邻域的搜索机制，基于双向交替搜索策略实现了全局路径规划；将全局路径离散为等间距轨迹点，并引入人工势能函数将位于轨线上的动态障碍物影响区域建模为椭圆区域，利用机器人与前进方向最近轨迹点的距离作为斥力函数修正因子，将其与前进方向轨迹点吸引力的合力方向作为机器人避障方向，实现局部避障。仿真结果表明，所提算法与传统双向A*算法相比，搜索时间减少了96%，遍历节点数减少了82.28%，机器人在实现避障的同时沿着全局最优路径前行，从而验证了算法的有效性。

关键词: 移动机器人, 路径规划, 改进A*算法, APF算法, 动态避障

Abstract: Aiming at the problems of limited search efficiency and insufficient dynamic obstacle avoidance ability of A* path planning algorithm in complex environments, a path planning method combining improved A* algorithm and artificial potential field method is proposed. Firstly, the static obstacles are preprocessed to obtain visual passage nodes, and then the search mechanism of triangle boundary and three neighborhood is established in the open area and the obstacle area respectively, and the global path planning is realized based on the bidirectional alternating search strategy. Secondly, the global path is discretized into equally spaced trajectory points, and the influence area of dynamic obstacles on the trajectory line is modeled as an ellipse area by introducing the artificial potential energy function. The distance between the robot and the nearest trajectory point in the forward direction is used as the correction factor of the repulsion function, and the resultant force direction between the robot and the attraction of the trajectory point in the forward direction is used as the collision avoidance direction of the robot, and the local obstacle avoidance is achieved. The simulation results show that compared with the traditional bidirectional A* algorithm, the search time of the proposed algorithm is reduced by 96%, and the number of traversed nodes is reduced by 82.28%. The robot moves along the global optimal path while avoiding obstacles, which verifies the effectiveness of the algorithm.

Key words: mobile robot, path planning, improve A* algorithm, artificial potential field（APF）algorithm, dynamic obstacle avoidance

冯泽鹏, 李宗刚, 夏广庆, 陈引娟. 改进A*与APF的移动机器人路径规划算法研究[J]. 计算机工程与应用, 2025, 61(20): 132-145.

FENG Zepeng, LI Zonggang, XIA Guangqing, CHEN Yinjuan. Research on Improving A* and APF Algorithms for Mobile Robot Path Planning[J]. Computer Engineering and Applications, 2025, 61(20): 132-145.

参考文献

[1] LIU L X, WANG X, YANG X, et al. Path planning techniques for mobile robots: review and prospect[J]. Expert Systems with Applications, 2023, 227: 120254.
[2] 崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59 (19): 10-20.
CUI W, ZHU F Z. Review of path planning algorithms for robot navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.
[3] 王旭, 朱其新, 朱永红. 面向二维移动机器人的路径规划算法综述[J]. 计算机工程与应用, 2023, 59(20): 51-66.
WANG X, ZHU Q X, ZHU Y H. Review of path planning algorithms for mobile robots[J]. Computer Engineering and Applic-ations, 2023, 59(20): 51-66.
[4] 巩慧, 倪翠, 王朋, 等. 基于Dijkstra算法的平滑路径规划方法[J]. 北京航空航天大学学报, 2024, 50(2): 535-541.
GONG H, NI C, WANG P, et al. A smooth path planning method based on Dijkstra algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 50(2): 535-541.
[5] CHEN J Q, LI M Y, SU Y S, et al. Direction constraints adaptive extended bidirectional A* algorithm based on random two-dimensional map environments[J]. Robotics and Autonomous Systems, 2023, 165: 104430.
[6] 黄书峤, 伍锡如, 黄国明. 基于动态视场的深度启发改进3维A*算法[J]. 机器人, 2024, 46(5): 513-523. ?
HUANG S Q, WU X R, HUANG G M. Deep heuristic-improved 3D A* algorithm based on dynamic field-of-view[J]. Robot, 2024, 46(5): 513-523.
[7] 潘作栋, 周悦, 郭威, 等. 基于CB-RRT*算法的滩涂履带车路径规划[J]. 兵工学报, 2024, 45(4): 1117-1128.
PAN Z D, ZHOU Y, GUO W, et al. Path planning of tidal flat tracked vehicle based on CB-RRT*?algorithm[J]. Acta Armamentarii, 2024, 45(4): 1117-1128.
[8] DING M, ZHENG X J, LIU L X, et al. Collision-free path planning for cable-driven continuum robot based on improved artificial potential field[J]. Robotica, 2024, 42(5): 1350-1367.
[9] LIAO T J, CHEN F, WU Y T, et al. Research on path planning with the integration of adaptive A-star algorithm and improved dynamic window approach[J]. Electronics, 2024, 13(2): 455.
[10] 葛杏卫, 苏浩冉, 张凯亮, 等. 智能土壤采样机改进A*算法路径规划[J]. 计算机工程与应用, 2025, 61(20): 123-131.
GE X W, SU H R, ZHANG K L, et al. Improved A* algorithm path planning for intelligent soil sampler[J]. Computer Engineering and Applications, 2025, 61(20): 123-131.
[11] 郭聚刚, 于军琪, 冯春勇, 等. 基于改进A*算法的机器人不平坦地形全局路径规划[J]. 计算机工程与应用, 2025, 61(5): 309-322.
GUO J G. YU J Q, FENG C Y, et al. Global path planning for robots on uneven terrain based on an improved A* algorithm[J]. Computer Engineering and Applications, 2025, 61(5): 309-322.
[12] 张伟民, 徐森生, 张月. 基于改进A*算法的室内巡检机器人路径规划研究[J]. 机械工程学报, 2024, 60(20): 315-326.
ZHANG W M, XU S S, ZHANG Y. Research on path planning of indoor inspection robot based on improved A*?algorithm[J]. Journal of Mechanical Engineering, 2024, 60(20): 315-326.
[13] LI C, LI J, LIU X Q. Static rectangle expansion A*algorithm for pathfinding[J]. IEEE Transactions on Games, 2022, 14(1): 23-35.
[14] XU X, ZENG J Z, ZHAO Y, et al. Research on global path planning algorithm for mobile robots based on improved A[J]. Expert Systems with Applications, 2024, 243: 122922.
[15] 梅艺林, 崔立堃, 胡雪岩, 等. 基于人工势场法的复杂环境下多无人车避障与编队控制[J]. 工程科学学报, 2025, 47(2): 364-373.
MEI Y L, CUI L K, HU X Y, et al. Obstacle avoidance and formation control of multiple unmanned vehicles in complex environments based on artificial potential field method[J]. Chinese Journal of Engineering, 2025, 47(2): 364-373.
[16] 姬鹏, 郭明皓. 基于Frenet坐标下改进人工势场法的无人车局部路径规划[J]. 兵工学报, 2024, 45(7): 2097-2109.
JI P, GUO M H. Local path planning for unmanned ground vehicles based on improved artificial potential field method in Frenet coordinate system[J]. Acta Armamentarii, 2024, 45(7): 2097-2109.
[17] WU Z T, DAI J Y, JIANG B P, et al. Robot path planning based on artificial potential field with deterministic annealing[J]. ISA Transactions, 2023, 138: 74-87.
[18] 赵丹丹, 王亚刚, 张一勤, 等. 基于模糊人工势场法的智能助行器人机共享控制策略[J]. 控制与决策, 2025, 40(5): 1474-1484.
ZHAO D D, WANG Y G, ZHANG Y Q, et al. Human-machine shared control strategy for an intelligent mobility aid based on the fuzzy artificial potential field method[J]. Control and Decision, 2025, 40(5): 1474-1484.
[19] SANG H Q, YOU Y S, SUN X J, et al. The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations[J]. Ocean Engineering, 2021, 223: 108709.
[20] 王洪斌, 赫策, 张平, 等. 基于 A*算法和人工势场法的移动机器人路径规划[J]. 中国机械工程, 2019, 30(20): 2489-2496.
WANG H B, HAO C, ZHANG P, et al. Path planning of mobile robots based on A* algorithm and artificial potential field algorithm[J]. China Mechanical Engineering, 2019, 30(20): 2489-2496.
[21] 孙月平, 方正, 袁必康, 等. 基于FIA*-APF算法的蟹塘投饵船动态路径规划[J]. 农业工程学报, 2024, 40(9): 137-145.
SUN Y P, FANG Z, YUAN B K, et al. Dynamic path planning for feeding boat in crab pond using FIA*-APF algorithm[J]. Transactions of the Chinese Society of Agricultural Engineering, 2024, 40(9): 137-145.
[22] GAO J, XU X R, PU Q C, et al. A hybrid path planning method based on improved A* and CSA-APF algorithms[J]. IEEE Access, 2024, 12: 39139-39151.
[23] TONG X L, YU S N, LIU G Y, et al. A hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm in the 2D random environments[J]. Advanced Engineering Informatics, 2022, 54: 101755.
[24] 朱泺谕, 胡明, 吴湘, 等. 基于A*算法奖惩机制改进并优化路径选择的AGV路径规划[J]. 计算机集成制造系统, 2025, 31(8): 2786-2796.
ZHU L Y, HU M, WU X, et al. AGV path planning based on A* algorithm reward and punishment mechanism to impr-ove and optimize path selection[J]. Computer Integrated Manufacturing Systems, 2025, 31(8): 2786-2796.
[25] 王雅如, 姚得鑫, 刘增力, 等. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.
WANG Y R, YAO D X, LIU Z L, et al. Path planning for mobile robot based on angle search[J]. Journal of System Simulation, 2024, 36(7): 1643-1654.
[26] 陈德童, 刘贤达, 刘生伟. 基于双向搜索改进A*算法的自动导引车路径规划[J]. 计算机应用, 2021, 41(2): 309-313.
CHEN D T, LIU X D, LIU S W. Improved A* algorithm based on two-way search for path planning of automated gui-ded vehicle[J]. Journal of Computer Applications, 2021, 41(2): 309-313.