留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于改进A*算法的煤矿救援机器人路径规划

姜媛媛 丰雪艳

姜媛媛,丰雪艳. 基于改进A*算法的煤矿救援机器人路径规划[J]. 工矿自动化,2023,49(8):53-59.  doi: 10.13272/j.issn.1671-251x.2022120027
引用本文: 姜媛媛,丰雪艳. 基于改进A*算法的煤矿救援机器人路径规划[J]. 工矿自动化,2023,49(8):53-59.  doi: 10.13272/j.issn.1671-251x.2022120027
JIANG Yuanyuan, FENG Xueyan. Path planning of coal mine rescue robot based on improved A* algorithm[J]. Journal of Mine Automation,2023,49(8):53-59.  doi: 10.13272/j.issn.1671-251x.2022120027
Citation: JIANG Yuanyuan, FENG Xueyan. Path planning of coal mine rescue robot based on improved A* algorithm[J]. Journal of Mine Automation,2023,49(8):53-59.  doi: 10.13272/j.issn.1671-251x.2022120027

基于改进A*算法的煤矿救援机器人路径规划

doi: 10.13272/j.issn.1671-251x.2022120027
基金项目: 安徽省重点研究与开发计划项目(202104g01020012);安徽理工大学环境友好材料与职业健康研究院研发专项基金资助项目(ALW2020YF18)。
详细信息
    作者简介:

    姜媛媛(1982—),女,安徽颍上人,教授,博士,主要研究方向为机器人导航与控制、智能诊断及故障预测,E-mail:jyyLL672@163.com

    通讯作者:

    丰雪艳(1999—),女,安徽太和人,硕士研究生,主要研究方向为机器人路径规划,E-mail:13352824082@qq.com

  • 中图分类号: TD774

Path planning of coal mine rescue robot based on improved A* algorithm

  • 摘要: 路径规划是煤矿救援机器人研究的重要内容之一。针对灾后煤矿环境非结构化的特点,以及传统A*算法规划的路径长度非最短、拐弯次数多和平滑度较差等问题,提出一种基于改进A*算法的煤矿救援机器人路径规划方法。对真实环境中的地图信息进行二值化处理,构建栅格地图;判断当前点与目标点的相对位置,利用改进A*算法进行路径规划,得到一条从当前点到目标点的路径;利用Douglas-Peucker(D−P)算法提取路径上的关键节点,采用三次样条插值函数对关键节点进行拟合,完成对路径的平滑处理。改进A*算法将传统A*算法的8邻域搜索扩展为有目的性的13邻域搜索,在进行路径搜索时,先对当前点和目标点的位置关系进行判断,从而减少路径节点,减小路径长度,提升路径平滑度。Matlab仿真结果表明:与8邻域A*算法、24邻域A*算法、48邻域A*算法相比,改进A*算法在路径长度、拐弯次数、平滑度等方面有一定优化,更适用于煤矿救援机器人路径规划;与Fuzzy算法相比,改进A*算法路径规划所用时间更短,规划的路径长度更短,拐弯次数更少。

     

  • 图  1  8邻域A*算法

    Figure  1.  8 neighborhood A* algorithm

    图  2  当前点与目标点的位置关系

    Figure  2.  The positional relationship between the current point and the target point

    图  3  改进A*算法的搜索邻域

    Figure  3.  Search neighborhood of improved A* algorithm

    图  4  煤矿救援机器人路径规划方法流程

    Figure  4.  Path planning process for coal mine rescue robots

    图  5  简单环境下不同邻域A*算法规划的路径

    Figure  5.  Paths planned by different neighborhoods A* algorithm in simple environment

    图  6  复杂环境下不同邻域A*算法规划的路径

    Figure  6.  Paths planned by different neighborhoods A* algorithm in complex environment

    图  7  同一环境下不同算法规划的路径对比

    Figure  7.  Comparison of paths planned by different algorithms in the same environment

    表  1  简单环境下不同邻域A*算法的性能对比

    Table  1.   Performance comparison of different neighborhoods A* algorithm in simple environment

    算法时间/s路径平滑
    前长度/m
    路径平滑
    后长度/m
    路径节点数路径平滑前拐弯次数路径平滑后拐弯次数
    8邻域A*算法0.464617.904605.28896172
    24邻域A*算法0.748602.761597.61374102
    48邻域A*算法0.823602.023598.9037282
    本文算法0.619602.761597.61374102
    下载: 导出CSV

    表  2  复杂环境下不同邻域A*算法的性能对比

    Table  2.   Comparison of the performance of different neighborhoods A* algorithm in complex environment

    算法时间/s路径平滑
    前长度/m
    路径平滑
    后长度/m
    路径节点数路径平滑前
    拐弯次数
    路径平滑后
    拐弯次数
    8邻域A*算法0.807707.696699.431121158
    24邻域A*算法1.212677.411672.73987116
    48邻域A*算法1.361676.673672.73985116
    本文算法1.009677.411672.73987116
    下载: 导出CSV

    表  3  本文算法与Fuzzy算法的性能对比

    Table  3.   Performance comparison between the algorithm in this article and Fuzzy algorithm

    算法路径长度/m时间/s拐弯次数
    Fuzzy算法695.2971.0675
    本文算法534.3220.8263
    下载: 导出CSV
  • [1] 朱华,由韶泽. 新型煤矿救援机器人研发与试验[J]. 煤炭学报,2020,45(6):2170-2181. doi: 10.13225/j.cnki.jccs.zn20.0352

    ZHU Hua,YOU Shaoze. Research and experiment of a new type of coal mine rescue robot[J]. Journal of China Coal Society,2020,45(6):2170-2181. doi: 10.13225/j.cnki.jccs.zn20.0352
    [2] 徐兴,俞旭阳,赵芸,等. 基于改进遗传算法的移动机器人全局路径规划[J]. 计算机集成制造系统,2022,28(6):1659-1672. doi: 10.13196/j.cims.2022.06.006

    XU Xing,YU Xuyang,ZHAO Yun,et al. Global path planning of mobile robot based on improved genetic algorithm[J]. Computer Integrated Manufacturing Systems,2022,28(6):1659-1672. doi: 10.13196/j.cims.2022.06.006
    [3] 王梓强,胡晓光,李晓筱,等. 移动机器人全局路径规划算法综述[J]. 计算机科学,2021,48(10):19-29. doi: 10.11896/jsjkx.200700114

    WANG Ziqiang,HU Xiaoguang,LI Xiaoxiao,et al. Overview of global path planning algorithms for mobile robots[J]. Computer Science,2021,48(10):19-29. doi: 10.11896/jsjkx.200700114
    [4] SHANG E,DAI Bin,NIE Yiming,et al. An improved A-star based path planning algorithm for autonomous land vehicles[J]. International Journal of Advanced Robotic Systems,2020,17(5):1-13.
    [5] 张瑜,宋荆洲,张琪祁. 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人,2020,42(5):617-625. doi: 10.13973/j.cnki.robot.190649

    ZHANG Yu,SONG Jingzhou,ZHANG Qiqi. Local path planning of outdoor cleaning robot based on an improved DWA[J]. Robot,2020,42(5):617-625. doi: 10.13973/j.cnki.robot.190649
    [6] MIN Huasong,LIN Yunhan,WANG Sijing,et al. Path planning of mobile robot by mixing experience with modified artificial potential field method[J]. Advances in Mechanical Engineering,2015,7(12):1-17.
    [7] 郭晓静,杨卓橙. 基于邻域拓展的静态路径规划A*算法研究[J]. 计算机工程与应用,2022,58(8):168-174. doi: 10.3778/j.issn.1002-8331.2010-0222

    GUO Xiaojing,YANG Zhuocheng. Improved A* algorithm based on neighbor extension in static environment[J]. Computer Engineering and Applications,2022,58(8):168-174. doi: 10.3778/j.issn.1002-8331.2010-0222
    [8] 崔宝侠,王淼弛,段勇. 基于可搜索24邻域的A*算法路径规划[J]. 沈阳工业大学学报,2018,40(2):180-184. doi: 10.7688/j.issn.1000-1646.2018.02.11

    CUI Baoxia,WANG Miaochi,DUAN Yong. Path planning for A* algorithm based on searching 24 neighborhoods[J]. Journal of Shenyang University of Technology,2018,40(2):180-184. doi: 10.7688/j.issn.1000-1646.2018.02.11
    [9] 刘小佳,狄梦然,梁利东,等. 基于象限判别下的改进A*算法路径规划[J]. 常州工学院学报,2020,33(2):26-30,35. doi: 10.3969/j.issn.1671-0436.2020.02.005

    LIU Xiaojia,DI Mengran,LIANG Lidong,et al. On the improved path planning of A* algorithm based on quadrant discrimination[J]. Journal of Changzhou Institute of Technology,2020,33(2):26-30,35. doi: 10.3969/j.issn.1671-0436.2020.02.005
    [10] 槐创锋,郭龙,贾雪艳,等. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用,2021,57(8):244-248. doi: 10.3778/j.issn.1002-8331.2008-0063

    HUAI Chuangfeng,GUO Long,JIA Xueyan,et al. Improved A* algorithm and dynamic window method for robot dynamic path planning[J]. Computer Engineering and Applications,2021,57(8):244-248. doi: 10.3778/j.issn.1002-8331.2008-0063
    [11] 程传奇,郝向阳,李建胜,等. 融合改进A*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报,2017,51(11):137-143.

    CHENG Chuanqi,HAO Xiangyang,LI Jiansheng,et al. Global dynamic path planning based on fusion of improved A* algorithm and dynamic window approach[J]. Journal of Xi'an Jiaotong University,2017,51(11):137-143.
    [12] 陶德俊,姜媛媛,刘延彬,等. 煤矿救援机器人路径平滑算法研究[J]. 工矿自动化,2019,45(10):49-54. doi: 10.13272/j.issn.1671-251x.2019050069

    TAO Dejun,JIANG Yuanyuan,LIU Yanbin,et al. Research on path smoothing algorithm of coal mine rescue robot[J]. Industry and Mine Automation,2019,45(10):49-54. doi: 10.13272/j.issn.1671-251x.2019050069
    [13] 李枭扬,周德云,冯琦. 基于分级规划策略的A*算法多航迹规划[J]. 系统工程与电子技术,2015,37(2):318-322. doi: 10.3969/j.issn.1001-506X.2015.02.14

    LI Xiaoyang,ZHOU Deyun,FENG Qi. Multiple routes planning for A* algorithm based on hierarchical planning[J]. Systems Engineering and Electronics,2015,37(2):318-322. doi: 10.3969/j.issn.1001-506X.2015.02.14
    [14] FU Bing,CHEN Lin,ZHOU Yuntao,et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics & Autonomous Systems,2018,106:26-37.
    [15] LI Chengming,GUO Peipei,WU Pengda,et al. Extraction of terrain feature lines from elevation contours using a directed adjacent relation tree[J]. International Journal of Geo-Information,2018,7(5):163-177. doi: 10.3390/ijgi7050163
    [16] ZHAO Liangbin,SHI Guoyou. A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm[J]. Ocean Engineering,2018,166(15):37-46.
    [17] 杨敏,陈媛媛,金澄,等. 保持移动速度特征的轨迹线化简方法[J]. 测绘学报,2017,46(12):2016-2023. doi: 10.11947/j.AGCS.2017.20170023

    YANG Min,CHEN Yuanyuan,JIN Cheng,et al. A method of speed-preserving trajectory simplification[J]. Acta Geodaetica et Cartographica Sinica,2017,46(12):2016-2023. doi: 10.11947/j.AGCS.2017.20170023
    [18] 胡峥楠,佘锋. 一种基于样条插值的局部路径规划模型与实现[J]. 微型电脑应用,2020,36(11):106-110. doi: 10.3969/j.issn.1007-757X.2020.11.032

    HU Zhengnan,SHE Feng. A local path planning model and implementation based on spline interpolation[J]. Microcomputer Applications,2020,36(11):106-110. doi: 10.3969/j.issn.1007-757X.2020.11.032
    [19] 高晓,杨志强,库新勃,等. 基于三次样条插值实现无人机高动态运动轨迹插值[J]. 全球定位系统,2020,45(1):37-42. doi: 10.13442/j.gnss.1008-9268.2020.01.006

    GAO Xiao,YANG Zhiqiang,KU Xinbo,et al. 3D-coordinate interpolation for UAV high dynamic positioning based on cubic spline interpolation[J]. GNSS World of China,2020,45(1):37-42. doi: 10.13442/j.gnss.1008-9268.2020.01.006
    [20] 张金泽. 水面无人艇路径规划及避障策略的研究[D]. 大连: 大连海事大学, 2022.

    ZHANG Jinze. Research on path planning and obstacle avoidance strategy of unmanned surface vehicle[D]. Dalian: Dalian Maritime University, 2022.
    [21] 刘胜,张豪,晏齐忠,等. 基于ACO−SA算法的变电站巡检机器人路径规划[J]. 南方电网技术,2022,16(9):75-82. doi: 10.13648/j.cnki.issn1674-0629.2022.09.009

    LIU Sheng,ZHANG Hao,YAN Qizhong,et al. Path planning of inspection robot in substation based on ACO-SA algorithm[J]. Southern Power System Technology,2022,16(9):75-82. doi: 10.13648/j.cnki.issn1674-0629.2022.09.009
  • 加载中
图(7) / 表(3)
计量
  • 文章访问数:  819
  • HTML全文浏览量:  26
  • PDF下载量:  55
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-12-08
  • 修回日期:  2023-08-10
  • 网络出版日期:  2023-09-04

目录

    /

    返回文章
    返回