Study on the whole area coverage of agricultural robot in complex environment based on ant colony-BFS algorithm

WANG Wei; ZHANG Yanfei; GONG Jinliang

doi:10.7671/j.issn.1001-411X.202009027

Journal of South China Agricultural University > 2021 > 42(3): 119-125. > DOI: 10.7671/j.issn.1001-411X.202009027

WANG Wei, ZHANG Yanfei, GONG Jinliang. Study on the whole area coverage of agricultural robot in complex environment based on ant colony-BFS algorithm [J]. Journal of South China Agricultural University, 2021, 42(3): 119-125. DOI: 10.7671/j.issn.1001-411X.202009027

Citation:

PDF (2661 KB)

Study on the whole area coverage of agricultural robot in complex environment based on ant colony-BFS algorithm

1.
School of Mechanical Engineering, Shandong University of Technology, Zibo 255000, China
2.
School of Agricultural Engineering and Food Science, Shandong University of Technology, Zibo 255000, China

More Information

Received Date: September 13, 2020
Available Online: May 17, 2023

Graphical Abstract

Abstract

Abstract

Objective
To solve the whole area coverage problem of agricultural robot in digital ecological farm with path repetition rate as the optimization target.

Method
Firstly, the obstacles in the raster map were expanded and rectangular partitioning was performed and the partitions were merged. Then, the improved ant colony algorithm was used to calculate the traversal order among partitions, and the improved breadth first search (BFS) algorithm was used to calculate the connecting path between the end point and the starting point between partitions. By this way, the whole area coverage of robot could be achieved. The improvement schemes of the two algorithms were as following: The selection and crossover operators of genetic algorithm were improved by artificial immune algorithm and particle swarm optimization algorithm respectively. The improved selection and crossover operators, mutation operator of original genetic algorithm and ant colony algorithm were combined to improve the pheromone updating method of traditional ant colony algorithm. The dynamic function was established to simplify the path planned by BFS algorithm.

Result
The simulation results showed that the number of iterations and path length of the improved ant colony algorithm were 83.1% and 4.8% less than those of the traditional ant colony algorithm. The path repetition rate of the improved ant colony algorithm and the improved BFS algorithm was 56% of the traditional ant colony algorithm and BFS algorithm, and the agricultural robot could achieve 100% coverage of farmland.

Conclusion
This study provides a solution for agricultural robots to perform the whole area coverage in digital ecological circular farm with complex environments.
- path repetition rate,
- agricultural robot,
- ant colony algorithm,
- travelling salesman problem,
- breadth first search algorithm

FullText(HTML)

References (19)

References

[1]	LAN Y B, CHEN S D. Current status and trends of plant protection UAV and its spraying technology in China[J]. International Journal of Precision Agricultural Aviation, 2018, 1(1): 1-9.
[2]	PATHAK R, BARZIN R, BORA G C. Data-driven precision agricultural applications using field sensors and unmanned aerial vehicle (UAVs)[J]. International Journal of Precision Agricultural Aviation, 2018, 1(1): 19-23.
[3]	唐东林, 袁波, 胡琳, 等. 储罐探伤爬壁机器人全遍历路径规划方法[J]. 工程设计学报, 2018, 25(3): 253-261.
[4]	李伟莉, 赵东辉. 基于栅格法与神经元的机器人全区域覆盖算法[J]. 机械设计与制造, 2017(8): 232-234.
[5]	CHOI Y H, LEE T K, BAEK S H, et al. Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Missouri, USA: IEEE, 2009: 5788-5793.
[6]	KAPANOGLU M, OZKAN M, YAZICI A, et al. Pattern-based genetic algorithm approach to overage path planning for mobile robots[M]. Berlin: Springer Berlin Heidelberg, 2009.
[7]	李楷, 陈永府, 金志勇, 等. 基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学, 2019, 41(7): 1227-1235.
[8]	曹翔, 俞阿龙. 移动机器人全覆盖信度函数路径规划算法[J]. 智能系统学报, 2018, 13(2): 314-321.
[9]	聂杨. 智能割草机器人的关键技术研究[D]. 重庆: 重庆大学, 2018.
[10]	张堂凯. 己知环境下智能清洁机器人路径规划研究[D]. 南京: 南京邮电大学, 2017.
[11]	谭阳. 求解广义旅行商问题的若干进化算法研究[D]. 广州: 华南理工大学, 2013.
[12]	马慧茹, 赵峰, 贾利民, 等. 基于随机机会约束规划模型的旅行商问题及其求解算法[J]. 长安大学学报(自然科学版), 2015, 35(S1): 179-183.
[13]	陈志, 韩兴国. 改进蚁群算法在移动机器人路径规划上的应用[J]. 计算机工程与设计, 2020, 41(8): 2388-2395.
[14]	周兰凤, 杨丽娜, 方华. 基于蚁群算法的滑移预测路径规划研究[J]. 华东师范大学学报(自然科学版), 2020(4): 72-78.
[15]	王槐彬, 彭雪, 周诗源, 等. 机器人导航路径的动态分级蚁群算法规划策略[J]. 机械设计与制造, 2020(6): 95-99.
[16]	YANG D D, JIAO L C, NIU R C, et al. Investigation of combinational clustering indices in artificial immune multi-objective clustering[J]. Computational Intelligence, 2014, 30(1): 115-144. doi: 10.1111/j.1467-8640.2012.00466.x
[17]	SAHIN O, AKAY B. Comparisons of metaheuristic algorithms and fitness functions on software test data generation[J]. Applied Soft Computing, 2016, 49: 1202-1214. doi: 10.1016/j.asoc.2016.09.045
[18]	TIAN T, GONG D W. Test data generation for path coverage of message-passing parallel programs based on coevolutionary genetic algorithms[J]. Automated Software Engineering, 2016, 23(3): 469-500. doi: 10.1007/s10515-014-0173-z
[19]	彭紫微. 面向多种体系结构的BFS算法研究[D]. 长沙: 国防科技大学, 2018.

Cited By

Cited by

Periodical cited type(3)

1.	付鸿博，李杰，杨永超. 石榴CCD基因家族的鉴定与分析. 分子植物育种. 2025(08): 2511-2518 .
2.	杜艳霞，王艺光，肖政，董彬，方遒，钟诗蔚，杨丽媛，赵宏波. 桂花OfNCED3调控转基因烟草叶片类胡萝卜素和叶绿素的合成. 园艺学报. 2023(06): 1284-1294 .
3.	蔡肖，王海涛，李兴河，甄军波，刘琳琳，刘迪，迟吉娜，张建宏. 亚洲棉NCED3基因克隆及其抗旱功能分析. 核农学报. 2022(09): 1713-1722 .

Other cited types(5)

Get Citation

PDF

XML

Article views (839) PDF downloads (734) Cited by(8)

Turn off MathJax

Article Contents

Abstract

References

Study on the whole area coverage of agricultural robot in complex environment based on ant colony-BFS algorithm

Abstract

References

Cited by

Periodical cited type(3)

Other cited types(5)

Catalog

Export File

Citation

Format

Content