Application of Improved PSO-PH-RRT* Algorithm in Intelligent Vehicle Path Planning

doi:10.12068/j.issn.1005-3026.2025.20239047

Abstract

Abstract:

In application scenarios like robot control and autonomous navigation of intelligent vehicle， path planning needs to account for factors including obstacles and terrain. To address the issues of directionless expansion target and low efficiency in rapidly-exploring random tree （RRT） algorithm in path planning， a particle swarm optimization for probabilistically homogeneous rapidly-exploring random tree （PSO-PH-RRT*） algorithm is proposed. This algorithm base on the probabilistically homogeneous rapidly-exploring random tree （PH-RRT*） algorithm by using the particle swarm optimization algorithm to update the probability of direction as the velocity direction for random tree nodes， thereby improving the node position update strategy. It also uses the distance between the node and the target vector， along with trajectory smoothness， as the fitness function in the particle swarm optimization algorithm. Finally， simulations across various scenarios demonstrate that the PSO-PH-RRT* algorithm can significantly reduce iteration time costs while improving path length and smoothness.

Key words: path planning, RRT algorithm, improved particle swarm optimization algorithm, target vector, cost function, fitness function

CLC Number:

TP 242.6

Qi-long JIANG, Jian XU. Application of Improved PSO-PH-RRT* Algorithm in Intelligent Vehicle Path Planning[J]. Journal of Northeastern University(Natural Science), 2025, 46(3): 12-19.

Figures/Tables 13

Fig.1 Node expansion schematic diagram of RRT* algorithm

Fig.2 Expanded random tree flowchart of RRT* algorithm

Fig.3 Rewire flowchart of RRT* algorithm

Fig.4 Node expansion schematic diagram of PH-RRT* algorithm

Fig.5 Definition of cost function

Fig.6 Definition of direction constraint angle γ

Fig.7 PSO-PH-RRT* algorithm flowchart

Fig.8 PSO-PH-RRT* algorithm fitness function value change curve

Table 1 Optimization algorithm and cost function comparative experiment plans

算法	步长代价函数	距离代价函数
原始RRT*算法	RRT*（lC）	RRT*（E）
均匀概率改进的RRT*算法	PH-RRT*（lC）	PH-RRT*（E）
粒子群优化的均匀概率RRT*算法	PSO-PH-RRT*（lC）	PSO-PH-RRT*（E）

Table 2 Main parameters in the program

参数	设定值
随机树增加步长ρ	5
均匀概率参数值P	0.9
补偿范围r	5
迭代次数h	50
学习因子c_h	1
惯性因子初值w₀	0.5

Fig.9 Repeated experimental box plot in random obstacle environment

Fig.10 Experiment results statistical chart

Fig.11 Planning paths consequence

References 17

1	车建涛，高方玉，解玉文，等. 基于Dijkstra算法的水下机器人路径规划［J］. 机械设计与研究， 2020， 36（1）：44-48.
	Che Jian-tao， Gao Fang-yu， Xie Yu-wen， et al. Path planning of underwater robot based on Dijkstra algorithm［J］. Machine Design & Research， 2020， 36（1）：44-48.
2	Tang F. Coverage path planning of unmanned surface vehicle based on improved biological inspired neural network［J］. Ocean Engineering， 2023， 278：114354.
3	Madridano Á， Kaff A， Martín D， et al. Trajectory planning for multi-robot systems：methods and applications［J］. Expert Systems with Applications， 2021， 173：114660.
4	La S M， Kuffner J J Jr. Randomized kinodynamic planning［J］. The International Journal of Robotics Research， 2001， 20（5）：378-400.
5	Urmson C， Simmons R. Approaches for heuristically biasing RRT growth［C］//RSJ International Conference on Intelligent Robots and Systems. Las Vegas， 2003：1178-1183.
6	Li Z， Ma H B， Zhang X F， et al. Path planning of the dual-arm robot based on VT-RRT algorithm［C］//Chinese Control Conference. Guangzhou： 2019：4359-4364.
7	Kuffner J J， LaValle S M. RRT-connect： an efficient approach to single-query path planning［C］//IEEE International Conference on Robotics and Automation. San Francisco， 2000：995-1001.
8	Karaman S， Frazzoli E. Sampling-based algorithms for optimal motion planning［J］. The International Journal of Robotics Research， 2011， 30（7）：846-894.
9	Wang B Y， Liu Z， Li Q B， et al. Mobile robot path planning in dynamic environments through globally guided reinforcement learning［J］. IEEE Robotics and Automation Letters， 2020， 5（4）： 6932-6939.
10	Noreen I， Khan A， Habib Z. A comparison of RRT， RRT* and RRT*-smart path planning algorithms［J］. International Journal of Computer Science and Network Security， 2016， 16（10）：20-27.
11	Hess R， Jerg R， Lindeholz T， et al. SRRT*-a probabilistic optimal trajectory planner for problematic area structures［J］. IFAC-PapersOnLine， 2016， 49（30）：331-336.
12	白晓兰，周文全，张振朋，等. 基于启发式粒子群算法的机器人平滑路径规划［J］. 组合机床与自动化加工技术， 2022（8）：44-47，52.
	Bai Xiao-lan， Zhou Wen-quan， Zhang Zhen-peng， et al. Smooth path planning of wheeled robot based on heuristic particle swarm optimization algorithm［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2022（8）：44-47，52.
13	屈新怀，单笛，孟冠军. 基于靠近目标粒子群算法的AGV路径规划［J］. 合肥工业大学学报（自然科学版）， 2022， 45（1）：1-6.
	Qu Xin-huai， Shan Di， Meng Guan-jun. AGV path planning based on particle swarm optimization approaching the target ［J］. Journal of Hefei University of Technology（Natural Science Edition）， 2022， 45（1）：1-6.
14	Lin S W， Liu A， Wang J G， et al. An intelligence-based hybrid PSO-SA for mobile robot path planning in warehouse［J］. Journal of Computational Science， 2023， 67：101938.
15	Krell E， Sheta A， Balasubramanian A P R， al et， Collision-free autonomous robot navigation in unknown environments utilizing PSO for path planning［J］.Journal of Artificial Intelligence and Soft Computing Research， 2019， 9（4）：267-282.
16	彭君. 改进RRT算法在移动机器人路径规划中的应用研究［D］. 南京：南京邮电大学， 2022.
	Peng Jun. Application of improved RRT algorithm in mobile robot path planning［D］.Nanjing： Nanjing University of Posts and Telecommunications， 2022.
17	左国玉，陈国栋，刘月雷，等. 基于均匀概率的目标启发式RRT机械臂路径规划方法［J］. 北京工业大学学报， 2022， 48（8）：812-821.
	Zuo Guo-yu， Chen Guo-dong， Liu Yue-lei， et al. Target heuristic RRT based on uniform probability for manipulator path planning［J］. Journal of Beijing University of Technology， 2022， 48（8）：812-821.

[1]	Yu-long PEI, Shuang-zhu ZHAI. Active Obstacle Avoidance Path Planning for Multi-scenario Autonomous Vehicles Under Icy and Snowy Road Conditions [J]. Journal of Northeastern University(Natural Science), 2025, 46(3): 1-11.
[2]	Jin-hua XU, Fei WANG, Fei HAN, Yan LI. A Method for Path Planning of Multi-vehicles Collaboration with Multi-agricultural UAVs [J]. Journal of Northeastern University(Natural Science), 2024, 45(2): 296-304.
[3]	ZHAO Jun-tao， LUO Xiao-chuan， LIU Jun-mi. Application of Improved Whale Optimization Algorithm in Robot Path Planning [J]. Journal of Northeastern University(Natural Science), 2023, 44(8): 1065-1071.
[4]	LIU Xiao-xi， JIANG Hui-yan， LUO Min. Multi-constraint Optimal Puncture Path Planning Algorithm for Liver Cancer Ablation [J]. Journal of Northeastern University(Natural Science), 2023, 44(7): 922-930.
[5]	ZHAO Zhao， YUAN Pei-xin， TANG Jun-wen， CHEN Jin-lin. Agent Path Planning Algorithm Based on Improved SNN-HRL [J]. Journal of Northeastern University(Natural Science), 2023, 44(11): 1548-1555.
[6]	WANG Hai-fang， CUI Yang-yang， LI Ming-fei， LI Guang-yu. Mobile Robot Path Planning Algorithm Based on Improved RRT*FN [J]. Journal of Northeastern University(Natural Science), 2022, 43(9): 1217-1225.
[7]	LIU Qi-ran， LIAN Jing， CHEN Shi， FAN Rong. Motion Planning Algorithm of Autonomous Driving Considering Interactive Trajectory Prediction [J]. Journal of Northeastern University(Natural Science), 2022, 43(7): 930-936.
[8]	ZHANG Yu， LI Dong-sheng， WANG Zhi-wei， GONG Ya-dong. Shortest Tool Path Generation Method for STEP-NC Complex Pockets Based on Graph Theory and Improved Dijkstra Algorithm [J]. Journal of Northeastern University Natural Science, 2020, 41(9): 1285-1291.
[9]	LIU Jie， YAN Qing-dong， MA Yue， TANG Zheng-hua. Global Path Planning Based on Improved Ant Colony Optimization Algorithm for Geometry [J]. Journal of Northeastern University Natural Science, 2015, 36(7): 923-928.
[10]	JI Ce， WANG Yan-ru， WANG Xiao-yu. A New Complex Blind Source Separation Algorithm Based on Standard Kurtosis [J]. Journal of Northeastern University Natural Science, 2015, 36(5): 614-617.
[11]	LI Li， FANG Lijin， WANG Guoxun. Cutting Robot PostProcessing Method Based on STEPNC [J]. Journal of Northeastern University Natural Science, 2014, 35(11): 1612-1616.
[12]	HUANG Yue， WU Chengdong， DONG Jingjing， JIA Zixi. WSNbased Optimal Path Planning for Escaping from Disaster Scene [J]. Journal of Northeastern University, 2013, 34(2): 162-165.
[13]	ZHANG Qi， MA Jiacheng， XIE Wei， MA Liyong. Improved Ant Colony AlgorithmBased Path Planning for Mobile Robot〓 [J]. Journal of Northeastern University(Natural Science), 2013, 34(11): 1521-1524.