基于栅格分区的覆盖路径规划方法

针对含有障碍物的作业区域,设计出一种划分区域的覆盖方法。首先将作业区域栅格化,建立栅格地图;其次进行区域划分,利用模糊 C 均值( FCM )聚类算法将障碍物进行聚类,根据聚类结果,求出每一类障碍物的横纵坐标的最小值和最大值;接着先利用 Bresenham 算法沿着障碍物边界最小值进行区域分割;然后求解子区域连接顺序,利用 A * 算法求得子区域间的最优路径;最后利用往复式覆盖方式实现子区域的全覆盖。仿真实验表明,该方法能够完整地覆盖整个作业区域,与传统的 A * 覆盖算法相比,覆盖路径长度减少 13.97% ,重复率降低了 94.44% ,转弯次数减少 16.00% ,且而与传统的遗传覆盖算法相比,覆盖路径长度减少了 3.78% ,重复率降低了 83.33% ,转弯次数增加了 1.61% 。

Coverage Path Planning Method Based on Grid Region Decomposition

Aiming at the working area with obstacles , a partition coverage path planning algorithm is designed.Firstly , the working area is rasterized and a grid map is established.Secondly , the region is divided.The obstacles are clustered using the fuzzy C-means clustering algorithm.According to the clustering results , the minimum and maximum values of the horizontal and vertical coordinates of each type of obstacles are obtained.Then , Bresenham algorithm is used to segment the region along the minimum value of the obstacle boundary , so as to divide the region into multiple sub-regions.The connection order of sub regions is solved , and the optimal motion path between sub-regions is obtained by using A* algorithm.Finally , the complete coverage of sub-regions is realized by back and forth coverage.Simulation experiments show that the designed coverage path planning method can completely cover the entire operation area. Compared with the traditional A* coverage algorithm , the coverage path length is reduced by 13.97% , the repetition rate is reduced by 94.44% , and the number of turns is reduced by 16.00%.Compared with the traditional genetic coverage algorithm , the coverage path length is reduced by 3.78%.The repetition rate decreased by 83.33% and the number of turns increased by 1.61%.