An Improved Path Planning Algorithm for Mobile Robots

doi:10.16182/j.issn1004731x.joss.23-0585

Abstract

Abstract:

To solve the problems of invalid sampling and non-optimal paths of the RRT, the quasi-stream avoidance algorithm is proposed. The RRT algorithm is introduced to specify the sampling interval to limit the sampling points and enhance the goal-oriented nature of sampling. The quasi-stream avoidance algorithm incorporating the A* algorithm (QSA*) is used to quickly bypass the obstacle when it is encountered. A path optimization algorithm is used to smooth the searched path. The simulation results show that compared with the RRT algorithm, the computation time of the RRT-QSA* algorithm is reduced by 96.83%~99.88%, the number of search nodes is reduced by 86.62%~96.01%, the number of path lengths is reduced by 9.9%~16.7%, and the turning angle decreased by 80.93%~93.04%. The RRT-QSA* algorithm shows a more intense improvement in computational efficiency than the RRT algorithm as the map size increases.

Key words: mobile robots, path planning, RRT, path optimization, Turtlebot2

CLC Number:

TP242.6

Sun Haijie, San Hongjun, Xiao Le, Yao Dexin, Chen Jiupeng, Yang Xiaoyuan. An Improved Path Planning Algorithm for Mobile Robots[J]. Journal of System Simulation, 2024, 36(9): 2193-2207.

Figures/Tables 27

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 1

Table 2

Correspondence table of flow conditions (clockwise)

流动	模式	极端限定条件	流动条件
$↑$	M1-Fig.6(1)	\	U0, RU1, R0
	M2-Fig.6(5)	\	R1, RU1, U0
	M3-Fig.6(14)	j=0	R1, RU1, U0
	M3-Fig.6(13)	j=0 & i=R	RU1, U0
$↗$	M2-Fig.6(6)	\	R1, U0, RU0
$↗$	M3-Fig.6(14)	j=0	R1, U0, RU0
$→$	M1-Fig.6(2)	\	R0, RD1, D0
	M2-Fig.6(7)	\	D1, RD1, R0
	M3-Fig.6(16)	i=0	D1, RD1, R0
	M3-Fig.6(15)	i=0 & j=0	RD1, R0
$↘$	M2-Fig.6(8)	\	D1, RD0, R0
$↘$	M3-Fig.6(16)	i=0	D1, R0, RD0
$↓$	M1-Fig.6(3)	\	D0, LD1, L0
	M2-Fig.6(9)	\	L1, LD1, D0
	M3-Fig.6(19)	j=C	L1, LD1, D0
	M3-Fig.6(17)	i=0 & j=C	LD1, D0
$↙$	M2-Fig.6(10)	\	L1, D0, LD0
$↙$	M3-Fig.6(19)	j=C	L1, LD0, D0
$←$	M1-Fig.6(3)	\	L0, LU1, U0
	M2-Fig.6(4)	\	U1, LU1, L0
	M3-Fig.6(20)	i=R	U1, LU1, L0
	M3-Fig.6(18)	i=R & j=C	LU1, L0
$↖$	M2-Fig.6(12)	\	U1, L0, LU0
$↖$	M3-Fig.6(20)	i=R	U1, LU0, L0

Table 2

Table 3

Correspondence table of flow conditions (counter-clockwise)

流动	模式	极端限定条件	流动条件
$↓$	M1-Fig.7(1)	\	D0, RD1, R0
	M2-Fig.7(5)	\	R1, RD1, D0
	M3-Fig.7(14)	j=0	R1, RD1, D0
	M3-Fig.7(13)	j=0 & i=0	RD1, D0
$↘$	M2-Fig.7(6)	\	R1, RD0, D0
$↘$	M3-Fig.7(14)	j=0	R1, D0, RD0
$→$	M1-Fig.7(2)	\	R0, RU1, U0
	M2-Fig.7(7)	\	U1, RU1, R0
	M3-Fig.7(16)	i=R	U1, RU1, R0
	M3-Fig.7(15)	i=R & j=0	RU1, R0
$↗$	M2-Fig.7(8)	\	U1, R0, RU0
$↗$	M3-Fig.7(16)	i=R	U1, R0, RU0
$↑$	M1-Fig.7(3)	\	U0, LU1, L0
	M2-Fig.7(9)	\	L1, LU1, U0
	M3-Fig.7(19)	j=C	L1, LU1, U0
	M3-Fig.7(17)	i=R & j=C	LU1, U0
$↖$	M2-Fig.7(10)	\	L1, U0, LU0
$↖$	M3-Fig.7(19)	j=C	L1, LU0, U0
$←$	M1-Fig.7(3)	\	L0, LD1, D0
	M2-Fig.7(4)	\	D1, LD1, L0
	M3-Fig.7(20)	i=0	D1, LD1, L0
	M3-Fig.7(18)	i=0 & j=C	LD1, L0
$↙$	M2-Fig.7(12)	\	D1, L0, LD0
$↙$	M3-Fig.7(20)	i=0	D1, LD0, L0

Table 3

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Table 4

Fig. 14

Table 5

Fig. 15

Table 6

Table 7

Algorithms statistics comparison (different maps)

参数	算法	50×50	100×100	150×150	200×200
时间/s	RRT	0.41 $±$ 0.34	3.39 $±$ 3.08	32.62 $±$ 21.39	102.39 $±$ 79.16
	RRT-QSA*	0.013 $±$ 0.01	0.07 $±$ 0.03	0.14 $±$ 0.05	0.16 $±$ 0.04
	A*	0.013 $±$ 0.02	0.04 $±$ 0.02	0.07 $±$ 0.01	0.12 $±$ 0.08
转折点数	RRT	553 $±$ 129	1 714 $±$ 674	5 074 $±$ 1529	9 331 $±$ 2 546
	RRT-QSA*	74 $±$ 46	183 $±$ 253	269 $±$ 57	372 $±$ 26
	A*	225 $±$ 0	431 $±$ 0	680 $±$ 0	951 $±$ 0
路径长度	RRT	94.1 $±$ 6.04	183.67 $±$ 10.69	283.78 $±$ 10.41	349.82 $±$ 18.34
	RRT-QSA*	78.3 $±$ 4.31	159.39 $±$ 6.19	244.71 $±$ 9.70	315.18 $±$ 10.68
	A*	76.9 $±$ 0	173.39 $±$ 0	242.93 $±$ 0	299.59 $±$ 0
转折角度/(°)	RRT	1 767 $±$ 133.84	3 440 $±$ 253.66	5 383 $±$ 302.93	6 713 $±$ 513.79
	RRT-QSA*	337 $±$ 8.99	290 $±$ 13.74	599 $±$ 73.86	467 $±$ 79.16
	A*	279 $±$ 0	242 $±$ 0	451.9 $±$ 0	448.21 $±$ 0

Table 7

Fig. 16

Fig. 17

Fig. 18

Fig. 19

Table 8

References 20

1	Patle B K, Ganesh Babu L, Pandey Anish, et al. A Review: On Path Planning Strategies for Navigation of Mobile Robot[J]. Defence Technology, 2019, 15(4): 582-606.
2	Liu Lixing, Wang Xu, Yang Xin, et al. Path Planning Techniques for Mobile Robots: Review and Prospect[J]. Expert Systems with Applications, 2023, 227: 120254.
3	林韩熙, 向丹, 欧阳剑, 等. 移动机器人路径规划算法的研究综述[J]. 计算机工程与应用, 2021, 57(18): 38-48.
	Lin Hanxi, Xiang Dan, Ouyang Jian, et al. Review of Path Planning Algorithms for Mobile Robots[J]. Computer Engineering and Applications, 2021, 57(18): 38-48.
4	Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
5	Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
6	Koenig S, Likhachev M. Fast Replanning for Navigation in Unknown Terrain[J]. IEEE Transactions on Robotics, 2005, 21(3): 354-363.
7	Lavalle S M. Rapidly-exploring Random Trees: A New Tool for Path Planning[J]. Research Report, 1999, 98(11): 1-4.
8	Wang Jiankun, Meng M Q H, Khatib O. EB-RRT: Optimal Motion Planning for Mobile Robots[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 2063-2073.
9	Liao Bin, Wan Fangyi, Hua Yi, et al. F-RRT^*: An Improved Path Planning Algorithm with Improved Initial Solution and Convergence Rate[J]. Expert Systems with Applications, 2021, 184: 115457.
10	陈秋莲, 蒋环宇, 郑以君. 机器人路径规划的快速扩展随机树算法综述[J]. 计算机工程与应用, 2019, 55(16): 10-17.
	Chen Qiulian, Jiang Huanyu, Zheng Yijun. Summary of Rapidly-exploring Random Tree Algorithm in Robot Path Planning[J]. Computer Engineering and Applications, 2019, 55(16): 10-17.
11	赵文龙, Yahouza M Sani Abdou. 基于改进RRT算法的移动机器人路径规划方法[J]. 计算机与数字工程, 2022, 50(8): 1733-1738.
	Zhao Wenlong, Yahouza M Sani Abdou. Path Planning Method Based on Improved RRT Algorithm for Mobile Robot[J]. Computer & Digital Engineering, 2022, 50(8): 1733-1738.
12	张伟民, 付仕雄. 基于改进RRT*算法的移动机器人路径规划[J]. 华中科技大学学报(自然科学版), 2021, 49(1): 31-36.
	Zhang Weimin, Fu Shixiong. Mobile Robot Path Planning Based on Improved RRT^* Algorithm[J]. Journal of Huazhong University of Science and Technology(Nature Science Edition), 2021, 49(1): 31-36.
13	Li Yanjie, Wei Wu, Gao Yong, et al. PQ-RRT^*: An Improved Path Planning Algorithm for Mobile Robots[J]. Expert Systems with Applications, 2020, 152: 113425.
14	Wang Jiankun, Li Baopu, Meng M Q H. Kinematic Constrained Bi-directional RRT with Efficient Branch Pruning for Robot Path Planning[J]. Expert Systems with Applications, 2021, 170: 114541.
15	Zhou Ying, Zhang Endong, Guo Hongling, et al. Lifting Path Planning of Mobile Cranes Based on an Improved RRT Algorithm[J]. Advanced Engineering Informatics, 2021, 50: 101376.
16	张瑞, 周丽, 刘正洋. 融合RRT^*与DWA算法的移动机器人动态路径规划[J/OL]. 系统仿真学报. (2023-03-24) [2024-03-18]. .
	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT^* and Dynamic Window Approach[J/OL]. Journal of System Simulation. (2023-03-24) [2024-03-18]. .
17	Miao Changwei, Chen Guangzhu, Yan Chengliang, et al. Path Planning Optimization of Indoor Mobile Robot Based on Adaptive Ant Colony Algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230.
18	孙瑞, 张文胜. 基于改进蚁群算法的移动机器人平滑路径规划[J]. 图学学报, 2019, 40(2): 344-350.
	Sun Rui, Zhang Wensheng. Smooth Path Planning of Mobile Robot Based on Improved Ant Colony Algorithm[J]. Journal of Graphics, 2019, 40(2): 344-350.
19	Zhong Xunyu, Tian Jun, Hu Huosheng, et al. Hybrid Path Planning Based on Safe A^* Algorithm and Adaptive Window Approach for Mobile Robot in Large-scale Dynamic Environment[J]. Journal of Intelligent & Robotic Systems, 2020, 99(1): 65-77.
20	Li Changgeng, Huang Xia, Ding Jun, et al. Global Path Planning Based on a Bidirectional Alternating Search A^*Algorithm for Mobile Robots[J]. Computers & Industrial Engineering, 2022, 168: 108123.

流动条件	含义	符号
field [i, j+1]	向右搜索	R
field [i+1, j]	向下搜索	D
field [i, j-1]	向左搜索	L
field [i-1, j]	向上搜索	U
field [i+1, j+1]	向右下搜索	RD
field [i-1, j+1]	向右上搜索	RU
field [i+1, j-1]	向左下搜索	LD
field [i-1, j-1]	向左上搜索	LU
= 0	搜索结果为可通行区域	0
= 1	搜索结果为可障碍物	1

指标	RRT
指标	时间/s	路径长度	节点数	转折角度/(°)
均值	0.25	87.74	483.80	1 861.75
标准差	0.26	3.27	206.32	251.30
最大值	0.87	110.65	878	2 252.23
最小值	0.02	72.15	185	1 513.73
指标	RRT-QSA*
指标	时间/s	路径长度	节点数	转折角度/(°)
均值	0.004	42.86	50.67	305.51
标准差	0.003	1.79	2.72	6.95
最大值	0.015	46.45	53	308.99
最小值	0.002	41.96	45	291.59

指标	RRT				RRT-QSA*
指标	时间/s	路径长度	节点数	转折角度/(°)	时间/s	路径长度	节点数	转折角度/(°)
均值	0.20	89.89	387.80	1 804.36	0.03	81.91	74.40	377.35
标准差	0.16	3.27	81.42	114.65	0.01	2.09	47.36	42.26
最大值	0.66	95.09	547	1 988.53	0.03	86.35	216	470.11
最小值	0.05	84.61	243	1 632.59	0.02	78.52	53	321.51

指标	RRT				RRT-QSA*
指标	时间/s	路径长度	节点数	转折角度/(°)	时间/s	路径长度	节点数	转折角度/(°)
均值	6.20	279.82	2 205.86	4 639.15	0.013	203.76	312.50	438.32
标准差	5.50	16.66	728.86	387.67	0.002	2.36	9.20	6.95
最大值	21.49	309.60	3 745	5 363.13	0.017	208.87	326	490.75
最小值	1.64	250.98	1 217	4 064.18	0.001	201.45	297	419.63

算法	S1-G1	S2-G2
RRT	1.5309	2.0347
RRT-QSA*	0.0326	0.0365