| With the emergence of driverless and sweeping robot markets,path planning has been a hot topic of research in robotics,and global path planning mainly refers to finding a feasible path that can reach the end point in the known two-dimensional or three-dimensional environment information.A Star Algorithm(A~*)algorithm as a heuristic algorithm,although it can find an asymptotically optimal path by calculating the predicted cost and the existing cost.Although it can find an asymptotically optimal path by calculating the estimated cost and existing cost it usually consumes too much time and memory.In contrast to the artificial potential field method,which often requires the establishment of potential fields for the map in advance to guide the robot to the end point,the robot is prone to fall into the local optimum in the superposition of potential fields leading to failure sometimes,as opposed to the sampling methods Rapidly-exploring random tree(RRT)and probabilistic road map method(PRM)with efficient randomness and completeness,in which the RRT does not need to calculate the distance cost and prediction cost.For stochastic exploration methods,scholars have proposed numerous optimization algorithms based on RRT,such as RRT~*,which optimizes the RRT father node,and B-RRT,which improves the efficiency of bidirectional sampling.It is improved on the basis of RRT by generating two trees at the start and end points in turn to explore the map and return the found path when the distance between the two tree nodes is less than a certain threshold.Compared with other algorithms,the bi-directional exploring random tree(B-RRT)algorithm is faster and consumes less memory.Formally based on this paper,an RRT is proposed in combination with experimental findings.This method is called Graft-RRT.The main advantages of this method are the low cost of the explored global path and the fast exploration speed.Based on the idea of bi-directional exploring random tree B-RRT,the algorithm generates a third random tree,Graft-Tree,by finite random sampling of the feasible region between the starting point and the ending point,and then extends the starting point random tree and the ending point random tree.When the global path is obtained,the global path cost is reduced by compressing the effective cost on the path several times.The simulation results show that the global path cost found by this method is significantly lower than that of B-RRT and RRT~*,and the time consumed is lower than that of RRT and RRT~* for the same complex and simple environments. |
