Path planning of coal mine rescue robot based on improved A* algorithm
-
摘要: 路径规划是煤矿救援机器人研究的重要内容之一。针对灾后煤矿环境非结构化的特点，以及传统A*算法规划的路径长度非最短、拐弯次数多和平滑度较差等问题，提出一种基于改进A*算法的煤矿救援机器人路径规划方法。对真实环境中的地图信息进行二值化处理，构建栅格地图；判断当前点与目标点的相对位置，利用改进A*算法进行路径规划，得到一条从当前点到目标点的路径；利用Douglas-Peucker（D−P）算法提取路径上的关键节点，采用三次样条插值函数对关键节点进行拟合，完成对路径的平滑处理。改进A*算法将传统A*算法的8邻域搜索扩展为有目的性的13邻域搜索，在进行路径搜索时，先对当前点和目标点的位置关系进行判断，从而减少路径节点，减小路径长度，提升路径平滑度。Matlab仿真结果表明：与8邻域A*算法、24邻域A*算法、48邻域A*算法相比，改进A*算法在路径长度、拐弯次数、平滑度等方面有一定优化，更适用于煤矿救援机器人路径规划；与Fuzzy算法相比，改进A*算法路径规划所用时间更短，规划的路径长度更短，拐弯次数更少。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.
-
-
![]()
图 2 当前点与目标点的位置关系
Figure 2. The positional relationship between the current point and the target point
![]()
图 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
-
[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
-
期刊类型引用(6)
1. 周昱，翁丽贞，权欣文. 基于改进A~*算法与时间窗检测法的多AGV路径规划方法. 船舶工程. 2024(01): 121-126 . 
百度学术
2. 薛光辉，王梓杰，王一凡，李亚男，刘文海. 基于改进人工势场算法的煤矿井下机器人路径规划. 工矿自动化. 2024(05): 6-13 . 本站查看
3. 朱洪波，花荣. 煤矿巡检机器人路径规划方法. 工矿自动化. 2024(07): 107-114 . 本站查看
4. 何媛媛，唐东林，车健波，王平杰，黄怡丁，张苏洋. 基于改进人工势场算法的爬壁机器人避障研究. 西部特种设备. 2024(05): 8-14 . 百度学术
5. 殷宏亮，朱洪波. 融合目标导向和跳跃点改进A*算法的煤矿巡检机器人路径规划. 煤矿机械. 2024(12): 180-184 . 百度学术
6. 张湘，余捷，于廷海，王奕辉，叶盛. 基于双向搜索的改进A~*算法路径规划. 福建理工大学学报. 2024(06): 567-572+604 . 百度学术
其他类型引用(4)
计量
- 文章访问数: 841
- HTML全文浏览量: 34
- PDF下载量: 64
- 被引次数: 10
