Abstract:

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

摘要：

面对三维空间移动机器人从起始点到终止点的最短路径问题，提出一种新型的边缘点树启发式搜索（Tree-EP）算法，该方法将地图空间进行密度可调的三维离散化处理，根据障碍安全距离筛选出障碍物的可靠边缘点信息，再利用树扩散架构选出最能引导搜索方向的潜力点进行扩散搜索，最终得出最短路径。提出局部调整策略，得到改进的Tree-EP算法。实验结果表明，在带障碍复杂地形最短路径搜索应用中，提出的Tree-EP算法与已有方法相比，能找到更短的移动路径。

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