Bi-directional Dijkstra with Binary Tree Sorted Algorithm in Robot Path Plan
Guangming Dai · Jisuanji gongcheng · 2007
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(n2).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.