An Adaptive Robot Path Planning Based on Improved REA* Algorithm

doi:10.16182/j.issn1004731x.joss.24-1327

Abstract

Abstract:

In order to improve the computational efficiency and path smoothness in a robot's global path planning, an adaptive robot path planning strategy based on an improved unilateral rectangle expansion A*(REA*) algorithm was proposed. The robot's operational safety was ensured by setting a buffer around obstacles. A passable interval formed by unilateral rectangle expansion was used as the operation unit, and bidirectional alternating search was combined to enhance the path planning efficiency. Inspired by potential field theory, the evaluation function was optimized by introducing a vector form to achieve fast adaptive obstacle avoidance. A new path planning strategy was proposed tooptimize the path smoothness. The simulation results show that compared with the classical A* algorithm, the REA* algorithm, and other algorithms, the proposed algorithm can find the shortest and smoothest path within the shortest time.

Key words: path planning, REA* algorithm, bidirectional alternating search, adaptive evaluation function, path smoothness

CLC Number:

TP391.9

Zhu Ling, Li Jing, Zhang Zhaohui. An Adaptive Robot Path Planning Based on Improved REA* Algorithm[J]. Journal of System Simulation, 2026, 38(2): 332-345.

Figures/Tables 15

Fig. 1

Table 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 2

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Table 3

Fig. 12

References 17

[1]	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.
[2]	Li Haodong, Zhao Tao, Songyi Dian. Forward Search Optimization and Subgoal-based Hybrid Path Planning to Shorten and Smooth Global Path for Mobile Robots[J]. Knowledge-Based Systems, 2022, 258: 110034.
[3]	Duraklı Zafer, Nabiyev Vasif. A New Approach Based on Bezier Curves to Solve Path Planning Problems for Mobile Robots[J]. Journal of Computational Science, 2022, 58: 101540.
[4]	Feng Haobo, Hu Qiao, Zhao Zhenyi, et al. Smooth Path Planning Under Maximum Curvature Constraints for Autonomous Underwater Vehicles Based on Rapidly-exploring Random Tree Star with B-spline Curves[J]. Engineering Applications of Artificial Intelligence, 2024, 133, Part F: 108583.
[5]	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26
	Tang Yunchao, Qi Shaojun, Zhu Lixue, et al. Obstacle Avoidance Motion in Mobile Robotics[J]. Journal of System Simulation, 2024, 36(1): 1-26.
[6]	Ye Lei, Wu Fengyun, Zou Xiangjun, 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.
[7]	Chen Xinqiang, Liu Shuhao, Zhao Jiansen, et al. Autonomous Port Management Based AGV Path Planning and Optimization Via an Ensemble Reinforcement Learning Framework[J]. Ocean & Coastal Management, 2024, 251: 107087.
[8]	张瑞, 周丽, 刘正洋. 融合RRT^*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT^* and Dynamic Window Approach[J]. Journal of System Simulation, 2024, 36(4): 957-968.
[9]	Sun Yuekun, Tong Xiaochong, Lei Yi, et al. A Multi-scale Path-planning Method for Large-scale Scenes Based on a Framed Scale-elastic Grid Map[J]. International Journal of Digital Earth, 2024, 17(1): 2383852.
[10]	Huang Chen, Zhou Xiangbing, Ran Xiaojuan, et al. Adaptive Cylinder Vector Particle Swarm Optimization with Differential Evolution for UAV Path Planning[J]. Engineering Applications of Artificial Intelligence, 2023, 121: 105942.
[11]	Zhang Jie, Chen Dugui, Han Guangjie, et al. Formation Path Planning for Collaborative Autonomous Underwater Vehicles Based on Consensus-sparrow Search Algorithm[J]. IEEE Internet of Things Journal, 2024, 11(8): 13810-13823.
[12]	Zhang Shuai, Yu Deshen, Sang Hongqiang, et al. A New Hybrid Path Planning Method for the Sailboat Architecture Wave Glider in the Wind Field Environment[J]. Ocean Engineering, 2023, 283: 115153.
[13]	Dai Jun, Zhang Yi, Deng Hua. Novel Potential Guided Bidirectional RRT^* with Direct Connection Strategy for Path Planning of Redundant Robot Manipulators in Joint Space[J]. IEEE Transactions on Industrial Electronics, 2024, 71(3): 2737-2747.
[14]	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.
[15]	Yu Jiabin, Yang Meng, Zhao Zhiyao, et al. Path Planning of Unmanned Surface Vessel in an Unknown Environment Based on Improved D^* Lite Algorithm[J]. Ocean Engineering, 2022, 266, Part 3: 112873.
[16]	Zhang An, Li Chong, Bi Wenhao. Rectangle Expansion A^∗ Pathfinding for Grid Maps[J]. Chinese Journal of Aeronautics, 2016, 29(5): 1385-1396.
[17]	Xu Xing, Zeng Jiazhu, Zhao Yun, et al. Research on Global Path Planning Algorithm for Mobile Robots Based on Improved A^* [J]. Expert Systems with Applications, 2024, 243: 122922.

矩阵元素数值	对应颜色	含义
1	白色	未阻塞单元NO
2	蓝色	阻塞单元O
3	浅蓝色	安全缓冲区域SBA
5	橘色	路径点PN
6	黄色	正向通行区间FPI
7	绿色	反向通行区间RPI

方向	向量	对应数字	方向	向量	对应数字
北	[-1, 0]	1	西	[0, -1]	3
南	[1, 0]	2	东	[0, 1]	4

地图	算法	A*	JPS	REA*	SBREA*	改进REA*
A型	平均搜索时间/s	2.74	0.14	0.06	0.27	0.11
	路径长度/m	98.63	93.11	96.29	94.48	87.84
	扩展次数	559	31	32	25	19
	转向角度和/(˚)	900.00	675.00	510.26	531.08	338.40
	转角数	19	15	12	12	10
	相对平滑度	1.00	1.33	1.76	1.69	2.66
B型	平均搜索时间/s	5.10	0.14	0.04	0.21	0.09
	路径长度/m	168.47	146.28	150.25	166.78	148.98
	扩展次数	1 075	31	21	18	13
	转向角度和/(˚)	2 070.00	945.00	852.97	908.08	858.17
	转角数	43	21	11	13	11
	相对平滑度	1.00	2.19	2.43	2.28	2.41
C型	平均搜索时间/s	1.19	0.19	0.08	0.27	0.12
	路径长度/m	236	47	39	23	25
	扩展次数	66.50	64.25	71.97	64.17	64.06
	转向角度和/(˚)	1 305.00	675.00	1 014.60	423.11	670.19
	转角数	26	15	27	20	23
	相对平滑度	1.00	1.93	1.29	3.08	1.95