融合简化可视图和A<sup>*</sup>算法的矿用车辆全局路径规划算法

张传伟; 芦思颜; 秦沛霖; 周睿; 赵瑞祺; 杨佳佳; 张天乐; 赵聪

doi:10.13272/j.issn.1671-251x.2024070048

融合简化可视图和A^*算法的矿用车辆全局路径规划算法

doi: 10.13272/j.issn.1671-251x.2024070048

张传伟^{1, 2,},
芦思颜^1, ,,
秦沛霖¹,
周睿¹,
赵瑞祺¹,
杨佳佳¹,
张天乐¹,
赵聪¹

1.
西安科技大学机械工程学院，陕西西安　710054
2.
陕西交通职业技术学院，陕西西安　710018

基金项目: 陕西省创新人才推进计划项目（2021TD-27）。

详细信息

作者简介:
张传伟（1974—），男，安徽淮南人，教授，博士，研究方向为机电系统智能控制和矿用智能车辆，E-mail：zhangcw@xust.edu.cn

通讯作者:
芦思颜（2000—），女，陕西西安人，硕士研究生，研究方向为井下无人车路径规划，E-mail：1332267051@qq.com。

中图分类号: TD634
计量
- 文章访问数: 130
- HTML全文浏览量: 19
- PDF下载量: 16
- 被引次数: 0
出版历程
- 收稿日期: 2024-07-12
- 修回日期: 2024-10-23
- 网络出版日期: 2024-09-03

Global path planning algorithm for mining vehicles integrating simplified visibility graph and A^* algorithm

1.
College of Mechanical Engineering, Xi'an University of Science and Technology, Xi'an 710054, China
2.
Shaanxi College of Communications Technology, Xi'an 710018, China

摘要

摘要: 针对矿用车辆在狭窄、弯曲及有未知障碍物的井下巷道中的路径规划效率低的问题，提出了一种融合简化可视图(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%，具有更高的环境适应性和稳定性。
- 井下无人驾驶 /
- 全局路径规划 /
- 简化可视图 /
- A^*算法 /
- 路径平滑
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.
- underground unmanned driving /
- global path planning /
- simplified visibility graph /
- A^* algorithm /
- path smoothing
注释:

1) 【编者按】矿山无人驾驶技术可显著提高矿山生产效率、保障矿山生产安全，是智能化矿山的核心建设内容之一。目前，露天矿山无人驾驶技术已取得较大进展并实现初步商用，地下矿山无人驾驶由于环境恶劣、设备性能受限，技术发展稍显迟缓，但亦在技术架构、感知设备、矿井车联网、定位导航、路径规划方面取得了较大进展。为促进矿山无人驾驶理论及技术发展，提升矿山运输无人驾驶水平，推进智能矿山建设，《工矿自动化》编辑部特邀西安科技大学张传伟教授担任客座主编，中国矿业大学胡青松教授、中煤科工集团常州研究院有限公司周李兵副研究员担任客座副主编，于2024年第10期组织出版“矿山无人驾驶技术”专题。在专题刊出之际，衷心感谢各位专家学者的大力支持！

HTML全文

图 1 可视切线及可视切点

Figure 1. Visual tangents and visual tangent points

下载: 全尺寸图片幻灯片

图 2 动态切线可视化

Figure 2. Dynamic tangents visualization

下载: 全尺寸图片幻灯片

图 3 DVGA^*算法原理

Figure 3. Principle of DVGA^* algorithm

下载: 全尺寸图片幻灯片

图 4 路径平滑流程

Figure 4. Path smoothing process

下载: 全尺寸图片幻灯片

图 5 路径平滑前后对比

Figure 5. Comparison of path before and after smoothing

下载: 全尺寸图片幻灯片

图 6 模拟环境下4种算法规划路径对比

Figure 6. Comparison of path planning by four algorithms in a simulated environment

下载: 全尺寸图片幻灯片

图 7 智能小车

Figure 7. Intelligent car

下载: 全尺寸图片幻灯片

图 8 模拟巷道实验场景

Figure 8. Simulated roadway experiment scene

下载: 全尺寸图片幻灯片

图 9 点云地图构建及路径规划结果

Figure 9. Point cloud map construction and path planning results

下载: 全尺寸图片幻灯片

图 10 DVGA^*算法规划路径局部放大

Figure 10. Local amplification of DVGA^* algorithm planning path

下载: 全尺寸图片幻灯片

图 11 智能小车实验轨迹对比

Figure 11. Comparison of experimental trajectories of the intelligent car

下载: 全尺寸图片幻灯片

图 12 井下巷道环境

Figure 12. Underground roadway environment

下载: 全尺寸图片幻灯片

图 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

参考文献(21)

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