Global path planning algorithm for mining vehicles integrating simplified visibility graph and A* algorithm
-
摘要: 针对矿用车辆在狭窄、弯曲及有未知障碍物的井下巷道中的路径规划效率低的问题，提出了一种融合简化可视图(SVG)和A*算法的全局路径规划算法DVGA*。在构建真实环境点云地图基础上，连接车辆在不同视点下的可视切点，动态生成SVG；将可视切点依次存入OPEN表作为节点，根据A*算法估价函数选取路径最短情况下的节点加入CLOSED表，得到最优路径点并存储路径，同时删除OPEN表中的其余节点，循环此过程，直到OPEN表中出现终点；最后利用路径平滑算法进一步减少路径节点数量，从而提高路径规划效率。实验结果表明，与完整可视图+A*算法、SVG+A*算法及SVGCA*算法对比，DVGA*算法对复杂长距离路径的规划时间最短，平均路径长度分别缩短了10.79 % ，6.26% 和2.86%，具有更强的适应性和更高的规划成功率。井下试验结果表明：在巷道宽度变换区域和躲避静态障碍物时，相比SVGCA*算法，DVGA*算法规划的路径更加平滑；躲避动态障碍物时，DVGA*算法能够及时进行路径纠正，保证了路径规划的时效性和稳定性；在复杂多变的巷道环境中，DVGA*算法的规划时间和路径长度相比SVGCA*算法分别减少了11.51%和1.54%，具有更高的环境适应性和稳定性。Abstract: To address the low path planning efficiency of mining vehicles in narrow, winding underground tunnels with unknown obstacles, a global path planning algorithm, DVGA*, was proposed, integrating simplified visibility graphs (SVG) and the A* algorithm. Based on the construction of a point cloud map of the real environment, the algorithm connected the vehicle's visual tangent points from different viewpoints to dynamically generate the SVG. The visual tangent points were sequentially stored in the OPEN list as nodes, and nodes were selected for the CLOSED list based on the A* algorithm's evaluation function to ensure the shortest path. This process continued until the endpoint appeared in the OPEN list, resulting in the optimal path points being stored while the remaining nodes in the OPEN list were deleted. Finally, a path smoothing algorithm was utilized to further reduce the number of path nodes, thereby enhancing path planning efficiency. Experimental results indicated that compared to the Complete Visibility Graph + A* algorithm, SVG + A* algorithm, and SVGCA* algorithm, the DVGA* algorithm had the shortest planning time for complex long-distance paths, with average path lengths reduced by 10.79%, 6.26%, and 2.86%, respectively, demonstrating stronger adaptability and higher planning success rates. Results from underground tests showed that in areas with variable tunnel widths and while avoiding static obstacles, the path planned by DVGA* was smoother compared to that of the SVGCA* algorithm. When avoiding dynamic obstacles, DVGA* was able to promptly correct the path, ensuring timely and stable path planning. In complex and variable tunnel environments, the planning time and path length of DVGA* were reduced by 11.51% and 1.54%, respectively, compared to SVGCA*, indicating higher environmental adaptability and stability.
-
【编者按】矿山无人驾驶技术可显著提高矿山生产效率、保障矿山生产安全，是智能化矿山的核心建设内容之一。目前，露天矿山无人驾驶技术已取得较大进展并实现初步商用，地下矿山无人驾驶由于环境恶劣、设备性能受限，技术发展稍显迟缓，但亦在技术架构、感知设备、矿井车联网、定位导航、路径规划方面取得了较大进展。为促进矿山无人驾驶理论及技术发展，提升矿山运输无人驾驶水平，推进智能矿山建设，《工矿自动化》编辑部特邀西安科技大学张传伟教授担任客座主编，中国矿业大学胡青松教授、中煤科工集团常州研究院有限公司周李兵副研究员担任客座副主编，于2024年第10期组织出版“矿山无人驾驶技术”专题。在专题刊出之际，衷心感谢各位专家学者的大力支持！
-
![]()
图 6 模拟环境下4种算法规划路径对比
Figure 6. Comparison of path planning by four algorithms in a simulated environment
![]()
图 11 智能小车实验轨迹对比
Figure 11. Comparison of experimental trajectories of the intelligent car
![]()
图 13 井下巷道路径规划试验结果
Figure 13. Experimental results of underground roadway path planning
![]()
图 14 智能小车井下试验轨迹对比
Figure 14. Comparison of underground test trajectories of the intelligent car
${\mathrm{CLOSED}}\left\{ {} \right\} \leftarrow {O_{{\mathrm{start}}}}$ ${\mathrm{OPEN}}\left\{ {} \right\} \leftarrow \left\{ {} \right\}$ $ {\mathrm{if}}\text{ }I\in \left\{{A}_{1},{A}_{2},{B}_{1},{B}_{2}\right\} $//I为视点范围内可视点且不同时通过 ${\mathrm{OPEN}}\left\{ {} \right\} \leftarrow I$ ${\mathrm{While}}({\mathrm{True}}) $ $ {A}_{2}\leftarrow f({\mathrm{OPEN}}) $//根据步骤3，评价最小值为可视扩展点 ${\mathrm{CLOSED}}\left\{ {} \right\} \leftarrow {A_2}$ $ {\mathrm{path}}\left\{\right\}\leftarrow [{O}_{{\mathrm{start}}},{A}_{2}]$//将边存储为路径 $ {\mathrm{clear}}({\mathrm{OPEN}}\{{A}_{1},{B}_{1},{B}_{2}\}) $//清空OPEN表中其余点 $I = {A_2}$ …//重复执行步骤2）,3）,4） $ {\mathrm{if}}\text{ }\left\{{A}_{i} \cdots {B}_{i} \cdots \right\}\cap {O}_{{\mathrm{goal}}}={O}_{{\mathrm{goal}}} $//视点范围内出现了终点 ${\mathrm{CLOSED}}\{ \} \leftarrow {O_{{\mathrm{goal}}}}$ $ {\mathrm{path}}\left\{\right\}\leftarrow [I,{O}_{{\mathrm{goal}}}] $//将边存储为路径 ${\mathrm{end}}$ 
下载: 导出CSV
表 1 模拟环境下4种算法的路径规划数据
Table 1 Path planning data for four algorithms in a simulated environments
算法 可视
边数算法执
行时间/s可视图
构建时间/s路径查
找时间/s路径
长度/m${\mathrm{OPEN}}$
表长度CVGA* 108 0.78 0.70 0.08 769.85 73 SVG−A* 40 0.53 0.50 0.03 769.85 20 SVGCA* 2 0.11 769.85 4 DVGA* 32 0.10 0.09 0.01 769.85 3
下载: 导出CSV
表 2 实验硬件设备信息
Table 2 Experimental hardware equipment information
设备名称 型号 上位机 CPU i7−9700，RTX 3060，ROS Melodic 激光雷达 velodyne VLP−16 惯性测量单元 LPMS−IG1 相机 D435i
下载: 导出CSV
表 3 不同算法实验数据对比
Table 3 Comparison of experimental data for different algorithms
算法 平均规划时间/s 平均路径长度/m 成功次数 CVGA* 296 75.107 20 SVG−A* 243 71.454 23 SVGCA* 218 68.981 26 DVGA* 183 67.005 30
下载: 导出CSV
表 4 井下巷道路径规划试验数据对比
Table 4 Comparison of experimental data on underground roadway path planning
算法 平均规划时间/s 平均路径长度/m 成功次数 SVGCA* 278 87.511 8 DVGA* 246 86.164 9
下载: 导出CSV
-
[1] 王虹桥,陈养才,王丹识. 我国“数字煤炭” 建设发展研究与探讨[J]. 中国煤炭,2024,50(1):9-14. WANG Hongqiao,CHEN Yangcai,WANG Danshi. Research and discussion on the development of "digital coal" construction in China[J]. China Coal,2024,50(1):9-14.
[2] WANG Maosen,BAO Jiusheng,YUAN Xiaoming,et al. Research status and development trend of unmanned driving technology in coal mine transportation[J]. Energies,2022,15(23). DOI: 10.3390/en15239133.
[3] 胡青松,孟春蕾,李世银,等. 矿井无人驾驶环境感知技术研究现状及展望[J]. 工矿自动化,2023,49(6):128-140. HU Qingsong,MENG Chunlei,LI Shiyin,et al. Research status and prospects of perception technology for unmanned mining vehicle driving environment[J]. Journal of Mine Automation,2023,49(6):128-140.
[4] 鲍久圣,刘琴,葛世荣,等. 矿山运输装备智能化技术研究现状及发展趋势[J]. 智能矿山,2020,1(1):78-88. BAO Jiusheng,LIU Qin,GE Shirong,et al. Research status and development trend of intelligent technologies for mine transportation equipment[J]. Journal of Intelligent Mine,2020,1(1):78-88.
[5] 蒲德全,高振刚,李鹏洲. 矿井无轨辅助运输车辆无人驾驶研究现状分析[J]. 现代矿业,2023,39(6):44-51. DOI: 10.3969/j.issn.1674-6082.2023.06.012 PU Dequan,GAO Zhengang,LI Pengzhou. Analysis of the research status of unmanned driving of mine trackless auxiliary transportation vehicles[J]. Modern Mining,2023,39(6):44-51. DOI: 10.3969/j.issn.1674-6082.2023.06.012
[6] 邓永胜. 煤矿井下无轨胶轮车的现状及应用[J]. 矿业装备,2023(2):165-167. DENG Yongsheng. Present situation and application of trackless rubber-tyred vehicle in coal mine[J]. Mining Equipment,2023(2):165-167.
[7] 陈善有,郭洋,田斌,等. 国内外露天矿山无人驾驶研究现状分析与发展前景[J]. 现代矿业,2023,39(12):12-16. DOI: 10.3969/j.issn.1674-6082.2023.12.002 CHEN Shanyou,GUO Yang,TIAN Bin,et al. Analysis of current research status and development prospects of unmanned driving in open-pit mines at home and abroad[J]. Modern Mining,2023,39(12):12-16. DOI: 10.3969/j.issn.1674-6082.2023.12.002
[8] 吕太之,赵春霞,夏平平. 基于同步可视图构造和A*算法的全局路径规划[J]. 南京理工大学学报,2017,41(3):313-321. LYU Taizhi,ZHAO Chunxia,XIA Pingping. Global path planning based on simultaneous visibility graph construction and A* algorithm[J]. Journal of Nanjing University of Science and Technology,2017,41(3):313-321.
[9] 崔宝侠,王淼弛,段勇. 基于可搜索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
[10] 程传奇,郝向阳,李建胜,等. 融合改进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.
[11] RICHTER C,ROY N. Learning to plan for visibility in navigation of unknown environments[C]. International Symposium on Experimental Robotics,Tokyo,2016:387-398.
[12] OLEYNIKOVA H,TAYLOR Z,SIEGWART R,et al. Safe local exploration for replanning in cluttered unknown environments for microaerial vehicles[J]. IEEE Robotics and Automation Letters,2018,3(3):1474-1481. DOI: 10.1109/LRA.2018.2800109
[13] 黄迎港,陈锴,罗文广. 复杂环境下无人机全覆盖路径规划混合算法研究[J]. 广西科技大学学报,2022,33(1):85-93. HUANG Yinggang,CHEN Kai,LUO Wenguang. Hybrid algorithm of UAV full coverage path planning in complex environment[J]. Journal of Guangxi University of Science and Technology,2022,33(1):85-93.
[14] 袁晓明,郝明锐. 煤矿辅助运输机器人关键技术研究[J]. 工矿自动化,2020,46(8):8-14. YUAN Xiaoming,HAO Mingrui. Research on key technologies of coal mine auxiliary transportation robot[J]. Industry and Mine Automation,2020,46(8):8-14.
[15] 黄友锐,李静,韩涛,等. 基于膜计算的煤矿井下机器人路径规划算法[J]. 工矿自动化,2021,47(11):22-29. HUANG Yourui,LI Jing,HAN Tao,et al. Research on path planning algorithm of robot in coal mine based on membrane computing[J]. Industry and Mine Automation,2021,47(11):22-29.
[16] 薛光辉,王梓杰,王一凡,等. 基于改进人工势场算法的煤矿井下机器人路径规划[J]. 工矿自动化,2024,50(5):6-13. XUE Guanghui,WANG Zijie,WANG Yifan,et al. Path planning of coal mine underground robot based on improved artificial potential field algorithm[J]. Journal of Mine Automation,2024,50(5):6-13.
[17] 夏静慧,肖战定,霍亚超,等. 一种改进人工势场的矿车避障路径规划方法[J]. 能源与环保,2024,46(5):196-201. XIA Jinghui,XIAO Zhanding,HUO Yachao,et al. An obstacle avoidance path planning method for mine cars with improved artificial potential field[J]. China Energy and Environmental Protection,2024,46(5):196-201.
[18] 黄荣杰,王亚刚. 基于可视图与改进遗传算法的机器人平滑路径规划[J]. 控制工程,2024,31(4):678-686. HUANG Rongjie,WANG Yagang. Smooth path planning for robot based on visibility graph and improved genetic algorithm[J]. Control Engineering of China,2024,31(4):678-686.
[19] 范晓临,张旭东,邹渊,等. 一种基于简化可视图的建图和规划方法[J]. 汽车工程,2024,46(7):1249-1258. FAN Xiaolin,ZHANG Xudong,ZOU Yuan,et al. A mapping and planning method based on simplified visibility graph[J]. Automotive Engineering,2024,46(7):1249-1258.
[20] BOTEA A,MÜLLER M,SCHAEFFER J. Near optimal hierarchical path-finding[J]. Journal of Game Development,2004,1:1-30.
[21] 张琦,马家辰,马立勇. 基于简化可视图的环境建模方法[J]. 东北大学学报(自然科学版),2013,34(10):1383-1386,1391. ZHANG Qi,MA Jiachen,MA Liyong. Environment modeling approach based on simplified visibility graph[J]. Journal of Northeastern University (Natural Science),2013,34(10):1383-1386,1391.
计量
- 文章访问数: 763
- HTML全文浏览量: 40
- PDF下载量: 62
