Path planning algorithm for tracked directional drilling rigs in coal mines
-
摘要: 煤矿履带式定向钻机路径规划过程中存在机身体积约束和实际场景下的行驶效率需求，而常用的A*算法搜索速度慢、冗余节点多，且规划路径贴近障碍物、平滑性较差。提出一种以改进A*算法规划全局路径、融合动态窗口法（DWA）规划局部路径的煤矿履带式定向钻机路径规划算法。考虑定向钻机尺寸影响，在传统A*算法中引入安全扩展策略，即在定向钻机和巷道壁、障碍物之间加入安全距离约束，以提高规划路径的安全性；对传统A*算法的启发函数进行自适应权重优化，同时将父节点的影响加入到启发函数中，以提高全局路径搜索效率；利用障碍物检测原理对经上述改进后的A*算法规划路径剔除冗余节点，并使用分段三次Hermite插值进行二次平滑处理，得到全局最优路径。将改进A*算法与DWA融合，进行煤矿井下定向钻机路径规划。利用Matlab对不同工况环境下定向钻机路径规划算法进行仿真对比分析，结果表明：与Dijkstra算法和传统A*算法相比，改进A*算法在保证安全距离的前提下，加快了搜索速度，搜索时间分别平均减少88.5%和63.2%，且在一定程度上缩短了规划路径的长度，路径更加平滑；改进A*算法与DWA融合算法可有效躲避改进A*算法规划路径上的未知障碍物，路径长度较PRM算法和RRT*算法规划的路径分别平均减小5.5%和2.9%。Abstract: In the process of path planning for tracked directional drilling rigs in coal mines, there are constraints on the body volume and the demand for driving efficiency in actual scenarios. However, the commonly used A* algorithm has slow search speed, multiple redundant nodes, and the planned path is close to obstacles and has poor smoothness. This study proposes a path planning algorithm for coal mine tracked directional drilling rigs, which uses the improved A* algorithm to plan global paths and integrates the dynamic window approach (DWA) to plan local paths. Considering the influence of directional drilling rig size, a safety extension strategy is introduced in the traditional A* algorithm. The safety distance constraints are added between the directional drilling rig, roadway walls, and obstacles to improve the safety of the planned path. Adaptive weighting is applied to the heuristic function of the traditional A* algorithm, while incorporating the influence of the parent node into the heuristic function to improve the efficiency of global path search. The principle of obstacle detection is used to eliminate redundant nodes in the path planning of the improved A* algorithm. The segmented cubic Hermite interpolation is used for quadratic smoothing to obtain the global optimal path. The improved A* algorithm is integrated with DWA for path planning of directional drilling rigs in coal mines. Matlab is used to simulate and do comparative analysis of directional drilling rig path planning algorithms under different working conditions.The results show that compared with Dijkstra algorithm and traditional A* algorithm, the improved A* algorithm accelerates the search speed while ensuring a safe distance. It reduces search time by 88.5% and 63.2% respectively, and to some extent shortens the length of the planned path, making the path smoother. The improved A* algorithm and DWA fusion algorithm can effectively avoid unknown obstacles on the path planned by the improved A* algorithm. The path length is reduced by 5.5% and 2.9% compared to the paths planned by the PRM algorithm and RRT * algorithm, respectively.
-
-
![]()
图 7 改进A*算法与DWA融合算法流程
Figure 7. Fusion algorithm flow of improved A* algorithm and dynamic window approach (DWA)
![]()
图 8 A*算法引入安全扩展策略前后20×20栅格地图内钻机路径规划
Figure 8. Drilling rig path planning in 20×20 grid map before and after introducing safety extension strategy in A* algorithm
![]()
图 9 A*算法启发函数优化前后20×20 栅格地图内钻机路径规划
Figure 9. Drilling rig path planning in 20×20 grid before and after optimizing heuristic function in A* algorithm
![]()
图 10 剔除冗余节点前后20×20 栅格地图内定向钻机路径规划
Figure 10. Drilling rig path planning in 20×20 grid before and after deleting redundant nodes
![]()
图 12 50 × 50栅格地图内不同算法路径规划结果
Figure 12. Path planning result of different algorithms in 50 × 50 grid map
![]()
图 13 50×50栅格地图内改进A*算法与DWA融合算法路径规划结果
Figure 13. Path planning results of fusion algorithm of the improved A* algorithm and DWA in 50 × 50 grid map
表 1 改进 A*算法与其他路径规划算法性能对比
Table 1 Performance comparison between improved A* algorithm and other path planning algorithms
工况 算法 搜索时间/s 路径长度/m 直行 Dijkstra 0.422 46.0 传统A* 0.088 46.0 改进A* 0.071 45.3 转弯 Dijkstra 0.508 49.0 传统A* 0.276 49.0 改进A* 0.049 38.4 转巷 Dijkstra 1.214 78.0 传统A* 0.819 78.0 改进A* 0.097 69.5 
下载: 导出CSV
表 2 融合算法与其他路径规划算法性能对比
Table 2 Performance comparison between the fusion algorithm and other path planning algorithms
工况 与障碍物最小距离/m 路径长度/m 改进A*算法 PRM/RRT*算法 融合算法 改进A*算法 PRM算法 RRT*算法 融合算法 直行 0 0.360 1.257 45.3 48.134 47.330 45.847 转弯 0 0.176 2.154 38.4 43.443 41.419 40.278 转巷 0 0.461 2.689 69.5 75.527 74.536 72.385
下载: 导出CSV
-
[1] 吉辰,蹇开林,郝忠. 煤与瓦斯突出过程中煤体破坏的有限元模拟[J]. 重庆大学学报,2020,43(4):85-93. JI Chen,JIAN Kailin,HAO Zhong. Finite element simulation of coal body failure in coal and gas outburst process[J]. Journal of Chongqing University,2020,43(4):85-93.
[2] 李东民,朱士明,赵元志,等. 煤矿钻机自动防卡钻电液控制系统研究[J]. 重庆大学学报,2022,45(2):114-124. DOI: 10.11835/j.issn.1000-582X.2020.258 LI Dongmin,ZHU Shiming,ZHAO Yuanzhi,et al. Electro-hydraulic control system for automatic anti-sticking of coal mine drilling rig[J]. Journal of Chongqing University,2022,45(2):114-124. DOI: 10.11835/j.issn.1000-582X.2020.258
[3] 李泉新,刘飞,方俊,等. 我国煤矿井下智能化钻探技术装备发展与展望[J]. 煤田地质与勘探,2021,49(6):265-272. LI Quanxin,LIU Fei,FANG Jun,et al. Development and prospect of intelligent drilling technology and equipment for underground coal mines in China[J]. Coal Geology & Exploration,2021,49(6):265-272.
[4] 高百战,孙保山,康奇岳. 我国煤矿坑道钻机研究现状及发展趋势[J]. 煤矿机械,2019,40(3):45-47. GAO Baizhan,SUN Baoshan,KANG Qiyue. Research status and development trend of coal mine tunnel drilling rig in China[J]. Coal Mine Machinery,2019,40(3):45-47.
[5] 石智军,姚克,姚宁平,等. 我国煤矿井下坑道钻探技术装备40年发展与展望[J]. 煤炭科学技术,2020,48(4):1-34. SHI Zhijun,YAO Ke,YAO Ningping,et al. 40 years of development and prospect on underground coal mine tunnel drilling technology and equipment in China[J]. Coal Science and Technology,2020,48(4):1-34.
[6] 张飞凯,黄永忠,李连茂,等. 基于Dijkstra算法的货运索道路径规划方法[J]. 山东大学学报(工学版),2022,52(6):176-182. ZHANG Feikai,HUANG Yongzhong,LI Lianmao,et al. Planning method of freight ropeway path based on Dijkstra algorithm[J]. Journal of Shandong University(Engineering Science),2022,52(6):176-182.
[7] NAN Guojun,LIU Zhuo,DU Haibo,et al. Transmission line-planning method based on adaptive resolution grid and improved Dijkstra algorithm[J]. Sensors (Basel,Switzerland),2023,23(13). DOI: 10.3390/S23136214.
[8] 邵琪,时维国. 基于改进蚁群算法的机器人路径规划研究[J]. 现代制造工程,2023(6):46-51. SHAO Qi,SHI Weiguo. Research on robot path planning based on improved ant colony algorithm[J]. Modern Manufacturing Engineering,2023(6):46-51.
[9] 郝兆明,安平娟,李红岩,等. 增强目标启发信息蚁群算法的移动机器人路径规划[J]. 科学技术与工程,2023,23(22):9585-9591. DOI: 10.12404/j.issn.1671-1815.2023.23.22.09585 HAO Zhaoming,AN Pingjuan,LI Hongyan,et al. Mobile robot path planning based on enhanced goal heuristic information ant colony algorithm[J]. Science Technology and Engineering,2023,23(22):9585-9591. DOI: 10.12404/j.issn.1671-1815.2023.23.22.09585
[10] 孙小倩,辛绍杰. 基于改进型A*算法的移动机器人路径规划[J]. 组合机床与自动化加工技术,2023(3):5-8. SUN Xiaoqian,XIN Shaojie. Research on mobile robot path planning based on improved A* algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique,2023(3):5-8.
[11] 孔慧芳,夏露,张倩. 基于改进人工势场法的智能车辆避撞路径规划[J]. 合肥工业大学学报(自然科学版),2023,46(5):583-589. DOI: 10.3969/j.issn.1003-5060.2023.05.002 KONG Huifang,XIA Lu,ZHANG Qian. Path planning for intelligent vehicle collision avoidance based on improved artificial potential field method[J]. Journal of Hefei University of Technology(Natural Science),2023,46(5):583-589. DOI: 10.3969/j.issn.1003-5060.2023.05.002
[12] 邱朋,汪光,赵理,等. 采用改进人工势场法的动态无人车路径规划[J]. 机械设计与制造,2023(3):291-296. QIU Peng,WANG Guang,ZHAO Li,et al. Unmanned vehicle path planning based on structured road improved artificial potential field method[J]. Machinery Design & Manufacture,2023(3):291-296.
[13] 陈奕梅,沈建峰,李柄棋. 改进TEB算法的多机器人动态避障策略研究[J]. 电光与控制,2022,29(5):107-112. CHEN Yimei,SHEN Jianfeng,LI Bingqi. On dynamic obstacle avoidance strategy for multi-robot with improved TEB algorithm[J]. Electronics Optics & Control,2022,29(5):107-112.
[14] 张伟民,张月,张辉. 基于改进A*算法的煤矿救援机器人路径规划[J]. 煤田地质与勘探,2022,50(12):185-193. 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.
[15] 赵久强,赵庭辉,冯毅萍,等. 基于改进A*算法和DWA融合的机器人路径规划研究[J]. 实验技术与管理,2023,40(3):87-92. ZHAO Jiuqiang,ZHAO Tinghui,FENG Yiping,et al. Research on robot path planning based on improved A* algorithm and DWA[J]. Experimental Technology and Management,2023,40(3):87-92.
[16] 薛光辉,刘爽,李圆,等. 基于障碍物尺度的封闭狭长空间路径规划研究[J]. 矿业安全与环保,2023,50(3):62-67. XUE Guanghui,LIU Shuang,LI Yuan,et al. Research on path planning in closed long and narrow space based on obstacle scale[J]. Mining Safety & Environmental Protection,2023,50(3):62-67.
[17] 金辉,牛若飞. 基于A*算法的智能车多红绿灯信号交叉口通行的经济车速规划研究[J]. 北京理工大学学报,2023,43(6):595-601. JIN Hui,NIU Ruofei. Economic speed planning based on A-star algorithm for intelligent vehicle in traffic light intersection[J]. Transactions of Beijing Institute of Technology,2023,43(6):595-601.
[18] TIAN Hao,YANG Zihui,SUN Guomin,et al. An improved A* path-planning algorithm for nuclear spill evacuation and radioactive source retrieval in complex terrain[J]. Nuclear Engineering and Design,2023,408. DOI: 10.1016/J.NUCENGDES.2023.112314.
[19] LI Dongcheng,YIN Wangping,WONG W E,et al. Quality-oriented hybrid path planning based on A* and Q-learning for unmanned aerial vehicle[J]. IEEE Access,2022,10:7664-7674. DOI: 10.1109/ACCESS.2021.3139534
[20] 王文飞,茹乐,鲁博,等. 基于改进DWA的无人机实时路径规划研究[J]. 电光与控制,2023,30(8):50-55,60. DOI: 10.3969/j.issn.1671-637X.2023.08.009 WANG Wenfei,RU Le,LU Bo,et al. Real-time path planning of UAV based on improved DWA[J]. Electronics Optics & Control,2023,30(8):50-55,60. DOI: 10.3969/j.issn.1671-637X.2023.08.009
[21] 封硕,谢廷船,康靖,等. 基于双粒子群算法的矿井搜救机器人路径规划[J]. 工矿自动化,2020,46(1):65-71. FENG Shuo,XIE Tingchuan,KANG Jing,et al. Path planning of mine search and rescue robot based on two-particle swarm optimization algorithm[J]. Industry and Mine Automation,2020,46(1):65-71.
[22] WANG Yinchu,HE Zhi,CAO Dandan,et al. Coverage path planning for kiwifruit picking robots based on deep reinforcement learning[J]. Computers and Electronics in Agriculture,2023,205. DOI: 10.1016/J.COMPAG.2022.107593.
[23] WANG Fang,BAI Yong,ZHAO Liang. Physical consistent path planning for unmanned surface vehicles under complex marine environment[J]. Journal of Marine Science and Engineering,2023,11(6). DOI: 10.3390/JMSE11061164.
