基于改进A*算法和DFS算法的割草机器人遍历路径规划

doi:10.13733/j.jcam.issn.2095-5553.2023.02.020

摘要/Abstract

摘要： 针对割草机器人大面积作业时遍历路径规划覆盖率低、重复率高、普适性弱的问题，提出一种改进A*算法与DFS算法相结合的遍历路径规划算法。首先，根据已知环境全局信息，通过牛耕式分解法将目标区域划分成多个不含障碍物的子区域；然后，根据子区域的邻接关系构建无向图，使用DFS算法规划子区域的遍历顺序；最后，采用改进A*算法进行跨区域路径转移并且往复式遍历各子区域的内部。仿真试验结果表明：该遍历算法的覆盖率达到100%，遍历重复率为0，改进A*算法所规划的跨区域转移路径长度和转向次数比A*算法分别减少3.26%和62.5%。所提出的遍历算法具有覆盖率高、重复率低、普适性强的特点，改进A*算法通过路径平滑性优化和添加防碰撞安全间距对A*算法进行改进，使之规划的路径更平滑、更安全，路径长度更短。该研究结果旨在为割草机器人遍历路径规划提供理论参考。

关键词: 割草机器人, 遍历路径规划, 路径转移, 改进A*算法, DFS算法

Abstract: Aiming at the problems of low coverage rate, high repetition rate and weak universality of traversal path planning when lawn mower robots operate in large areas, an improved traversal path planning algorithm combining A* algorithm and DFS algorithm is proposed. First, according to the known global information of the environment, the target area is divided into multiple subareas without obstacles by the cattle farming decomposition method. Then, an undirected graph is constructed according to the adjacency relationship of the subregions, and the traversal order of the subregions is planned using the DFS algorithm. Finally, the improved A* algorithm is used to transfer the path across regions and traverse the interior of each subregion in a reciprocating manner. The simulation experiment results show that the coverage rate of the traversal algorithm reaches 100%, and the traversal repetition rate is 0. The length of the crossregional transfer path and the number of turns planned by the improved A* algorithm are reduced by 3.26% and 62.5% respectively compared with the A* algorithm. The traversal algorithm proposed in this paper has the characteristics of high coverage, low repetition rate, and strong universality. Improved A* algorithm improves the A* algorithm by optimizing path smoothness and increasing the anticollision safety distance to make the planned path smoother, safer and shorter path length. The research results are designed to provide theoretical reference for ergodic path planning of lawn mower robot.

Key words: lawn mower robot, traverse path planning, path transfer, improved A* algorithm, DFS algorithm

中图分类号:

TP391.4

王新彦, 盛冠杰, 张凯, 易政洋. 基于改进A*算法和DFS算法的割草机器人遍历路径规划[J]. 中国农机化学报, 2023, 44(2): 142-147.

Wang Xinyan, Sheng Guanjie, Zhang Kai, Yi Zhengyang.. Traversal path planning of lawn mower robot based on improved A* algorithm and DFS algorithm[J]. Journal of Chinese Agricultural Mechanization, 2023, 44(2): 142-147.

参考文献

［1］　

王飞涛, 樊春春, 李兆东, 等. 机器人在设施农业领域应用现状及发展趋势分析［J］. 中国农机化学报, 2020, 41(3): 93-98, 120.

Wang Feitao, Fan Chunchun, Li Zhaodong, et al. Application status and development trend of robots in the field of facility agriculture ［J］. Journal of Chinese Agricultural Mechanization, 2020, 41(3): 93-98, 120.

［2］　
Hirel J, Gaussier P, Quoy M. Biologically inspired neural networks for spatiotemporal planning in robotic navigation tasks ［C］. 2011 IEEE International Conference on Robotics and Biomimetics. IEEE, 2011: 1627-1632.

［3］　
Nilsson R S, Zhou K. Method and benchmarking framework for coverage path planning in arable farming ［J］. Biosystems Engineering, 2020, 198: 248-265.

［4］　
刘成良, 林洪振, 李彦明, 等. 农业装备智能控制技术研究现状与发展趋势分析［J］. 农业机械学报, 2020, 51(1): 1-18.

Liu Chengliang, Lin Hongzhen, Li Yanming, et al. Analysis on status and development trend of intelligent control technology for agricultural equipment ［J］. Transactions of the Chinese Society for Agricultural Machinery, 2020, 51(1): 1-18.

［5］　
Choset H. Coverage for robotics—a survey of recent results ［J］. Annals of Mathematics and Artificial Intelligence, 2001, 31(1): 113-126.

［6］　
Sandamurthy K, Ramanujam K. A hybrid weed optimized coverage path planning technique for autonomous harvesting in cashew orchards ［J］. Information Processing in Agriculture, 2020, 7(1): 152-164.

［7］　
杨俊成, 李淑霞, 蔡增玉. 路径规划算法的研究与发展［J］. 控制工程, 2017, 24(7): 1473-1480.

Yang Juncheng, Li Shuxia, Cai Zengyu. Research and development of path planning algorithm ［J］. Control Engineering of China, 2017, 24(7): 1473-1480.

［8］　
Yakoubi M A, Laskri M T. The path planning of cleaner robot for coverage region using genetic algorithms ［J］. Journal of Innovation in Digital Ecosystems, 2016, 3(1): 37-43.

［9］　
任云天. 扫地机器人避障全覆盖路径规划算法的研究与设计［D］. 武汉: 华中科技大学, 2019.

Ren Yuntian. The research and design of obstacle avoidance complete coverage path planning algorithm for robot vacuums ［D］. Wuhan: Huazhong University of Science and Technology, 2019.

［10］　
张赤斌, 王兴松. 基于蚁群算法的完全遍历路径规划研究［J］. 中国机械工程, 2008, 19(16): 1945-1949.

Zhang Chibin, Wang Xingsong. Complete coverage path planning based on ant colony algorithm ［J］. China Mechanical Engineering, 2008, 19(16): 1945-1949.

［11］　
李楷, 陈永府, 金志勇, 等. 基于回溯法的全覆盖路径规划算法［J］. 计算机工程与科学, 2019, 41(7): 1227-1235.

Li Kai, Chen Yongfu, Jin Zhiyong, et al. A full coverage path planning algorithm based on backtracking method ［J］. Computer Engineering and Science, 2019, 41(7): 1227-1235.

［12］　
Le A V, Nhan N H K, Mohan R E. Evolutionary algorithmbased complete coverage path planning for tetriamond tiling robots ［J］. Sensors, 2020, 20(2): 445.

［13］　
马全坤, 张彦斐, 宫金良. 基于记忆模拟退火和A*算法的农业机器人遍历路径规划［J］. 华南农业大学学报, 2020, 41(4): 127-132.

Ma Quankun, Zhang Yanfei, Gong Jinliang. Traversal path planning of agricultural robot based on memory simulated annealing and A* algorithm ［J］. Journal of South China Agricultural University, 2020, 41(4): 127-132.

［14］　
余翀, 邱其文. 基于栅格地图的分层式机器人路径规划算法［J］. 中国科学院大学学报, 2013, 30(4): 528-538.

Yu Chong, Qiu Qiwen. Hierarchical robot path planning algorithm based on grid map ［J］. Journal of University of Chinese Academy of Sciences, 2013, 30(4): 528-538.

［15］　
张堂凯. 已知环境下智能清洁机器人路径规划研究［D］. 南京: 南京邮电大学, 2017.

Zhang Tangkai. Research on path planning of intelligent cleaning robot in known environment ［D］. Nanjing: Nanjing University of Posts and Telecommunications, 2017.

［16］　
Coombes M, Chen W H, Liu C. Boustrophedon coverage path planning for UAV aerial surveys in wind ［C］. 2017 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 2017: 1563-1571.

［17］　
Sucan I A, Moll M, Kavraki L E. The open motion planning library ［J］. IEEE Robotics & Automation Magazine, 2012, 19(4): 72-82.

［18］　
Li C, Ueno M. A depthfirst search algorithm for optimal triangulation of Bayesian network ［J］. International Journal of Approximate Reasoning, 2017, 80: 294-312.

［19］　
Qian J, Zhou Z, Zhao L, et al. Accelerating reconfiguration for VLSI arrays with AStar algorithm ［J］. IEEJ Transactions on Electrical and Electronic Engineering, 2018, 13(10): 1511-1519.

[1]	王新彦, 易政洋. 基于改进YOLOv5的割草机器人工作环境障碍物检测方法研究[J]. 中国农机化学报, 2023, 44(3): 171-176.
[2]	代玉梅, 张瑞玲, 马黎. 改进A*算法的采摘机器人路径规划与跟踪控制[J]. 中国农机化学报, 2022, 43(3): 138-145.
[3]	王新彦, 张凯, 盛冠杰, 易政洋. 基于单线激光雷达的割草机器人建图方法研究[J]. 中国农机化学报, 2022, 43(10): 51-56.
[4]	王新彦;吕峰;易政洋;. 基于深度学习的草坪树木检测方法研究[J]. 中国农机化学报, 2021, 42(7): 136-141.