下载:
-
开放科学（资源服务）标识码（OSID）：
-
随着现代化果园的建设和城市绿化的推进，除草工作变得尤为重要。传统的人工除草存在劳动效率低、生产成本高、工作量大等问题[1]，智能割草机可以解放人们的双手，大大提升劳动效率[2]。智能割草机是一个集外界环境感知、路径规划、障碍物检测与躲避以及多种传感器技术相结合的综合性系统[3]。在割草机的应用中，研究的重点在于如何规划割草机的行走路径[4]，主要集中在全覆盖路径规划、路径跟踪控制和避障路径规划等方面[5]。路径规划的目的是最大限度地减少割草机的行走路径和行驶时间，同时使它们能够自主避开障碍物[6-7]，减少设备磨损，并降低制造成本[8]。常用的路径规划算法包括快速探索随机树(RRT)[9]、概率路线图法(PRM)[10]、Dijkstra算法、A*算法[11]等。
近年来，国内外众多学者对割草机及其路径规划开展了大量研究。谢金燕等[12]提出了一种改进遗传算法，为每台割草机分配并优化作业路径。宋黎明等[13]以STM32为主控制器，结合无线传感技术，提高了草坪修剪机器人的修剪效率。谢逢博等[14]在对果园割草机器人进行路径规划时，控制方法确定为横向偏差修正算法，有效降低了机器人行进的误差。Höffmann等[15]提出了一种智能割草机自动路径规划和高精度定位的方法。张旭东等[16]为割草机增加了避障、报警和自适应割草等功能，提高了割草效率。Martelli等[17]提出了农业四轮差速驱动车辆开发路径规划和路径跟踪算法，引入LD的动态值提高了算法效率并减少了计算时间。周敬东等[18]提出了一种基于改进蚁群算法的移动机器人路径规划方法，通过改变初始化信息素浓度分配、改变启发式函数等方法对蚁群算法进行优化，提高了算法的鲁棒性和寻优能力。上述研究在割草机路径规划的效率和精度上取得了较好的进展，但在复杂地形的适应性、动态环境的实时路径规划以及算法的鲁棒性和计算效率方面仍有改进空间。
本文提出一种基于改进深度优先搜索(Depth-First Search，DFS)算法和A*算法的全覆盖路径规划方法，结合2种算法的优势，改进传统路径规划技术在复杂环境中的适应性和效率。通过引入覆盖优先级导向机制和动态深度控制策略，优化DFS算法的局部搜索效率; 采用A*算法通过改进启发式成本函数，动态调整路径选择，以期提升保障能力和覆盖效率。此外，本文还结合膨胀算法对障碍物区域进行处理，为路径规划提供安全边界，降低冗余路径，提高割草机作业效率。
全文HTML
-
割草机在进行路径规划之前，需要对其作业环境建立地图模型，本文使用MATLAB R2022b软件中的栅格法对割草机的工作环境进行建模，将割草机的工作环境全局信息分解成一系列具有二值信息的等大小正方形网格单元[19]。环境地图由30×30个单元栅格构成，其特征是具有分布不均匀的障碍物，赋予栅格不同的值来表示栅格不同的状态：0表示黑色栅格，代表环境地图中的障碍物区域; 1表示白色栅格，代表环境地图中的自由区域。
由于环境中存在不规则的障碍物，所建立的栅格地图中的一些障碍物不能占满一个完整的单元栅格，且此时建立的栅格地图未考虑割草机的车身尺寸，不仅容易使规划后的路径与障碍物发生碰撞，也可能陷入盲区或死角，因此需要对不规则的障碍物进行膨胀处理。在栅格地图路径规划中，膨胀算法可以帮助处理栅格图中障碍物的边界，使障碍物的范围适当扩大，从而为路径规划留出一定的安全边界，避免割草机靠近障碍物边缘并产生碰撞风险。
-
膨胀操作的定义是使用一个结构元素B扩展图像中的目标区域A。在二值图像中，该操作将所有与结构元素重叠的像素设为目标像素，从而使目标区域扩大，其公式如下：
式中：A为原始栅格图中的障碍物区域; B为结构元素，是一个形状规则的3×3方形小矩阵; BZ表示将结构元素B平移到位置Z。A⊕B的结果是所有能使B与A至少有一个像素重叠的位置的集合。这一膨胀操作的功能实现可以参考ROS Wiki中的costmap_2d功能包[20]。
-
在路径规划中，为确保安全性，通常需要在障碍物区域周围留出一个安全边界，即对障碍物区域执行膨胀。假设A表示栅格图中的障碍物区域，定义安全距离为d，结构元素可以选择具有半径为d的圆形结构元素Bd，其公式如下：
式中：Bd是半径为d的圆形结构元素。膨胀后的障碍物区域Aexpanded包含了原障碍物区域及其周围的安全距离区域。
-
为了实现更大范围的膨胀，可以多次应用膨胀操作，以获得所需的扩展效果。对于重复执行膨胀操作n次，其膨胀结果可以表示为：
栅格图上膨胀算法的实现步骤如下：
步骤1 选择结构元素。根据障碍物区域的形状特征和所需的安全距离，选择大小和形状适当的结构元素B。
步骤2 应用膨胀操作。对栅格地图中的障碍物区域A进行膨胀操作，将B在栅格图上进行逐像素移动，检查其是否与障碍物区域有重叠。
步骤3 生成膨胀后的地图。将膨胀结果合并到栅格图中，得到包含安全区域的膨胀障碍物区域Aexpanded。
所建栅格地图与经过膨胀处理后的栅格地图进行对比，如图 1所示。
在实际应用中，膨胀算法结合路径规划有助于在智能割草机导航时避开障碍物，并创建更安全的路径。通过设置合适的膨胀半径和结构元素，能实现灵活的障碍物扩展效果，从而提高路径规划的可靠性。
1.1. 膨胀操作的基础公式
1.2. 路径规划中的安全区域膨胀
1.3. 多步膨胀公式
-
覆盖路径规划(Coverage Path Planning，CPP)是移动机器人执行清扫、巡逻等任务的核心技术，其目标是高效覆盖目标区域，避免冗余路径和遗漏区域。经典的DFS和A*算法因其良好的搜索性能和路径规划能力被广泛应用，但各有局限。DFS算法虽具有低复杂度和快速覆盖的优势，但在复杂或障碍物密集环境中易产生冗余路径，效率较低; A*算法通过综合实际成本与启发式成本，擅长全局路径优化，但对区域覆盖的关注不足。
本文结合两者优点，提出改进算法。对DFS算法引入覆盖优先级导向机制，使其优先访问未覆盖区域，减少重复覆盖; 对A*算法改进其代价函数，引入障碍物距离和未覆盖区域优先级，提高避障能力和覆盖效率。此外，通过分阶段规划方法，在初始阶段用改进DFS实现基础覆盖，在动态调整阶段结合改进A*优化路径，兼顾全局最优性与局部最优性。
-
为了提高路径规划的效率和适应性，本文对传统A*算法和DFS算法进行了改进，分别提出了改进的启发式成本函数和局部搜索方法，以下将详细阐述改进方法及其作用。
-
改进后的启发式成本函数基本形式如下：
式中：g(n)为从起点到节点n的实际成本，与传统A*算法相同; h(n)为节点n到目标节点的启发式距离，可以使用曼哈顿距离; c(n)为覆盖成本修正项，用于衡量当前节点n的覆盖需求优先级; α和β为权重系数，分别控制距离启发项和覆盖修正项对总成本的影响。
-
启发式距离保持与原始A*算法一致，使用曼哈顿距离表示当前位置与目标位置之间的距离。
-
覆盖成本修正项提升未覆盖区域优先级，并结合障碍物分布动态调整路径选择。定义覆盖成本修正项c(n)为：
式中：Un为节点n周围未覆盖的邻居节点数; Sn为节点n的总邻居数(最大为8); γ为障碍物权重系数; dobstacle(n)为节点n到最近障碍物的距离，定义为曼哈顿距离，即：
式中：O为障碍物节点的集合; (xn，yn)为节点n的坐标; (x0，y0)为障碍物位置的坐标。
-
将上述改进部分结合，得到改进后的启发式成本函数为：
改进后的启发式成本函数f′(n)通过结合未覆盖区域优先级和障碍物距离控制，使得算法在进行路径规划时，既能够快速找到目标位置，又能有效覆盖未访问区域，同时还能动态避开障碍物，提升了整体路径规划的安全性和效率。
-
为了验证上述改进A*算法的有效性，在试验环境为Windows 10系统、处理器为Intel i5-7200U、运行内存为16 GB的硬件平台上采用MATLAB R2022b仿真软件进行试验。将改进的A*算法与传统A*算法在复杂环境下进行了对比，仿真结果如图 2所示。
由仿真结果可知，本文提出的改进A*算法相较于传统A*算法在复杂环境下的搜索过程更具目的性和导向性，生成的路径不仅更短，同时路径平滑度显著提升。在本次试验中，该算法表现出更高的效率和适应性。
为进一步量化性能差异，本文对改进A*算法与传统A*算法在路径长度、拐点数量、遍历节点数量方面进行统计，结果如图 3所示。统计数据显示，改进A*算法在遍历节点数量上减少了53.74%，拐点数量减少了40%，路径长度降低了12.55%，充分证明了改进算法在提升路径规划效率和质量方面的有效性和优势。
-
DFS算法用来寻找从出发点至目标点的可行路径，通过依次访问与上一节点相邻的可行节点，访问完图中所有与出发点有路径相通的节点[21]。在传统DFS算法基础上，设定一个改进的DFS算法，定义路径优先级评分Pscore(n)与动态深度控制函数dlimit(n)，以控制DFS算法的搜索方向和深度。
-
每个节点的路径优先级评分Pscore(n)定义如下：
式中：Un为节点n周围未覆盖的邻居节点数; Sn为节点n的总邻居数; dcenter(n)为节点n到局部搜索中心(起始节点)的曼哈顿距离; N(n)为节点n的邻居集合; P(j)为指示函数，如果节点j是障碍物或已覆盖，则P(j)=1，否则为0; ω1、ω2、ω3分别为控制每个评分项的权重系数;
$\frac{U_n}{S_n} $ 为未覆盖邻居比率，鼓励割草机优先访问未覆盖邻居较多的节点;$\frac{1}{d_{\text {center }}(n)+1} $ 为路径优先级评分的节点到中心节点的距离，鼓励在局部区域内保持一定的覆盖密度;$\frac{1}{1+\sum\limits_{j \in N(n)} P(j)} $ 为障碍物和已覆盖节点的密度。 -
动态深度控制函数dlimit(n)根据当前节点n周围的未覆盖密度来动态调整DFS的最大搜索深度，以避免进入过深的递归，定义如下：
式中：dlimit(n)为节点n的动态深度控制; dbase为基本搜索深度，可以根据任务设定一个初始值; α为控制未覆盖密度对深度的影响。
当前节点n的深度d(n)＞dlimit(n)时，表示当前区域的未覆盖邻居节点密度低，应限制搜索深度，防止搜索陷入不必要的深层。当节点n周围的未覆盖密度较高时，dlimit(n)增加，允许DFS深入搜索该区域; 当未覆盖密度较低时，dlimit(n)保持在较小值，减少不必要的深度搜索。
-
输出局部路径的触发条件包括：
① 当前节点n的Pscore(n)达到最大值(即邻域中最优)。
② 在某次DFS扩展过程中，遍历到的所有邻居节点评分均低于某一设定阈值θ，局部搜索收益下降。其中，θ为评分阈值，可根据任务密集度经验设定(如0.3~0.5)，本文仿真中取值为0.4。
③ 搜索深度已达到dlimit(n)，无法继续向前推进，即当前节点n的深度d(n)＞dlimit(n)。
当计算路径优先级评分时，若为以上①和②的情况，则触发局部路径输出，否则触发动态深度控制; 当动态深度控制中达到情况③时，也触发局部路径输出。
-
针对DFS算法在局部搜索中的应用，本文对其进行优化，以提升局部覆盖的效率和路径规划的合理性。通常情况下，DFS容易导致重复访问或不必要的深度回溯，因此可以引入以下改进方法来优化其搜索路径。
① 路径优先级评分：在每个节点上为不同方向赋予优先级评分，以引导割草机优先访问未覆盖、低成本或重要的节点。
② 动态深度控制：引入动态深度控制，根据当前区域的未覆盖密度来调整DFS的搜索深度，以避免进入不必要的深度递归。
③ 局部启发式选择：在每次深度搜索中，使用启发式信息(如未覆盖邻居数、距离中心区域的距离等)选择最佳路径。
改进前后DFS算法的路径规划如图 4所示，可以看出，改进前DFS在规划过程中的拐点数量为4个，路径平滑度较低，而改进后的DFS通过优先访问未覆盖区域、合理控制搜索深度，有效减少了路径中的拐点数量，拐点仅为2个，提升了局部覆盖的效率和路径的整体平滑性。改进后的算法流程图如图 5所示。
-
为了验证本文所提出的改进DFS算法和A*算法的可靠性，对改进前和改进后的算法分别进行了仿真试验。试验在不同障碍物数量的栅格地图中进行，以测试算法在不同复杂环境下的性能表现。在试验环境为Windows 10系统、处理器为Intel i5-7200U、运行内存为16 GB的硬件平台上采用MATLAB R2022b仿真软件进行试验。
本文设计了3组对照试验，分别在3张地图上设置1、3、5个障碍物，以此来模拟不同复杂度的环境，其中5个障碍物的对照试验图如图 6所示。在地图中，粉色五星表示路径的起始栅格，红色直线表示割草机覆盖的路径，绿色栅格表示重复遍历的区域，灰色栅格表示障碍物。
仿真结果显示，在障碍物数量相同且起点一致的地图中，改进后的算法相较于改进前在转向次数、重复遍历的栅格数量以及路径长度等关键指标上均展现出显著优化效果。改进后的算法路径更加高效，避免了不必要的重复和多余的转向操作。
改进前后算法在不同障碍物数量下的性能对比如表 1所示，随着障碍物数量的增加，地图复杂度提升，割草机的转向次数、重复遍历栅格数量和路径长度均呈上升趋势。然而，无论在何种复杂程度下，改进后的算法能够有效减少转向次数和重复遍历区域，同时缩短路径长度，尤其在高复杂度地图中优势更加明显，表明了算法改进的有效性。
2.1. 改进路径规划算法设计
2.1.1. 改进的A*启发式成本函数
2.1.1.1. 曼哈顿距离
2.1.1.2. 覆盖成本修正项c(n)
2.1.1.3. 改进后的启发式成本函数
2.1.1.4. 算法验证
2.1.2. 改进的DFS局部搜索方法
2.1.2.1. 路径优先级评分
2.1.2.2. 动态深度控制函数
2.1.2.3. 输出局部路径的触发条件
2.1.2.4. 搜索路径优化方法
2.2. 算法仿真
-
本文设计的智能割草机主要由割草模块、控制模块、传感器模块、供电模块以及驱动模块组成，如图 7所示。该智能割草机移动平台采用四轮驱动模式，四轮驱动有更好的牵引力和通过性，并且减少轮胎打滑的可能性，能够使割草机在较为复杂的环境下进行割草作业，例如果园以及地形崎岖的草地。
-
为验证本文提出的改进路径规划算法在实际应用中的可靠性与有效性，将其应用于四驱智能割草机。割草机装配了激光雷达、惯性测量单元、编码器等传感器，通过电脑上的虚拟机进行远程连接，发送指令到ROS主控负责路径规划，STM32控制板接收路径信息并控制电机运动完成任务。试验评价指标包括路径长度、路径拐点数量以及重复路径长度。
试验在草坪上进行，如图 8所示，割草机通过激光雷达构建二维地图，规划路径并完成覆盖作业。ROS可视化界面显示生成的全覆盖导航路径，系统自动记录路径长度、拐点数量和重复路径长度等指标，用于对比分析不同算法的性能。
试验结果如表 2所示，改进算法在路径长度、拐点数量和重复路径长度3个方面均表现出显著优势。具体而言，改进前算法的路径长度为424 m，而改进后算法将其缩短至403 m，减少了4.95%，表明改进算法能够生成更加紧凑的覆盖路径。此外，拐点数量由86个减少至48个，降幅达44.19%，显著提升了路径的平滑性，有助于减少割草机运行中的转向时间和能耗。同时，重复路径长度由45 m减少至28 m，降低了37.78%，充分体现了改进算法在避免重复覆盖方面的效率。
3.1. 总体方案
3.2. 试验验证
-
为验证智能割草机在复杂环境下的全覆盖路径规划性能，本文对改进DFS算法和A*算法进行了仿真试验与实物验证研究，得出以下结论：
1) 通过仿真试验对改进前后算法在不同障碍物数量下(1、3、5个)的性能进行对比研究，结果表明改进算法在路径长度、拐点数量和重复遍历栅格数量方面均表现出显著优势。在障碍物数量为5个的场景中，改进算法将路径长度从436 m减少至400 m，拐点数量从104个减少至61个，重复遍历栅格数量从63个减少至34个，验证了改进算法在复杂环境下的优越性。
2) 在实际草坪场景中对改进算法进行试验验证，改进算法显著优化了路径长度、拐点数量和重复路径长度等指标。实物试验中，路径长度由424 m减少至403 m，拐点数量从86个减少至48个，重复路径长度从45 m减少至28 m。改进算法生成的路径在ROS可视化界面中更加平滑高效，实物运行过程表现出良好的覆盖率和作业效率。
3) 实物试验与仿真试验在路径规划指标的变化趋势上具有较高的一致性，证明了改进算法具有一定的可靠性。同时，验证了本文提出的路径规划算法能够有效减少转向次数和重复路径长度，从而提升割草机的覆盖效率，为复杂环境下的路径规划提供了可靠的技术支持。