留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

融合改进A*算法与动态窗口法的煤矿足式机器人路径规划

王利民 孙瑞峰 翟国栋 张佳伟 徐弘 赵杰 化一行

王利民,孙瑞峰,翟国栋,等. 融合改进A*算法与动态窗口法的煤矿足式机器人路径规划[J]. 工矿自动化,2024,50(6):112-119.  doi: 10.13272/j.issn.1671-251x.2024020042
引用本文: 王利民,孙瑞峰,翟国栋,等. 融合改进A*算法与动态窗口法的煤矿足式机器人路径规划[J]. 工矿自动化,2024,50(6):112-119.  doi: 10.13272/j.issn.1671-251x.2024020042
WANG Limin, SUN Ruifeng, ZHAI Guodong, et al. Path planning of coal mine foot robot by integrating improved A* algorithm and dynamic window approach[J]. Journal of Mine Automation,2024,50(6):112-119.  doi: 10.13272/j.issn.1671-251x.2024020042
Citation: WANG Limin, SUN Ruifeng, ZHAI Guodong, et al. Path planning of coal mine foot robot by integrating improved A* algorithm and dynamic window approach[J]. Journal of Mine Automation,2024,50(6):112-119.  doi: 10.13272/j.issn.1671-251x.2024020042

融合改进A*算法与动态窗口法的煤矿足式机器人路径规划

doi: 10.13272/j.issn.1671-251x.2024020042
基金项目: 煤炭资源与安全开采国家重点实验室开放基金项目(SKLCRSM21KFA12)。
详细信息
    作者简介:

    王利民(1999—),男,内蒙古赤峰人,硕士研究生,主要研究方向为机器人技术等,E-mail:wanglm01@126.com

    通讯作者:

    翟国栋(1973—),男,河北高碑店人,教授,博士,主要从事机械现代设计理论方法、煤矿机械及其智能化、智能矿山及装备等方面的教学与科研工作,E-mail:zgd@cumtb.edu.cn

  • 中图分类号: TD67

Path planning of coal mine foot robot by integrating improved A* algorithm and dynamic window approach

  • 摘要: 为提高煤矿足式机器人路径规划算法的运行效率、搜索精度及避障灵活性,提出了一种融合改进A*算法与动态窗口法(DWA)的煤矿足式机器人路径规划方法。首先对A*算法进行改进,通过去冗余节点策略减短规划路径的长度,通过改进邻域搜索方式和代价函数提高路径规划速度,采用分段二阶贝塞尔曲线进行路径平滑。将改进A*算法规划出的路径节点依次作为局部路径规划DWA的局部目标点进行算法融合,筛选邻近的障碍物节点,从而再次缩短路径长度,并通过调整DWA代价函数中的权值比例提升避障性能。针对机器人遇到无法避开的障碍物而陷入“假死”状态的问题,以当前初始点为起点,重新调用融合算法,即重新进行全局路径规划,将得到的新节点代替原有的局部目标点,按照新路径进行后续工作。仿真结果表明:在保证机器人行走安全稳定的基础上,改进A*算法较传统A*算法的计算时间缩短了65%,路径长度缩短了24.1%,路径节点数量减少了27.65%,最终得出的路径更为平滑;融合算法进一步提升了全局路径规划能力,在多障碍物环境下能够绕开新增的动态和静态障碍物;机器人遇到“L”型障碍物进入“假死”状态时,在“假死”位置重新进行全局路径规划,更新行走路径,成功到达了最终目标点。基于融合算法的JetHexa六足机器人路径规划实验结果验证了融合算法的有效性和优越性。

     

  • 图  1  A*算法改进途径

    Figure  1.  A* algorithm improvement approach

    图  2  去冗余节点策略

    Figure  2.  Redundant node removal strategy

    图  3  八邻域搜索方式

    Figure  3.  Eight neighborhood search method

    图  4  机器人行走方案流程

    Figure  4.  Robot walking plan flow

    图  5  改进A*算法仿真结果

    Figure  5.  Improved A* algorithm simulation results

    图  6  RRT算法路径规划结果

    Figure  6.  RRT algorithm path planning results

    图  7  融合算法路径规划结果

    Figure  7.  Fusion algorithm path planning results

    图  8  融合算法避障性能验证

    Figure  8.  Verification of obstacle avoidance performance of fusion algorithm

    图  9  单一路径规划算法避障性能

    Figure  9.  Obstacle avoidance performance of single path planning algorithm

    图  10  融合算法在随机地图上的测试结果

    Figure  10.  Test results of fusion algorithm on random maps

    图  11  “假死”应对方案路径规划结果

    Figure  11.  Path planning results of the response plan for "feigned death"

    图  12  实验地图环境

    Figure  12.  Experimental map environment

    图  13  地图构建

    Figure  13.  Map construction

    图  14  算法改进前后路径规划结果

    Figure  14.  Path planning results before and after algorithm improvement

    图  15  融合算法避障性能验证

    Figure  15.  Verification of obstacle avoidance performance of fusion algorithm

    表  1  邻域删除策略

    Table  1.   Neighborhood deletion strategy

    角度区间 删除邻域
    −22.5°≤θ<22.5° 出发点左侧邻域
    22.5°≤θ<67.5° 出发点左下侧邻域
    67.5°≤θ<112.5° 出发点下侧邻域
    112.5°≤θ<157.5° 出发点右下侧邻域
    −180°≤θ<−157.5° 或 157.5°≤θ<180° 出发点右侧邻域
    −157.5°≤θ<−112.5° 出发点右上侧邻域
    −112.5°≤θ<−67.5° 出发点上侧邻域
    −67.5°≤θ<−22.5° 出发点左上侧邻域
    下载: 导出CSV

    表  2  A*算法改进前后性能对比

    Table  2.   Comparison of performance before and after A* algorithm improvement

    算法 规划时间/s 规划路径长度/cm 路径节点数/个
    传统A*算法 1.20 55.6 47
    应用去冗余节点 1.19 38.8 31
    改进A*算法 0.42 42.2 34
    下载: 导出CSV

    表  3  算法改进前后性能对比

    Table  3.   Comparison of performance before and after algorithm improvement

    算法 规划时间/s 路径长度/cm
    A*算法+DWA 1.97 424
    改进A*算法+DWA 1.10 368
    下载: 导出CSV
  • [1] 涂亮杰,李林升,林国湘. 果园移动机器人的全局最优路径规划研究[J]. 南华大学学报(自然科学版),2017,31(4):71-74.

    TU Liangjie,LI Linsheng,LIN Guoxiang. Orchard global optimal path planning for mobile robot research[J]. Journal of University of South China (Science and Technology),2017,31(4):71-74.
    [2] 张毅,杨光辉,花远红. 基于改进人工鱼群算法的机器人路径规划[J]. 控制工程,2020,27(7):1157-1163.

    ZHANG Yi,YANG Guanghui,HUA Yuanhong. Robot path planning based on improved artificial fish swarm algorithm[J]. Control Engineering of China,2020,27(7):1157-1163.
    [3] 张正昊. 基于RRT的移动机器人路径规划算法与实验研究[D]. 南京:南京航空航天大学,2021.

    ZHANG Zhenghao. Path planning algorithm for mobile robot based on RRT and its experiments[D]. Nanjing:Nanjing University of Aeronautics and Astronautics,2021.
    [4] 蒋仁炎,俞万能,廖卫强,等. 智能全电船的低能耗路径规划算法研究[J]. 中国造船,2021,62(2):245-254.

    JIANG Renyan,YU Wanneng,LIAO Weiqiang,et al. Optimal energy consumption based path planning for intelligent all-electric ships[J]. Shipbuilding of China,2021,62(2):245-254.
    [5] 李航宇,郭晓利. 考虑多因素的自适应遗传算法机器人路径规划[J]. 制造业自动化,2022,44(10):76-78,95.

    LI Hangyu,GUO Xiaoli. Path planning of robot based on adaptive genetic algorithm considering multiple factors[J]. Manufacturing Automation,2022,44(10):76-78,95.
    [6] 郝琨,张慧杰,李志圣,等. 基于改进避障策略和双优化蚁群算法的机器人路径规划[J]. 农业机械学报,2022,53(8):303-312,422.

    HAO Kun,ZHANG Huijie,LI Zhisheng,et al. Path planning of mobile robot based on improved obstacle avoidance strategy and double optimization ant colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery,2022,53(8):303-312,422.
    [7] 王宪伦,王天宇,丁文壮. 基于改进人工势场法的机械臂路径规划[J]. 组合机床与自动化加工技术,2022(6):24-27.

    WANG Xianlun,WANG Tianyu,DING Wenzhuang. Path planning algorithm of manipulator based on improved artificial potential field method[J]. Modular Machine Tool & Automatic Manufacturing Technique,2022(6):24-27.
    [8] 陈奕梅,沈建峰,李柄棋. 改进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.
    [9] 丁皓,刘浩宇,庄逸,等. 基于四轮差速模型的多机器人路径规划[J]. 控制工程,2023,30(4):730-738.

    DING Hao,LIU Haoyu,ZHUANG Yi,et al. Multi-robot path planning based on four-wheel differential speed model[J]. Control Engineering of China,2023,30(4):730-738.
    [10] LI Yue,ZHAO Jianyou,CHEN Zenghua,et al. A robot path planning method based on improved genetic algorithm and improved dynamic window approach[J]. Sustainability,2023,15(5). DOI: 10.3390/su15054656.
    [11] ZHOU Yuyang,WANG Dongshu. Path planning of mobile robot in complex environment based on improved Q-learning algorithm[J]. International Journal of Mechanisms and Robotic Systems,2023,5(3):223-245. doi: 10.1504/IJMRS.2023.129453
    [12] 张阳伟,乔越,李成凤. 基于四叉树栅格环境的变步长双向A*算法[J]. 控制工程,2021,28(10):1960-1966.

    ZHANG Yangwei,QIAO Yue,LI Chengfeng. Variable step size bidirectional A* algorithm based on quadtree grid environment[J]. Control Engineering of China,2021,28(10):1960-1966.
    [13] SUN Yang,WANG Haipeng. A novel A* method fusing bio-inspired algorithm for mobile robot path planning[J]. ICST Transactions on Scalable Information Systems,2018. DOI: 10.4108/eai.14-9-2021.170953.
    [14] DURAKL Z,NABIYEV V. A new approach based on Bezier curves to solve path planning problems for mobile robots[J]. Journal of Computational Science,2022,58. DOI: 10.1016/j.jocs.2021.101540.
    [15] XIANG Dan,LIN Hanxi,OUYANG Jian,et al. Combined improved A* and greedy algorithm for path planning of multi-objective mobile robot[J]. Scientific Reports,2022,12(1). DOI: 10.1038/s41598-022-17684-0.
    [16] WANG Zelin,GAO Feng,ZHAO Yue,et al. Improved A* algorithm and model predictive control-based path planning and tracking framework for hexapod robots[J]. Industrial Robot:the International Journal of Robotics Research and Application,2023,50(1):135-144. doi: 10.1108/IR-01-2022-0028
    [17] 汪四新,谭功全,蒋沁,等. 基于改进A*算法的移动机器人路径规划[J]. 计算机仿真,2021,38(9):386-389,404.

    WANG Sixin,TAN Gongquan,JIANG Qin,et al. Path planning for mobile robot based on improved A* algorithm[J]. Computer Simulation,2021,38(9):386-389,404.
    [18] 徐嘉骏,辛绍杰,邓寅喆. 基于改进A*与TEB算法融合的移动机器人路径规划[J]. 计量与测试技术,2022,49(5):26-30.

    XU Jiajun,XIN Shaojie,DENG Yinzhe. Mobile robot path planning based on the fusion of improved A* and TEB algorithm[J]. Metrology & Measurement Technique,2022,49(5):26-30.
    [19] YANG Hongxia,TENG Xingqiang. Mobile robot path planning based on enhanced dynamic window approach and improved A algorithm[J]. Journal of Robotics,2022. DOI: 10.1155/2022/2183229.
    [20] 庞永旭,袁德成. 融合改进A*与DWA算法的移动机器人路径规划[J]. 计算机与现代化,2022(1):103-107.

    PANG Yongxu,YUAN Decheng. Mobile robot path planning based on fusion of improved A* and DWA algorithms[J]. Computer and Modernization,2022(1):103-107.
    [21] XU Zhenyang,YUAN Wei. Mobile robot path planning based on fusion of improved A* algorithm and adaptive DWA algorithm[J]. Journal of Physics:Conference Series,2022,2330(1). DOI:10.1088/1742-6596/2330/ 1/012003.
  • 加载中
图(15) / 表(3)
计量
  • 文章访问数:  47
  • HTML全文浏览量:  12
  • PDF下载量:  10
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-02-26
  • 修回日期:  2024-06-11
  • 网络出版日期:  2024-07-10

目录

    /

    返回文章
    返回