[1]陈一馨,段宇轩,刘　豪,等.基于障碍密度优先策略改进A∗算法的AGV路径规划[J].郑州大学学报(工学版),2025,46(02):26-34.[doi:10.13705/j.issn.1671-6833.2025.02.018]
　CHEN Yixin,DUAN Yuxuan,LIU Hao,et al.Improved A∗ Algorithm for AGV Path Planning Based on Obstacle Density Prioritization Strategy[J].Journal of Zhengzhou University (Engineering Science),2025,46(02):26-34.[doi:10.13705/j.issn.1671-6833.2025.02.018]
点击复制

基于障碍密度优先策略改进A∗算法的AGV路径规划()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
46
期数:
2025年02期
页码:
26-34
栏目:
出版日期:
2025-03-10

文章信息/Info

Title:
Improved A∗ Algorithm for AGV Path Planning Based on Obstacle Density Prioritization Strategy
文章编号:
1671-6833(2025)02-0026-09
作者:
陈一馨;  段宇轩;  刘　豪;  谭世界;  郑天乐
长安大学 道路施工技术与装备教育部重点实验室,陕西 西安 710064
Author(s):
CHEN Yixin;  DUAN Yuxuan;  LIU Hao;  TAN Shijie;  ZHENG Tianle
Key Laboratory of Road Construction Technology & Equipment of Ministry of Education, Chang’an University, Xi’an 710064, China
关键词:
路径规划;  栅格地图;  改进A∗算法;  启发函数;  动态邻域搜索;  冗余节点优化
Keywords:
path planning;  grid map;  improved A∗ algorithm;  heuristic function;  dynamic neighborhood search;  redundant node optimization
分类号:
TP242
DOI:
10.13705/j.issn.1671-6833.2025.02.018
文献标志码:
A
摘要:
针对传统A∗算法在障碍物较多的实际场景下进行AGV路径规划时,存在路径拐点多、路径冗余节点过多以及易陷入局部最优解等问题,提出一种改进A∗算法,采用栅格法进行环境建模。首先,在启发函数中引入障碍物密度函数K(n)改进代价函数,用于更准确地估计当前节点到目标节点的实际代价;其次,采用动态邻域搜索策略提高算法的搜索效率和运行效率;最后,通过冗余节点处理策略减少路径拐点和删除冗余节点,得到只包含起点、转折点以及终点的路径。采用不同尺寸和复杂度的栅格环境地图进行仿真实验,结果表明:所提改进A∗算法与传统A∗算法以及其他改进的A∗算法相比,路径长度分别缩短了4.71%和2.07%,路径拐点数量分别减少了45.45%和20.54%,路径存在节点分别减少了82.24%和62.45%。
Abstract:
An improved A∗ algorithm was proposed to address the problems of excessive path turning points, redundant nodes, and susceptibility to local optimum in AGV path planning when the traditional A∗ algorithm was applied in obstacle-dense scenarios. The environment model was constructed using the grid method. Firstly, an obstacle density function K(n) was introduced into the heuristic function to improve the cost function, enabling a more accurate estimation of the actual cost from the current node to the target node. Secondly, a dynamic neighborhood search strategy was adopted to enhance the search efficiency and operational performance of the algorithm. Finally, a redundant node processing strategy was implemented to reduce path turning points and remove redundant nodes, yielding a path that contained only the starting point, turning points, and the endpoint. Simulation experiments were conducted on grid maps with varying sizes and complexities. The results demonstrated that, compared to the traditional A∗ algorithm and other improved A∗ algorithm, the proposed algorithm achieved path length reductions of 4.71% and 2.07%, turning point reductions of 45.45% and 20.54%, and node reductions of 84.24% and 62.45%, respectively.

参考文献/References:

[1]赵学健, 叶昊, 贾伟, 等. AGV路径规划及避障算法研究综述[J]. 小型微型计算机系统, 2024, 45(3): 529-541. 

ZHAO X J, YE H, JIA W, et al. Survey on AGV path planning and obstacle avoidance algorithms[J]. Journal of Chinese Computer Systems, 2024, 45(3): 529-541. 
[2]刘子豪,赵津,刘畅,等.基于改进A∗算法室内移动机器人路径规划[J].计算机工程与应用, 2021, 57(2): 186-190. 
LIU Z Y, ZHAO J, LIU C, et al. Path planning of indoor mobile robot based on improved A∗ algorithm[J]. Computer Engineering and Applications, 2021,57(2): 186-190. 
[3]XIAO S, WU H Y, CHEN Z H. Research of mobile robot path planning based on improved A∗ algorithm[C]∥ 2020 Chinese Automation Congress (CAC). Piscataway: IEEE, 2020: 7619-7623. 
[4]TANG G, TANG C Q, CLARAMUNT C, et al. Geometric A-star algorithm: an improved A-star algorithm for AGV path planning in a port environment[J]. IEEE Access, 2021, 9: 59196-59210. 
[5]姜辰凯, 李智, 盘书宝, 等. 基于改进Dijkstra算法的AGVs无碰撞路径规划[J]. 计算机科学, 2020, 47 (8): 272-277. 
JIANG C K, LI Z, PAN S B, et al. Collision-free path planning of AGVs based on improved Dijkstra algorithm [J]. Computer Science, 2020, 47(8): 272-277. 
[6]杨炜, 谭亮, 孙雪, 等. 基于优化快速搜索随机树算法的全局路径规划[J]. 汽车技术, 2024(3): 31-36. 
YANG W, TAN L, SUN X, et al. The global path planning algorithm based on optimization RRT algorithm[J]. Automobile Technology, 2024(3): 31-36. 
[7]唐旭晖, 辛绍杰. 改进蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2022, 58(5): 287-295. 
TANG X H, XIN S J. Improved ant colony algorithm for mobile robot path planning[J]. Computer Engineering and Applications, 2022, 58(5): 287-295. 
[8]陈江义, 殷笑勇, 王婷婷, 等. 基于改进斥力模型的人工势场局部路径规划[J]. 郑州大学学报(工学版), 2023, 44(3): 83-87, 101. 
CHEN J Y, YIN X Y, WANG T T, et al. Local path planning of artificial potential field based on improved repulsive model[J]. Journal of Zhengzhou University (Engineering Science), 2023, 44(3): 83-87, 101. 
[9]刘生伟, 马钺, 孟树峰, 等. 改进A∗算法的AGV路径规划[J]. 计算机应用, 2019, 39(增刊2): 41-44. 
LIU S W, MA Y, MENG S F, et al. AGV path planning based on improved A∗ algorithm[J]. Journal of Computer Applications, 2019, 39(S2): 41-44. 
[10]余震,王栋,王明天,等.基于改进A∗算法的AGV全局路径规划[J].武汉科技大学学报,2024,47(3):234-240. 
YU Z, WANG D, WANG M T, et al. Global path planning for AGV based on improved A∗ algorithm[J]. Journal of Wuhan University of Science and Technology, 2024,47(3):234-240. 
[11] JIAN Z Q, ZHANG S Y, CHEN S T, et al. A global-local coupling two-stage path planning method for mobile robots[J]. IEEE Robotics and Automation Letters, 2021, 6(3): 5349-5356. 
[12] XIANG D, LIN H X, OUYANG J, et al. Combined improved A∗ and greedy algorithm for path planning of multi-objective mobile robot [J]. Scientific Reports, 2022, 12(1): 13273. 
[13]张辉, 张瑞亮, 许小庆, 等. 基于关键节点的改进A∗无人车路径规划算法[J]. 汽车技术, 2023(3): 10-18. 
ZHANG H, ZHANG R L, XU X Q, et al. Key nodes-based improved A∗ algorithm for path planning of unmanned vehicle[J]. Automobile Technology, 2023(3): 10-18. 
[14]孔慧芳, 盛阳. 基于改进A∗算法的AGV路径规划研究[J]. 现代制造工程, 2021(10): 60-64. 
KONG H F, SHENG Y. Research on AGV path planning based on improved A∗ algorithm[J]. Modern Manufacturing Engineering, 2021(10): 60-64.
[15]李强, 于振中, 樊启高, 等. 基于改进A∗算法在AGV路径规划中的应用[J]. 组合机床与自动化加工技术,2019(5): 98-101. 
LI Q, YU Z Z, FAN Q G, et al. Application of improved A∗ algorithm for AGV path planning[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2019 (5): 98-101. 
[16] CHEN S, ZHANG Q, HE G C, et al. Multiple-AGV path planning method for two industrial links[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2022, 36(12):2259029. 
[17] ZHANG R D, CHAI R Q, CHAI S C, et al. Design and practical implementation of a high efficiency two-layer trajectory planning method for AGV[J]. IEEE Transactions on Industrial Electronics, 2024, 71(2): 1811-1822. 
[18]孙波, 姜平, 周根荣, 等. 基于改进遗传算法的AGV路径规划[J]. 计算机工程与设计, 2020, 41(2): 550-556. 
SUN B, JIANG P, ZHOU G R, et al. AGV optimal path planning based on improved genetic algorithm[J]. Computer Engineering and Design, 2020, 41(2): 550-556. 
[19]姚得鑫,伞红军,王雅如,等.移动机器人路径规划中A∗算法的改进研究[J].系统仿真学报,2024,36(11): 2684-2698. 
YAO D X, SAN H J, WANG Y R, et al. Research on the improvement of A∗ algorithm in path planning of mobile robot[J]. Journal of System Simulation,2024,36 (11):2684-2698. 
[20] AKKA K, KHABER F. Mobile robot path planning using an improved ant colony optimization[J]. International Journal of Advanced Robotic Systems, 2018, 15(3): 172988141877467. 
[21]刘宇庭, 郭世杰, 唐术锋, 等. 改进A∗与ROA-DWA融合的机器人路径规划[J]. 浙江大学学报(工学版), 2024, 58(2): 360-369. 
LIU Y T, GUO S J, TANG S F, et al. Path planning based on fusion of improved A∗ and ROA-DWA for robot [J]. Journal of Zhejiang University (Engineering Science), 2024, 58(2): 360-369.

相似文献/References:

[1]欧阳海滨,全永彬,高立群,等.基于混合遗传粒子群优化算法的层次路径规划方法[J].郑州大学学报(工学版),2020,41(04):34.[doi:10.13705/j.issn.1671-6833.2020.01.011]
　OUYANG Haibin,QUAN Yongbin,GAO Liqun,et al.Hierarchical Path Planning Method for Mobile Robots Based on Hybrid Genetic Particle Swarm Optimization Algorithm[J].Journal of Zhengzhou University (Engineering Science),2020,41(02):34.[doi:10.13705/j.issn.1671-6833.2020.01.011]
[2]姜晓东,任奕辰,朱晓东.基于改进人工鱼群算法的蠕虫机器人路径规划[J].郑州大学学报(工学版),2024,45(03):55.[doi:10. 13705/ j. issn. 1671-6833. 2024. 03. 007]
　JIANG Xiaodong,REN Yichen,ZHU Xiaodong.New Grid Map Path Planning Based on Improved Artificial Fish Swarm Algorithm[J].Journal of Zhengzhou University (Engineering Science),2024,45(02):55.[doi:10. 13705/ j. issn. 1671-6833. 2024. 03. 007]

更新日期/Last Update: 2025-03-13