摘要： 在分析现有路径规划和碰撞检测方法的基础上，提出了一种新的机器人路径规划方法：双向Dijkstra二叉树算法。在机器人路径规划中应用传统的Dijkstra算法时间复杂度是O(n¬¬¬¬2)，应用该文提出的算法进行路径规划的时间复杂度为O(nlog2n)。通过一些数据的检测，验证了在机器人路径规划中，尤其是在测试数据较多的情况下，该算法可以有效提高效率。

关键词: 机器人路径规划, 最短路径, 双向Dijkstra, 二叉树

Abstract: On the basis of analysis of current path plan methods and collision examining methods, a new robot path plan method is put forward: bi-directional Dijkstra with binary tree sorted algorithm. It is well known that Dijkstra algorithm solves the path plan problem in time O(n¬¬¬¬2). As an improvement on Dijkstra algorithm, because it begins from start point and end point at one time when it executes the algorithm, and sorts the set of the points which have not been marked by binary tree, the algorithm solves path planning problem in time O (nlog n). And the enhancement on the efficiency in robot path plan with the algorithm has been proved by testing some data, especially in the situation where the number of testing data is very large.

Key words: Robot path plan, Shortcut, Bi-directional Dijkstra, Binary tree

中图分类号: 

• TP312