留言板

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

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

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

张伟民 张月 张辉

张伟民,张月,张辉. 基于改进A*算法的煤矿救援机器人路径规划[J]. 煤田地质与勘探,2022,50(12):185−193. doi: 10.12363/issn.1001-1986.22.04.0317
引用本文: 张伟民,张月,张辉. 基于改进A*算法的煤矿救援机器人路径规划[J]. 煤田地质与勘探,2022,50(12):185−193. doi: 10.12363/issn.1001-1986.22.04.0317
ZHANG Weimin,ZHANG Yue,ZHANG Hui. Path planning of coal mine rescue robot based on improved A* algorithm[J]. Coal Geology & Exploration,2022,50(12):185−193. doi: 10.12363/issn.1001-1986.22.04.0317
Citation: ZHANG Weimin,ZHANG Yue,ZHANG Hui. Path planning of coal mine rescue robot based on improved A* algorithm[J]. Coal Geology & Exploration,2022,50(12):185−193. doi: 10.12363/issn.1001-1986.22.04.0317

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

doi: 10.12363/issn.1001-1986.22.04.0317
基金项目: 国家重点研发计划课题(2019YFC0605101)
详细信息
    第一作者:

    张伟民,1976年生,男,湖北武汉人,博士,副教授,从事机电一体化教学与科研工作. E-mail:wmzhang@cug.edu.cn

  • 中图分类号: TD41;TP242

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

  • 摘要: 煤矿救援机器人在执行救援任务时,在获得任务指令后首先需要获得环境模型,再利用内置算法在该环境模型中规划出一条从当前位置到目标位置的无碰撞路径。为减少救援机器人的移动时间,通常要求该路径为时间最优,而目前使用较多的传统A*算法在栅格地图环境下规划的路径存在路径冗余点多、路径转折角度大等问题,导致该路径对于可沿任意方向灵活移动的救援机器人来说是“非最优”的。为解决这一问题,在传统A*算法的基础上提出一种改进A*算法。首先,该算法在传统A*算法的基础上增加当前扩展节点的邻接点数量,以快速搜索获得初始路径;其次,通过设置距离阈值并重连路径点,去除初始路径的冗余点;根据步长分割路径获得间距更小的路径点集合,并再次去除冗余点;最后,为进一步对所得路径的转角进行平滑处理,采用5次B样条曲线进行拟合,最终得到路径点更少、路径代价更小、累计转折角度更小的优化路径。在5种不同尺寸、障碍物覆盖率为20%的栅格地图环境中利用MATLAB对上述改进A*算法进行仿真实验,并将改进A*算法的仿真结果与传统A*算法的仿真结果进行对比。结果表明:相对于传统A*算法,改进A*算法通过扩展邻接点、去除路径冗余点及路径平滑等操作,有效改善了传统A*算法的路径冗余点多和路径转折角度大等问题;此外,改进A*算法还能在一定程度上减少生成初始路径时的扩展节点数量,降低系统内存占用。

     

  • 图  栅格地图

    Fig. 1  Grid map

    图  传统A*算法搜索结果

    Fig. 2  Search result of conventional A* algorithm

    图  邻接点数量为8和24时A*算法规划结果

    Fig. 3  Planning results of A* algorithm with 8 and 24 adjacency points

    图  去除路径冗余点流程

    Fig. 4  Flow chart of removing redundant points in path

    图  CheckPath函数伪代码

    Fig. 5  Pseudo-code of function CheckPath

    图  示例路径

    Fig. 6  sample path

    图  去除路径冗余点后的路径

    Fig. 7  The path after removing redundant points

    图  不同阶数的B样条曲线平滑效果

    Fig. 8  Smoothing results of B-spline curves of different orders

    图  传统A*算法和改进A*算法的仿真结果

    Fig. 9  Simulation result of conventional A* algorithm and improved A* algorithm

    表  1  改进A*算法和标准A*算法的部分参数比值

    Table  1  Partial parameter ratio between improved A* algorithm and standard A* algorithm

    地图尺寸搜索节点比/%路径代价比/%转折角度比/%
    20×2084.4590.4625.95
    30×3082.0591.1821.35
    50×5082.9991.5622.56
    80×8080.6692.1019.90
    100×10080.7492.6720.10
    下载: 导出CSV
  • [1] 孙国栋,李雨潭,朱华. 一种新型煤矿救援机器人履带行走机构设计[J]. 工矿自动化,2015,41(6):21−25.. doi: 10.13272/j.issn.1671-251x.2015.06.006

    SUN Guodong,LI Yutan,ZHU Hua. Design of a new type of crawler travelling mechanism of coal mine rescue robot[J]. Industry and Mine Automation,2015,41(6):21−25.. doi: 10.13272/j.issn.1671-251x.2015.06.006
    [2] 田华亭,李涛,秦颖. 基于A*改进算法的四向移动机器人路径搜索研究[J]. 控制与决策,2017,32(6):1007−1012.

    TIAN Huating,LI Tao,QIN Ying. Research of four–way mobile robot path search based on improved A* algorithm[J]. Control and Decision,2017,32(6):1007−1012.
    [3] 庞强伟,胡永江,李文广,等. 多无人机协同侦察任务规划方法研究综述[J]. 电讯技术,2019,59(6):741−748.

    PANG Qiangwei,HU Yongjiang,LI Wenguang,et al. Research on multi–UAV cooperative reconnaissance mission planning methods:An overview[J]. Telecommunication Engineering,2019,59(6):741−748.
    [4] 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 and Cybernetics,1968,4(2):100−107.. doi: 10.1109/TSSC.1968.300136
    [5] KENNEDY J, EBERHART R. Particle swarm optimization[C]//IEEE International Conference on Neural Networks. Washington DC: IEEE, 1995: 1942–1948.
    [6] BAGLEY J D. The behavior of adaptive systems which employ genetic and correlation algorithms[D]. Michigan: University of Michigan Proquest Dissertations Publishing, 1967.
    [7] STENTZ A. Optimal and efficient path planning for partially known environments[C]//IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2002: 3310–3317.
    [8] KHATIB O. Real–time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research,1986,5(1):90−98.. doi: 10.1177/027836498600500106
    [9] 陶德俊,姜媛媛,刘延彬,等. 煤矿救援机器人路径平滑算法研究[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
    [10] 刘梦杰,朱希安,王占刚,等. 基于双向A*算法的矿井水灾逃生路径应用研究[J]. 煤炭工程,2019,51(9):42−47.

    LIU Mengjie,ZHU Xi’an,WANG Zhangang,et al. Application research of mine flood escape route based on bidirectional A* algorithm[J]. Coal Engineering,2019,51(9):42−47.
    [11] 郭江,肖宇峰,刘欣雨,等. Bezier曲线与A*算法融合的移动机器人路径规划[J]. 微型机与应用,2017,36(2):52−55.

    GUO Jiang,XIAO Yufeng,LIU Xinyu,et al. Mobile robot path planning based on fusion of A* algorithm and Bezier curve[J]. Microcomputer & its Applications,2017,36(2):52−55.
    [12] 单伟,孟正大. 基于改进A*算法的平滑路径设计[J]. 东南大学学报(自然科学版),2010,40(增刊1):155−161.

    SHAN Wei,MENG Zhengda. Smooth path design for mobile service robots based on improved A* algorithm[J]. Journal of Southeast University (Natural Science Edition),2010,40(Sup.1):155−161.
    [13] 赵晓,王铮,黄程侃,等. 基于改进A*算法的移动机器人路径规划[J]. 机器人,2018,40(6):903−910.

    ZHAO Xiao,WANG Zheng,HUANG Chengkan,et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot,2018,40(6):903−910.
    [14] 王春颖,刘平,秦洪政. 移动机器人的智能路径规划算法综述[J]. 传感器与微系统,2018,37(8):5−8.. doi: 10.13873/j.1000-9787(2018)08-0005-04

    WANG Chunying,LIU Ping,QIN Hongzheng. Review on intelligent path planning algorithm of mobile robots[J]. Transducer and Microsystem Technologies,2018,37(8):5−8.. doi: 10.13873/j.1000-9787(2018)08-0005-04
    [15] 王雷,石鑫. 基于改进蚁群算法的移动机器人动态路径规划[J]. 南京理工大学学报,2019,43(6):700−707.

    WANG Lei,SHI Xin. Dynamic path planning of mobile robot based on improved ant colony algorithm[J]. Journal of Nanjing University of Science and Technology,2019,43(6):700−707.
    [16] KORF R E. Real–time heuristic search[J]. Artificial Intelligence, 1990, 42(2/3): 189–211.
    [17] 张皞宇,杨刘一,陈旭淼. 基于A*算法与人工势场法无人车路径规划的改进探索[J]. 电脑知识与技术,2021,17(17):233−235.. doi: 10.14004/j.cnki.ckt.2021.1628

    ZHANG Aoyu,YANG Liuyi,CHEN Xumiao. Improved exploration of unmanned vehicle path planning based on A* algorithm and artificial potential field method[J]. Computer Knowledge and Technology,2021,17(17):233−235.. doi: 10.14004/j.cnki.ckt.2021.1628
    [18] 王永忠,徐天羿,李佳骏,等. 基于多层路径规划的自动布线优化研究[J]. 科技和产业,2021,21(10):169−174.. doi: 10.3969/j.issn.1671-1807.2021.10.029

    WANG Yongzhong,XU Tianyi,LI Jiajun,et al. Research on the optimization of integrated circuit automatic routing based on multi–layer path planning[J]. Science Technology and Industry,2021,21(10):169−174.. doi: 10.3969/j.issn.1671-1807.2021.10.029
    [19] 张伟民,付仕雄. 基于改进RRT*算法的移动机器人路径规划[J]. 华中科技大学学报(自然科学版),2021,49(1):31−36.

    ZHANG Weimin,FU Shixiong. Mobile robot path planning based on improved RRT* algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition),2021,49(1):31−36.
    [20] BOTEA A,MULLER M,SCHAEFFER J. Near optimal hierarchical path–finding[J]. Journal of Game Development,2004,2004:1−30.
  • 加载中
图(9) / 表(1)
计量
  • 文章访问数:  246
  • HTML全文浏览量:  21
  • PDF下载量:  37
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-04-26
  • 修回日期:  2022-06-30
  • 刊出日期:  2022-12-25
  • 网络出版日期:  2022-12-03

目录

    /

    返回文章
    返回