一种基于简化可视图的建图和规划方法

A Mapping and Planning Method Based on Simplified Visibility Graph

当前车辆路径规划大部分是基于栅格地图的规划方法,这种方法在搜索面积较大时计算量也会大幅增加。相比之下,基于可视图的方法能够在路径搜索时减小计算量,但是受到障碍物复杂程度的影响较大。针对这一问题,本文结合SLAM和可视图的方法,提出了一种简化可视图的建图和规划方法。首先使用改进的SLAM算法生成点云地图,并进行动态障碍物的剔除。接着生成可视图,并基于障碍物的大小和顶点处内凹角的大小对可视图中多边形的复杂边缘进行简化,剔除冗余的顶点。最后通过仿真和实车实验证明,该方法相对原有的算法,在保证建图精度的情况下,可视图中多边形的顶点数量减少20%~30%,地图更新时间和整体算法的运行时间减少30%以上。这表明本文方法能够有效减小建图和规划过程的计算量和算法的运行时间。

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 obsta-cles.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 re-duce the amount of calculation and the running time of the algorithm in the mapping and planning process.