Abstract: Under the premise of using grid method in environment modeling, the problem of real-time path planning for mobile robot in the larger-scale working environment with dense obstacles is difficult to solve. A new method of the global path planning for mobile robot-relaxed Dijkstra algorithm was proposed according to the characteristics of grid-map structure. A potential Manhattan distance filed from the start point to global points was constructed first by four neighborhood searching in linear time. Then, eight neighborhood searching was used to get a collision-free, near-optimal path from the target point to the start point. Last, the results of Matlab simulation experiments proved that the proposed method was ten times faster than the Dijkstra algorithm and A-star 〖JP2〗algorithm that had used heap sort on computing time, and compared with the shortest path, the length of its path had a reasonable error.〖JP〗


Key words: grid method, mobile robot, path planning, relaxed Dijkstra algorithm