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*算法还能在一定程度上减少生成初始路径时的扩展节点数量,降低系统内存占用。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.
-
Key words:
- A* algorithm /
- coal mine rescue robot /
- path planning /
- path smoothing /
- quintic B-spline curve
-
表 1 改进A*算法和标准A*算法的部分参数比值
Table 1 Partial parameter ratio between improved A* algorithm and standard A* algorithm
地图尺寸 搜索节点比/% 路径代价比/% 转折角度比/% 20×20 84.45 90.46 25.95 30×30 82.05 91.18 21.35 50×50 82.99 91.56 22.56 80×80 80.66 92.10 19.90 100×100 80.74 92.67 20.10 -
[1] 孙国栋,李雨潭,朱华. 一种新型煤矿救援机器人履带行走机构设计[J]. 工矿自动化,2015,41(6):21−25.. doi: 10.13272/j.issn.1671-251x.2015.06.006SUN 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.2019050069TAO 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-04WANG 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.1628ZHANG 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.029WANG 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.