Traversal path planning of agricultural robot based on memory simulated annealing and A* algorithm
-
摘要:目的
解决农业机器人大田作业时遍历路径规划的问题。
方法提出一种记忆模拟退火与A*算法相结合的遍历算法。首先通过记忆模拟退火算法搜索出任务最优目标点行走顺序，然后使用A*算法进行跨区域衔接路径规划。
结果仿真试验结果表明，该算法规划的遍历路径曼哈顿距离比传统模拟退火算法减少了9.4%，遍历路径覆盖率能达到100%，重复率控制为4.2%。
结论记忆模拟退火通过为传统模拟退火算法增加记忆器，增强了跳出局部最优陷阱的能力，提高了算法所得解的质量。该研究结果可为农业机器人遍历路径规划提供理论基础。
Abstract:ObjectiveTo solve the problem of traversal path planning of agricultural robot in field operation.
MethodA memory simulated annealing algorithm combined with A* algorithm was proposed. Firstly, the optimal walking sequence of target points in task was found by memory simulated annealing algorithm, and then A* algorithm was used for crossing regional linking of path planning.
ResultThe simulation experiments showed that the Manhattan distance of traversal path planned by this algorithm was reduced by 9.4% compared with the traditional simulated annealing algorithm, the coverage of traversal path could reach 100%, and the repetition rate could be controlled at 4.2%.
ConclusionMemory simulated annealing algorithm enhances the ability to jump out of the local optimal trap, and improves the quality of the solution obtained by adding memory device to the traditional simulated annealing algorithm. The research results can provide a theoretical basis for the path planning of agricultural robot.
-
香蕉枯萎病是由尖镰孢古巴专化型Fusarium oxysporum f. sp. cubense引起的香蕉毁灭性病害[1]，在亚洲、非洲和澳洲等香蕉产区均有分布，给全球的香蕉产业造成严重的经济损失。据报道，香蕉枯萎病菌有4个生理小种，不同的生理小种侵染的香蕉品种及所造成的病害程度不同，分布区域也不同[2]。我国目前存在的1号和4号生理小种危害性最大。1号生理小种最易侵染大蜜啥(Gros Michel)、Apple和Silk等香蕉品系，而4号生理小种毁灭性最大，能侵染大蜜啥、矮香蕉和Cavendish等香蕉品系[3]。2号和3号生理小种在我国尚未发现，2号生理小种在中美洲侵染三倍体杂种煮食蕉和某些Jamaica四倍体等，3号生理小种被报道只危害芭蕉科的野生羯尾蕉Heliconia spp.[4]。
目前对香蕉枯萎病菌4个生理小种分子鉴定的报道较少。应用核糖体DNA(Ribosomal DNA, rDNA)ITS序列的保守性鉴定菌种是植物病原菌分子鉴定中较常用的方法[5-8]。基于DNA限制性片段长度多态性(Restriction fragment length polymorphism，RFLP)的遗传标记技术目前已成为对生物物种及种以下单元分类的常用方法[5, 9-12]。
本研究利用真菌通用引物ITS4/ITS5对香蕉枯萎病菌不同生理小种的ITS序列进行扩增，并进行RFLP分析，旨在寻找香蕉枯萎病菌不同生理小种ITS序列的差异，阐明该方法是否可用于区分香蕉枯萎病菌的不同生理小种。
1. 材料与方法
1.1 材料
1号生理小种WG02菌株、2号生理小种WG03菌株、3号生理小种WG04菌株、4号生理小种WG05菌株由澳大利亚Bentley博士惠赠。4号生理小种Z13和Z16菌株，1号生理小种Z14和Z15菌株，由华南农业大学植物病理系研究室姜子德教授提供。
限制性内切酶Alu Ⅰ、Hpa Ⅱ和Taq Ⅰ购于宝生物工程(大连)有限公司。
1.2 方法
1.2.1 真菌总DNA的提取及ITS序列的扩增
提取以上4个生理小种8个菌株的基因组DNA，具体方法参照OMEGA公司的真菌DNA提取试剂盒说明书。以香蕉枯萎病菌4个生理小种8个菌株的基因组DNA为模板，采用ITS4(5′-TCCTCCGCTTATTGATATGC-3′)和ITS5(5′-GGAAGTAAAAGTCGTAACAAGG-3′)引物PCR，扩增体系如下：10×缓冲液2.5 μL，2.5 mmol·L-1 dNTP 2 μL，5 μmol·L-1引物各1 μL，5 U·μL -1Taq酶0.2 μL，模板DNA约30 ng，ddH2O 17.5 μL。PCR扩增程序为: 95 ℃预变性3 min，94 ℃变性45 s，56 ℃复性45 s，72 ℃延伸1.5 min，30个循环；72 ℃延伸10 min。反应结束后取5 μL PCR产物电泳。将阳性PCR产物纯化、连接和克隆，挑选出阳性转化子，送北京奥科基因公司测序，每个菌株重复测序3次。PCR产物的测序结果用DNAMAN软件和BLAST进行序列比对和同源性分析。
1.2.2 ITS-RFLP分析
将15 μL ITS-PCR产物，0.5 μL内切酶(5 U)，2 μL酶切缓冲液和2.5 μL ddH2O依次加入0.2 mL PCR管内，短暂离心混匀后，放入所需温度的水浴锅中反应4 h，其中Alu Ⅰ、Hpa Ⅱ限制性内切酶反应温度为37 ℃，Taq Ⅰ限制性内切酶反应温度为65 ℃，酶切产物通过电泳检测。
2. 结果与分析
2.1 不同生理小种ITS-PCR扩增
利用ITS4/ITS5和优化的扩增条件，对香蕉枯萎病菌4个生理小种共8个菌株的rDNA-ITS区进行了扩增。PCR扩增结果表明，8个菌株扩增出的特异性条带大小一致，位于500~700 bp，经测序确定其大小为568 bp(图 1)。
![图 1 香蕉枯萎病菌4个生理小种的ITS-PCR扩增产物]()
图 1 香蕉枯萎病菌4个生理小种的ITS-PCR扩增产物M:DL2000 DNA Marker；1:WG02；2:WG03；3:WG04；4:WG05；5:Z13；6:Z14；7:Z15;8:Z16；9:ddH2O。Figure 1. ITS-PCR products of four physiological races of Fusarium oxysporum f. sp. cubense2.2 不同生理小种ITS的序列分析
对4个生理小种8个菌株的ITS区段进行克隆并测序，结果均得到568 bp的片段。用DNAMAN对8个菌株的ITS全长序列进行比对，结果(图 2)发现，8个菌株只在第344、390和409个碱基处存在差异：在344 bp处，除3号生理小种(WG04) 的碱基为C外，其他的均为T；在390 bp处，除4号生理小种(Z13、Z16) 的碱基为C外，其余的均为T；在409 bp处，1号和2号生理小种的为T，3号和4号生理小种的为C。用DNAMAN对4个生理小种8个菌株进行序列比对，相似性高达99.85%。国内、外的1号生理小种ITS序列基本相同；除WG05外，国内、外的4号生理小种的ITS序列基本相同。WG02和WG03 ITS序列完全相同。与GenBank中的已知序列进行相似性比对，发现其与GenBank中的尖镰孢F. oxysporum的序列相似性高达100%，表明ITS序列可以作为鉴定尖镰孢F. oxysporum的依据。
![图 2 香蕉枯萎病菌4个生理小种的ITS序列比对]()
图 2 香蕉枯萎病菌4个生理小种的ITS序列比对WG02、WG03、WG04、WG05分别为国外的1~4号生理小种菌株；Z13和Z16为国内的4号生理小种菌株；Z14和Z15为国内的1号生理小种菌株。Figure 2. ITS sequences alignment of four physiological races of Fusarium oxysporum f. sp. cubense2.3 不同生理小种ITS-RFLP分析
3种限制性内切酶(Alu Ⅰ、Hpa Ⅱ、Taq Ⅰ)对ITS扩增产物的酶切图谱见图 3。由图 3A可看出，Alu Ⅰ对供试的4个生理小种8个菌株均有2个共同的酶切位点，供试菌株只有1种酶切图谱，每个菌株的ITS片段被酶切为大约380、130和50 bp的3个片段，50 bp左右的片段很模糊甚至不容易观察到。由图 3B可看出，Hpa Ⅱ对供试菌株的酶切位点较少，且比较保守；4个生理小种8个菌株均有1个共同的酶切位点，每个菌株的ITS片段被酶切为大约430和130 bp的2个片段；供试菌株只有1种酶切图谱。由图 3C可以看出，Taq Ⅰ对供试的8个菌株的酶切位点较多，均有3个共同的酶切位点，每个菌株的ITS片段被酶切为大约240、140、90和60 bp的4个片段；供试菌株只有1种酶切图谱。
![图 3 香蕉枯萎病菌4个生理小种ITS-PCR产物的酶切图谱]()
图 3 香蕉枯萎病菌4个生理小种ITS-PCR产物的酶切图谱M:DL500 Marker; 1:WG02；2:WG03；3:WG04；4:WG05；5:Z13；6:Z14；7:Z15；8:Z16；9:ddH2O。Figure 3. Restriction patterns of ITS-PCR products of four physiological races of Fusarium oxysporum f. sp. cubense从上述ITS酶切图谱的分析中可知，3种内切酶对香蕉枯萎病菌4个生理小种8个菌株所产生的酶切带型一致，并不能将香蕉枯萎病菌的不同生理小种区分开来，表明该病菌的种内rDNA ITS区段比较保守，遗传多样性有限。
3. 讨论与结论
rDNA已被广泛应用于植物病原菌亲缘关系以及致病性相关的研究。ITS区段在核基因组中是高度保守的，可用与它们序列互补的通用引物对ITS区进行PCR扩增、序列对比[8, 13]以及RFLP分析[11, 14-15]。Mills等[16]用RFLP区分不同地理来源和不同果树寄主的胶孢炭疽病菌Colletotrichum gloeosporioides，但不能区分不同地理来源芒果上的胶孢炭疽病菌的菌株。张瑞萍等[17]通过rDNA-ITS序列分析法成功鉴定出大豆根腐病菌F. oxysporum的菌株。李志芳等[6]用ITS-RFLP快速鉴定了棉花上的6种主要病原真菌，其ITS-RFLP产物大小各异、具有多态性，参考标准电子图谱可准确鉴定其种类。ITS-RFLP技术在担子菌的鉴定方面也有很多成功的例子[18-20]，表明该技术适用性强。
本研究利用真菌通用引物ITS4/ITS5对香蕉枯萎病菌4个生理小种8个菌株的ITS进行了克隆和序列分析以及ITS-RFLP比较研究。结果表明，4个生理小种菌株的ITS序列只有3个碱基的差异，序列相似性高达99.85%，与GenBank中尖镰孢菊花专化型F. oxysporum f. sp. chrysanthemi(编号DQ452449.1)、尖镰孢黄瓜专化型F. oxysporum f. sp. cucumerinum(编号DQ452450.1) 和一品冠(仙客来)枯萎病菌F. oxysporum f. sp. cyclaminis strain ATCC 16061(编号DQ452451.1) 的序列相似性为99%以上，表明尖镰孢不同专化型在rDNA-ITS序列上差异性较小，因而rDNA-ITS区段序列在一定程度上不适合于种内专化型及生理小种的鉴定。
通过序列比对，发现香蕉枯萎病菌1号生理小种的3个菌株(WG02，Z14和Z15) 的rDNA-ITS区段序列完全一致，而4号生理小种的3个菌株(WG05，Z13和Z16) 的rDNA-ITS区段序列存在着一定程度的差异，可以推断现阶段香蕉枯萎病菌4号生理小种的变异频率比1号生理小种快，这与王文华[7]的研究结果一致，其原因可能是地域差异导致的生理分化。
通过比对香蕉枯萎病菌4个生理小种8个供试菌株的序列，还发现4号生理小种(Z13、Z16) 在390 bp与409 bp位点的碱基为C，而1号生理小种在此位点的碱基为T。笔者推测，4号生理小种在rDNA-ITS区段序列这2个位点上存在着专一性，为通过rDNA-ITS序列比对鉴定4号和1号生理小种提供了一定的理论依据。
本研究采用3种不同的限制性内切酶进行了ITS-RFLP分析，均未能将4个生理小种的8个菌株区分开，再次证实了其ITS序列的保守性。曾莉莎等[21]通过ITS遗传进化树将18个香蕉枯萎病菌分为4个分支，其中1号生理小种、2号生理小种及非致病性香蕉枯萎病菌共享1个分支，3号生理小种和4号生理小种也共享1个分支，提出了ITS不能代表香蕉枯萎病菌的种间亲缘关系，不适合做系统发育分析。本研究对ITS片段进行RFLP分析，结果获得的酶切谱带很单一，在一定程度上可能是因为内切酶种类太少，或者是因为单酶切的局限性等。尽管单个内切酶在一定程度上可以区分一些种和小种，如Alu Ⅰ能够将大豆灰斑病菌Cercospora sojina Hara[22]与其他种分开，但是仅有的单个酶对菌株进行鉴定是不可靠的，因为种内该位点可能存在多态性，酶切位点的突变也可能带来错误的结果。因此，为了更好地鉴定和监测香蕉枯萎病菌的生理小种，应结合4个生理小种的致病性试验[7]，同时选择TEF-1α、IGS、histone H3等基因[21]以及复合限制性内切酶进行RFLP分析，以获得更为有力的证据和更为准确的鉴定结果。
-
![]()
图 3 矩形子区域划分结果
图中数字为标号
Figure 3. Result of rectangular sub-region division
The figures in the diagram are labels
![]()
图 4 农业机器人A*算法路径搜索
红色圆点即从起点A到目标点B的最短路径；方格中左上角数字为 f 值，代表由起点A到目标点B的代价值；右下角数字为 h 值，代表从指定节点到终点B的估算成本；左下角数字为 g 值，代表农业机器人从起点A移动到指定节点的移动代价
Figure 4. Path search of agricultural robot by A* algorithm
The red dots are the shortest path from starting point A to target point B; The upper left number is f value, representing the cost value for moving from starting point A to target point B; The bottom right number is h value, representing the estimated cost for moving from an assigned node to target point B; The bottom left number is g value, representing the movement cost for moving from starting point A to an assigned node
![]()
图 7 遍历路径规划图
绿色圆点和红色五角星分别为整个遍历路径规划的起点和终点，蓝色线条为遍历规划路线
Figure 7. Traversal path planning
The green dot is the starting point and the red pentagram is the ending point of the whole planned traversal path, the blue line is the planned traversal path
表 1 算法遍历顺序规划对比
Table 1 Comparison of traversal sequence planning in different algorithm
算法名称 Algorithm name 遍历顺序1) Traversal order 曼哈顿距离/m Manhattan distance 传统模拟退火算法
Traditional simulated annealing algorithm1-4-3-7-9-10-11-6-2-5-8 29.6 记忆模拟退火算法
Memory simulated annealing algorithm1-3-4-7-9-10-11-6-2-5-8 26.8 1) 数字表示矩形子区域中心基点
1)The figures are center points of rectangular sub-region
下载: 导出CSV
-
[1] 朱铁欣, 董桂菊, 颜丙学, 等. 基于改进蚁群算法的农业机器人路径规划研究[J]. 农机化研究, 2016, 38(9): 48-52. doi: 10.3969/j.issn.1003-188X.2016.09.009 [2] 邱雪娜, 刘士荣, 宋加涛, 等. 不确定动态环境下移动机器人的完全遍历路径规划[J]. 机器人, 2006(6): 586-592. doi: 10.3321/j.issn:1002-0446.2006.06.007 [3] 邱雪娜, 刘士荣, 俞金寿, 等. 移动机器人的完全遍历路径规划: 生物激励与启发式模板方法[J]. 模式识别与人工智能, 2006, 19(1): 122-128. doi: 10.3969/j.issn.1003-6059.2006.01.022 [4] 谢斌, 刘士荣, 俞金寿. 基于在线图搜索的移动机器人遍历运动规划[J]. 华东理工大学学报(自然科学版), 2007(4): 551-557. doi: 10.3969/j.issn.1006-3080.2007.04.021 [5] ZOU D X, WANG G G, PAN G, et al. A modified simulated annealing algorithm and an excessive area model for floorplanning using fixed-outline constraints[J]. Front Inform Tech El, 2016, 17(11): 1228-1244. doi: 10.1631/FITEE.1500386
[6] 路鹏, 周东岱, 钟绍春, 等. 基于模拟退火算法的计算机自适应测试项目选择方法研究[J]. 计算机应用与软件, 2012, 29(10): 175-179. [7] 杜利超, 钱桦, 肖爱平. 路径规划技术及其在大棚作业机器人中的应用[J]. 湖北农业科学, 2010, 49(5): 1205-1208. doi: 10.3969/j.issn.0439-8114.2010.05.058 [8] 史兵, 段锁林, 李菊, 等. 温室移动机器人复合栅格地图构建方法研究[J]. 计算机应用研究, 2019, 36(3): 824-828. [9] 张堂凯. 己知环境下智能清洁机器人路径规划研究[D]. 南京: 南京邮电大学, 2017. [10] QIAN J Y, ZHOU Z D, ZHAO L Z, et al. Accelerating reconfiguration for VLSI arrays with A‐star algorithm[J]. IEEJ T Electr Electr , 2018, 13(10): 1511-1519. doi: 10.1002/tee.22716
[11] 王维, 裴东, 冯璋. 改进A*算法的移动机器人最短路径规划[J]. 计算机应用, 2018, 38(5): 1523-1526. [12] 张欣欣, 薛金林. 基于云模型的农业移动机器人人机合作路径规划[J]. 华南农业大学学报, 2017, 38(6): 105-111. doi: 10.7671/j.issn.1001-411X.2017.06.016 [13] 张文, 刘勇, 张超凡, 等. 基于方向A*算法的温室机器人实时路径规划[J]. 农业机械学报, 2017, 48(7): 22-28. doi: 10.6041/j.issn.1000-1298.2017.07.003 [14] 孙秀巧, 王健, 巫威眺. 基于改进遗传退火算法的高速公路巡逻车路径优化调度[J]. 科学技术与工程, 2019, 19(21): 296-302. doi: 10.3969/j.issn.1671-1815.2019.21.045 [15] MIAO Z W, YANG F, FU K, et al. Transshipment service through crossdocks with both soft and hard time windows[J]. Ann Oper Res, 2012, 192(1): 21-47. doi: 10.1007/s10479-010-0780-4
