[1]胡馨丹,杨盛毅,等.基于栅格分区的覆盖路径规划方法[J].机械与电子,2022,(05):13-16.
　HU Xindan,YANG Shengyi,et al.Coverage Path Planning Method Based on Grid Region Decomposition[J].Machinery & Electronics,2022,(05):13-16.
点击复制

基于栅格分区的覆盖路径规划方法()
分享到：

机械与电子[ISSN:1001-2257/CN:52-1052/TH]

卷:
期数:
2022年05期
页码:
13-16
栏目:
设计与研究
出版日期:
2022-05-24

文章信息/Info

Title:
Coverage Path Planning Method Based on Grid Region Decomposition
文章编号:
1001-2257 ( 2022 ) 05-0013-04
作者:
胡馨丹 1 ; 2 ; 杨盛毅 2 ;  3 ; 朱 力 1 ;  2 ; 宋云云 1 ;  2
1. 贵州民族大学数据科学与信息工程学院,贵州 贵阳 550025;2. 贵州省模式识别与智能系统重点实验室,贵州 贵阳 550025 ;3. 贵州民族大学机械电子工程学院,贵州 贵阳 550025
Author(s):
HU Xindan1 ;  2 ;  YANG Shengyi2 ;  3 ;  ZHU Li1 ;  2 ;  SONG Yunyun1 ; 2
(1.School of Data Science and Information Engineering , Guizhou Minzu University , Guiyang 550025 , China ;2.Key Laboratory of Pattern Recognition and Intelligent Systems of Guizhou Province , Guiyang 550025 , China ;3.School of Mechatronics Engineering , Guizhou Minzu University , Guiyang 550025 , China )
关键词:
分区覆盖; FCM 聚类;  Bresenham 算法;  A* 算法; 往复式覆盖
Keywords:
partition coverage ;  FCM clustering ;  Bresenham algorithm ;  A* algorithm ;  back and forth coverage
分类号:
TP242
文献标志码:
A
摘要:
针对含有障碍物的作业区域,设计出一种划分区域的覆盖方法。首先将作业区域栅格化,建立栅格地图;其次进行区域划分,利用模糊 C 均值( FCM )聚类算法将障碍物进行聚类,根据聚类结果,求出每一类障碍物的横纵坐标的最小值和最大值;接着先利用 Bresenham 算法沿着障碍物边界最小值进行区域分割;然后求解子区域连接顺序,利用 A * 算法求得子区域间的最优路径;最后利用往复式覆盖方式实现子区域的全覆盖。仿真实验表明,该方法能够完整地覆盖整个作业区域,与传统的 A * 覆盖算法相比,覆盖路径长度减少 13.97% ,重复率降低了 94.44% ,转弯次数减少 16.00% ,且而与传统的遗传覆盖算法相比,覆盖路径长度减少了 3.78% ,重复率降低了 83.33% ,转弯次数增加了 1.61% 。
Abstract:
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%.

参考文献/References:

[ 1 ] AGGARWAL S , KUMAR N.Path planning techniques for unmanned aerial behicles : a review , solutions , and challenges [ J ] .Computer communications , 2020 , 149 :270-299.

[ 2 ] CHEN H B , LAN Y B , FRITZ B K , et al.Review of agricultural spraying technologies for plant protection using unmanned aerial vehicle( UAV )[ J ] .International journal of agricultural and biological engineering ,2021 , 14 ( 1 ): 38-49.
[ 3 ] FAICAL B S , PESSIN G , FILHO G P R , et al.Fine tuning of UAV control rules for spraying pesticides on crop fields : an approach for dynamic environments [ J ] . International journal on artificial intelligence tools , 2016 , 25 ( 1 ): 1660003-1-1660003-19.
[ 4 ] DELAVARPOUR N , KOPARAN C , NOWATZKI J , et al.A technical study on UAV characteristics for precision agriculture applications and associated practical challenges [ J ] .Remote sensing , 2021 , 13 ( 6 ): 1204-1-1204-25.
[ 5 ] BOURSIANIS A D , PAPADOPOULOU M S , BA ROUCHAS P , et al.Internet of things( IoT ) and agricultural unmanned aerial vehicles( UAVs ) in smart farming : a comprehensive review [ J ] .Internet of things , 2020 : 100187-1-100187-17.
[ 6 ] CAI Z Y , LI S X , GAN Y , et al.Research on complete coverage path planning algorithms based on A* algorithms [ J ] .The open cybernetics and systemics journal , 2014 , 8 : 418-426.
[ 7 ] CABREIRA T M , BRISOLARA L B , FERREIRA JR. P R.Survey on coverage path planning with unmanned aerial vehicles [ J ] .Drones , 2019 , 3 ( 1 ): 1-38.
[ 8 ] 王嘉琪 . 多旋翼农用无人机航迹规划的方法研究[ D ] .武汉:湖北工业大学,2019.
[ 9 ] PHAM T H , ICHALAL D , MAMMAR S.Complete coverage path planning for pests-ridden in precision agriculture using UAV [ C ]// 2020 IEEE International Conference on Networking , Sensing and Control( ICNSC ) .New York : IEEE , 2020 : 1-6.
[ 10 ] 王维一,裴韬,秦承志 . 栅格地理数据模糊 C 均值聚类算法的并行化研究 [ J ] . 地理与地理信息科学,2013 , 29 ( 4 ): 77-80 , 90.
[ 11 ] AU C , WOO T.Three dimensional extension of Bresenham ’ s algorithm with Voronoi diagram [ J ] .Computer-aided design , 2011 , 43 ( 4 ): 417-426.

备注/Memo

备注/Memo:
收稿日期: 2021-12-07
基金项目:贵州省科学技术基金(黔科合基础[ 2017-]-1088 )
作者简介:胡馨丹 ( 1996- ),女,贵州贵阳人,硕士研究生,研究方向为统计学;杨盛毅 ( 1986- ),男,贵州平塘人,副教授,研究方向为飞行器动力学与控制;朱 力 ( 1996- ),女,贵州织金人,硕士研究生,研究方向为统计学;宋云云 ( 1997- ),女,贵州纳雍人,硕士研究生,研究方向为统计学。
更新日期/Last Update: 2022-05-25