基于改进REA*算法的机器人自适应路径规划

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

摘要/Abstract

摘要：

为提高机器人全局路径规划的计算效率及路径平滑度，提出了一种基于改进单边矩形扩展（rectangle expansion A*，REA*)算法的机器人自适应路径规划策略。在障碍物周围设置缓冲区保障机器人运行的安全性；以矩形单边扩展形成的通行区间作为运算单位，结合双向交替搜索策略加速路径规划的效率；基于势场理论，引入向量形式优化评价函数自适应快速避障；提出一种新的路径规划策略以优化路径平滑度。仿真结果表明：与经典的A*算法及REA*算法等相比，该算法能够在更短时间内找到较短且平滑的路径。

关键词: 路径规划, REA*算法, 双向交替搜索, 自适应评价函数, 路径平滑度

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

中图分类号:

TP391.9

朱玲,李靖,张朝辉 . 基于改进REA*算法的机器人自适应路径规划[J]. 系统仿真学报, 2026, 38(2): 332-345.

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.

图/表 15

图1

表1

图2

图3

图4

图5

图6

表2

图7

图8

图9

图10

图11

表3

图12

参考文献 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