Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (11): 164-171.DOI: 10.3778/j.issn.1002-8331.1903-0411

Previous Articles     Next Articles

Novel Tree Heuristic Search Algorithm for Robot Path Planning

HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min   

  1. 1.School of Computers, Guangdong University of Technology, Guangzhou 510006, China
    2.School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China
  • Online:2020-06-01 Published:2020-06-01



  1. 1.广东工业大学 计算机学院,广州 510006
    2.广东工业大学 信息工程学院,广州 510006


In order to solve the shortest path of mobile robots in a 3D space from the starting point to the ending point, a new edge point tree heuristic diffusion search(Tree-EP) algorithm is proposed. Firstly, the map space is subjected to density-adjustable 3D discretization. Secondly, the reliable edge point information of the obstacles is screened out according to the safe distance of the obstacles. Thirdly, the potential points are selected to perform a diffusion search for guiding the search direction, according to the tree diffusion architecture. Finally the shortest path is created. A local backtracking adjustment strategy is proposed to locally adjust the path in the search process, resulting in an improved Tree-EP algorithm. In the shortest path search application with complex terrain, the experimental results show that the proposed Tree-EP can find shorter moving paths than other existing algorithms.

Key words: mobile robot, path planning, heuristic algorithm



关键词: 移动机器人, 路径规划, 启发式算法