[1]张博强,张成龙,冯天培,等.基于JPS和变半径RS曲线的Hybrid A∗路径规划算法[J].郑州大学学报(工学版),2025,46(02):19-25.[doi:10.13705/j.issn.1671-6833.2025.02.022]
　ZHANG Boqiang,ZHANG Chenglong,FENG Tianpei,et al.The Hybrid A∗ Planning Algorithm Based on JPS and Variable Radius RS Curves[J].Journal of Zhengzhou University (Engineering Science),2025,46(02):19-25.[doi:10.13705/j.issn.1671-6833.2025.02.022]
点击复制

基于JPS和变半径RS曲线的Hybrid A∗路径规划算法()
分享到：

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

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

文章信息/Info

Title:
The Hybrid A∗ Planning Algorithm Based on JPS and Variable Radius RS Curves
文章编号:
1671-6833(2025)02-0019-07
作者:
张博强1;  张成龙1;  冯天培1;  高向川2
1.河南工业大学 机电工程学院,河南 郑州 450001;2.郑州大学 电气与信息工程学院,河南 郑州 450001
Author(s):
ZHANG Boqiang1;  ZHANG Chenglong1;  FENG Tianpei1;  GAO Xiangchuan2
1.School of Mechanical and Electrical Engineering, Henan University of Technology, Zhengzhou 450001, China; 2.School of Electrical and Information Engineering, Zhengzhou University, Zhengzhou 450001, China
关键词:
HybridA∗算法;  启发函数;  JPS算法;  RS曲线;  路径规划
Keywords:
HybridA∗ algorithm;  heuristic function;  JPS algorithm;  RS curve;  path planning
分类号:
TP242TP391.9
DOI:
10.13705/j.issn.1671-6833.2025.02.022
文献标志码:
A
摘要:
为解决混合A∗(HybridA∗)算法在高分辨率地图和复杂场景下搜索效率低、耗费时间长的问题,通过对影响传统HybridA∗算法搜索效率的因素进行分析,提出了J-HybridA∗算法。首先,在HybridA∗算法扩展节点前,使用跳点搜索(JPS)算法进行起点到终点的路径搜索,将该路径进行拉直处理后作为计算节点启发值的基础;其次,设计了新的启发函数,在HybridA∗算法扩展前就能完成所有节点启发值的计算,减少了HybridA∗扩展节点时计算启发值所需的时间;最后,将RS曲线由最小转弯半径搜索改为变半径RS曲线搜索,使RS曲线能够更早搜索到一条无碰撞路径,进一步提升了HybridA∗算法的搜索效率。仿真结果表明:所提J-HybridA∗算法在简单环境中比传统HybridA∗算法和反向HybridA∗算法用时分别缩短68%、21%,在复杂环境中缩短59%、27%。在不同分辨率地图场景中,随着地图分辨率的提高,规划效率显著提升。实车实验表明:所提J-HybridA∗算法相较于传统HybridA∗算法和反向HybridA∗算法的搜索用时分别减少88%、82%,有效提升了HybridA∗算法的搜索效率、缩短了路径规划所需时间。
Abstract:
In order to solve the problems of HybridA∗ algorithm′s, such as low search efficiency and long time consumption in high-resolution map of complex scenes, J-HybridA∗ algorithm was proposed after analyzing the factors affecting the search efficiency of traditional HybridA∗ algorithm. Firstly, before HybridA∗ algorithm expanded its nodes, JPS algorithm was used to search the path from the starting point to the end point, and the path was straightened and processed as the basis for calculating the node heuristic value, which reduced the time required for HybridA∗ to calculate the heuristic value when expanding the nodes. Second, a new function is created to calculate all of the node heuristic values before the HybridA∗ algorithm is expanded. This reduces the time needed to calculate the heuristic values when HybridA∗ expands the nodes. Finally, the change of the RS curve from minimum turning radius search to variable radius RS curve search enabled the RS curve to search for a collision-free path earlier, which further accelerated the search of the HybridA∗ algorithm. The results of the simulation demonstrate that the enhanced J-HybridA∗ algorithm reduced the search time by 68% and 21% in comparison to the conventional HybridA∗ algorithm and the reverse HybridA∗ algorithm in straightforward environments. In complex environments, the reduction in search time was 59% and 27%. Furthermore, the planning efficiency is markedly enhanced with the increase of map resolution in diverse resolution map scenarios. Experiments conducted on actual vehicles demonstrated that the J-HybridA∗ algorithm, reduced the search time by 88% and 82% in comparison to the traditional HybridA∗ algorithm and the reverse HybridA∗ algorithm. This effectively enhanced the search efficiency of the HybridA∗ algorithm and reduced the time required for path planning.

参考文献/References:

[1]龙邱天. 无人驾驶车辆非结构化道路检测方法研究[D]. 沈阳: 沈阳理工大学, 2023. 

LONG Q T. Research on unstructured road detection method for unmanned vehicles[D]. Shenyang: Shenyang Ligong University, 2023. 
[2]AKRAM M, HABIB A, ALCANTUD J C R. An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers[J]. Neural Computing and Applications, 2021, 33(4): 1329-1342. 
[3]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. 
[4]陈江义, 殷笑勇, 王婷婷, 等. 基于改进斥力模型的人工势场局部路径规划[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. 
[5]YE L, WU F Y, ZOU X J, et al. Path planning for mobile robots in unstructured orchard environments: an improved kinematically constrained bi-directional RRT approach[J]. Computers and Electronics in Agriculture, 2023, 215: 108453. 
[6]MIAO C W, CHEN G Z, YAN C L, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230. 
[7]DOLGOV D, THRUN S, MONTEMERLO M, et al. Practical search techniques in path planning for autonomous driving[C]∥Proceedings of the AAAI Conference on Artifical Intelligence. Wasington DC: AAAI, 2008: 32-37. 
[8]崔高健, 陆柏霖, 贺红春, 等. 基于逆向HybridA∗算法的自动泊车路径规划[J]. 长春工业大学学报, 2022, 43(4/5): 627-633. 
CUI G J, LU B L, HE H C, et al. Automatic parking path planning based on reverse HybridA∗[J]. Journal of Changchun University of Technology, 2022, 43(4/ 5): 627-633. 
[9]陈翔翔.基于HybridA∗算法的自动泊车路径规划与跟踪控制研究[D].西安:长安大学,2022. 
CHEN X X. Research on HybridA∗ algorithm path planning and tracking control for automatic parking[D]. Xi’ an:Chang’an University, 2022.
[10]张会丽,钱徽,陈武斌,等.基于连续状态空间的启发式路径规划算法[J]. 华中科技大学学报(自然科学版),2011,39(增刊2): 374-377,381. 
ZHANG H L, QIAN H, CHEN W B, et al. Heuristic path planning algorithm in continuous state spaces[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2011, 39(S2): 374377,381. 
[11]曹彦博, 颜京才, 李旭升, 等. 基于改进混合A∗算法的自动泊车系统路径搜索方法[J]. 汽车技术, 2023 (6): 37-41. 
CAO Y B, YAN J C, LI X S, et al. A method of path search for automatic parking system based on improved HybridA∗ algorithm[J]. Automobile Technology, 2023 (6): 37-41. 
[12]秦东晨, 张文灿, 王婷婷, 等. 受限泊车通道下自动驾驶平行泊车的路径规划方法[J]. 郑州大学学报(工学版), 2024, 45(5): 1-7. 
QIN D C, ZHANG W C, WANG T T, et al. A path planning method for parallel parking in constrained parking channels[J]. Journal of Zhengzhou University (Engineering Science), 2024, 45(5): 1-7. 
[13]陈鑫鹏, 徐彪, 胡满江, 等. 一种基于等步长分层拓展的混合A∗路径规划方法[J]. 控制与信息技术, 2021(1): 17-22, 29. 
CHEN X P, XU B, HU M J, et al. A HybridA∗ path planning method based on equal step hierarchical expansion[J]. Control and Information Technology, 2021(1): 17-22, 29. 
[14] SEDIGHI S, NGUYEN D V, KUHNERT K D. Guided Hybrid A-star path planning algorithm for valet parking applications[C]∥2019 5th International Conference on Control, Automation and Robotics (ICCAR). Piscataway: IEEE, 2019: 570-575. 
[15]邓穆坤, 刘勇, 黄佳德, 等. 基于混合A∗算法的无人驾驶矿用卡车路径优化研究[J]. 控制与信息技术, 2022(5): 60-67. 
DENG M K, LIU Y, HUANG J D, et al. Research on HybridA∗ based path optimization of unmanned mine truck[J]. Control and Information Technology, 2022 (5): 60-67. 
[16]胡智焕, 杨子恒, 张卫东. 基于混合A∗搜索和贝塞尔曲线的船舶进港和靠泊路径规划算法[J]. 中国舰船研究, 2024, 19(1): 220-229. 
HU Z H, YANG Z H, ZHANG W D. Path planning for auto docking of underactuated ships based on Bezier curve and HybridA∗ search algorithm[J]. Chinese Journal of Ship Research, 2024, 19(1): 220-229. 
[17] BONETTI A, GUIDETTI S, SABATTINI L. Improved path planning algorithms for non-holonomic autonomous vehicles in industrial environments with narrow corridors: roadmap HybridA∗ and waypoints HybridA∗[C]∥ 2023 European Conference on Mobile Robots (ECMR). Piscataway: IEEE, 2023: 1-7. 
[18] TANG B J, HIROTA K, WU X D, et al. Path planning based on improved HybridA∗Algorithm[J]. Journal of Advanced Computational Intelligence and Intelligent Informatics, 2021, 25(1): 64-72. 
[19] MENG T C, YANG T H, HUANG J, et al. Improved Hybrid A-star algorithm for path planning in autonomous parking system based on multi-stage dynamic optimization [J]. International Journal of Automotive Technology, 2023, 24(2): 459-468. 
[20] DANG C V, AHN H, LEE D S, et al. Improved analytic expansions in Hybrid A-star path planning for non-holonomic robots [ J]. Applied Sciences, 2022, 12 (12): 5999. 
[21]吴梓聪. 基于改进HybridA∗算法的移动机器人路径规划研究[D]. 广州: 华南理工大学, 2020. 
WU Z C. Research on path planning of mobile robot based on improved HybridA∗ algorithm[D].Guangzhou: South China University of Technology, 2020. 
[22]邱磊, 刘辉玲, 雷建龙. 跳点搜索算法的原理解释及性能分析[J]. 新疆大学学报(自然科学版), 2016, 33(1): 80-87. 
QIU L, LIU H L, LEI J L. Principle explanation and performance analysis of jump point search algorithm[J]. Journal of Xinjiang University (Natural Science Edition), 2016, 33(1): 80-87. 
[23]姚智龙, 张小俊, 王金刚. 改进Bi-RRT∗算法的自动泊车路径规划[J]. 机械科学与技术, 2024, 43(6): 1063-1071. 
YAO Z L, ZHANG X J, WANG J G. Automatic parking path planning with improved Bi-RRT∗ algorithm[J]. Mechanical Science and Technology for Aerospace Engineering, 2024, 43(6): 1063-1071. 
[24] RAJENDRAN G, UMA V, O’BRIEN B. Unified robot task and motion planning with extended planner using ROS simulator[J]. Journal of King Saud University-Computer and Information Sciences, 2022, 34(9): 7468-7481.

相似文献/References:

[1]陈一馨,段宇轩,刘　豪,等.基于障碍密度优先策略改进A∗算法的AGV路径规划[J].郑州大学学报(工学版),2025,46(02):26.[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.[doi:10.13705/j.issn.1671-6833.2025.02.018]

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