Path Planning of Robot Combing Safety A* Algorithm and Dynamic Window Approach

doi:10.19678/j.issn.1000-3428.0062264

Abstract

Abstract: The A^* algorithm relies on heuristic information to guide the search direction and is widely used for path planning of mobile robots.However, the search path of this algorithm has redundant nodes that are similar to obstacles, which prevent the algorithm from meeting the requirements of dynamic obstacle avoidance.This study aims to improve the standard A^* algorithm by designing a safe A^* algorithm and integrating the Dynamic Window Approach(DWA) for path planning.Particularly, the safety distance factor is defined and introduced into the heuristic function of the A^* algorithm to improve the safety of the path planned by the algorithm.Simultaneously, the plane structure method is used to optimize the path planned by the algorithm.The relationship between the positions of adjacent nodes and obstacles is used to determine whether obstacles exist between adjacent nodes to reduce the number of inflection points of the path and improve the smoothness of the path.When the mobile robot is in an unknown environment, the A^* algorithm alone cannot prevent the robot from avoiding obstacles on its way to reaching the target point;therefore, the local obstacle avoidance function of the DWA is used.The global optimal path node coordinates are planned using the safe A^* algorithm.In addition, the fusion sub-function is designed to improve the evaluation function of the DWA to solve the tendency of the DWA to easily converge to local optima.The experimental results show that in a complex environment, integration of the safe A^* algorithm and the DWA ensures real-time random obstacle avoidance based on the safe path, thereby enabling the robot to reach the end point safely.

Key words: A^* algorithm, safety distance factor, plane structure method, Dynamic Window Approach(DWA), path planning

摘要： A^*算法通过启发信息指引搜索方向，被广泛应用于移动机器人的路径规划，但其规划出的搜索路径存在冗余节点且与障碍物相近，无法满足动态避障需求。对标准A^*算法进行改进，设计安全A^*算法并融合动态窗口法进行路径规划。定义安全距离因子引入A^*算法的启发函数中，提高算法规划路径的安全性，同时采用平面结构法对算法规划得到的路径进行优化，根据相邻节点与障碍物之间的位置关系判断该相邻节点间是否存在障碍物，由此减少路径拐点数，提高路径平滑度。由于当移动机器人处于未知环境时，仅靠A^*算法不能避开障碍物到达目标点，因此借助动态窗口法的局部避障功能。通过安全A^*算法规划全局最优路径节点坐标，设计融合子函数改进动态窗口法的评价函数，解决动态窗口法易陷入局部最优的问题。实验结果表明，在复杂环境中，该方法通过融合安全A^*算法和动态窗口法，能够确保在安全路径基础上实时随机避障，使机器人安全到达终点。

关键词: A^*算法, 安全距离因子, 平面结构法, 动态窗口法, 路径规划

CLC Number:

TP391

ZHAN Jingwu, HUANG Yiqing. Path Planning of Robot Combing Safety A^* Algorithm and Dynamic Window Approach[J]. Computer Engineering, 2022, 48(9): 105-112,120.

詹京吴, 黄宜庆. 融合安全A^*算法与动态窗口法的机器人路径规划[J]. 计算机工程, 2022, 48(9): 105-112,120.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0062264

http://www.ecice06.com/EN/Y2022/V48/I9/105

Figures/Tables 12

References

[1] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik, 1959, 1(1):269-271.
[2] WANG L, HUI X.Improved ant colony-genetic algorithm for information transmission optimization in remanufacturing service system[J].Chinese Journal of Mechanical Engineering, 2018, 31(6):106-117.
[3] MAC T T, COPOT C, TRAN D T, et al.A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J].Applied Soft Computing, 2017, 59(3):68-76.
[4] 付丽霞, 任玉洁, 张勇, 等.基于改进平滑A^*算法的移动机器人路径规划[J].计算机仿真, 2020, 37(8):271-276. FU L X, REN Y J, ZHANG Y, et al.Path planning of mobile robot based on improved smoothing A^* algorithms[J].Computer Simulation, 2020, 37(8):271-276.(in Chinese)
[5] 周滔, 赵津, 胡秋霞, 等.复杂环境下移动机器人全局路径规划与跟踪[J].计算机工程, 2018, 44(12):208-214. ZHOU T, ZHAO J, HU Q X, et al.Global path planning and tracking for mobile robot in cluttered environment[J].Computer Engineering, 2018, 44(12):208-214.(in Chinese)
[6] DROGE G.Dual-mode dynamic window approach to robot navigation with convergence guarantees[J].Journal of Control and Decision, 2021, 8(2):77-88.
[7] YANG W L, WU P, ZHOU X Q, et al.Improved artificial potential field and dynamic window method for amphibious robot fish path planning[J].Applied Sciences, 2021, 12(5):14-19.
[8] HART P, NILSSON N, RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
[9] 辛煜, 梁华为, 杜明博, 等.一种可搜索无限个邻域的改进A^*算法[J].机器人, 2014, 36(5):627-633. XIN Y, LIANG H W, DU M B, et al.An improved A^* algorithm for searching infinite neighbourhoods[J].Robot, 2014, 36(5):627-633.(in Chinese)
[10] 张志文, 张鹏, 毛虎平, 等.改进A^*算法的机器人路径规划研究[J].电光与控制, 2021, 28(4):21-25. ZHANG Z W, ZHANG P, MAO H P, et al.Path planning of mobile robot based on improved A^* algorithm[J].Electronics Optics & Control, 2021, 28(4):21-25.(in Chinese)
[11] 王志中.复杂动态环境下自主机器人路径规划研究[J].组合机床与自动化加工技术, 2018(1):64-68. WANG Z Z.Automatic robot path planning under complicit dynamic environment[J].Modular Machine Tool & Automatic Manufacturing Technique, 2018(1):64-68.(in Chinese)
[12] LI X Y, LIU F, LIU J, et al.Obstacle avoidance for mobile robot based on improved dynamic window approach[J].Turkish Journal of Electrical Engineering & Computer Sciences, 2017, 25:666-676.
[13] 常新新, 胡为, 姬书得, 等.基于改进动态窗口法的移动机器人避障研究[J].组合机床与自动化加工技术, 2021(7):33-36, 39. CHANG X X, HU W, JI S D, et al.Obstacle avoidance of mobile robot based on improved dynamic window method[J].Modular Machine Tool & Automatic Manufacturing Technique, 2021(7):33-36, 39.(in Chinese)
[14] 阳钧, 鲍泓, 梁军, 等.一种基于高精度地图的路径跟踪方法[J].计算机工程, 2018, 44(7):8-13. YANG J, BAO H, LIANG J, et al.Application of improved fireworks algorithm in path planning of virtual soldier[J]. Computer Engineering, 2018, 44(7):8-13.(in Chinese)
[15] 卞永明, 季鹏成, 周怡和, 等.基于改进型DWA的移动机器人避障路径规划[J].中国工程机械学报, 2021, 19(1):44-49. BIAN Y M, JI P C, ZHOU Y H, et al.Obstacle avoidance path planning of mobile robot based on improved DWA[J].Chinese Journal of Construction Machinery, 2021, 19(1):44-49.(in Chinese)
[16] BAYILI S, POLAT F.Limited-Damage A^*:a path search algorithm that considers damage as a feasibility criterion[J].Knowledge-Based Systems, 2011, 24(4):501-512.
[17] AINE S, SWAMINATHAN S, NARAYANAN V, et al.Multi-Heuristic A^*[J].International Journal of Robotics Research, 2016, 35(1/2/3):224-243.
[18] 黄令苇, 全燕鸣, 王荣辉.基于安全A^*算法的AGV路径规划[J].自动化与仪表, 2021, 36(1):45-48. HUANG L W, QUAN Y M, WANG R H.AGV path planning based on safe-A^* algorithm[J].Automation & Instrumentation, 2021, 36(1):45-48.(in Chinese)
[19] SUN Y, YOU Y, SUN X et al.The hybrid path planning algorithm based on improved A^* and artificial potential field for unmanned surface vehicle formations[J].Ocean Engineering, 2021, 22(3):3-4.
[20] JIANG H J, SUN Y, WANG X W, et al.Research on path planning of mobile disinfection robot based on improved A^* algorithm[J].Journal of Physics:Conference Series, 2021, 1871(1):1-10.
[21] 张家旭, 王欣志, 赵健, 等.汽车高速换道避让路径规划及离散滑模跟踪控制[J].吉林大学学报(工学版), 2021, 51(3):1081-1090. ZHANG J X, WANG X Z, ZHAO J, et al.Path planning and discrete sliding mode tracking control for high-speed lane changing collision avoidance of vehicle[J].Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3):1081-1090.(in Chinese)
[22] FOX D, BURGARD W, THRUN S.The dynamic window approach to collision avoidance[J].IEEE Robotics & Automation Magazine, 1997, 4(1):23-33.
[23] 张瑜, 宋荆洲, 张琪祁.基于改进动态窗口法的户外清扫机器人局部路径规划[J].机器人, 2020, 42(5):617-625. ZHANG Y, SONG J Z, ZHANG Q Q.Local path planning of outdoor cleaning robot based on an improved DWA[J].Robot, 2020, 42(5):617-625.(in Chinese)
[24] 迟旭, 李花, 费继友.基于改进A^*算法与动态窗口法融合的机器人随机避障方法研究[J].仪器仪表学报, 2021, 42(3):132-140. CHI X, LI H, FEI J Y.Research on robot random obstacle avoidance method based on fusion of improved A^* algorithm and dynamic window method[J].Chinese Journal of Scientific Instrument, 2021, 42(3):132-140.(in Chinese)
[25] ZHONG X Y, TIAN J, HU H S, et al.Hybrid path planning based on safe A^* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment[J].Journal of Intelligent & Robotic Systems, 2020, 99(1):65-77.

Please choose a citation manager

Content to export