融合环境信息和运动约束的改进A*算法研究

doi:10.3778/j.issn.1002-8331.2101-0346

摘要/Abstract

摘要： 标准A*算法存在着无法考虑移动机器人运动特性及处理后的路径不利于移动机器人运动等问题。针对这一问题提出了一种新改进A*算法，通过环境信息引入障碍物权重系数来改进算法的启发函数并进行全局路径规划；优化搜索节点的选取方式和设定障碍物与路径之间的安全距离；基于对移动机器人的运动特性的考虑优化其路径，并在不同环境地图中与其他算法进行仿真实验对比分析。相关实验表明：基于新改进A*算法规划的路径始终与障碍物保持一定的安全距离；改进A*算法在时间上相比标准A*算法平均减少了80%，路径长度平均减少了2%，路径转角平均降低了82%。改进后算法相比其他算法在时间、搜索节点以及平滑度上有很大的改进，融合机器人环境信息和运动特性的规划路径算法可为移动机器人的路径规划提供一种新的方法。

关键词: 改进A*算法, Floyd算法, 移动机器人, 运动特性, 路径规划

Abstract: The standard A* algorithm cannot consider the motion characteristics of the mobile robot and the processed path is not conducive to the motion of the mobile robot. In this study, a new improved A* algorithm is proposed to solve this problem. The heuristic function of the algorithm is improved by introducing the weight coefficient of obstacles and the global path planning is carried out. The selection of search nodes is optimized and the safe distance between obstacles and paths is set. The path of the mobile robot is optimized based on the consideration of its motion characteristics, and the simulation experiment is compared with other algorithms in different environment maps. Relevant experiments show that the planned path based on the new improved A* algorithm always keeps a certain safe distance from the obstacle. Compared with the standard A* algorithm, the time of the improved A* algorithm is reduced by 80% on average, while the path length is reduced by 2% on average, and the path corner is reduced by 82% on average. Compared with other algorithms, the improved algorithm has a great improvement in time, search nodes and smoothness. The path planning algorithm integrating robot motion characteristics can provide a new method for path planning of mobile robots.

Key words: improved A* algorithm, Floyd algorithm, mobile robot, motion constraints, path planning

白雄, 鲁吉林, 路宽, 陈鹏云, 崔俊杰, 刘泽华. 融合环境信息和运动约束的改进A*算法研究[J]. 计算机工程与应用, 2022, 58(18): 311-317.

BAI Xiong, LU Jilin, LU Kuan, CHEN Pengyun, CUI Junjie, LIU Zehua. Research on Path Planning with Improved A* Algorithm Fusing Environmental Information and Motion Constraints[J]. Computer Engineering and Applications, 2022, 58(18): 311-317.

参考文献

[1] 黄章俊.基于全景视觉的多机器人协调定位[D].马鞍山：安徽工业大学，2017.
HUANG Z J.Multi-robot coordinated positioning based on panoramic vision[D].Ma’anshan：Anhui University of Technology，2017.
[2] 槐创锋，郭龙，贾雪艳，等.改进A*算法与动态窗口法的机器人动态路径规划[J].计算机工程与应用，2021，57（8）：244-248.
HUAI C F，GUO L，JIA X Y，et al.Improved A* algorithm and dynamic window method for robot dynamic path planning[J].Computer Engineering and Applications，2021，57（8）：244-248.
[3] 王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报（自然科学版），2012，52（8）：1085-1089.
WANG D J.Indoor mobile-robot path planning based on an improved A* algorithm[J].Journal of Tsinghua University（Science and Technology），2012，52（8）：1085-1089.
[4] 劳彩莲，李鹏，冯宇.基于改进的A*与DWA算法融合的温室机器人路径规划[J].农业机械学报，2021，52（1）：14-22.
LAO C L，LI P，FENG Y.Path planning of greenhouse robot based on fusion of improved A* algorithm and dynamic window approach[J].Transactions of the Chinese Society for Agricultural

Machinery，2021，52（1）：14-22.
[5] 付丽霞，任玉洁，张勇，等.基于改进平滑A*算法的移动机器人路径规划[J].计算机仿真，2020，37（8）：271-276.
FU L X，REN Y J，ZHANG Y，et al.Path planning for mobile robots based on improved smoothing A* algorithm[J].Computer Simulation，2020，37（8）：271-276.
[6] ZHANG C，AO L，YANG J，et al.An improved A* algorithm applying to path planning of games[C]//Journal of Physics：Conference Series，2020.
[7] LIU Y，LIU X.Application of improved A* algorithm in customized bus path planning[J].Computer Science and Application，2020，10（1）：21-28.
[8] ZHANG W，LIU Y.Real-time path planning of the greenhouse robot based on directional A* algorithm[J].Transactions of the Chinese Society for Agricultural Machinery，2017，48（7）：

22-28.
[9] 吴飞龙，郭世永.基于改进A*算法的AGV路径规划[J].黑龙江工业学院学报（综合版），2020，20（9）：90-93.
WU F L，GUO S Y.AGV’s path planning based on improved A* algorithm[J].Journal of Heilongjiang University of Technology（Comprehensive Edition），2020，20（9）：90-93.
[10] 陈靖辉，崔岩，刘兴林，等.基于改进A*算法的移动机器人路径规划方法[J].计算机应用研究，2020，37（S1）：118-119.
CHEN J H，CUI Y，LIU X L，et al.Path planning method for mobile robot based on improved A* algorithm[J].Application Research of Computers，2020，37（S1）：118-119.
[11] 乔云侠，王庆，阳媛，等.基于背向障碍物搜索A*算法的平滑路径规划[J].传感器与微系统，2020，39（8）：127-129.
QIAO Y X，WANG Q，YANG Y，et al.Smooth path planning based on backward obstacle search A* algorithm[J].Transducer and Microsystem Technologies，2020，39（8）：127-129.
[12] 李世国，苏卫华，郭鹏飞，等.基于改进A*算法的无人搜救全局路径规划研究[J].医疗卫生装备，2020，41（12）：16-20.
LI S G，SU W H，GUO P F，et al.Research on SAR drone global path planning based on improved A* algorithm[J].Chinese Medical and Equipment Journal，2020，41（12）：16-20.
[13] 陈娇，陈佳，刘卿.改进A*和动态窗口法的移动机器人路径规划[J].计算机集成制造系统，2020（6）：1650-1658.
CHEN Jiao，CHEN Jia，LIU Qing.Path planning based on improved A* and dynamic window approach for mobile robot[J].Computer Integrated Manufacturing Systems，2020（6）：1650-1658.
[14] 于洋，杜学历，冯迎宾.融合A*算法和动态窗口法的全局动态路径规划方法[J].沈阳理工大学学报，2020，39（5）：1-7.
YU Y，DU X L，FENG Y B.Global dynamic path planning method based on A* algorithm and dynamic window approach[J].Transactions of Shenyang Ligong University，2020，39（5）：1-7.
[15] THOMPSON S，KAGAMI S.Smooth trajectory planning with obstacle avoidance for car-like mobile robots[C]//Proceedings of the 23rd Conference of the Robotics Society of Japan，2005.
[16] 陈伟，何伟.基于Bezier曲线的机器人路径规划[J].机器人技术与应用，2009（5）：56-59.
CHEN W，HE W.Robot path planning based on Bezier curves[J].Robot Technology and Application，2009（5）：56-59.