改进A<sup>*</sup>算法的移动机器人路径规划

杨明亮; 李宁

doi:10.13433/j.cnki.1003-8728.20220005

改进A^*算法的移动机器人路径规划

doi: 10.13433/j.cnki.1003-8728.20220005

杨明亮,
李宁

太原科技大学机械工程学院, 太原 030024

基金项目:

山西省重点研发计划 2020XXX010

详细信息

作者简介:
杨明亮(1976-), 教授, 博士, 研究方向为移动机器人路径规划, yangmingliang@tyust.edu.cn

中图分类号: TP24
计量
- 文章访问数: 312
- HTML全文浏览量: 102
- PDF下载量: 36
- 被引次数: 0
出版历程
- 收稿日期: 2020-10-20
- 刊出日期: 2022-05-01

Study on Mobile Robot Path Planning based on Improved A^* Algorithm

School of Mechanical Engineering, Taiyuan University of Science and Technology, Taiyuan 030024, China

摘要

摘要: 机器人在执行各种任务中需要具备运动控制、定位、建图与路径规划的能力, 针对传统A^*算法在路径规划中容易陷入局部最优点和转折较多问题, 提出了一种改进A^*(A-Star)和动态窗口法(Dynamic window approach, DWA)相结合的混合算法。移动机器人平台以激光传感器作为核心传感器, 获得环境的二维信息, 针对同步定位与建图问题, 改进了Lazy Decision算法提高回环质量、减少计算量。针对机器人在路径规划中存在的问题, 在A^*算法中引入预测距离, 设定动态衡量启发式A^*算法中的h(n)权重系数, 解决了使用A^*算法扩展节点多、容易陷入局部最优的问题, 同时对路径规划中拐角进行修正, 有效地将路径规划时间降低14%。并在由运动底盘、2D激光雷达传感器和计算机运算平台组成的自主移动机器人系统试验平台上验证了方法的有效性, 不仅缩短运行时间、优化了路径复杂度, 还有效克服了传统路径规划中转折角多、转折角度大的缺点。
- 移动机器人 /
- 路径规划 /
- 改进A^*算法 /
- 动态窗口法
Abstract: Robots need to have the ability of motion control, positioning, mapping and path planning in performing various tasks. Aiming at the problem of traditional A^* algorithms that are easy to fall into local optimal points and turning points in path planning, an improved A^* (A-Star) and dynamic window approach (DWA) combined hybrid algorithm. The mobile robot platform uses laser sensors as the core sensor to obtain two-dimensional information of the environment. Aiming at the problem of synchronous positioning and mapping, the Lazy Decision algorithm is improved to improve the loop quality and reduce the amount of calculation. In view of the problems in robot path planning, the prediction distance is introduced into the A^* algorithm, and the h(n) weight coefficient in the dynamic weighing heuristic A^* algorithm is set to solve the problem of using A^* algorithm to expand the number of nodes and easily fall into local optimal problem, while correcting the corners in the path planning, effectively reducing the path planning time by 14%. The effectiveness of the method is verified on an autonomous mobile robot system experimental platform composed of a moving chassis, 2D LIDAR sensors and a computer computing platform. The method not only shortens the running time, optimizes the path complexity, and effectively overcomes disadvantages of a large turning angle and multiple turning angles of traditional path planning methods.
- mobile robot /
- path planning /
- improved A^* algorithm /
- dynamic window approach

HTML全文

图 1 A^*算法示意图

下载: 全尺寸图片幻灯片

图 2 本文算法流程图

下载: 全尺寸图片幻灯片

图 3 传统A^*搜索算法路径规划结果

下载: 全尺寸图片幻灯片

图 4 改进A^*算法和DWA算法路径规划结果

下载: 全尺寸图片幻灯片

图 5 系统架构与工作流程

下载: 全尺寸图片幻灯片

图 6 ROS功能包在SLAM和路径规划上的应用

下载: 全尺寸图片幻灯片

图 7 移动机器人室内试验

下载: 全尺寸图片幻灯片

图 8 多障碍物路径规划试验

下载: 全尺寸图片幻灯片

表 1 改进前后算法性能指标的对比

算法	运行时间/s	运行时间降低率/%
改进前	90.64	-
改进后	78.02	14

下载: 导出CSV

表 2 试验数据

算法	路径规划平均耗时/s	到达目标点耗时/s	在障碍物前停滞时间/s	走过的路径长度/m
本文	0.5	20	5	2.8
原有	0.5	26	8	3.2

下载: 导出CSV

参考文献(18)

[1]	李宏达, 范继祥. 基于ROS的轮式机器人建模与路径规划仿真[J]. 哈尔滨师范大学(自然科学学报), 2020, 36(6): 16-23 https://www.cnki.com.cn/Article/CJFDTOTAL-HEBY202006003.htm LI H D, FAN J X. Modeling and path planning simulation of wheeled robot based on ROS[J]. Natural Science Journal of Harbin Normal University, 2020, 36(6): 16-23 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HEBY202006003.htm
[2]	陈靖辉, 崔岩, 刘兴林, 等. 基于改进A^算法的移动机器人路径规划方法[J]. 计算机应用研究, 2020, 37(S1): 118-119 https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ2020S1039.htm 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 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ2020S1039.htm
[3]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY202012016.htm XU X Q, WANG M Y, MAO Y. Path planning of mobile robot based on improved artificial potential field method[J]. Journal of Computer Applications, 2020, 40(12): 3508-3512 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY202012016.htm
[4]	柯文德, 蔡则苏, 彭志平, 等. 一种混合路径规划方法在轮式机器人中的应用[J]. 计算机应用研究, 2011, 28(2): 505-507, 531 doi: 10.3969/j.issn.1001-3695.2011.02.027 KE W D, CAI Z S, PENG Z P, et al. Application of a hybrid path-planning method in dual-wheel robot[J]. Application Research of Computers, 2011, 28(2): 505-507, 531 (in Chinese) doi: 10.3969/j.issn.1001-3695.2011.02.027
[5]	辛煜, 梁华为, 杜明博, 等. 一种可搜索无限个邻域的改进A^算法[J]. 机器人, 2014, 36(5): 627-633 https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201405015.htm XIN Y, LIANG H W, DU M B, et al. An improved A^ algorithm for searching infinite neighborhoods[J]. Robot, 2014, 36(5): 627-633 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR201405015.htm
[6]	卜新苹, 苏虎, 邹伟, 等. 基于非均匀环境建模与三阶Bezier曲线的平滑路径规划[J]. 自动化学报, 2017, 43(5): 710-724 https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201705003.htm BU X P, SU H, ZOU W, et al. Smooth path planning based on non-uniformly modeling and cubic Bezier curves[J]. Acta Automatica Sinica, 2017, 43(5): 710-724 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201705003.htm
[7]	王洪斌, 尹鹏衡, 郑维, 等. 基于改进的A^算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42(3): 346-353 https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR202003010.htm WANG H B, YIN P H, ZHENG W, et al. Mobile robot path planning based on improved A^ algorithm and dynamic window method[J]. Robot, 2020, 42(3): 346-353 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JQRR202003010.htm
[8]	HESS W, KOHLER D, RAPP H, et al. Real-time loop closure in 2D LIDAR SLAM[C]//2016 IEEE International Conference on Robotics and Automation. Stockholm, Sweden: IEEE, 2016: 1271-1278
[9]	吴成鼎, 姚剑敏, 胡海龙. Cartographer 2D SLAM算法研究[J]. 有线电视技术, 2018, 25(4): 20-22 https://www.cnki.com.cn/Article/CJFDTOTAL-YXDJ201804007.htm WU C D, YAO J M, HU H L. Cartographer 2D SLAM algorithm research[J]. Cable TV Technology, 2018, 25(4): 20-22 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YXDJ201804007.htm
[10]	OLSON E B. Real-time correlative scan matching[C]//IEEE International Conference on Robotics and Automation. Kobe, Japan: IEEE Press, 2009: 1233-1239
[11]	KOHLBRECHER S, STRYK O V, MEYER J, et al. A flexible and scalable SLAM system with full 3D motion estimation[C]//2011 IEEE International Symposium on Safety, Security, and Rescue Robotics. Kyoto, Japan: IEEE, 2011
[12]	李维鑫. 室内测绘机器人SLAM技术的研究与实现[D]. 西安: 西安科技大学, 2018 LI W X. Research and implementation of SLAM technology for indoor surveying and mapping machine[D]. Xi'an: Xi'an University of Science and Technology, 2018 (in Chinese)
[13]	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 & Cybernetics, 1968, 4(2): 100-107
[14]	徐保来, 管贻生, 苏泽荣, 世等. 改进动态窗口法的阿克曼移动机器人局部路径规划器[J]. 机电工程技术, 2016, 45(9): 21-26 XU B L, GUAN Y S, SU Z R, et al. A modified dynamic window approach to local path planning for the ackermann mobile robot[J]. Mechanical & Electrical Engineering Technology, 2016, 45(9): 21-26 (in Chinese)
[15]	王醒策, 张汝波, 顾国昌. 基于势场栅格法的机器人全局路径规划[J]. 哈尔滨工程大学学报, 2003, 24(2): 170-174 doi: 10.3969/j.issn.1006-7043.2003.02.013 WANG X C, ZHANG R B, GU G C. Potential grid based global path planning for robots[J]. Journal of Harbin Engineering University, 2003, 24(2): 170-174 (in Chinese) doi: 10.3969/j.issn.1006-7043.2003.02.013
[16]	李元, 王石荣, 于宁波. 基于RGB-D信息的移动机器人SLAM和路径规划方法研究与实现[J]. 智能系统学报, 2018, 13(3): 445-451 https://www.cnki.com.cn/Article/CJFDTOTAL-ZNXT201803022.htm LI Y, WANG S R, YU N B. RGB-D-based SLAM and path planning for mobile robots[J]. CAAI Transactions on Intelligent Systems, 2018, 13(3): 445-451 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZNXT201803022.htm
[17]	马丁内斯. ROS机器人程序设计[M]. 刘品杰, 译. 北京: 机械工业出版社, 2014 MARTINEZ A. ROS robot programming[M]. LIU P J, trans. Beijing: Machinery Industry Press, 2014 (in Chinese)
[18]	KOUBAA A. Robot operating system (ROS)[J]. Studies in Computational Intelligence, 2016, 1(6): 342-348