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六足机器人路径规划实验结果验证了融合算法的有效性和优越性。Abstract: In order to improve the operational efficiency, search precision, and obstacle avoidance flexibility of the path planning algorithm for coal mine foot robot, a path planning method for coal mine foot robots is proposed, which integrates the improved A* algorithm and the dynamic window approach (DWA). Firstly, the A* algorithm is improved by reducing the length of the planned path through a redundant node removal strategy. The method improves the neighborhood search method and cost function to increase the speed of path planning, and uses segmented second-order Bessel curves for path smoothing. The path nodes planned by the improved A* algorithm are sequentially used as local target points for local path planning DWA for algorithmic fusion. The method filters neighboring obstacle nodes to shorten the path length again, and improves obstacle avoidance performance by adjusting the weight ratio in the DWA cost function. In response to the problem of robots falling into a "feigned death" state when encountering unavoidable obstacles, the method starts from the current initial point, the fusion algorithm is called up again. The global path planning is carried out again, and the new nodes obtained replace the original local target points, and the subsequent work is carried out according to the new route. The simulation results show that, while ensuring the safety and stability of robot walking, the improved A* algorithm reduces the calculation time by 65%, the path length by 24.1%, and the number of path nodes by 27.65% compared to the traditional A* algorithm, resulting in a smoother path. The fusion algorithm further enhances the global path planning capability, enabling it to bypass newly added dynamic and static obstacles in multi obstacle environments. When the robot encounters an L-shaped obstacle and enters a "feigned death" state, it reconducts global path planning at the "feigned death" position, updates its walking path, and successfully reaches the final target point. The experimental results of path planning for JetHexa hexapod robot based on fusion algorithm have verified the effectiveness and superiority of the fusion algorithm.
-
图 8 融合算法避障性能验证
Figure 8. Verification of obstacle avoidance performance of fusion algorithm
图 9 单一路径规划算法避障性能
Figure 9. Obstacle avoidance performance of single path planning algorithm
图 11 “假死”应对方案路径规划结果
Figure 11. Path planning results of the response plan for "feigned death"
图 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)
计量
- 文章访问数: 94
- HTML全文浏览量: 23
- PDF下载量: 15
- 被引次数: 0
