A* algorithm of global path planning based on the grid map and V-graph environmental model for the mobile robot

Abstract

According to the problem of point-to-point global path planning, this paper presents an A∗ algorithm based on the grid map and V-graph (Visual graph) environmental model for the mobile robot to obtain the optimal path. The algorithm mainly consists of three parts, namely building the grid map, designing the visual point-to-point lines and devising the search strategy of the path planning. The quantized grid shows the coordinates of visual point and expresses the searching cost of the A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup> algorithm. The improved V-graph method computes the vertical distance of the obstacle in a rectangular area from the visual point to the straight line connecting the start point to goal point. The node owning the least distance in one obstacle is selected as the effective point. Then all the effective points are connected to form the visual lines. The improved method reduces the nodes in the searching process, and can achieve the high efficiency of the path planning. The feasibility and effectiveness of the algorithm are verified by the simulation.