The Hybrid A∗ Planning Algorithm Based on JPS and Variable Radius RS Curves

NAVIGATE

Table of Contents

STATISTICS

Viewed153

Downloads80

The Hybrid A∗ Planning Algorithm Based on JPS and Variable Radius RS Curves

[HTML] PDF下载 (80)

[1]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]

Copy

Journal of Zhengzhou University (Engineering Science)[ISSN 1671-6833/CN 41-1339/T] Volume: 46 Number of periods: 2025 02 Page number: 19-25 Column: Public date: 2025-03-10

Title:: The Hybrid A∗ Planning Algorithm Based on JPS and Variable Radius RS Curves

Author(s):: ZHANG Boqiang¹; ZHANG Chenglong¹; FENG Tianpei¹; GAO Xiangchuan²; 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

Keywords:: HybridA∗ algorithm; heuristic function; JPS algorithm; RS curve; path planning

CLC:: TP242TP391.9

DOI:: 10.13705/j.issn.1671-6833.2025.02.022

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.

Similar References:

Memo

Last Update: 2025-03-13