Abstract:

Most of the current vehicle route planning is based on the grid map planning method， which will greatly increase the amount of calculation when the search area is large. In contrast， the method based on visibility graph can reduce the amount of calculation during path search， but is greatly affected by the complexity of obstacles. For this problem， combining the SLAM and visibility graph methods， a simplified visibility graph construction and planning method is proposed in this paper. Firstly， the improved SLAM algorithm is used to generate point cloud maps， and dynamic obstacles are removed. Then a visibility graph is generated， and the complex edges of polygons in the visibility graph are simplified based on the size of the obstacle and the size of the concave angle at the vertex to eliminate redundant vertices. Finally， through simulation experiments and real vehicle experiments， it is proved that compared with the original algorithm， this method can reduce the number of polygon vertices in the visibility graph by 20%-30% while ensuring the accuracy of mapping. The map update time and the running time of the overall algorithm are also reduced by more than 30%. It shows that the method in this paper can effectively reduce the amount of calculation and the running time of the algorithm in the mapping and planning process.

Key words: visibility graph, path planning, SLAM, intelligent vehicle