Path Planning Based on Hybrid A* and Modified RS Curve Fusion

doi:10.19678/j.issn.1000-3428.0068338

Abstract

Abstract:

This paper proposes a path-planning method based on hybrid A^* and modified RS curve fusion to address the issue of unmanned transfer vehicles in limited scenarios being unable to maintain a safe distance from surrounding obstacles during path planning, resulting in collisions between vehicles and obstacles. First, a distance cost function based on the KD Tree algorithm is proposed and added to the cost function of the hybrid A^* algorithm. Second, the expansion strategy of the hybrid A^* algorithm is changed by dynamically changing the node expansion distance based on the surrounding environment of the vehicle, achieving dynamic node expansion and improving the algorithm's node search efficiency. Finally, the RS curve generation mechanism of the hybrid A^* algorithm is improved to make the straight part of the generated RS curve parallel to the boundary of the surrounding obstacles to meet the requirements of road driving in the plant area. Subsequently, the local path is smoothed to ensure that it meets the continuity of path curvature changes under the conditions of vehicle kinematics constraints to improve the quality of the generated path. The experimental results show that, compared with traditional algorithms, the proposed algorithm reduces the search time by 38.06%, reduces the maximum curvature by 25.2%, and increases the closest distance from the path to the obstacle by 51.3%. Thus, the proposed method effectively improves the quality of path generation of the hybrid A^* algorithm and can operate well in limited scenarios.

Key words: limited scenarios, path planning, KD-Tree algorithm, hybrid A^* algorithm, RS curve

摘要：

在限定场景内, 无人转运车辆在路径规划过程中不能与周围障碍物保持安全距离, 导致发生车辆与障碍物发生剐蹭的问题, 提出基于混合A^*算法和修正RS曲线融合的路径规划。首先, 将提出的基于KD-Tree算法的距离代价函数加入到混合A^*算法的代价函数中。其次, 改变混合A^*算法的扩展策略, 根据车辆周围环境动态改变节点扩展距离, 实现节点的动态扩展, 提高算法的节点搜索效率。最后, 改进混合A^*算法的RS曲线生成机制, 使生成的RS曲线直线部分与周围障碍物边界保持平行, 从而符合厂区内道路行驶要求, 通过对局部路径进行平滑处理, 在保证路径符合车辆运动学约束的条件下满足路径曲率变化的连续性, 从而提高生成路径的质量。实验结果表明, 与传统算法相比, 提出算法的搜索时间缩短了38.06%, 最大曲率减少了25.2%, 路径到障碍物的最近距离增加了51.3%, 有效提高了混合A^*算法生成路径的质量, 并能较好地在限定场景中运行。

关键词: 限定场景, 路径规划, KD-Tree算法, 混合A^*算法, RS曲线

ZHANG Boqiang, CHEN Xinming, FENG Tianpei, WU Lan, LIU Ningning, SUN Peng. Path Planning Based on Hybrid A^* and Modified RS Curve Fusion[J]. Computer Engineering, 2025, 51(4): 373-382.

张博强, 陈新明, 冯天培, 吴兰, 刘宁宁, 孙朋. 基于混合A^*和修正RS曲线融合的路径规划[J]. 计算机工程, 2025, 51(4): 373-382.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0068338

https://www.ecice06.com/EN/Y2025/V51/I4/373

Figures/Tables 21

Fig.1 Technology roadmap

Fig.2 Implementation procedure KD-Tree algorithm

Fig.3 Schematic diagram of surrounding area of the vehicle

Fig.4 Schematic diagram of dynamic expansion

Fig.5 Effect of dynamic expansion

Fig.6 RS curve plots with different curvatures

Fig.7 Experimental effect diagram of revised RS curve

Fig.8 Smooth local effects of RS curves with different curvatures

Fig.9 Simulation effect of path local smoothing processing

Fig.10 Comparison of simulation effects

Fig.11 Experimental results of different locations

Fig.12 Real vehicle testing platform

Fig.13 Actual vehicle experiment effect

References 24

1	刘霞. 人工智能助力物流"最后一公里"[N]. 科技日报, 2023-07-25(04).
	LIU X. Artificial intelligence assists in the"last mile"[N]. Logistics Science and Technology Daily, 2023-07-25(04). (in Chinese)
2	吕宗旺, 吴建军, 孙福艳, 等. 现代智慧粮库系统的设计与研究. 河南工业大学学报(自然科学版), 2013, 34 (5): 79- 82.
	LÜ Z W , WU J J , SUN F Y , et al. Research and design of modern smart grain depot system. Journal of Henan University of Technology (Natural Science Edition), 2013, 34 (5): 79- 82.
3	陶德馨. 智慧港口发展现状与展望. 港口装卸, 2017 (1): 1- 3. doi: 10.3963/j.issn.1000-8969.2017.01.001
	TAO D X . The current development situation and prospect of intelligent port. Port Operation, 2017 (1): 1- 3. doi: 10.3963/j.issn.1000-8969.2017.01.001
4	孙羽, 汪沛. 无人驾驶技术在未来智慧港口的应用. 珠江水运, 2019 (23): 5- 7.
	SUN Y , WANG P . Application of autonomous driving technology in future smart ports. Pearl River Water Transport, 2019 (23): 5- 7.
5	张捍东, 郑睿, 岑豫皖. 移动机器人路径规划技术的现状与展望. 系统仿真学报, 2005, 17 (2): 439- 443. doi: 10.3969/j.issn.1004-731X.2005.02.050
	ZHANG H D , ZHENG R , CEN Y W . Present situation and prospect of path planning technology for mobile robots. Journal of System Simulation, 2005, 17 (2): 439- 443. doi: 10.3969/j.issn.1004-731X.2005.02.050
6	霍凤财, 迟金, 黄梓健, 等. 移动机器人路径规划算法综述. 吉林大学学报(信息科学版), 2018, 36 (6): 639- 647. doi: 10.3969/j.issn.1671-5896.2018.06.007
	HUO F C , CHI J , HUANG Z J , et al. Review of path planning for mobile robots. Journal of Jilin University (Information Science Edition), 2018, 36 (6): 639- 647. doi: 10.3969/j.issn.1671-5896.2018.06.007
7	成伟明, 唐振民, 赵春霞, 等. 移动机器人路径规划中的图方法应用综述. 工程图学学报, 2008, 29 (4): 6- 14. doi: 10.3969/j.issn.1003-0158.2008.04.002
	CHENG W M , TANG Z M , ZHAO C X , et al. A survey of mobile robots path planning using geometric methods. Journal of Engineering Graphics, 2008, 29 (4): 6- 14. doi: 10.3969/j.issn.1003-0158.2008.04.002
8	DIJKSTRA E W . A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1 (1): 269- 271. doi: 10.1007/BF01386390
9	HART P , NILSSON N , RAPHAEL B . A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968, 4 (2): 100- 107. doi: 10.1109/TSSC.1968.300136
10	DOLGOV D, THRUN S, MONTEMERLO M, et al. Practical search techniques in path planning for autonomous driving[C]//Proceedings of the 1st International Symposium on Search Techniques in Artificial Intelligence and Robotics. Washington D. C., USA: Press, 2008: 32-37.
11	SCHWARTING W , ALONSO-MORA J , RUS D . Planning and decision-making for autonomous vehicles. Annual Review of Control, Robotics, and Autonomous Systems, 2018 (1): 187- 210.
12	柏鉴, 徐元浩, 冀杰, 等. 基于图搜索和几何曲线的自主代客泊车路径规划. 重庆理工大学学报(自然科学), 2022, 36 (6): 115- 125.
	BAI J , XU Y H , JI J , et al. Path planning for automate valet parking based on graph search and geometry curve. Journal of Chongqing University of Technology (Natural Science), 2022, 36 (6): 115- 125.
13	ZHANG Z , WAN Y H , WANG Y , et al. Improved hybrid A* path planning method for spherical mobile robot based on pendulum. International Journal of Advanced Robotic Systems, 2021, 18 (1): 671- 680.
14	崔高健, 陆柏霖, 贺红春, 等. 基于逆向Hybrid A* 的自动泊车路径规划. 长春工业大学学报, 2022, 43 (S1): 627- 633.
	CUI G J , LU B L , HE H C , et al. Path planning based on inverted Hybrid A* for autonomous parking. Journal of Changchun University of Technology, 2022, 43 (S1): 627- 633.
15	TANG B J , HIROTA K , WU X D , et al. Path planning based on improved hybrid A* Algorithm. Journal of Advanced Computational Intelligence and Intelligent Informatics, 2021, 25 (1): 64- 72.
16	任秉韬, 王淅淅, 邓伟文, 等. 基于混合A* 和可变半径RS曲线的自动泊车路径优化方法. 中国公路学报, 2022, 35 (7): 317- 327.
	REN B T , WANG X X , DENG W W , et al. Path optimization algorithm for automatic parking based on hybrid A* and reeds-shepp curve with variable radius. China Journal of Highway and Transport, 2022, 35 (7): 317- 327.
17	REEDS J , SHEPP L . Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics, 1990, 145 (2): 367- 393.
18	ELFES A . Using occupancy grids for mobile robot perception and navigation. Computer, 1989, 22 (6): 46- 57.
19	刘依卓. 无人车全局路径规划与局部避障方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2021.
	LIU Y Z. Research on global path planning and local obstacle avoidance for unmanned vehicles[D]. Harbin: Harbin Engineering University, 2021. (in Chinese)
20	汪丽娟, 钱育蓉, 侯海耀, 等. 基于k-d树分区的聚类算法并行加速策略. 计算机工程与设计, 2019, 40 (12): 3437- 3442.
	WANG L J , QIAN Y R , HOU H Y , et al. Parallel acceleration strategy of clustering algorithm based on k-d tree partition. Computer Engineering and Design, 2019, 40 (12): 3437- 3442.
21	齐尧, 徐友春, 李华, 等. 一种基于改进混合A* 的智能车路径规划算法. 军事交通学院学报, 2018 (8): 85- 90.
	QI Y , XU Y C , LI H , et al. Hybrid A* algorithm-based path planning for intelligent vehicle. Journal of Military Transportation University, 2018 (8): 85- 90.
22	任孝平, 蔡自兴. 基于阿克曼原理的车式移动机器人运动学建模. 智能系统学报, 2009, 4 (6): 534- 537.
	REN X P , CAI Z X . Using the Ackerman principle for kinematic modeling of wheeled mobile robots. Transactions on Intelligent Systems, 2009, 4 (6): 534- 537.
23	安峰. 基于开源操作系统ROS的机器人软件开发. 单片机与嵌入式系统应用, 2017, 17 (5): 27-29, 33.
	AN F . Robot software development based on open-source operating system ROS. Microcontrollers & Embedded Systems, 2017, 17 (5): 27-29, 33.
24	徐正鹏. 基于MEMS IMU的车载组合导航技术研究[D]. 武汉: 武汉大学, 2017.
	XU Z P. Research on vehicle integrated navigation technology based on MEMS IMU[D]. Wuhan: Wuhan University, 2017. (in Chinese)

[1]	ZHOU Qing, PAN Fan'an, CHEN Wenchong, JIANG Bo. Research on Selective Crowdsourcing and Path Planning of Logistics Services for Industrial Internet Platform [J]. Computer Engineering, 2025, 51(4): 360-372.
[2]	LI Shuyi, YANG Bo, CHEN Ling, SHEN Ling, TANG Wensheng. Surface Coverage Method Based on PPO with Adaptive Reward Function [J]. Computer Engineering, 2025, 51(3): 86-94.
[3]	CHEN Hao, CHEN Jun, LIU Fei. Research on Path Planning of Mobile Robots Based on Autonomous Exploration [J]. Computer Engineering, 2025, 51(1): 60-70.
[4]	ZHANG Guosheng, LI Caihong, ZHANG Yaoyu, ZHOU Ruihong, LIANG Zhenying. Robot Local Path Planning Based on Improved Artificial Potential Field Method [J]. Computer Engineering, 2025, 51(1): 88-97.
[5]	Zhite WANG, Liping LUO, Yikui LIAO. Mobile Robot Path Planning by Improved A^* Algorithm Fused with Improved Dynamic Window Approach [J]. Computer Engineering, 2024, 50(8): 86-101.
[6]	LIU Guoming, LI Caihong, LI Yongdi, ZHANG Guosheng, ZHANG Yaoyu, GAO Tengteng. Local Path Planning of Robot Based on Improved PPO Algorithm [J]. Computer Engineering, 2023, 49(2): 119-126,135.
[7]	Qiru LI, Xia GENG. Robot Path Planning Based on Improved DQN Algorithm [J]. Computer Engineering, 2023, 49(12): 111-120.
[8]	ZHAN Jingwu, HUANG Yiqing. Path Planning of Robot Combing Safety A^* Algorithm and Dynamic Window Approach [J]. Computer Engineering, 2022, 48(9): 105-112,120.
[9]	MA Huawei, MA Kai, GUO Jun. Research on Vehicle Routing Problem with Drones Considering Multi-Delivery [J]. Computer Engineering, 2022, 48(8): 299-305.
[10]	LI Guanda, JIN Jing, WANG Fan, XIA Yingwei, YANG Xuezhi. Efficient Path Planning Algorithm Using Topology for Indoor Environment [J]. Computer Engineering, 2022, 48(6): 95-106.
[11]	YANG Siming, SHAN Zheng, CAO Jiang, GUO Jiayu, GAO Yuan, GUO Yang, WANG Ping, WANG Jing, WANG Xiaonan. Application of Model-Based Reinforcement Learning in Path Planning of Unmanned Aerial Vehicle [J]. Computer Engineering, 2022, 48(12): 255-260,269.
[12]	GAO Wanbo, ZHU Junwu, ZHANG Yonglong, ZHANG Xiaowei. Unmanned Vehicle Path Planning Based on Selection Crossover Fireworks Algorithm [J]. Computer Engineering, 2022, 48(11): 314-320.
[13]	HUANG Yifan, HU Likun, XUE Wenchao. Mobile Robot Path Planning Based on Improved RRT-Connect Algorithm [J]. Computer Engineering, 2021, 47(8): 22-28.
[14]	YAN Jiaojie, ZHANG Qieshi, HU Xiping. Review of Path Planning Techniques Based on Reinforcement Learning [J]. Computer Engineering, 2021, 47(10): 16-25.
[15]	LIU Qingzhou, WU Feng. Research Progress of Multi-Agent Path Planning [J]. Computer Engineering, 2020, 46(4): 1-10.

Please choose a citation manager

Content to export