A Fast Path Planning Method for Mobile Robot Based on Voronoi Diagram and Improved D* Algorithm

Abstract

Fast path planning is hard to achieve for a mobile robot due to the difficulties in balancing the efficiency and distance security requirements between the desired path and obstacle. To address this problem, a practical path planning method is proposed by combining Voronoi and D* (VD*) algorithm. A Voronoi-based method is presented to re-divide the map and re-fit the obstacles so that the intensity of the sampling points is specified satisfactorily and the consuming time can be mitigated. Moreover, by utilizing the improved VD* algorithm, the search step size is regulated adaptively to speed up the planning convergence. Thus, an efficiently-planned and smooth path can be guaranteed. Moreover, the effectiveness and superiority of the proposed method is verified by simulations in two mobile robot situations, which show reduced calculation burden while achieving a smooth and short path.