移动机器人用改进的双向A*二次路径规划算法

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

摘要/Abstract

摘要：

针对传统A*算法存在规划路径与障碍物相交、规划的路径拐点多和搜索时间长等问题，提出了一种面向室内环境改进的双向A*二次路径规划算法。通过对地图进行膨胀处理，解决了规划路径与障碍物相交的问题；通过引入新的启发函数和双向扩展等方法，提高了双向A*算法的搜索速度和精度；引入转弯代价函数和自适应权重，减少了拐点数量；利用二次规划和二阶贝塞尔曲线对路径进行平滑处理，删除了冗余节点和不符合实际移动的拐角。仿真结果表明：算法的搜索速度提高了55.7%，路径长度缩短了15.6%，拐点和拐角减小了31.6%和56.1%。

关键词: 评价函数, 路径平滑, 双向A*算法, 二次规划, 路径规划, 移动机器人

Abstract:

Aiming at the problems of the traditional A* algorithm, such as the unhoped intersection between the planned path and the obstacles, the planned path has many inflection points and the search time is long, an improved bidirectional A* quadratic path planning algorithm for the indoor environments is proposed. Through the expansion of the map, the intersection between the planned path and the obstacle is solved. By new heuristic functions and bidirectional expansion methods, the search speed and accuracy of the bidirectional A* algorithm are improved. Turning cost function and adaptive weight are introduced to reduce the number of turning points. Quadratic programming and second-order Bezier curves are used to smooth the path, and the redundant nodes and the corners that do not conform to actual movement are deleted. Simulation results show that, the search speed is increased by 55.7%, the path length is shortened by 15.6%, and the inflection points and corners are reduced by 31.6% and 56.1%.

Key words: evaluation function, path smoothing, bidirectional A* algorithm, quadratic programming, path planning, mobile robots

中图分类号:

TP242.6

李炯逸,李强,张新闻等 . 移动机器人用改进的双向A*二次路径规划算法[J]. 系统仿真学报, 2025, 37(2): 498-507.

Li Jiongyi,Li Qiang,Zhang Xinwen,et al . Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots[J]. Journal of System Simulation, 2025, 37(2): 498-507.

图/表 16

图1

表1

图2

表2

图3

图4

图5

图6

表3

图7

图8

图9

图10

图11

图12

图13

参考文献 18

1	Thi Thoa Mac, Copot Cosmin, Duc Trung Tran, et al. Heuristic Approaches in Robot Path Planning: A Survey[J]. Robotics and Autonomous Systems, 2016, 86: 13-28.
2	Jeddisaravi Kossar, Reza Javanmard Alitappeh, C A Pimenta Luciano, et al. Multi-objective Approach for Robot Motion Planning in Search Tasks[J]. Applied Intelligence, 2016, 45(2): 305-321.
3	吴宗胜. 室外移动机器人的道路场景识别及路径规划研究[D]. 西安: 西安理工大学, 2017.
	Wu Zongsheng. Research for the Road Scene Recognition and Path Planning for the Outdoor Mobile Robots[D]. Xi'an: Xi'an University of Technology, 2017.
4	Min Haitao, Xiong Xiaoyong, Wang Pengyu, et al. Autonomous Driving Path Planning Algorithm Based on Improved A^* Algorithm in Unstructured Environment[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 2021, 235(2/3): 513-526.
5	江洪, 蒋潇杰. 基于RRT改进的路径规划算法[J]. 重庆理工大学学报(自然科学), 2021, 35(7): 10-16, 124.
	Jiang Hong, Jiang Xiaojie. Improved Path Planning Algorithm Based on RRT[J]. Journal of Chongqing University of Technology(Natural Science), 2021, 35(7): 10-16, 124.
6	Yue Longwang, Chen Hanning. Unmanned Vehicle Path Planning Using a Novel Ant Colony Algorithm[J]. EURASIP Journal on Wireless Communications and Networking, 2019, 2019(1): 136.
7	邓修朋, 崔建明, 李敏, 等. 深度强化学习在机器人路径规划中的应用[J]. 电子测量技术, 2023, 46(6): 1-8.
	Deng Xiupeng, Cui Jianming, Li Min, et al. Application of Deep Reinforcement Learning in Robot Path Planning[J]. Electronic Measurement Technology, 2023, 46(6): 1-8.
8	Zhang Xin, Shi Xiaoxu, Zhang Zuqiong, et al. A DDQN Path Planning Algorithm Based on Experience Classification and Multi Steps for Mobile Robots[J]. Electronics, 2022, 11(14): 2120.
9	Wang Huanwei, Qi Xuyan, Lou Shangjie, et al. An Efficient and Robust Improved A^* Algorithm for Path Planning[J]. Symmetry, 2021, 13(11): 2213.
10	Saeed R A, Diego Reforgiato Recupero, Remagnino P. A Boundary Node Method for Path Planning of Mobile Robots[J]. Robotics and Autonomous Systems, 2020, 123: 103320.
11	Wang Xiangyu, Liu Zuoshi, Liu Jiahu. Mobile Robot Path Planning Based on an Improved A^*Algorithm[C]//International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2022). Bellingham: SPIE, 2023: 1260449.
12	李鑫, 廖凯文, 陈薇, 等. 多自动导引车路径规划的时空冲突约束A^*算法[J]. 计算机集成制造系统, 2021, 27(11): 3219-3226.
	Li Xin, Liao Kaiwen, Chen Wei, et al. Space-time Conflict Constrained A^* Algorithm for Path Planning of Multiple AGVS[J]. Computer Integrated Manufacturing Systems, 2021, 27(11): 3219-3226.
13	Song Baoye, Wang Zidong, Zou Lei. An Improved PSO Algorithm for Smooth Path Planning of Mobile Robots Using Continuous High-degree Bezier Curve[J]. Applied Soft Computing, 2021, 100: 106960.
14	孙小飞, 余涛, 陈锐. 基于ROS的自动分拣机器人系统设计[J]. 制造业自动化, 2021, 43(7): 141-146.
	Sun Xiaofei, Yu Tao, Chen Rui. Design of Automatic Sorting Robot System Based on ROS[J]. Manufacturing Automation, 2021, 43(7): 141-146.
15	Shi Yangyang, Li Qiongqiong, Bu Shengqiang, et al. Research on Intelligent Vehicle Path Planning Based on Rapidly-exploring Random Tree[J]. Mathematical Problems in Engineering, 2020, 2020(1): 5910503.
16	鲁毅, 高永平, 龙江腾. A^*算法在移动机器人路径规划中的研究[J]. 湖北师范大学学报(自然科学版), 2022, 42(2): 59-65.
	Lu Yi, Gao Yongping, Long Jiangteng. A study on A^* Algorithm in Mobile Robot Path Planning[J]. Journal of Hubei Normal University(Natural Science), 2022, 42(2): 59-65.
17	高九州, 徐威峰, 张立辉, 等. 基于改进A^*算法的无人机避障航线规划[J]. 现代电子技术, 2023, 46(8): 181-186.
	Gao Jiuzhou, Xu Weifeng, Zhang Lihui, et al. Obstacle Avoidance Route Planning of UAV Based on Optimized A^*Algorithm[J]. Modern Electronics Technique, 2023, 46(8): 181-186.
18	Liao Maosheng, Wang Di, Yang Hao. Deploy Indoor 2D Laser SLAM on a Raspberry Pi-based Mobile Robot[C]//2019 11th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). Piscataway: IEEE, 2019: 7-10.

算法	搜索邻域数	方向
传统A*算法	4	4
传统3×3搜索邻域的A*	8	8
改进5×5搜索邻域的A*	24	16
改进7×7搜索邻域的A*	48	32

角度θ/(˚)	保留的节点扩展方向
[0, 22.5)∪[337.5, 360)	D1、D2、D3、D4、D5、D6、D7、D8、D9、D10、D11、D12、D13、D14、D15、D16、D17
[22.5, 67.5)	D1、D2、D3、D4、D5、D6、D7、D8、D9、D10、D11、D12、D13、D29、D30、D31、D32
[67.5, 112.5)	D1、D2、D3、D4、D5、D6、D7、D8、D9、D25、D26、D27、D28、D29、D30、D31、D32
[112.5, 157.5)	D1、D2、D3、D4、D5、D21、D22、D23、D24、D25、D26、D27、D28、D29、D30、D31、D32
[157.5, 202.5)	D1、D17、D18、D19、D20、D21、D22、D23、D24、D25、D26、D27、D28、D29、D30、D31、D32
[202.5, 247.5)	D13、D14、D15、D16、D17、D18、D19、D20、D21、D22、D23、D24、D25、D26、D27、D28、D29
[247.5, 292.5)	D9、D10、D11、D12、D13、D14、D15、D16、D17、D18、D19、D20、D21、D22、D23、D24、D25
[292.5, 337.5)	D5、D6、D7、D8、D9、D10、D11、D12、D13、D14、D15、D16、D17、D18、D19、D20、D21

算法名称	路径长度	路径拐点	搜索节点	危险节点	路径节点	转弯总角度/(°)	时间/s
传统4搜索A*算法	100.000	15	1 087	47	101	1 350	2.398
传统8搜索A*算法	86.125	20	1 120	11	66	1 170	1.752
文献[16]算法	89.397	17	1 062	33	73	900	1.398
文献[17]算法	102.770	13	370	0	20	825	1.527
本文算法	84.387	12	744	0	15	592	1.062

[1]	齐本胜, 李岩, 苗红霞, 陈家林, 李成林. 基于改进启发式RRT的AUV路径规划[J]. 系统仿真学报, 2025, 37(1): 245-256.
[2]	许建民, 宋雷, 邓冬冬, 陈尧箬, 杨炜. 基于多尺度A*与优化DWA算法融合的移动机器人路径规划[J]. 系统仿真学报, 2025, 37(1): 257-270.
[3]	王琪玮, 张琪, 杨硕, 彭勇. 动态任务环境下智能体健壮行为树控制架构设计[J]. 系统仿真学报, 2025, 37(1): 54-65.
[4]	尹安琳, 张著洪. 复杂环境下无人机路径规划及其改进型人工兔优化[J]. 系统仿真学报, 2025, 37(1): 79-94.
[5]	姚万业, 庞泽伟, 孙沛杰, 王祝. 基于窗口化匹配估计的ORB-SLAM算法研究[J]. 系统仿真学报, 2024, 36(9): 2032-2042.
[6]	王越龙, 王松艳, 晁涛. 基于多步信息辅助的Q-learning路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2137-2148.
[7]	霍韩淋, 邹湘军, 陈燕, 周馨曌, 陈明猷, 李承恩, 潘耀强, 唐昀超. 基于视觉机器人障碍点云映射避障规划及仿真[J]. 系统仿真学报, 2024, 36(9): 2149-2158.
[8]	姬鹏, 张新元, 高帅轩, 魏铄让. 融合改进A*算法与动态窗口法的路径规划研究[J]. 系统仿真学报, 2024, 36(9): 2171-2180.
[9]	孙海杰, 伞红军, 肖乐, 姚得鑫, 陈久朋, 杨晓园. 一种改进的移动机器人路径规划算法[J]. 系统仿真学报, 2024, 36(9): 2193-2207.
[10]	刘佳仑, 杨帆, 谢玲利, 李诗杰, 王腾飞. 面向智能航行避碰决策与规划的虚拟仿真测试技术研究[J]. 系统仿真学报, 2024, 36(8): 1780-1789.
[11]	刘斌, 兰莹, 黄文焘, 范勤勤. 融合动态窗口法的无人机动态路径规划算法[J]. 系统仿真学报, 2024, 36(8): 1843-1853.
[12]	赖荣燊, 窦磊, 巫志勇, 孙帅. 融合改进A*算法和动态窗口法的移动机器人路径规划[J]. 系统仿真学报, 2024, 36(8): 1884-1894.
[13]	康亮, 杜奕, 尹丽华. 一种面向异质多移动机器人的改进猫群算法[J]. 系统仿真学报, 2024, 36(8): 1958-1968.
[14]	黄志锋, 刘媛华. 基于改进哈里斯鹰和B-spline曲线的无人机路径规划研究[J]. 系统仿真学报, 2024, 36(7): 1509-1524.
[15]	王雅如, 姚得鑫, 刘增力, 彭艺. 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.