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

Authors

ZHANG Weimin, School of Mechanical and Electronic Information, China University of Geoscience, Wuhan 430074, ChinaFollow
ZHANG Yue, School of Mechanical and Electronic Information, China University of Geoscience, Wuhan 430074, China
ZHANG Hui, Wuhan Heavy Duty Machine Tool Group Corporation, Wuhan 430074, China

Abstract

A coal mine rescue robot that performs a rescue task needs to obtain the environment model and plan a collision-free path from the current location to the target location with the built-in algorithm upon receiving a task instruction. In order to reduce the moving time of the rescue robot, the path is usually required to be time-optimal. However, the path planned by the conventional A* algorithm that is widely used at present under the grid map environment has many problems, such as many path redundancy points and large turning angle, which leads to the fact that the path is suboptimal for the rescue robot that could move flexibly in any direction. To solve these problems, an improved A* algorithm was proposed based on the conventional A* algorithm. Firstly, the improved algorithm has the number of adjacency points of the current expanding node increased on the basis of the conventional A* algorithm to obtain the initial path through quick search. Then, the redundant points of the initial path were removed by setting the distance threshold and reconnecting the path points. Thus, the set of path points with smaller spacing could be obtained by dividing the path according to the step size, and then the redundant points were further removed. Finally, in order to further smooth the turning point of the obtained path, an optimized path with fewer path points, lower path cost and smaller cumulative turning angle was obtained by fitting with the quintic B-spline curve. Besides, the improved A* algorithm was experimentally simulated in five grid map environments with different sizes and 20% obstacle coverage by MATLAB, and the simulation results of the improved A* algorithm were compared with that of the conventional A* algorithm. The result shows that the improved A* algorithm effectively improves the problems of the conventional A* algorithm, such as many path redundancy points and large path turning angle, by expanding the adjacency points, removing the redundancy points and path smoothing. In addition, the improved A* algorithm could decrease the number of expanding nodes during the generation of the initial path to a certain extent, and thus reduce the occupation of system memory.

Keywords

A* algorithm, coal mine rescue robot, path planning, path smoothing, quintic B-spline curve

DOI

10.12363/issn.1001-1986.22.04.0317

Recommended Citation

ZHANG Weimin, ZHANG Yue, ZHANG Hui, et al. (2022) "Path planning of coal mine rescue robot based on improved A* algorithm," Coal Geology & Exploration: Vol. 50: Iss. 12, Article 20.
DOI: 10.12363/issn.1001-1986.22.04.0317
Available at: https://cge.researchcommons.org/journal/vol50/iss12/20

Reference

[1] 孙国栋,李雨潭,朱华. 一种新型煤矿救援机器人履带行走机构设计[J]. 工矿自动化,2015,41(6):21−25

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

[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.

[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.

[9] 陶德俊,姜媛媛,刘延彬,等. 煤矿救援机器人路径平滑算法研究[J]. 工矿自动化,2019,45(10):49−54

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

[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

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

[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

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

[18] 王永忠,徐天羿,李佳骏,等. 基于多层路径规划的自动布线优化研究[J]. 科技和产业,2021,21(10):169−174

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

[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.