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

Coverage Path Planning Method Based on Grid Region Decomposition

作　　者：胡馨丹 杨盛毅 朱力 宋云云 HU Xindan;YANG Shengyi;ZHU Li;SONG Yunyun(School of Data Science and Information Engineering,Guizhou Minzu University,Guiyang 550025,China;Key Laboratory of Pattern Recognition and Intelligent Systems of Guizhou Province,Guiyang 550025,China;School of Mechatronics Engineering,Guizhou Minzu University,Guiyang 550025,China)

机构地区：[1]贵州民族大学数据科学与信息工程学院,贵州贵阳550025 [2]贵州省模式识别与智能系统重点实验室,贵州贵阳550025 [3]贵州民族大学机械电子工程学院,贵州贵阳550025

出　　处：《机械与电子》2022年第5期13-16,共4页Machinery & Electronics

基　　金：贵州省科学技术基金(黔科合基础[2017]1088)。

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

关 键 词：分区覆盖 FCM聚类 BRESENHAM算法 A*算法 往复式覆盖 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]