基于改进单元分解法的全覆盖路径规划.pdf

第45卷第12 期2023年12 月文章编号：10 0 1-50 6 X(2023)12-3949-09基于改进单元分解法的全覆盖路径规划吴靖宇1.2，朱世强2.3，宋伟2.3.*，施浩磊4，吴泽南4（1.浙江大学海洋学院，浙江舟山316 0 2 1；2.浙江大学机器人研究院，浙江宁波31540 0；3.之江实验室，浙江杭州31112 1；4.舟山市质量技术监督检测研究院，浙江舟山316 0 13摘要：传统的单元分解法在静态已知环境中进行全覆盖路径规划时，若障碍物分布不规则或具有较多的凹形障碍物，则所得的单元数量较多，这导致最终路径易出现较多的余和不必要的转向。首先，将栅格地图分解为若千个路径片段，每个路径片段由位于同一行且左右相邻的栅格组成；然后，合并这些路径片段以生成单元；再基于贪心算法和拓扑地图三次求解单元间的遍历顺序，合并减少了单元数量，并对局部路径进行了优化，最终完成遍历路径的规划。仿真结果验证了所提算法的有效性，且规划的路径具有更少的余和转向次数。关键词：全覆盖路径规划；单元分解法；单元合并；贪心算法中图分类号：TP242Coverage path planning based on improved cellular decompositionWU Jingyul-2,ZHU Shiqiang3,SONG Wei?3.*,SHI Haolei,WU Zenan(1.Ocean College,Zhejiang University,Zhoushan 316021,China;2.Robotics Institute,Zhejiang University,Ningbo 315400,China;3.Zhijiang Lab,Hangzhou 311121,China;4.Zhoushan Institute ofCalibration and Testing for Qualitative and Technical Supervision,Zhoushan 316013,China)Abstract:When the traditional cellular decomposition method is used for complete coverage path planningin a static known environment,if the obstacles are irregularly distributed or many concave obstacles exist in theenvironment,the number of cells obtained is large.This finally leads to much redundancy and unnecessarysteering in the final path.Firstly,the grid map is decomposed into several path segments,each of the pathsegment is composed of grids located in the same row and adjacent to the left and right.Secondly,these pathfragment are merged for generating cells.Thirdly,based on greedy algorithm and topological map,the traversalorder between cells is solved three times to merge and to reduce the number of cells,and the local path isoptimized.Finally,the planning of traversal path is completed.Simulation results show that the algorithm iseffective and the planned path has less redundancy and steering times.Keywords:complete coverage path planning;cellular decomposition;cellular mergence;greedy algorithm0 引 言路径规划是影响移动机器人作业效率的重要环节。按照所得路径的特点，路径规划可分为“点到点”和“全覆盖”两类。其中，前者可应用于山地救援、自动驾驶2 、物流运输9等两点之间无碰撞的移动场景,现有方法包括A-5法、人工势场法6、快速扩展随机树7 等；后者则应用于地收稿日期：2 0 2 2-11-2 2；修回日期：2 0 2 3-0 4-0 6；网络优先出版日期：2 0 2 3-0 8-14。网络优先出版地址：https：/k n s.c n k i,n e t/k c m s/d e t a il/11.2 42 2.T N.2 0 2 30 8 14.10 51.0 0 2.h t m l基金项目：浙江省市场监督管理局维鹰计划培育项目（CY2022231)资助课题*通讯作者。引用格式：吴靖宇，朱世强，宋伟，等基于改进单元分解法的全覆盖路径规划。系统工程与电子技术，2 0 2 3，45（12）：3949-3957.Reference format:WU J Y,ZHU S Q,SONG W,et al.Coverage path planning based on improved cellular decompositionJJ.SystemsEngineering and Electronics,2023,45(12):3949-3957.系统工程与电子技术Systems Engineering and Electronics文献标志码：AVol.45No.12December 2023网址：www.sys-D0I:10.12305/j.issn.1001-506X.2023.12.25面清扫8、农业植保9、油罐底面清洗10 等需要遍历某一区域的场景，现有方法包括生物激励神经网络算法1-12、生成树覆盖算法13-14、单元分解法15等。当在静态已知环境中进行全覆盖路径的离线规划时，单元分解法是一种常用的方法16-17。该方法的实现过程主要分为两个步骤，分别为划分单元和求解单元间遍历顺序。其中划分单元是指将待遍历的区域划分为若干个互不重3950:叠的子区域。传统的单元分解法在此步骤采用的是根据障碍物的形状和位置划分单元的方式，包括：Trapezoidal分解18 、Boustrophedon分解19-2 1和Morse分解2-2 3。而求解单元间遍历顺序则是一个旅行商问题，常用的方法包括深度优先搜索2 4、模拟退火法2 5、蚁群算法2 6、粒子群优化算法2 7、遗传算法2 8-2 9、强化学习30 1和深度强化学习31等。但传统的单元分解法在障碍物分布不规则和凹形障碍物较多的场景下却易出现较多的?余路径和转向次数。其中分布不规则是指在栅格地图上，各个障碍物的几何中心一般位于不同的行和列。日常生活中椅子、凳子等物件即会因人们的使用而成为分布不规则的障碍物。凹形障碍物则可见于办公区域等场景，例如只有一扇门进出的房间，其四周墙壁即可视为凹形障碍物。在这两种场景中，待遍历区域的形状变得不规则，使得传统的单元分解法所得单元的数量较多。而单元数量的增加会使得每个单元的平均面积减少，造成传统的单元分解法难以在更大的范围内应用并优化局部路径，故易产生较多的穴余路径和转向次数。对此，本文提出一种改进的规划算法，目的是减少最终路径的穴余和转向次数。改进后的单元划分通过在栅格地图上合并路径片段来实现（路径片段由位于同一行且左右相邻的栅格组成）。这样，单元的划分不再完全依赖于障碍物的形状和位置，而是兼顾了单元内的路径规划。同时，为了减少单元的数量，在求解单元间遍历顺序时，结合贪心算法和拓扑地图进行三次求解，不断合并单元，并对局部路径进行了优化。本文的结构安排如下：引言部分介绍了路径规划的研究现状和传统单元分解法存在的一些不足；第1节阐述了路径片段初步合并生成单元的过程；第2 节阐述了基于贪心算法和拓扑地图的单元间遍历顺序的求解过程；第3节进行了仿真实验，其结果验证了本文算法的有效性；第4节对全文进行了总结，指出当前本文算法存在的不足。本文的主要创新点在于：改进了传统单元分解法划分单元的方式，并通过对单元的合并，降低了在障碍物分布不规则和凹形障碍物较多的场景下单元划分的数量，减少了穴余路径和转向次数。1单元初步合并生成本节通过合并路径片段初步生成单元，以实现对待遍历区域的单元划分。相关步骤包括：栅格地图初始化、生成路径片段、确定遍历起始单元和合并路径片段。1.1栅格地图初始化首先，建立平面直角坐标系，其原点O位于地图左上角,向下为X轴，向右为Y轴,则第行、第6 列栅格可以用坐标(a，b)表示。然后，建立与栅格地图对应的同维度矩阵，并将待遍历栅格以数字0 表示，将障碍物以数字1表示。为获取该矩系统工程与电子技术阵对应位置的数值,定义函数 F(a,b)如下：F(a,b)=1，障碍物栅格或边界之外设地图上所有的栅格组成集合Cll，则其中待遍历栅格可以表示为Cov=(xi,y,)ECll/F(a,y,)=0)1.2生成路径片段定义路径片段如下：地图上位于同一行且未被障碍物阻隔的全部连通栅格的有序排列集合，则第R行的某一路径片段Cr=(aRy),(aRy2),.,(CR,y,)满足:F(R,yi-1)=1F(aR,y,+1)=1F(R,y)=o,1erJ/-yf-1=1,2fr设某一地图的待遍历区域通过划分共生成了n个路径片段，则它们组成的集合Cpath=（Ci，C2，,C.）满足：CiUC,U.UC,=CovCnCh=,1gn;lhn;gh图1所示为一个生成路径片段的示例（图中黑色栅格为障碍物，白色栅格为待遍历区域，下同）其中属于同一路径片段的栅格以线段依次相连。显然，每条线段均可作为机器人的潜在移动路径，而单元则可通过合并这些路径片段来生成。图1生成路径片段Fig.1 Path fragments generation1.3确定遍历起始单元假定机器人的直线运动平行于坐标轴，且平均速度为u；机器人每转过9 0 视为一次转向，且所需时间为t。机器人在从坐标为(a,b)的栅格移动到坐标为（c,d)的过程中共转向M次，直线运动的总路程长度为L，则该次移动所需的总时间为T(a,b),(c,d)=+tM若在该时间内机器人始终以平均速度做直线运动，则可移动距离为L=.T(a,b),(c,d)J=L+tM记P=ut,则机器人从栅格（a,b)移动到（c,d)的等效路径长度为第45卷0，待遍历栅格(1)(2)(3)(4)(5)(6)第12 期由于和t的值仅与机器人的自身性能有关,数值可由实验测出。当机器人的型号确定后，参数P即为一个常量。因此，由式（7)计算所得的等效路径长度L可作为评价路径优劣的评价指标。以式（7)计算机器人的初始位置所在栅格到每个路径片段首尾两个端点栅格的等效路径长度，根据最小值确定起始路径片段和起始栅格。若起始栅格位于起始路径片段的末端，则对起始路径片段中的栅格进行倒序排列。后续由起始路径片段合并生成的单元即是遍历起始单元，记为Cs。1.4合并路径片段路径片段的合并流程如图2 所示。开始初始化集合CMe否存在集合C满足合并要求？是将Ca合并至Cm并调整C.内部排列集合C是否满足合并要求？将C.添加至CMer，并从Cpa中移除Cm剩余集合记为CMo2结束图2 路径片段合并流程图Fig.2Flowchart of path fragment mergency具体步骤如下：步骤1生生成空集合CMer，对合并完成的单元进行存储。步骤2 判断Cpath中是否存在某一路径片段C（1mn)且满足以下两个要求：（1）Cm在地图上的相邻路径片段Cacj属于Cpath;（2）C a 仅有一个端点栅格与Cm的某一端点栅格上下相邻。其中，两个路径片段相邻的定义为：存在两个上下相邻的栅格分别属于这两个路径片段,即日（a,b)ECm，日（c,d)ECad，满足：(8)b=d此外，为避免起始栅格之前出现路径，将起始栅格视为与所有栅格均不相邻。若存在Cm满足要求,则将 Cai合并至Cm，并跳转至步骤3，否则跳转至步骤7。吴靖宇等：基于改进单元分解法的全覆盖路径规划L=L+PM(7)是a-cl=13951图3所示为本步骤中路径片段满足合并要求的两种情形。其中情形1表示两个路径片段除了一组端点栅格上下相邻，还存在其他栅格相邻；情形2 则与之相反。(a)情形1(b)情形2(a)Situation 1(b)Situation 2图3满足合并要求的两种情形Fig.3Two situations meeting the mergency requirements步骤3对合并后的 Cm，调整其栅格排列顺序，确保以该顺序生成的移动路径连贯，如图4所示。(a)情形1路径(a)Path of Situation 1图4调整集合内栅格排列顺序后所生成的路径Fig.4Path generated after adjusting grid arrangementorder in the column步骤4对调整后的集合Cm重复步骤2 和步骤3，直至Cm不满足步骤2 中的要求。步骤5将Cm从Cpath中移除，并添加至CMer，以防止出现重复规划。步骤6 重复步骤2 步骤5，直至Cpath中不存在集合满足步骤2 中的要求。步骤7 将Cpath中剩余的集合记为CMer2则CMer和CMer2中的每个元素即为初次合并后的单元。这些单元具有以下两个特点：（1）以栅格排列顺序所生成的路径可无重复地遍历该单元；（2）该路径的起点为排列在首末位置的两个栅格之一。这样，单元的生成除了考虑障碍物的形状和位置，也兼顾了单元内的路径规划。图5(a)所示为路径片段初步合并后的结果，图5（b)为合并形成的单元，共有13个（图中黑色圆点代表路径起点，下同）。后续单元的合并以及局部路径的优化需参照单元间的遍历顺序进行。(a)路径片段的合并结果(a)Mergency result of path fragments(b)情形2 路径(b)Path of Situation 23952：系统工程与电子技术2第45卷开始?8(b)由路径片段所生成的单元(b)Cellular generated by path fragments图5单元初步合并生成的结果Fig.5Result of preliminary cellular mergence2基于贪心算法和拓扑地图的单元间遍历顺序求解本节求解单元间的遍历顺序，以生成最终路径。相关步骤包括：生成拓扑地图和执行3次基于贪心算法的求解。其中，拓扑地图根据单元间的相邻情况生成，用于求解过程中单元的再次合并。而在3次求解中，后一次求解均基于前一次求解的结果，以使得局部路径不断得到优化，从而减少最终总体路径的穴余和转向次数。2.1生成拓扑地图依据各单元的相邻情况生成拓扑地图。图6 即是由图5所得的拓扑地图。1289：根节点；：通道节点；图6 生成拓扑地图Fig.6Generation of topology map其中，每个单元均可视为一个节点，而整个地图则可视为一个树形结构。为便于进一步合并单元，进行如下定义，从而将所有节点分为3类：（1）根节点：遍历起始单元Cs，以及相邻节点数之和大于2 的节点（一般为枢纽）。（2）通道节点：用于连接两个根节点的节点。（3）分枝节点：除以上节点的节点（一般为处于凹形区域的节点）。2.2第一次求解第一次求解的流程图如图7 所示。初始化集合Covi是判断是否已遍历所有单元？?否否判断上一个遍历单元及其相邻单元是否满足优先条件？是选择最近单元作为选择该相邻单元作为将该单元添加至下一个遍历单元下一个遍历单元判断下一个遍历单元存在已遍历的相邻单元？是计算该单元添加至CNav末端时的等效路径长度计算该单元添加至CNavi中间时的等效路径长度选择最优的添加方式以A*算法生成实际路径结束图7 第一次求解流程图Fig.7Flowchart of the first solution具体步骤如下：?步骤1生成集合CNavi=Cs，用于存储机器人先后经过的栅格，即导航点。其中，两个导航点之间的实际移动路13）径由A*算法获取。：分枝节点。步骤2 判断是否存在未遍历的单元，若不存在，则跳转至步骤11。步骤3判断上一个遍历的单元CLast和它的相邻单元CNear是否满足优先遍历的两个要求：(1）CLa s t 与CNear均为通道节点；（2）单元CNear未遍历。若是，则将CNear作为下一个待遍历的单元CNext；若否，则选择最近单元作为CNext（即贪心算法）。最近单元定义为：以式（7)计算当前排列在集合CNavl末端的栅格，其到某一单元的首端或末端栅格的等效路径长度即为所有未遍历单元中的最小值。执行此步骤的目的是，使得处于同一通道的单元优先集中完成遍历，否则遍历路径可能发生割裂，出现如图8(a)CNaM末端否第12 期所示的规划，导致不必要的转向；而图8（b)所示则采用了优先遍历的规划路径，其路径长度和转向次数得到了降低。吴靖宇等：基于改进单元分解法的全覆盖路径规划3953图10 为第一次求解结果（图中黑色三角形代表路径终点，下同）。该路径的长度为116 个栅格，转向次数为48。图10 第一次求解结果(a)未采用优先遍历(a)Without priority traversal图8 优先遍历效果示意Fig.8Schematic diagram of priority traversal effect步骤4判断CNex是否存在已遍历的相邻单元。若否，则跳转至步骤5；若是，则跳转至步骤6。步骤 5以式(7)分别计算 CNavi的当前末端栅格，及其到CNext的第一和最后一个栅格的等效路径长度，以此确定最佳的单元内遍历路径起点。调整CNext的栅格排序，将之添加至CNavl的末端，并将该单元标记为已遍历。之后返回步骤2。步骤6 与步骤5操作类似,以最优方式将 CNext中的栅格坐标添加至CNavI的末端，并以式（7）计算此时由CNavl生成的路径的等效路径长度。步骤7 获取与 CNext相邻的所有已遍历的栅格,并寻找这些栅格在CNavi中的排列序号，设最小序号为Nmin、最大序号为Nmax。步骤8 将CNext内所有栅格以正序插人CNnavi中的Nmin一1处（如图9所示，其中箭头方向代表栅格的遍历顺序），计算此时CNavi的等效路径长度。BCDN图9将CNext以正序插人CNavi中的Nmin一1处Fig.9 Inserting CNext into Nmin-1 of CNavi with positive order再将CNext内所有栅格以倒序插人至CNavi中的Nmin一1处，再次计算此时CNavi的等效路径长度。步骤9重复步骤8,但每次 CNext内所有栅格的插入位置在上次位置的基础上右移一位，直至Nmax十1处。步骤10 寻找步骤8 步骤9中获得的最短等效路径长度，将之与步骤6 所得的等效路径长度进行比较，选取最小值。将对应的添加方式作为CNext的最终添加结果，并标记相应的单元为已遍历，之后返回步骤2。步骤11根据最终所得导航点集合CNavl，以A*算法生成机器人的实际运动路径，若在生成时某导航点已在已生成的路径中，则跳过。(b)采用优先遍历(b)With priority traversal2kUNmxFig.1oResults of thefirst solution2.3第二次求解第一次求解时未合并分枝和通道节点，导致单元的数量较多。而未在初始时就合并的原因在于，该分枝或通道的遍历起点栅格还未确定。因此，第一次求解完成后，依托于第一次求解的结果，将连接两个根节点的位于同一通道中的通道节点进行合并。同时，对每个分枝，从位于其末端的分枝节点开始，对分枝内的每个节点进行判定：若某个分枝节点的父节点在第一次规划时先于该节点遍历，则将该节点合并至其父节点。合并单元时需调整单元内栅格的排列顺序，方法与第一次求解时的步骤7 步骤9 类似，此处不再赘述。然后，对完成合并的每个单元进行形状判定：若形状为矩形，且单元的首尾两个栅格位于同一列，则再次调整该单元内栅格的排序，以预留出撤离路径，如图11（b)所示。这样相对于图11(a)所示的调整前的规划路径，单元内的穴余路径实现了降低。CNextWCNar(a)调整前(a)Before adjustment(b)调整后(b)After adjustment图11栅格排列顺序调整比较Fig.ll Comparison of grid arrangement order adjustment重复以上操作，直至所有分枝节点和通道节点均得到判定与处理。这样合并后的总体规划路径更优。如图12(a)所示，合并单元前规划的路径出现了重复，而在图12（b)中，合并后再规划的路径则得到了改善。3954(a)Path planned before cells mergence系统工程与电子技术图15为单元再次合并后的结果。相较于图13，分枝节点11以及由节点3和节点4合并而成的节点均被合并，单元总数为6。图16 为第三次求解的结果，其路径长度为108个栅格，转向次数为46。相较于第二次求解，路径的长(a)合并单元前规划的路径度进一步减少。第45卷(b)合并单元后规划的路径(b)Path planned after cells mergence图12 合并单元前后的规划路径对比Fig.12 Comparison of paths planned before and after cells mergence图15第三次单元合并结果图13为第二次合并后的结果。相较于图5，通道节点5、6、7 和分枝节点3、4、9、10、12、13被合并了，单元总数为8。之后采用与第一次求解相同的方式获取第二次求解结果CNav2，此处不再赘述。图14所示为第二次求解结果，其路径长度为112 个栅格，转向次数为46。相较于第一次求解，路径的长度和转向次数获得了降低。Fig.15Result after the third cellular mergence图16 第三次求解结果Fig.16Result of the third solution3仿真实验与分析本节分“障碍物分布不规则”和“凹形障碍物较多”两种场景对本文算法进行了规划测试。其中，图17 和图18 所图13第二次单元合并后的结果Fig.13Result after the second cell mergence示地图的尺寸均为40 40。地图中的障碍物由计算机+人工随机生成，以验证本文算法在较复杂环境下的有效性。作为对比的单元分解法，在划分单元部分，选取了应用较多的Boustrophedon分解；在单元间遍历顺序的求解部分，则选取了贪心算法和遗传算法。同时，在单元分解法之外，选取了常见的生物激励神经网络算法作为对比。图14第二次求解结果Fig.14Result of the second solution2.4第三次求解在第二次求解时可能出现以下两种情形：同一分枝中某一子节点先于其父节点遍历，以及分枝中某一节点先于该分枝所在根节点遍历。为进一步减少单元的数量，将这些节点合并后再进行规划。节点的合并方式以及第三次求解获取CNav3的步骤与第二次类似，此处亦不再赘述。(a)本文算法规划的路径(a)Path planned by the algorithm in this paper第12 期吴靖宇等：基于改进单元分解法的全覆盖路径规划3955！门(a)本文算法规划的路径(a)Path planned by the algorithm inthis paper(b)Boustrophedon分解+贪心算法规划的路径(b)Path planned by Boustrophedon decomposition andgreedy algorithm一1.(b)Boustrophedon分解+贪心算法规划的路径一(b)Path planned by Boustrophedon decomposition andgreedy algorithm(c)Boustrophedon分解+遗传算法规划的路径(c)Path planned by Boustrophedon decomposition andgenetic algorithm(c)Boustrophedon分解+遗传算法规划的路径(c)Path planned by Boustrophedon decomposition andgenetic algorithm计(d)生物激励神经网络算法规划的路径(d)Path planned by biologically inspired neuralnetwork algorithm图17 场景1下不同算法的路径规划结果Fig.17 Path planning results of different algorithmsin Scenario 1(d)生物激励神经网络算法规划的路径(d)Path planned by biologically inspired neuralnetworkalgorithm图18 场景2 下不同算法的路径规划结果Fig.18 Path planning results of different algorithms in Scenario 23956.为计算方便，将路径的长度用栅格数表示。同时，假定仿真中机器人的平均移动速度和一次转向用时t的乘积Ut=2,即式（7)中P=2,物理意义为机器人一次转向所花的时间可以移动两个栅格的距离。而为了直观地显示不同算法规划出的路径的优劣，以式(7)计算各路径的等效路径长度，作为判断的标准。此外，本文算法在每次求解时的单元数在表1和表2 中依次列出。其中，表1为障碍物分布不规则的地图（场景1），表2 为凸形障碍物较多的地图(场景2)。表1场景1下不同算法的路径规划结果比较Table 1 Comparison of path planning results of differentalgorithms in Scenario 1单元路径路径算法转向/次数量/个长度/个重复率/%本文算法37,25,241 366Boustrophedon分解十贪心算法Boustrophedon分解十遗传算法生物激励神经网络算法表2 场景2 下不同算法的路径规划结果比较Table 2Comparison of path planning results of differentalgorithms in Scenario 2单元路径路径算法转向/次数量/个长度/个重复率/%本文算法47,31,311457Boustrophedon分解十贪心算法Boustrophedon分解十遗传算法生物激励神经网络算法由实验结果可以看出，当在相对复杂的地图中进行全覆盖路径规划时,无论是障碍物分布不规则的场景，还是凹形障碍物较多的场景，本文算法所生成的单元在规划求解的过程中逐步被合并，其数量不断减少，且最终的单元数均少于Boustrophedon分解。同时，本文算法所得遍历路径的重复率约为3种对比算法的50%，表明路径具有更少的余，且转向次数也更低。此外，等效路径长度也表明，本文算法规划的路径更优。系统工程与电子技术4结论在障碍物分布不规则或凹形障碍物较多的静态已知环境中，传统的单元分解法存在单元划分数量较多的问题。这使得最终路径易出现较多穴余和不必要的转向。本文对传统的单元分解法进行了改进：在划分单元阶段，通过在栅格地图上合并路径片段来生成初始单元，使得单元的划分不再完全根据障碍物的形状和位置进行，而是兼顾了单元内的路径规划；在单元间遍历顺序的求解阶段，基于贪心算法和拓扑地图三次求解，合并减少了单元数量，并优化了局部路径。仿真实验结果表明，相较于Boustrophedon分解方法和生物激励神经网络算法，本文算法能够有效减少最终遍历路径的允余和转向次数。但由于单元的合并和局部等效路径路径的优化存在较大的计算量，故本文仅进行了三次求解，长度/个且算法的实时性不够，目前仅适用于离线规划，这也是后续8.07306371446371.4871.4613916783916141.669第45卷1978研究需改进的方向。参考文献14.4033817.6435015.59434等效路径长度/个13.3933430.5839425.6038829.8851221222187232921252466239026931伍跃飞，李建微，毕胜，等面向山地徒步应急救援路径规划的改进蚁群算法研究J地球信息科学学报，2 0 2 3，2 5（1）：90-101.WU Y F,LIJ W,BI S,et al.Research on improved ant colonyalgorithm for mountain hiking emergency rescue path planningJJ.Journal of Geo-information Science,2023,25(1):90-101.2 HUANG G H,MA Q L.Research on path planning algorithmof autonomous vehicles based on improved RRT algorithmJ.International Journal of Intelligent Transportation Systems Re-search,2022,20(1):170-180.3 CUIJ Y,WU D Q,MANSOUR R F.Research on EVRP ofcold chain logistics distribution based on improved ant colonyalgorithmCJ/Proc.of the 8th International Conference on Artifi-cial Intelligence and Security,2022:537-548.4 HONG Z H,SUN P F,TONG X H,et al.Improved A-staralgorithm for long-distance off-road path planning using terraindata mapLJJ.ISPRS International Journal of Geo-Information,2021,10(11):785.5 ZHANG Y,LI L L,LIN H C,et al.Development of path planningapproach using improved A-star algorithm in AGV systemLJJ.Jour-nal of Internet Technology,2019,20(3):915-924.6 RASEKHIPOUR Y,KHAJEPOUR A,CHEN S K,et al.Apotential field-based model predictive path-planning controller forautonomous road vehiclesJ.IEEE Trans.on Intelligent Trans-portation Systems,2016,18(5):1255-1267.7 WANG J,LI B,MENG Q H.Kinematic constrained bi-directionalRRT with efficient branch pruning for robot path planningJJ.Expert Systems withApplications,2021,170:114541.8 PHAM H V,LAM T N.A new method using knowledge rea-soning techniques for robot performance in coverage path plan-ning J.International Journal of Computer Applications inTechnology,2019,60(1):57-64.第12 期9刘洋成，耿端阳，兰玉彬，等：基于自动导航的农业装备全覆盖路径规划研究进展J中国农机化学报，2 0 2 0，41（11)：185-192.LIU Y C,GENG D Y,LAN Y B,et al.Research progress ofagricultural equipment full coverage path planning based on auto-matic navigationJJ.Journal of Chinese Agricultural Mechaniza-tion,2020,41(11):185-192.10代峰燕，高庆珊，陈家庆，等储油罐清洗机器人全覆盖路径规划研究J.机械设计与制造，2 0 2 0，58（2）：2 6 3-2 6 6.DAI F Y,GAO Q S,CHEN J Q,et al.Research of full coveredpath planning for oil tank cleaning robotJJ.Machinery DesignandManufacture,2020,58(2):263-266.11J ZHU D Q,TIAN C,SUN B,et al.Complete coverage pathplanning of autonomous underwater vehicle based on GBNNalgorithmJJ.Journal of Intelligent and Robotic Systems,2019,94(1):237-249.12J ZHU DQ,ZHOU B,YANG S X.A novel algorithm of multi-AUVs task assignment and path planning based on biologicallyinspired neural network mapJJ.IEEE Trans.on IntelligentVehicles,2021,6(2):333-342.13J VAN P H,ASADI F,ABUT N,et al.Hybrid spiral STC-hedge algebras model in knowledge reasonings for robot cove-rage path planning and its applicationsJ.Applied Sciences,2019,9(9):1909.14J DONG W,LIU S S,DING Y,et al.An artificially weighted span-ning tree coverage algorithm for decentralized flying robotsJ.IEEE Trans.on Automation Science and Engineering,2020,17(4):1689-1698.15JJANCHIV A,BATSAIKHAN D,KIM B S,et al.Time-effi-cient and complete coverage path planning based on flow net-works for multi-robotsJ