基于改进A<sup>*</sup>算法的煤矿救援机器人路径规划

姜媛媛; 丰雪艳

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

基于改进A^*算法的煤矿救援机器人路径规划

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

姜媛媛^{1, 2,},
丰雪艳^1, ,

1.
安徽理工大学电气与信息工程学院, 安徽淮南　232000
2.
安徽理工大学环境友好材料与职业健康研究院(芜湖), 安徽芜湖　241003

基金项目: 安徽省重点研究与开发计划项目(202104g01020012)；安徽理工大学环境友好材料与职业健康研究院研发专项基金资助项目(ALW2020YF18)。

详细信息

作者简介:
姜媛媛(1982—)，女，安徽颍上人，教授，博士，主要研究方向为机器人导航与控制、智能诊断及故障预测，E-mail：jyyLL672@163.com

通讯作者:
丰雪艳(1999—)，女，安徽太和人，硕士研究生，主要研究方向为机器人路径规划，E-mail：13352824082@qq.com

中图分类号: TD774
计量
- 文章访问数: 794
- HTML全文浏览量: 26
- PDF下载量: 55
- 被引次数: 0
出版历程
- 收稿日期: 2022-12-08
- 修回日期: 2023-08-10
- 网络出版日期: 2023-09-04

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

JIANG Yuanyuan^{1, 2
,},
FENG Xueyan^{1
, ,}

1.
School of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan 232000, China
2.
Institute of Environmental Friendly Materials and Occupational Health (Wuhu), Anhui University of Science and Technology, Wuhu 241003, China

摘要

摘要: 路径规划是煤矿救援机器人研究的重要内容之一。针对灾后煤矿环境非结构化的特点，以及传统A^*算法规划的路径长度非最短、拐弯次数多和平滑度较差等问题，提出一种基于改进A^*算法的煤矿救援机器人路径规划方法。对真实环境中的地图信息进行二值化处理，构建栅格地图；判断当前点与目标点的相对位置，利用改进A^*算法进行路径规划，得到一条从当前点到目标点的路径；利用Douglas-Peucker（D−P）算法提取路径上的关键节点，采用三次样条插值函数对关键节点进行拟合，完成对路径的平滑处理。改进A^*算法将传统A^*算法的8邻域搜索扩展为有目的性的13邻域搜索，在进行路径搜索时，先对当前点和目标点的位置关系进行判断，从而减少路径节点，减小路径长度，提升路径平滑度。Matlab仿真结果表明：与8邻域A^*算法、24邻域A^*算法、48邻域A^*算法相比，改进A^*算法在路径长度、拐弯次数、平滑度等方面有一定优化，更适用于煤矿救援机器人路径规划；与Fuzzy算法相比，改进A^*算法路径规划所用时间更短，规划的路径长度更短，拐弯次数更少。
- 煤矿救援机器人 /
- 路径规划 /
- A^*算法 /
- 邻域扩展 /
- Douglas-Peucker算法 /
- 路径平滑 /
- 三次样条插值函数
Abstract: Path planning is one of the important contents of research on coal mine rescue robots. A path planning method for coal mine rescue robots based on improved A^* algorithm is proposed to address the unstructured features of post disaster coal mine environments and the problems of non-shortest path length, multiple turns, and poor smoothness of path planned by traditional A^* algorithm. The method constructs raster maps by binarizing map information in real environments, determines the relative position between the current point and the target point, and uses the improved A^* algorithm for path planning. Then a path from the current point to the target point is obtained. Douglas-Pucker (D-P) algorithm is used to extract key nodes on the path, and cubic spline interpolation function is used to fit the key nodes, thereby completing the smooth processing of the path. The improved A^* algorithm expands the traditional A^* algorithm's 8 neighborhood search to a purposeful 13 neighborhood search. When conducting path search, the position relationship between the current point and the target point is first determined, thereby reducing path nodes and length, and improving path smoothness. The Matlab simulation results show that compared with the 8 neighborhood A^* algorithm, 24 neighborhood A^* algorithm, and 48 neighborhood A^* algorithm, the improved A^* algorithm has certain optimizations in path length, number of turns and smoothness. It is more suitable for path planning of coal mine rescue robots. Compared with the Fuzzy algorithm, the improved A^* algorithm achieve shorter path planning time, shorter planned path length, and fewer turns.
- coal mine rescue robot /
- path planning /
- A^* algorithm /
- neighborhood extension /
- Douglas-Pucker algorithm /
- smooth path /
- cubic spline interpolation function

HTML全文

图 1 8邻域A^*算法

Figure 1. 8 neighborhood A^* algorithm

下载: 全尺寸图片幻灯片

图 2 当前点与目标点的位置关系

Figure 2. The positional relationship between the current point and the target point

下载: 全尺寸图片幻灯片

图 3 改进A^*算法的搜索邻域

Figure 3. Search neighborhood of improved A^* algorithm

下载: 全尺寸图片幻灯片

图 4 煤矿救援机器人路径规划方法流程

Figure 4. Path planning process for coal mine rescue robots

下载: 全尺寸图片幻灯片

图 5 简单环境下不同邻域A^*算法规划的路径

Figure 5. Paths planned by different neighborhoods A^* algorithm in simple environment

下载: 全尺寸图片幻灯片

图 6 复杂环境下不同邻域A^*算法规划的路径

Figure 6. Paths planned by different neighborhoods A^* algorithm in complex environment

下载: 全尺寸图片幻灯片

图 7 同一环境下不同算法规划的路径对比

Figure 7. Comparison of paths planned by different algorithms in the same environment

下载: 全尺寸图片幻灯片

表 1 简单环境下不同邻域A^*算法的性能对比

Table 1. Performance comparison of different neighborhoods A^* algorithm in simple environment

算法	时间/s	路径平滑前长度/m	路径平滑后长度/m	路径节点数	路径平滑前拐弯次数	路径平滑后拐弯次数
8邻域A^*算法	0.464	617.904	605.288	96	17	2
24邻域A^*算法	0.748	602.761	597.613	74	10	2
48邻域A^*算法	0.823	602.023	598.903	72	8	2
本文算法	0.619	602.761	597.613	74	10	2

下载: 导出CSV

表 2 复杂环境下不同邻域A^*算法的性能对比

Table 2. Comparison of the performance of different neighborhoods A^* algorithm in complex environment

算法	时间/s	路径平滑前长度/m	路径平滑后长度/m	路径节点数	路径平滑前拐弯次数	路径平滑后拐弯次数
8邻域A^*算法	0.807	707.696	699.431	121	15	8
24邻域A^*算法	1.212	677.411	672.739	87	11	6
48邻域A^*算法	1.361	676.673	672.739	85	11	6
本文算法	1.009	677.411	672.739	87	11	6

下载: 导出CSV

表 3 本文算法与Fuzzy算法的性能对比

Table 3. Performance comparison between the algorithm in this article and Fuzzy algorithm

算法	路径长度/m	时间/s	拐弯次数
Fuzzy算法	695.297	1.067	5
本文算法	534.322	0.826	3

下载: 导出CSV

参考文献(21)

[1]	朱华,由韶泽. 新型煤矿救援机器人研发与试验[J]. 煤炭学报,2020,45(6):2170-2181. doi: 10.13225/j.cnki.jccs.zn20.0352 ZHU Hua,YOU Shaoze. Research and experiment of a new type of coal mine rescue robot[J]. Journal of China Coal Society,2020,45(6):2170-2181. doi: 10.13225/j.cnki.jccs.zn20.0352
[2]	徐兴,俞旭阳,赵芸,等. 基于改进遗传算法的移动机器人全局路径规划[J]. 计算机集成制造系统,2022,28(6):1659-1672. doi: 10.13196/j.cims.2022.06.006 XU Xing,YU Xuyang,ZHAO Yun,et al. Global path planning of mobile robot based on improved genetic algorithm[J]. Computer Integrated Manufacturing Systems,2022,28(6):1659-1672. doi: 10.13196/j.cims.2022.06.006
[3]	王梓强,胡晓光,李晓筱,等. 移动机器人全局路径规划算法综述[J]. 计算机科学,2021,48(10):19-29. doi: 10.11896/jsjkx.200700114 WANG Ziqiang,HU Xiaoguang,LI Xiaoxiao,et al. Overview of global path planning algorithms for mobile robots[J]. Computer Science,2021,48(10):19-29. doi: 10.11896/jsjkx.200700114
[4]	SHANG E,DAI Bin,NIE Yiming,et al. An improved A-star based path planning algorithm for autonomous land vehicles[J]. International Journal of Advanced Robotic Systems,2020,17(5):1-13.
[5]	张瑜,宋荆洲,张琪祁. 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人,2020,42(5):617-625. doi: 10.13973/j.cnki.robot.190649 ZHANG Yu,SONG Jingzhou,ZHANG Qiqi. Local path planning of outdoor cleaning robot based on an improved DWA[J]. Robot,2020,42(5):617-625. doi: 10.13973/j.cnki.robot.190649
[6]	MIN Huasong,LIN Yunhan,WANG Sijing,et al. Path planning of mobile robot by mixing experience with modified artificial potential field method[J]. Advances in Mechanical Engineering,2015,7(12):1-17.
[7]	郭晓静,杨卓橙. 基于邻域拓展的静态路径规划A^算法研究[J]. 计算机工程与应用,2022,58(8):168-174. doi: 10.3778/j.issn.1002-8331.2010-0222 GUO Xiaojing,YANG Zhuocheng. Improved A^ algorithm based on neighbor extension in static environment[J]. Computer Engineering and Applications,2022,58(8):168-174. doi: 10.3778/j.issn.1002-8331.2010-0222
[8]	崔宝侠,王淼弛,段勇. 基于可搜索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
[9]	刘小佳,狄梦然,梁利东,等. 基于象限判别下的改进A^算法路径规划[J]. 常州工学院学报,2020,33(2):26-30,35. doi: 10.3969/j.issn.1671-0436.2020.02.005 LIU Xiaojia,DI Mengran,LIANG Lidong,et al. On the improved path planning of A^ algorithm based on quadrant discrimination[J]. Journal of Changzhou Institute of Technology,2020,33(2):26-30,35. doi: 10.3969/j.issn.1671-0436.2020.02.005
[10]	槐创锋,郭龙,贾雪艳,等. 改进A^算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用,2021,57(8):244-248. doi: 10.3778/j.issn.1002-8331.2008-0063 HUAI Chuangfeng,GUO Long,JIA Xueyan,et al. Improved A^ algorithm and dynamic window method for robot dynamic path planning[J]. Computer Engineering and Applications,2021,57(8):244-248. doi: 10.3778/j.issn.1002-8331.2008-0063
[11]	程传奇,郝向阳,李建胜,等. 融合改进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.
[12]	陶德俊,姜媛媛,刘延彬,等. 煤矿救援机器人路径平滑算法研究[J]. 工矿自动化,2019,45(10):49-54. doi: 10.13272/j.issn.1671-251x.2019050069 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. doi: 10.13272/j.issn.1671-251x.2019050069
[13]	李枭扬,周德云,冯琦. 基于分级规划策略的A^算法多航迹规划[J]. 系统工程与电子技术,2015,37(2):318-322. doi: 10.3969/j.issn.1001-506X.2015.02.14 LI Xiaoyang,ZHOU Deyun,FENG Qi. Multiple routes planning for A^ algorithm based on hierarchical planning[J]. Systems Engineering and Electronics,2015,37(2):318-322. doi: 10.3969/j.issn.1001-506X.2015.02.14
[14]	FU Bing,CHEN Lin,ZHOU Yuntao,et al. An improved A^* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics & Autonomous Systems,2018,106:26-37.
[15]	LI Chengming,GUO Peipei,WU Pengda,et al. Extraction of terrain feature lines from elevation contours using a directed adjacent relation tree[J]. International Journal of Geo-Information,2018,7(5):163-177. doi: 10.3390/ijgi7050163
[16]	ZHAO Liangbin,SHI Guoyou. A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm[J]. Ocean Engineering,2018,166(15):37-46.
[17]	杨敏,陈媛媛,金澄,等. 保持移动速度特征的轨迹线化简方法[J]. 测绘学报,2017,46(12):2016-2023. doi: 10.11947/j.AGCS.2017.20170023 YANG Min,CHEN Yuanyuan,JIN Cheng,et al. A method of speed-preserving trajectory simplification[J]. Acta Geodaetica et Cartographica Sinica,2017,46(12):2016-2023. doi: 10.11947/j.AGCS.2017.20170023
[18]	胡峥楠,佘锋. 一种基于样条插值的局部路径规划模型与实现[J]. 微型电脑应用,2020,36(11):106-110. doi: 10.3969/j.issn.1007-757X.2020.11.032 HU Zhengnan,SHE Feng. A local path planning model and implementation based on spline interpolation[J]. Microcomputer Applications,2020,36(11):106-110. doi: 10.3969/j.issn.1007-757X.2020.11.032
[19]	高晓,杨志强,库新勃,等. 基于三次样条插值实现无人机高动态运动轨迹插值[J]. 全球定位系统,2020,45(1):37-42. doi: 10.13442/j.gnss.1008-9268.2020.01.006 GAO Xiao,YANG Zhiqiang,KU Xinbo,et al. 3D-coordinate interpolation for UAV high dynamic positioning based on cubic spline interpolation[J]. GNSS World of China,2020,45(1):37-42. doi: 10.13442/j.gnss.1008-9268.2020.01.006
[20]	张金泽. 水面无人艇路径规划及避障策略的研究[D]. 大连: 大连海事大学, 2022. ZHANG Jinze. Research on path planning and obstacle avoidance strategy of unmanned surface vehicle[D]. Dalian: Dalian Maritime University, 2022.
[21]	刘胜,张豪,晏齐忠,等. 基于ACO−SA算法的变电站巡检机器人路径规划[J]. 南方电网技术,2022,16(9):75-82. doi: 10.13648/j.cnki.issn1674-0629.2022.09.009 LIU Sheng,ZHANG Hao,YAN Qizhong,et al. Path planning of inspection robot in substation based on ACO-SA algorithm[J]. Southern Power System Technology,2022,16(9):75-82. doi: 10.13648/j.cnki.issn1674-0629.2022.09.009