这是用户在 2025-1-3 13:39 为 https://www.mdpi.com/2077-0472/13/11/2112 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？





















 
 
期刊
农业
第十三卷
第 11 期
10.3390/农业13112112
农业徽标

提交本期刊评论 提出特刊
► Article Menu

  文章菜单

分享   分享 公告   帮助 格式报价   引用 问题答案   在 SciProfiles 中讨论 竖起大拇指
0
  赞同 短信
0
  评论 格式报价 easyScholar 文献收藏
首页
  下载PDF
设置

订购文章重印本
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
  开放获取文章


曲率约束农用车最优覆盖路径规划

  作者：玛丽亚·霍夫曼
和克里斯托夫·比斯肯斯

优化与最优控制，工业数学中心，不莱梅大学，28359 不来梅，德国
*

信件应寄给的作者。

农业 2023, 13(11), 2112; https://doi.org/10.3390/agriculture13112112

提交材料收到：2023年9月5日/修订：2023年11月2日/接受：2023年11月6日/发布：2023年11月7日

（本文属于智慧农业中的农业自动化特刊）

下载浏览数字版本注释

  抽象的


完整覆盖路径规划（CCPP）在移动机器人应用中至关重要。优化 CCPP 在精准农业中尤其重要，它可以提高资源利用率、减少土壤板结并提高作物产量。这项工作为具有曲率约束的农用车辆提供了一种全面的 CCPP 方法。我们的方法包括四个关键阶段。首先，它将复杂的农业区域分解为更简单的单元，每个单元都配备引导轨道，形成固定的轨道系统。随后的路线规划和平滑路径规划阶段计算一条遵循路径约束、最佳地穿过单元格并与轨道系统对齐的路径。我们使用广义旅行商问题（GTSP）来确定最佳遍历序列。此外，我们引入了一种算法，用于计算单个单元内既平滑又受曲率约束的路径，以及能够在单元之间实现无缝过渡的路径，从而产生平滑的曲率约束覆盖路径。我们的模块化方法允许每个步骤的方法灵活性。我们在真实的农田上评估我们的方法，证明其在最小化路径长度、确保有效覆盖和遵守曲率约束方面的有效性。这项工作为精确高效的农业覆盖路径规划奠定了坚实的基础，并具有进一步实际应用和增强的潜力。

关键词：全覆盖路径规划；优化;引导轨道；路线规划；路径平滑；农业;现场机器人技术

1. 简介

完整覆盖路径规划 (CCPP) 问题是工业运动规划的一个重要方面，涉及指定区域内每个点的有效遍历。找到该问题的最优解对各个领域都具有重要意义，在移动机器人应用领域尤为重要，包括农业、自主清洁 [ 1 ]、割草 [ 2 ]、结构检查 [ 3 ] 和监控 [ 4 ]。此外，CCPP 在工业和处理应用中也占有一席之地，例如铣削 [ 5 ]、激光清洗 [ 6 ]、消毒 [ 7 ] 和喷漆 [ 8 ]。值得注意的是，在精准农业中，无人地面车辆发挥着关键作用，实现最佳覆盖路径具有特殊重要性。CCPP 问题的最佳解可以合理利用燃料、肥料和土地等资源，同时减少重型机械对土壤的压实，最终提高作物产量。鉴于这些考虑，本研究深入研究了 CCPP 问题的复杂性，重点研究其在农业领域操作机器中的应用。
CCPP 的目标是确定具有固定工作宽度的移动机器人的有效路径 瓦∈R+覆盖指定的感兴趣区域(ROI)，同时保持在工作空间内。可以考虑各种目标来衡量这种效率，例如最小总路径长度、执行时间、转弯操作次数、重叠区域或能耗。在优化农业领域覆盖率时，平衡最大化区域覆盖和最小化能耗之间的权衡至关重要。目标函数的选择取决于农民或客户。
地面农业机械通常是非完整的，因为它们受到机械约束，规定了最小转弯半径 r分钟[ 9、10、11 ]。计算出的路径必须遵循这一约束，以尽量减少机器和土壤上的应力。该半径转化 为最大曲率为κ最大限度=r分钟−1在路径内。此外，为实现机器的最佳性能并防止突然的转向命令，路径应具有高度的平滑度，理想情况下至少应具有连续的曲率 [ 9 ]。总之，结合平滑度和曲率约束对于确保路径可由非完整机器驱动以及提高运行效率和保持土壤质量至关重要。忽视这些约束可能导致路径执行不准确，使机器难以精确跟踪轨迹。此外，不遵守路径约束会给机器的控制器带来额外的压力，增加能耗和磨损。此外，这些偏离路径约束的行为违背了现代精准农业的核心目标，后者优先考虑精准、效率、资源优化和环境可持续性。
精准农业旨在通过减少土壤压实和优化资源利用来提高作物产量。一种策略是生成与固定导轨系统一致的覆盖路径，确保车辆始终使用预定义的行车道，同时最大限度地减少对环境的影响。该策略与受控交通耕作(CTF) 的概念相一致 [ 12 ]，这是一种农业实践和管理系统，涉及将农业机械限制在田地内一组特定的永久交通车道上。CTF 的目标是通过精确控制农业机械的运动来最大限度地减少土壤压实并优化土地利用。
在本研究中，我们通过一个由四个关键部分组成的综合程序扩展了这一概念，如图1所示。我们首先应用一种成熟的农业田地处理方法，即ROI 分解。这涉及将田地分割成两个不同的区域：地头区域和内部田地，如图1a所示。随后将内部田地划分为简单的单元。接下来，我们进行引导轨道生成，以描绘路径生成过程中要遵循的固定轨道系统，如图 1b所示。
农业 13 02112 g001

图 1. CCPP 工作流程的四个关键步骤的示例可视化。 (a) ROI 分解，将岬角区域（黄色）和内部区域（绿色）分成单元。 (b) 生成岬角（橙色）和内部（绿色）引导轨道。 (c) 路线规划：计算单元格遍历顺序（数字）以及入口（红色）和出口（绿色）轨迹。 (d) 规划平滑的内部路径（红色）。

随后，执行两项任务。首先，在路线规划步骤中确定单元格及其相应轨道的处理顺序，如图 1c 所示。其次，为了将有关轨道及其遍历顺序的信息转换为平滑的可遍历路径，采用了路径平滑步骤，如图1d所示。需要强调的是，这两个步骤是相互依赖的，并且是并行执行的，而不是严格顺序执行的。整体方法可以在随后的第 3 节中找到。

  1.1.问题陈述

本研究要解决的问题是开发 CCPP 问题的解决策略，重点关注地面农业机械。此外，该问题被归类为二维和单机器人问题，即我们假设一台机器在二维环境中移动。为确保该过程的普遍适用性，所采用的方法与特定的动态机器模型无关。考虑的唯一基本参数是工作宽度w和最小转弯半径 r分钟，这两者对于指导计算都至关重要。我们的方法涉及两个目标：应最小化转弯操作的数量以及总路径长度。由于转弯操作的执行比沿直线移动更耗费能源和时间，因此首先应最小化转弯操作的数量，这也隐含地最小化操作时间。之后，应以最小路径长度计算路径，并遵守路径约束。这些约束包括实现至少 碳2连续性，即连续曲率，并满足曲率约束，曲率最大 κ最大限度=r分钟−1。为了设置该问题的几何边界，假设 ROI 相当于工作空间，从而将机器的移动限制在 ROI 的范围内。ROI 定义为具有单个外边界的二维多边形区域，其中完全包含非自相交障碍物。

我们的目标是产生一个往返的完整覆盖路径，消除对特定起点和终点位置的需要。这与利用固定导轨系统的 CTF 方法是一致的。为了确保这一点，我们开发了一个四步方法，之前在图 1 中进行了描述和可视化，该方法将在第 3 节中详细介绍。虽然讨论了该方法的所有阶段，但特别强调组合路线规划和路径平滑方法，代表了这项工作的核心。要解决的关键挑战是计算最佳单元遍历序列，以及计算每个单元内路径的最佳入口点和出口点。该问题被编码为广义旅行商问题（GTSP），为寻找最佳解决方案提供了结构化框架。此外，还提出了一种算法来计算该离散遍历序列的整体平滑且曲率约束的覆盖路径，确保满足定义的约束。本文专门关注内部领域内的覆盖路径。平滑岬角路径的解决方案在单独的工作中提供[11]。

  1.2.主要贡献


这项工作的主要贡献总结如下：

  • 全面的 CCPP 管道：我们以通用且与机器无关的方式展示了完整 CCPP 管道的系统组装，专为农业机械量身定制。该方法结合了平滑度和曲率约束等考虑因素，这对于自主非完整代理的有效路径跟踪控制至关重要。我们在管道的各个阶段引入优化方法，增强农业机械精确高效的覆盖路径的生成。

  • 基于 GTSP 的路线规划：在这项工作中，我们通过将 CCPP 制定为 GTSP 来解决 CCPP 中的路线规划问题。与通常考虑单元遍历序列的其他工作相反，这些工作使用每个单元的质心作为参考[13, 14]或具有固定的入口和出口点，在我们的工作中，我们还优化了每个单元的入口和出口点，这会对大规模农业投资回报率的路径长度产生重大影响。
  • 区域间路径计算：本研究还涉及区域间路径的计算，这是现有文献中关注较少的领域。我们提出了一种算法，首先创建可行的分段线性路径，然后使用 NURBS 曲线对其进行平滑处理。优化这些曲线的权重，使路径长度最小，同时满足平滑度和曲率约束。

总之，这些贡献通过提供全面且适应性强的路径规划方法，同时解决该领域以前未探索过的挑战，推动了农业机械 CCPP 的发展。


1.3.作品结构


本文的结构如下。在第 2 部分中，我们首先概述该领域的相关出版物。在第 3 节中，我们详细介绍了本文开发和使用的四阶段方法。在后续部分中将更深入地探讨这四个阶段中的每一个阶段。第 4 节重点介绍 ROI 分解和引导轨道系统的生成。在第 5 节中，我们解释了平滑和曲率约束的区域内和区域间路径的生成。第 6 节详细介绍了路线规划步骤，我们将问题转化为 GTSP。本节阐述如何利用前一阶段的结果来计算最佳单元格遍历序列并确定每个单元格的最佳进入点和退出点。最后，在第 7 节中，我们在实际农业领域实施并评估了我们提出的方法。我们在第 8 节中介绍了我们的发现和结论，以及对进一步研究的潜在领域的见解。

2.相关工作

已有多项研究使用多种算法和优化技术解决了各种农业和测量应用中的完全覆盖路径规划 (CCPP) 问题。综述 [ 15 ] 及其参考文献对引导轨迹生成主题进行了广泛的讨论。在 [ 16 ] 中，介绍了一种用于在有障碍物的多个农田中规划路线的进化邻域发现算法。目标函数最小化包含边的总和、田地之间的巡回距离、机器往返仓库的距离以及第一条和最后一条要收割的轨道之间的距离。在使用无人机 (UAV) 测量脱节区域的背景下，[ 17 ] 解决了访问顺序和航线方向的优化问题。作者应用乡村邮递员问题来确定无人机测量的最有效路线。在 [ 13 , 14 ] 中，探索了使用流网络的多个清洁机器人的 CCPP。该工作采用细胞分解将清洁区域划分为细胞，并根据细胞质心之间的距离开发了一种有效的覆盖顺序。在另一项研究 [ 18 ] 中，作者使用莫尔斯函数推广了无人机区域分解的牛耕式行走系统变体。将单元格分为两类，以创建更适合旅行商问题 (TSP) 的单元格集。采用遗传算法和 TSP 算法来获取单元格周围的最短路径。[ 19 ] 的研究侧重于将 CCPP 应用于不相交区域的检查。该问题分为两个阶段：区域间和区域内路径规划。对于区域间路径规划，使用连通图表示多个不相交区域，并提出了两种基于混合整数线性规划 (MILP) 和启发式方法的新方法来生成要遍历的区域的有序序列。区域内路径规划涉及将每个区域分解为网格并规划每个区域上的牛耕式行走运动。
[ 20 ]中的综述概述了机器人导航中应用的各种路径平滑技术。虽然这项工作涉及为各种机器人运动生成平滑路径，但提到的技术，例如基于插值的平滑、样条函数、基于特殊曲线（如 Dubins 或 Reed–Shepp [ 21 , 22 ]）的平滑以及基于优化的平滑，可直接应用于完全覆盖规划。为农业领域中的非完整车辆生成平滑路径的问题大致可分为两类。第一类涉及创建平滑的地头轨道，其中通常使用一组形成多边形的点来生成连续曲率路径。参考文献 [ 11探讨了利用权重优化的 NURBS（非均匀有理 B 样条）曲线来生成这种平滑的地头轨迹。通过优化曲线权重，这项工作确保路径尽可能接近多边形轨迹，同时保持系统的曲率约束。
第二类平滑技术用于生成连接两个内部轨道的平滑转弯。[ 10 ] 介绍了一种自动生成地头非完整车辆平滑转弯路径的方法。该方法考虑了变速曲线和执行器动力学，允许从初始状态到最终状态的完整路径。[ 23 ] 提出了一个多目标成本函数，该函数整合了自动驾驶农业车辆的偏航角、曲率、倒车和路径长度的额外成本，结合 Reeds-Shepp 曲线长度的启发式函数，生成一个综合优先级值，确保生成的路径连续平滑。[ 24 ] 提出了一种生成平滑完整覆盖路径的算法，该算法利用回旋曲线，使非完整移动机器人能够以最佳时间移动。[ 9 ] 提出了一种为具有连续曲率路径的平行轨道生成地头转弯的方法。以最短的计算时间提供了九种地头转弯机动。

3. 方法论

在本节中，我们将详细介绍为解决地面农业机械 CCPP 问题而开发的四步方法。由于重量和转向限制，这些重型非完整机器带来了独特的挑战，因此需要采用结构化的方法进行覆盖路径规划。CTF 概念的核心原则是在田间建立固定的引导轨道，农业机械将遵循这些轨道，从而最大限度地减少土壤压实。本文开发的方法基于这一概念，旨在解决特定的农业挑战，下面将介绍四个关键组成部分。此外，图 2中显示的工作流程将引导读者了解这些关键组成部分。
农业 13 02112 g002
图 2. 本研究建立的 CCPP 工作流程，包括四个关键部分：ROI 分解（紫色）、引导轨迹生成（蓝色）、路线规划（红色）和平滑路径规划（绿色），以及输入参数（灰色）和输出路径（橙色）。本研究重点处理该流程的右侧弧线，从而产生内部覆盖路径，而左侧部分处理地头路径，如 [ 11 ] 中所述。
ROI 分解：我们方法的第一步涉及 ROI 分解。在此阶段，田地被划分为两个主要区域：地头区域和田地内部。地头区域位于田地外围，用于机器操纵和转弯。其宽度根据机器特定参数确定，包括最小转弯半径和工作宽度。内部田地构成 ROI 的中心区域，并经过进一步划分。我们应用多边形单元分解方法来创建简单单元，作为后续路径规划和覆盖优化的基础单元。这确保将内部田地划分为不受障碍物干扰、因此可连续穿越的部分，从而简化覆盖规划过程。

引导轨道的生成：在 ROI 分解之后，CCPP 过程继续生成引导轨道系统。该系统引导最终覆盖路径，实现全场覆盖，分为地头引导轨道和内部引导轨道。地头引导轨道位于地头区域内，其数量取决于该区域的宽度和工作宽度 w。此外，ROI 分解产生的每个单元都填充有平行的内部导轨，间隔最大距离为 w。所需的覆盖路径紧密遵循该轨道系统，在确保有组织、高效的现场覆盖方面发挥着至关重要的作用。

路线规划：路线规划在 CCPP 中非常重要，特别是在确定导航生成的内部引导轨道的最有效序列方面。它涉及确定遍历单元的顺序以及对每个单元内的轨迹进行排序。在这项工作中，我们假设每个单元内的轨道是连续的。我们专注于计算最佳单元遍历序列以及每个单元的入口点和出口点。主要目标是建立一个序列，最大限度地减少行进距离，同时确保系统覆盖整个场地。

平滑路径规划：CCPP 过程的此阶段重点是根据引导轨道和遍历序列生成平滑且可行驶的覆盖路径。这包括生成用于在单个小区内平滑覆盖的区域内路径和连接两个区域内路径的区域间路径。目的是通过保证连续曲率并考虑曲率约束，保证农用车在田间行驶时不会突然移动。这最大限度地减少了土壤压实、资源浪费和机械压力的可能性。该阶段的另一个方面涉及基于地角轨迹生成平滑的地角路径。由于我们的重点主要是内部覆盖路径，因此有关地头路径生成的更多详细信息可以在[11]中找到。

ROI 分解和引导轨道系统的生成密切相关，并将在第 4 节中一起讨论这项工作。如图 2 所示，路线规划和平滑路径规划的阶段紧密相连。在路线规划过程的问题表述中利用平滑的区域内和区域间路径，以便能够计算精确的目标函数，即路径长度。因此，第 5 节首先讨论平滑路径规划，然后再深入研究第 6 节的整体路线规划阶段。
总之，本研究采用的算法在算法 1 中概述。该算法分为不同的阶段：第 1-2 行包含 ROI 分解过程，第 3-6 行涉及导轨系统的创建，均在第 4 节中详细介绍。第 7 行描述了路线规划和路径平滑步骤，在第 5 节和第 6 节以及算法 3 中详细介绍。
算法1 完全覆盖路径规划算法。
输入：感兴趣区域（ROI）、工作宽度w、最小转弯半径 r分钟
输出： ROI 的平滑且曲率受限的覆盖路径
1：
将 ROI 分为田头区域和内部田地
2：
将内部场分解为简单单元
3：
生成岬角轨迹
4：
分解中的细胞
对于分解中的细胞做
5：
 生成内部引导轨道
6：
结束于
7：
算法3  返回算法3

4. ROI 分解和引导轨迹生成

本节简要概述了 ROI 分解和导航轨迹生成过程的基本组成部分。有关这些主题的全面综述，请参阅 [ 15 ]。第一步是将地头区域与内部场分离。接下来是对内部场进行单元分解，并简要概述对每个结果单元应用的内部导航轨迹生成方法。

4.1. 地头区域分离和地头引导轨道

通用方法首先对 ROI 进行分类，将其划分为地头区域和内部区域，如图 1a 所示。为了将地头区域与内部区域分开，多边形偏移技术 [ 25 ] 已被证明是有价值的，该技术采用外边界向内偏移和障碍物向外偏移。该技术可用于生成覆盖地头区域的地头引导轨道，如图1b（橙色）所示。对于解决处理多边形角的几种方案的解决方案，Clipper2 [ 26 ] 是一个很有前途的库，它提供了一个用于多边形偏移（和裁剪）的多功能工具包。更多详细信息可在 [ 15 ]中找到。

4.2 内部场和内部制导轨道的单元分解

一种广泛使用的精确细胞分解方法（尤其是在 CCPP 中）基于线扫描算法。该方法利用扫描线扫描 ROI，检测特定事件，并在这些事件处插入与扫描线平行的线来分解区域，如图3所示。该技术的一个直接示例是梯形分解[ 27 ]，如图4a所示。在这种情况下，所有多边形顶点都被视为事件，这可能导致大量狭窄细胞。另一种突出且有效的基于扫描线的分解技术是牛耕式细胞分解(BCD) [ 28 ]，如图 4b所示。该技术背后的主要思想是生成可以使用来回运动覆盖的细胞，与梯形分解相比，产生的细胞数量较少。这些细胞相对于扫描方向是单调多边形，因此可以通过简单的来回运动（轨迹与扫描线平行）实现单独覆盖。该技术最初于 [ 28 ]中引入，后来于 [ 29 ] 中得到扩展。BCD 广泛应用于各个领域，如多机器人完全覆盖路径规划 [ 30 ]、高效点对点路径规划 [ 31 ]、无人机巡检 [ 32 ]、AUV 港口海底勘测 [ 33 ] 以及实现最小路径长度 [ 34 ]。
农业 13 02112 g003
图 3. 基于扫描线的分解：扫描线（红色）扫过（此处从左到右）具有一个障碍物（灰色）的区域，检测事件（绿色），并使用与扫描线平行的线（红色）分解该区域，经 [ 15 ]（2023，Höffmann，M.）许可转载。（a）初始区域。（b）分解为 4 个单元。（c）将更复杂的区域分解为 10 个单元的示例。
农业 13 02112 g004
图 4.基于扫描线的不同分解技术，其中考虑的事件（绿色），假设扫描线为垂直，经 [ 15 ] (2023, Höffmann, M.) 许可转载（ a）梯形 [ 27 ]。（b）牛耕式行走系统 [ 28 ]。
在本文中，我们按照 [ 15 ]中的建议，采用 BCD 方法将 ROI 分解为简单的（在本例中为单调的）单元。扫描线的角度被视为一个变量，使我们能够确定最佳分解。为了实现这一点，我们专注于优化转弯机动的数量，特别是内部引导轨道的数量，因为它们会显著影响路径执行成本 [ 35 ]。优化过程包括评估各种扫描线方向的结果单元的最小高度总和。此优化的数学公式可在 [ 15 ] 中找到。
一旦成功且最佳地分解了该区域，每个得到的单调单元都会被直线平行的内部导轨覆盖，导轨的距离小于或等于w，与分解所用的扫描线平行。由于单元相对于扫描线方向是单调的，因此以这种方式来回覆盖单元是可能的，而且很简单。图 1b中的示例对此进行了说明。

5. 平滑路径规划

平滑的路径规划在机器人导航中起着至关重要的作用，特别是对于具有较大最小转弯半径的大型机器，可确保操作过程中机器和土壤的稳定性。我们方法中的整体路径由两种不同的路径类型组成：
  • 区域内路径，负责覆盖细胞分解产生的单个细胞并遵循内部引导轨道，主要侧重于管理轨道之间的转弯机动；
  • 区域间路径连接与轨道系统对齐的两个不同单元的区域内路径，包括内部轨道和地头轨道。
图 5显示了这两种不同的路径类型。下一节将描述这两种路径类型的计算，采用各种平滑技术来确保机器无缝、高效地遍历。
农业 13 02112 g005
图 5. 区域内（红色）和区域间（蓝色）路径之间的区别。区域内路径覆盖每个单元，而区域间路径使用地头引导轨道（橙色）连接不同的区域内路径。

5.1. 区域内路径

区域内路径规划的目的是计算从一个引导轨道到另一个引导轨道的转弯机动轨迹。单个单元内轨道的遍历顺序也提供了优化的机会。然而，在本文中，我们将采用顺序轨道遍历顺序，以简化和易于实施。值得注意的是，文献中的研究表明，单元内轨道的遍历顺序确实可以进行优化，以提高效率和覆盖率 [ 16，36，37，38 ]。
每个转弯动作都可以独立计算，并且需要满足连续曲率 (CC) 约束，以考虑机器的有限转向速度。这是通过从给定的起始配置计算 CC Dubins 模型 [ 21 ] 的轨迹来实现的γ1结束配置 γ2. 配置 γ=（十，是，θ，κ）由姿势定义 （十，是，θ）和曲率 κCC Dubins 模型的数学描述由微分方程组给出 [ 21 ]
十˙是˙θ˙κ˙=五余弦θ五罪θ五κσ
其中控制输入v和 σ分别对应于后轮的驱动速度和角加速度。因此， σ与...相关 φ˙为前轮转向速度。与轴距b一起，有以下关系成立[ 21 ]：
κ=棕褐色φb，σ=κ˙=φ˙b余弦2φ。
图 6显示了该模型的状态。CC Dubins 模型假设单位行驶速度恒定，并且曲率和角加速度有上限，这是由于现实世界的转向限制（转向角 φ受到机械限制，st |φ|≤φ最大限度）
五=1和|κ|≤κ最大限度=棕褐色φ最大限度b和|σ|≤σ最大限度。
农业 13 02112 g006
图 6. Dubins 模型中关键组成部分的可视化（1）：位置 （十，是），方向 θ，曲率 κ（作为转弯半径的倒数）、速度v以及转向角 φ轴距为b。
CC Dubins 模型是常规 Dubins 模型 [ 39 ]的扩展，其中曲率的连续性不是条件。目的是找到一条连续曲率平面曲线，该曲线遵循 ( 1 ) 连接两个点 （十1，2，是1，2）在具有规定切线的平面上 θ1，2和曲率 κ1，2。曲线必须满足 ( 3 ) 中的曲率和曲率导数界限。配置 γ1，2由当前轨迹的出口姿态和下一轨迹的入口姿态决定，在机动开始和结束时均受零曲率约束，以确保连续曲率过渡到直线引导轨迹。这在图7中进行了概述。
农业 13 02112 g007

图 7. 示例性起始姿势（ 𝑥1 、 𝑦1 、 𝑞1 ）和结束姿势（ 𝑥1 、 𝑦1 ， 𝑞1 ）的两个内部导轨（蓝色）和草图转弯机动（红色）。

使用该模型可确保生成的路径保持连续曲率并遵守必要的曲率约束。这种灵活性强调了该模型对各种农业机械的适用性，有助于其实际应用。

基于这些机动规范，我们制定了一个最优控制问题，其目标是最小化路径长度。为了有效地解决此类最优控制问题，我们可以利用 TransWORHP [40] 等软件库，它基于 ESA NLP 求解器 WORHP [41]，提供强大的轨迹规划和优化功能。此外，针对这种特定场景的专门替代方案是软件库 hbanzhaf/steering_functions [22]，它是专门为计算 CC Dubins 曲线而定制的。这两个库都提供了有效的方法来查找遵循曲率约束的轨迹，同时优化路径长度，从而促进使用 CC Dubins 模型成功进行区域内路径规划。

农业背景下不同轮流类型的研究在[9,10,42]等参考文献中有详细记录，提供了可用技术的全面概述。值得注意的转弯操作如图 8 所示，这些操作显着影响农用车辆路径规划的效率和精度。在特定情况下， Ω 转弯与钩形转弯相比表现出更短的转弯距离，尽管后者需要更小的地头宽度。这些轮流类型之间的选择可能会受到农民偏好的影响。总体而言，当满足 𝑟min<𝑤2 时，（平坦）U形转弯是最佳的，而当不满足此条件时， Ω 或钩形转弯是首选。
农业 13 02112 g008

图 8. 选择最常见的农业转弯类型，在岬角区域从一个内部引导轨道穿越到另一个内部引导轨道，经 [15] 许可转载（2023 年，Höffmann，M.）。 (a) U。 (b) 扁平 U。 (c) Ω 。 (d) 钩子。

整个区域内路径由一系列所描述的转弯操作组成。这些区域内路径的说明性表示如图 5（红色）所示，其中路径也通过区域间路径（蓝色）连接。这些区域间路径用于在连续的区域内路径之间建立连续性和过渡。

  5.2.区域间路径


区域间路径是将一个区域内路径的末端与另一区域内路径的起点连接起来的关键组件。该路径必须具备基本特性，包括保持在投资回报率范围内以避免障碍物、主要遵循引导轨道（地头和内部）以最大限度地减少土壤压实，以及相对较短以优化整体操作时间。实现平滑度（即连续曲率）对于机器的无缝操作也是必要的。为了满足这些要求，我们的方法涉及生成初始分段线性区域间路径。随后，我们采用非均匀有理 B 样条 (NURBS) 曲线，在每个控制点中结合权重 [43]。通过这些，我们平滑分段线性路径，同时通过权重优化考虑曲率约束，类似于[11]中描述的方法。


5.2.1.分段线性区域间路径


算法 2 中介绍了计算分段线性区域间路径 ℒ 的算法，图 9 中提供了步骤的可视化表示。其主要目标是在两个区域内路径之间建立连接。
农业 13 02112 g009

图 9.分段线性区域间路径计算的可视化（红色虚线和实线的组合）。对应于起点和终点（紫色）的轨迹被展开（黑色虚线），并计算与田边轨迹（橙色）的交点（红点）。然后，(1) 沿着岬角轨道细化路径，(2) 沿着内部轨道（绿色）对齐路径，(3) 使用共享的岬角轨道（红色虚线）连接两条子路径。

该算法首先检查第一条区域内路径的终点轨迹和第二条区域内路径的起点是否相邻，并且可以直接与简单的 CC Dubins 转弯连接，如上一节所述。这种连接如图 5 所示（右上角和左下角的第二条区域间路径），其特点是平滑且曲率最小。然而，如果直接连接不可行，算法会延伸起始轨道和结束轨道，如图 9 中的黑色虚线所示。这些延伸会导致与地头轨道的交叉点，在图 9 中标记为红点。 ，对于每种交叉口组合（一个来自起始轨道延伸段，一个来自结束轨道延伸段），当它们对应于相同的地头轨道时，路径会进一步优化，如第 6-13 行所总结。为了确保区域间路径在 ROI 方面的可行性，特别是在避障方面，该算法通过使用地头轨迹绕障碍物绕行来对其进行改进。此外，在遇到从一个岬角轨道过渡到另一个岬角轨道的情况下，该算法会寻求将路径与内部引导轨道对齐，从而最大限度地减少该区域的土壤压实。这导致形成两条子路径，每条子路径将起始或结束轨道与相同的地头轨道连接起来。然后将这两个子路径结合起来以创建分段线性区域间路径的候选路径。重要的是，对所有交叉点组合重复此过程，最后，算法选择总路径长度最短的候选路径。 该算法确保 ℒ 保持在 ROI 内并沿着地头和内部引导轨道移动。这种方法有效地创建了一种有效且可行的分段线性区域间路径，用于从一个单元过渡到另一个单元。

算法2 分段线性区域间路径。

输入：在点 𝑝1 开始内部轨迹 𝑡1 ，在点 𝑝2 结束内部轨迹 𝑡2 ，地头引导轨迹 ℋ

输出：连接 𝑝1 和 p2 的分段线性区域间路径
1：

如果 𝑡1 和 𝑡2 是相邻轨道 && 𝑝1 和 p 2 接近，则
2：
 
返回 CC Dubins 从 p 1 转向 p 2 页2
3：
如果结束
4：
延伸轨道 吨1在 页1和 吨2在 页2
5：
计算交点集 我1，2由于扩展 吨1，2与轨道相交 赫
6：
为了（我1，我2）在 我1×我2 做
7：
 如果 我1和 我2处于不同的轨道上 赫 然后
8：
  继续
9：
 如果结束
10：
 完善初始点之间的直接连接 页1，2以及交点 我1，2使路径符合所有轨道的轮廓 赫。
11：
 如果精炼导致不同轨道之间的转换 赫 然后
12：
  如果可能的话，将路径与最近的内部导轨对齐。
13：
 如果结束
14：
 这会产生两条子路径，每条路径的起点均为 页1或者 页2并在同一岬角小径结束
15：
 组合这些路径（包括沿着岬角轨道的中间点）以构建路径候选。
16：
结束于
17：
返回具有最小长度的路径候选
后续阶段涉及平滑该路径，以确保具有曲率约束的非完整车辆能够在该路径上行驶。为了实现这一点，我们采用了 NURBS 曲线，遵循 [ 11 ]的思想。

5.2.2. 非均匀有理 B 样条 (NURBS) 曲线

NURBS 曲线是 B 样条曲线和贝塞尔曲线的泛化，它们基于一组控制点共享一个定义 磷={磷0，…，磷n}⊂R2和一个结向量 乌={你0，…，你米}⊂R。然而，主要的区别在于它们的合理性，这是由于权重的加入而产生的 瓦=（瓦0，…，瓦n）电视∈R≥0n+1与控制点 [ 43 , 44 ] 相关的 NURBS 曲线 页∈否权重w定义为 碳瓦：德→R2， 和
碳瓦（你）=∑我=0n否我，页（你）瓦我磷我∑杰=0n否杰，页（你）瓦杰，
与域名 德=[你页，你n−页]， 和 否我，页：[你0，你米]→R阶数为p的第i 个基函数[ 43 ]。在本研究中，我们采用均匀节点向量，这是 NURBS 曲线实现中广泛使用的方法 [ 43 ]。利用 NURBS 曲线可以让我们非常灵活地实现所需的平滑度，因为我们可以自由选择阶数p以满足我们的特定需求。利用均匀节点向量可确保阶数为p的 NURBS 曲线达到 碳页−1连续性，提供平滑的轨迹。然而，在选择曲线的度数时，在实现所需的平滑度和管理计算成本之间取得平衡至关重要，因为更高的度数会导致计算复杂性的增加。

5.2.3. 使用 NURBS 曲线平滑区域间路径

为了在满足曲率约束的同时实现平滑连续的区域间路径，我们借鉴了 [ 11 ] 中提出的方法。优化 NURBS（非均匀有理 B 样条）曲线的权重以适应其形状，确保符合曲率约束。分段线性区域间路径的路径点 大号作为控制点，或者进一步离散路径以使其具有相等的步长。然后，我们解决非线性优化问题来计算最佳权重w。表示 NURBS 曲线上点与点之间的平方欧几里德距离 碳瓦（你）以及最近的点 大号作为 分布瓦2（大号，你）∈R为了 你∈德，并将该点的 NURBS 曲线对应的曲率表示为 κ瓦（你），非线性优化问题的公式如下：
分钟瓦∈R≥0n+11|德|∫德分布瓦2（大号，你）d你κ瓦（你）2−κ最大限度2≤0，你∈德
目标函数确保生成的 NURBS 曲线紧密遵循分段线性路径 大号。同时，约束确保曲率保持在预定义的上限内 κ最大限度使用 ESA NLP 求解器 WORHP [ 41 ]解决该非线性优化问题，使我们能够获得符合曲率约束的平滑区域间路径。

6. 路线规划

路线规划用于确定各个单元的最佳遍历顺序，从而得到一条长度最短的完整覆盖路径，该路径由一系列区域内和区域间路径组成。为了解决这一优化挑战，我们将其表述为一个图问题，其中节点表示区域内路径，边表示区域间路径。具体来说，我们将这个问题视为一个广义旅行商问题 (GTSP)，并将其表述为一个整数规划。随后，我们演示了如何将不同的路径编码为节点和边，使我们能够将 GTSP 技术应用于我们的特定问题。通过将覆盖路径规划转化为基于图的优化问题，我们旨在有效地确定遍历单元的最有效顺序，最终得到一条高度优化和缩短的完整覆盖路径。

6.1. 广义旅行商问题（GTSP）

旅行商问题 (TSP) 是一个经典的优化挑战，涉及一个完全图，旨在找到最便宜的汉密尔顿循环，该循环访问每个节点一次。尽管它在大型实例中的计算复杂度很高，但它在物流、运输和网络设计中的实际意义已导致开发出各种有效的解决方法[ 45、46、47、48、49 ]。
相比之下，广义旅行商问题 (GTSP) 是 TSP 的一个变体，其中节点被组织成簇。目标是找到访问每个簇中一个节点的最佳汉密尔顿循环。这种基于簇的结构使 GTSP 有别于标准 TSP，使其在需要优化跨多个位置子组的路线的场景中很有价值 [ 50 , 51 ]。
表示 GTSP 的图定义为 格=（五，埃）， 和 五表示节点集和 埃表示边集，每条边都分配有成本。节点被划分为m 个不同的簇 五我，我∈{1，…，米}， 和 五我∩五杰=∅为了 我≠杰。通过利用二进制变量，可以将 GTSP 公式化为整数线性规划。从而最小化广义循环的成本。Gurobi 优化器 [ 52 ] 因其对稀疏线性代数的有效处理、精确的数值误差管理和有效的启发式策略而在整数线性规划方面表现出色。SCIP [ 53 ] 是另一种用于混合整数规划和非线性规划的快速求解器，兼作约束整数规划和分支定价的框架。在本文中，我们将使用 Gurobi 优化器。

6.2. 使用 GTSP 实现最佳单元遍历序列


我们方法的主要优化目标是最小化总路径长度，同时确保每个单元被恰好覆盖一次。将问题编码为 GTSP 涉及定义图的节点、边及其相关成本。这种方法将平滑路径规划的概念与路线规划方面错综复杂地交织在一起，如图 1 所示。算法 3 总结了路线规划和平滑路径规划阶段。

第一步是引入节点的表示。有四种不同的方法可以利用给定的平行引导轨道以区域内路径覆盖单个单元，如图 10 所示。假设起始轨道和结束轨道是两个最外面的轨道。这些可能性中的每一种都被转换为图中的一个节点。因此，每个节点都拥有一条特定的区域内路径，由指定的起始和结束轨道和位置来描绘。此外，同一小区对应的四个节点聚集在一起。如果细胞分解总共产生 m 个细胞，则该图将包含总共 n = 4 m 个节点和 m 个簇。
农业 13 02112 g010

图 10. 由于起始（绿色）和结束（红色）位置不同，有四种不同的方式覆盖单元格。 (a) 轨道数为奇数。 (b) 轨道数为偶数。

连接两个节点的边由连接相应的两个区域内路径的线性区域间路径表示。该边的成本由分段线性区域间路径的长度与前一节点的区域内路径的长度之和定义。该成本函数符合最小化总路径长度的目标。

构建该图可以制定整数程序来求解 GTSP，最终识别哈密顿循环。该循环提供了节点和边的最佳序列。将它们解码回来会产生一系列区域内路径和分段线性区域间路径。在平滑后者之后，如第 5.2.3 节所述，这些路径可以连续连接，产生平滑且曲率约束的覆盖路径。
值得注意的是，在 GTSP 求解过程中，必须计算连接各种像元组合的所有区域间路径的成本。为了提高计算效率，可以只考虑分段线性路径 大号在此优化步骤中。平滑区域间路径的计算可以推迟到建立完整覆盖路径时的最后一步。由于平滑过程对路径长度的影响很小，因此这种近似仍然有效。同样，对于区域内路径，其长度不会显著影响优化结果，并且可以进行相应的管理。这种简化的方法既确保了计算效率，又确保了最佳覆盖路径的推导。
算法3 路线规划和平滑路径规划
输入：固定导轨系统，最小转弯半径 r分钟，轨道宽度w
输出：最佳覆盖路径
1：
细胞中的细胞
对于细胞中的细胞做
2：

通过计算单元的四个区域内路径，从轨道系统创建一个由四个节点组成的集群
3：
结束于
4：
对于不同集群中的一对节点
5：
 计算分段线性区域间路径
6：
 创建连接两个节点的边
7：
 为边分配成本：第一个节点的区域间路径和区域内路径的长度之和
8：
结束于
9：
聚类的节点和边对应于 GTSP。制定线性规划并使用求解器计算解决方案
10：
解决方案是节点（及其连接边）的最佳序列。
11：
将节点和边编码回区域内和分段线性区域间路径，得到路径向量
12：
对于路径向量中的路径
13：
 如果路径是区域间路径，则
14：
  使用 NURBS 曲线的平滑路径
15：
 如果结束
16：
 将路径附加到最终覆盖路径
17：
结束于
18：
返回最终覆盖路径

7.结果与讨论

在本节中，我们将介绍路径规划方法的成果。由于我们选择了一种成熟的多边形分解技术，因此我们不提供对 ROI 分解和引导轨迹生成步骤的评估。值得注意的是，我们的模块化方法允许灵活地互换所选的分解方法，而不会影响后续步骤。评估侧重于平滑阶段，包括区域内和区域间路径。我们检查示例路径，研究不同最大曲率对这些轨迹的影响。随后，我们将我们提出的路径规划方法应用于四个不同的现实世界农业领域。通过此应用，我们试图评估我们的方法生成的曲率约束覆盖路径的有效性。之后，我们对基于 GTSP 的路线规划算法和启发式方法进行了比较分析，以强调前者的优势。

7.1 不同曲率约束对平滑路径规划的影响

我们将首先关注区域内路径，考虑（平坦）U 型转弯和 Ω转弯。利用TransWORHP软件库[ 40 ]，我们解决了（1）和（3）中描述的最优控制问题。图11通过视觉对比展示了传统Dubins曲线[ 39 ]和CC Dubins曲线之间的定量差异，特别是在平坦的U形转弯和 Ω-转弯。此外，还可以看到这两种转弯类型的特征曲率轮廓。虽然 CC 转弯的路径长度略大于传统的 Dubins 曲线，但明显的区别在于曲率轮廓的连续性。
农业 13 02112 g011
图 11. 两种最常见的转弯动作的常规 Dubins（蓝色）和 CC Dubins（橙色）转弯的相位图和曲率曲线。（a）平缓 U 型转弯。（b） Ω-转动。
涵盖各种最大曲率的综合评估 κ最大限度图 12和图 13显示了相同机动和两种转弯类型的曲线。检查曲率曲线可发现曲线中存在七个相位。值得注意的是，三个相位在值处保持恒定曲率 ±κ最大限度或 0，分别表示圆弧或直线上的运动。这些曲率值之间的连续过渡是通过引入斜率来实现的 ±σ最大限度曲率增加/减少，从而产生回旋弧。此特性将这些 CC Dubins 路径与常规 Dubins 曲线区分开来。
农业 13 02112 g012
图 12. 不同转弯半径的平缓 U 形转弯 r分钟<瓦2和 κ最大限度=r分钟−1和 σ最大限度=20. ( a ) 相位图。( b ) 曲率分布。
农业 13 02112 g013
图 13. Ω- 针对不同的转弯半径 r分钟>瓦2和 κ最大限度=r分钟−1和 σ最大限度=10. ( a ) 相位图。( b ) 曲率分布。
为了阐明区域间路径平滑，图 14b中展示了一个说明性示例。此视觉表示包括分段线性路径 大号（以黑色表示）以及通过权重优化的 NURBS 曲线计算出的不同最大曲率的平滑路径 κ最大限度权重优化过程采用 ESA NLP 求解器 WORHP [ 41 ] 进行求解。其中，平滑度 页=5被采用，产生曲线 碳4。这一特征在连续且可微的曲率分布中也很明显。相位图和曲率分布都强调了所得区域间路径与分段线性路径的显著一致性，同时遵守曲率约束。需要强调的是，在区域间路径平滑过程中，目标不仅仅是实现最短路径，而是紧密遵循分段线性路径。
农业 13 02112 g014
具有不同转弯半径 r 的区域间路径的示例性可视化基于分段线性路径（黑色）。（）相位图。（）沿（标准化）路径的曲率分布。
图 14. 基于分段线性路径（黑色）的具有不同转弯半径 r 米我n 的区域间路径的示例可视化。 (a) 相图。 (b) 沿（归一化）路径的曲率剖面。

7.2 最优 CCPP 算法在实际农田中的应用

在本节中，我们展示了将我们的方法应用于四个不同的实际农田的结果，田间数据由 NEXAT GmbH [ 54 ] 提供。为了确保更好的可比性，将田地重新缩放到相似的尺寸，并使用 Gurobi 软件版本 10.0.1 [ 52 ]求解 GTSP 。所考虑的田地的规格和由此产生的覆盖路径总结在表 1中，并在图 15、图 16、图 17和图 18中以视觉方式描述。
农业 13 02112 g015
田地 1。给定田地边界（黑色）、牛耕式耕作分解（灰色）以及包含地头轨道（绿色）和内部轨道（蓝色）的引导轨道系统。最佳单元遍历顺序（数字）以及每个单元的入口点（红色）和出口点（绿色）。最终的平滑覆盖路径（红色）。
图 15. 场地 1。给定场地边界（黑色）、环足分解（灰色）以及包含岬角轨道（绿色）和内部轨道（蓝色）的最终引导轨道系统。最佳单元格遍历序列（数字）以及每个单元格的入口点（红色）和出口点（绿色）。由此产生的平滑覆盖路径（红色）。
农业 13 02112 g016
图 16. 田地 2。给定田地边界（黑色）、牛耕式耕作分解（灰色）以及包含地头轨道（绿色）和内部轨道（蓝色）的引导轨道系统。最佳单元遍历顺序（数字）以及每个单元的入口点（红色）和出口点（绿色）。最终的平滑覆盖路径（红色）。
农业 13 02112 g017
图 17. 田地 3。给定田地边界（黑色）、牛耕式耕作分解（灰色）以及包含地头轨道（绿色）和内部轨道（蓝色）的引导轨道系统。最佳单元遍历顺序（数字）以及每个单元的入口点（红色）和出口点（绿色）。最终的平滑覆盖路径（红色）。
农业 13 02112 g018
图 18. 场地 4。给定场地边界（黑色）、牛耕式行进道路分解（灰色）以及包含地头轨道（绿色）和内部轨道（蓝色）的引导轨道系统。最佳单元遍历顺序（数字）以及每个单元的入口点（红色）和出口点（绿色）。最终的平滑覆盖路径（红色）。
表 1.图 15、图 16、图 17和图 18 中示例字段的字段和路径规范。
然而，对于不熟悉我们方法的观察者来说，直观地检查结果有时可能会显得不合常规。这主要是由于两个原因。首先，我们的目标是计算往返覆盖路径，其次，区域间路径并不总是等同于最直接的直线连接。因此，最佳解决方案可能并不总是符合直观的预期。
我们的方法的计算时间取决于场的复杂性，从场 1、2 和 4 的毫秒级到场 3 的几分钟级不等。由于我们的主要关注点是在已知环境中的离线路径规划，因此只要计算时间不超过几个小时，它就不会发挥重要作用。
解释这些结果的效率可能具有挑战性。例如，仅考虑路径长度可能无法提供对整体路径质量的全面评估。尽管考虑的优化标准是最小化路径长度，但为了能够进一步评估和比较结果，不建议只看路径长度而不考虑其他背景信息。由于导轨系统，区域内路径的长度只能在一定程度上改变。此外，由于区域间路径主要用于单元之间的遍历，而实际的场处理由区域内路径处理，因此最小化区域间路径的长度是可取的。为了应对这一挑战，我们引入了两个不同的指标。首先，我们使用公式 计算覆盖面积 (CA) 的比率
加州=小路长度·瓦内场地区域。
由于内部轨道的设计确保完全覆盖内部场地，因此该比率自然会超过 1，因此希望将其最小化。它对应于内部场地和沿田头的路径的重叠区域。如表 1所示，归因于转弯和区域间路径的面积徘徊在 10-15% 左右。该百分比在场地 3 中最高，因为该场地有最多的障碍物和产生的单元，因此需要更多数量的区域间路径，从而增加了路径和田头区域内路径的重叠区域数量。
其次，我们引入区域间路径比率（IR），定义为
红外线=跨国公司-地区小路长度小路长度。
IR 值越小，结果越有利，表明用于在单元之间移动的路径越少，用于实际现场处理的路径越多。表 1中的列表结果表明，该比率从 2.4% 到 6.0% 不等，凸显了我们的方法在保持较短区域间路径方面的有效性。正如预期的那样，分解产生的单元数量直接影响所需的连接路径数量。

7.3. 基于 GTSP 的路径规划与启发式方法的比较

在本节中，我们将对本文提出的基于 GTSP 的路线规划方法与启发式替代方案进行比较分析。虽然总体方法（包括 ROI 分解以及区域内和区域间路径的计算）保持一致，但两种方法之间的关键区别在于如何计算单元遍历序列。为了进行评估，我们使用图 15、图 16、图 17和图 18中的字段 1 至 4中的字段 1 至 4 。
本文详细介绍的基于 GTSP 的方法是第一种正在考虑的方法。
对于启发式方法，我们使用与基于 GTSP 的方法相同的节点创建方法。这意味着，对于产生m 个单元的分解， 4米创建节点，其中每个节点代表一个覆盖的单元和该单元内路径的起始位置。从具有预定起始轨道和位置的指定单元开始，局部搜索识别下一个尚未覆盖的节点。因此，区域间路径的长度被视为成本函数。该过程持续到所有节点都被覆盖，之后路径返回到起点。这产生了一个启发式解决方案。为了与我们的最优方法进行有意义的比较，我们应用了启发式方法 4米时间，考虑所有可能的起始轨迹和位置。最后，我们选择具有最短总路径长度的启发式解决方案，以便与基于 GTSP 的方法进行比较。
比较结果如表 2所示。显而易见，基于 GTSP 的最优方法在总路径长度和内​​部路径总长度方面始终优于启发式局部搜索方法。
所提出的基于 GTSP 的路线规划方法与最佳启发式路线规划方法的比较。
表 2. 所提出的基于 GTSP 的方法与最佳启发式路线规划方法的比较。
基于 GTSP 的方法相对于启发式方法的优势大小在各个领域有所不同。对于领域 1 和 2，区域间路径长度缩短了约 13%，这显示了基于 GTSP 的方法的显著优势。相比之下，领域 3 和 4 表现出的差异较小，区域间路径长度仅缩短了约 2%。这种变化凸显了基于 GTSP 的方法的多功能性和有效性，它可以在某些情况下产生显著的改进，同时在其他情况下仍然提供好处。

8. 结论和未来工作

总之，我们的研究引入了一种全面的方法，用于在遵守关键曲率约束的同时在农业领域生成平滑的完全覆盖路径。该方法包括四个基本步骤：ROI 分解、引导轨迹生成、路线规划和平滑路径规划。我们强调了我们的方法的模块化特性，使其能够适应不同的需求，并允许每个步骤中的方法互换。本文提出的算法旨在易于实施和理解。
通过在实际农业领域的实际应用，我们验证了该算法适合解决农业环境带来的独特挑战。与启发式方法的比较评估揭示了在路线规划阶段采用基于 GTSP 的问题公式的优势。
必须承认，与任何方法一样，我们的方法也有其局限性。一个显著的限制是计算工作量与 GTSP 中单元格数量之间的关系。随着单元格数量的增加，GTSP 的复杂性也会增加，在极端情况下，这可能导致某些田地不可行。当处理大量单元格时，即使是像 Gurobi 这样强大的优化求解器也很难在合理的时间内计算出解决方案。然而，值得注意的是，这种限制通常不是实际农业应用所关心的问题。大多数农田往往呈矩形，障碍物相对较少，将单元格数量保持在可控范围内。
尽管如此，在处理非常规或不规则的田地几何形状时，我们的方法可能会面临挑战，特别是在计算和平滑区域间路径时。鉴于田地布局和条件的多样性，我们无法保证我们的方法适用于所有可能的边缘情况。然而，对于绝大多数典型的农业场景，我们的方法仍然是覆盖路径规划的强大而有效的解决方案。仔细考虑田地特征和明确定义的分解过程可以帮助减轻这些限制，确保我们的方法在实际应用中的有效性。
然而，还有几个地方可以改进。我们解决的一个限制是单个单元格内内部引导轨道的顺序遍历以及每个单元格中起始和终止轨道的选择受限。为了提高算法的效率，未来的工作可以集中在优化单元格内轨道的排序以及起始和终止轨道的选择上。
此外，还有一个关键方面需要整合，即考虑机器容量限制，这在现实世界的农业场景中尤其重要，因为机器会因为各种原因（例如卸载收获的材料）定期返回仓库。这项附加功能将涉及计算多条往返路径，其中一些路径可能无法覆盖每个单元，但受到其总路径长度和需要经过指定仓库位置的限制。整合此功能将进一步增强我们方法的实际适用性，从而实现更精确、更有效的田间路径规划策略。
总的来说，我们的工作为应对 CCPP 挑战奠定了坚实的基础，我们期待未来的发展能够在这些原则的基础上提高农业田间作业的效率和适应性。

作者贡献

概念化、方法论、软件、验证、形式分析、调查、资源、数据管理、MH；写作——原始草稿准备，MH 和 SP；写作——审查和编辑，MH 和 SP；可视化，MH；监督，SP 和 CB；项目管理，CB；资金获取，CB 所有作者均已阅读并同意手稿的出版版本。

资金

该项目由德国政府土地和房地产租赁银行设立的专项基金（拨款编号 909052）资助。

机构审查委员会声明

不适用。

数据可用性声明

本研究中提供的数据可根据要求向相应的作者提供。

利益冲突

作者声明没有利益冲突。

参考

  1. Ntawumenyikizaba, A.；Viet, HH；Chung, T. 基于牛耕式行走运动和 A* 搜索的清洁机器人在线完全覆盖算法。第 8 届信息科学与数字内容技术国际会议 (ICIDT) 论文集，韩国济州岛，2012 年 6 月 26-28 日；第 2 卷，第 401-405 页。[ Google 学术搜索]]
  2. Höffmann, M.；Clemens, J.；Stronzek-Pfeifer, D.；Simonelli, R.；Serov, A.；Schettino, S.；Runge, M.；Schill, K.；Büskens, C. 自动割草机的覆盖路径规划和精确定位。在第六届 IEEE 国际机器人计算会议 (IRC) 论文集上，意大利那不勒斯，2022 年 12 月 5 日至 7 日；第 238-242 页。[ Google 学术搜索] [ CrossRef ]
  3. Galceran，E.；Campos，R.；Palomeras，N.；Ribas，D.；Carreras，M.；Ridao，P. 使用自主水下航行器检查三维水下结构的覆盖路径规划与实时重新规划和表面重建。J . Field Robot。2015 年，32，952-983。[ Google 学术搜索] [ CrossRef ]
  4. Basilico, N.；Carpin, S. 在合作的两级监视任务中部署异构无人机团队。在 IEEE/RSJ 国际智能机器人与系统会议 (IROS) 论文集上，德国汉堡，2015 年 9 月 28 日至 10 月 2 日；第 610-615 页。[ Google 学术搜索] [ CrossRef ]
  5. Kalburgi，S.；G Nair，V.；Guruprasad，K.覆盖路径规划算法在铣削操作中的应用；Springer：新加坡，2020 年；第 213-220 页。[ Google 学术搜索] [ CrossRef ]
  6. 叶晓燕；罗琳；侯琳；段燕；吴燕。基于改进蚁群算法的激光烧蚀机械手覆盖路径规划方法。应用科学。2020，10，8641。 [ Google Scholar ] [ CrossRef ]
  7. Rodrigo, DV；Sierra- García , JE；Santos, M. Glasius 基于生物启发神经网络的 UV-C 消毒路径规划通过预防死锁处理算法得到改进。Adv . Eng. Softw. 2023，175，103330。 [ Google Scholar ] [ CrossRef ] [ PubMed ]
  8. Kiemel, J.；Yang, P.；Meißner, P.；Kröger, T. PaintRL：使用强化学习进行工业喷漆的覆盖路径规划。在德国弗莱堡举行的“缩小机器人操作 Sim2real 传输中的现实差距”RSS 研讨会论文集上，2019 年 6 月 23 日。[ Google 学术]
  9. Sabelhaus, D.；Röben , F.；zu Helligen, LM； Lammers , PS 使用连续曲率路径生成可行的岬角转弯机动。Biosyst . Eng. 2013，116，399–409。[ Google 学术搜索] [ CrossRef ]

  10. 巴克曼，J.；皮莱宁，P.； Oksanen, T. 岬角农用车辆的平滑转弯路径生成。百奥系统。工程师。 2015, 139, 76–86。 [谷歌学术][交叉引用]
  11. Höffmann，M.；Patel，S.；Büskens，C. 重量优化的 NURBS 曲线：非完整场机器人的地头路径。第 8 届国际自动化、机器人和应用会议 (ICARA) 论文集，捷克共和国布拉格，2022 年 2 月 18-20 日；第 81-85 页。[ Google 学术搜索] [ CrossRef ]
  12. Hamza, M.；Anderson, W. 种植系统中的土壤压实：性质、原因和可能的解决方案的回顾。土壤耕作研究。2005 年，82，121-145。[ Google 学术搜索] [ CrossRef ]
  13. Nam, SH; Shin, IS; Kim, JJ; Lee, SG 使用流网络的多机器人完全覆盖路径规划。2008 年控制、自动化和系统国际会议论文集，韩国首尔，2008 年 10 月 14-17 日；第 2117-2120 页。[ Google 学术搜索] [ CrossRef ] ]
  14. Janchiv, A.；Batsaikhan, D.；Kim, Gh；Lee, SG 基于多机器人的完全覆盖路径规划。在 2011 年第 11 届控制、自动化和系统国际会议论文集上，韩国京畿道，2011 年 10 月 26-29 日；第 824-827 页。[ Google 学术搜索]
  15. Höffmann，M.；Patel，S.；Büskens，C. 精准农业的最佳引导轨迹生成：覆盖路径规划技术回顾。J . Field Robot。2023 年。 已提交。[ Google 学术搜索] [ CrossRef ] ]
  16. Utamima, A.； Reiners , T.；Ansaripoor, AH 用于多领域农业路线规划的进化邻域发现算法。Ann . Oper. Res. 2022，316，955–977。[ Google Scholar ] [ CrossRef ] ]
  17. Vasquez-Gomez, JI；Herrera-Lozada, JC；Olguin-Carbajal, M。用于测量不相交区域的覆盖路径规划。在 2018 年国际无人机系统会议 (ICUAS) 论文集上，美国德克萨斯州达拉斯，2018 年 6 月 12 日至 15 日；第 899-904 页。[ Google 学术搜索] [ CrossRef ] ]
  18. Pham, TH；Bestaoui, Y.；Mammar, S. 精准农业中带凹面障碍物的空中机器人覆盖路径规划方法。在 2017 年无人机系统研究、教育和发展研讨会 (RED-UAS) 论文集上，瑞典林雪平，2017 年 10 月 3-5 日；第 43-48 页。[ Google 学术搜索] [ CrossRef ] ]
  19. Khanam，Z.；Saha，S.；Ehsan ， S.；Stolkin，R.；Mcdonald-Maier，K. 具有优先权的不相交区域检查覆盖路径规划技术。IEEE Access 2021，9，5412–5427 。 [ Google 学术搜索] [ CrossRef ]
  20. Ravankar, A.; Ravankar, AA; Kobayashi , Y.; Hoshino, Y.; Peng, CC 机器人导航中的路径平滑技术：最新技术、当前和未来的挑战。传感器 2018，18，3170。 [ Google学术搜索] [ CrossRef ]
  21. Fraichard, T.；Scheuer, A. 从 Reeds 和 Shepp 的到连续曲率路径。IEEE机器人学报。2004 年， 20，1025–1035 。[ Google 学术搜索] [ CrossRef ]
  22. Banzhaf, H.；Palmieri, L.；Nienhüser, D.；Schamm, T.；Knoop, S.；Zöllner, JM 混合曲率转向：一种用于在紧密环境中基于采样的非完整运动规划的新型扩展函数。在 2017 年 IEEE 第 20 届智能交通系统国际会议 (ITSC) 论文集上，日本横滨，2017 年 10 月 16-19 日；第 1-8 页。[ Google 学术搜索] [ CrossRef ]
  23. 吴晓玲；白建军；李晓玲；郝峰。基于改进混合 A* 的农用车平滑路径规划方法。2023 年 IEEE 第三届信息技术、大数据和人工智能国际会议 (ICIBA) 论文集，中国重庆，2023 年 5 月 26-28 日；第 3 卷，第 664-668 页。[谷歌学术] [ CrossRef ]
  24. Šelek, A.; Seder, M .; Brezak, M.; Petrović, I. 非完整机器人的平滑完全覆盖轨迹规划算法。传感器 2022，22，9269。 [ Google学术搜索] [ CrossRef ]
  25. Chen, X.; McMains, S. 通过计算绕组数进行多边形偏移，第 2 卷：第 31 届设计自动化会议，A 和 B 部分。在国际设计工程技术会议和计算机与工程信息会议论文集，美国加利福尼亚州长滩，2005 年 9 月 24-28 日。[ Google 学术搜索]
  26. Johnson, A. Clipper2：剪辑和偏移库。2023 年。可在线访问：https ://angusj.com/clipper2/Docs/Overview.htm （2023 年 9 月 1 日访问）。
  27. Choset, H.；Lynch, K.；Hutchinson, S.；Kantor, G.；Burgard, W.；Kavraki, L.；Thrun, S.机器人运动原理：理论、算法与实施；麻省理工学院出版社：美国马萨诸塞州剑桥，2005 年。[ Google 学术搜索]]
  28. Choset，H. 已知空间的覆盖：牛耕式细胞分解。Auton。Robot。2000，9，247-253 。 [ Google 学术] [ CrossRef ]
  29. Huang, WH 基于线扫描的最佳覆盖算法分解。在 IEEE 国际机器人与自动化会议 (ICRA) 论文集上，韩国首尔，2001 年 5 月 21-26 日；第 1 卷，第 27-32 页。[ Google 学术搜索] [ CrossRef ]
  30. Rekleitis, I.；New, AP；Rankin, ES；Choset , H. 高效的牛耕式多机器人覆盖：一种算法方法。Ann . Math. Artif. Intell. 2008，52，109–142。[ Google 学术搜索] [ CrossRef ]
  31. 刘燕；田梅；王晓玲；吕建军。基于超宽带定位的智能割草机路径规划研究。第 7 届机器人智能技术与应用国际会议论文集，韩国大田，2019 年 11 月 1 日至 3 日；第 248-253 页。[ Google 学术搜索] [ CrossRef ]
  32. 佩雷斯·冈萨雷斯，A.；贝尼特斯-蒙托亚，N.；哈拉米洛-杜克，A.； Cano-Quintero，JB 光伏电站中无人机的语义分割覆盖路径规划。应用。科学。 2021 , 11 , 12093. [谷歌学术] [交叉引用]
  33. Fang, C.；Anstee, S. 使用自主水下航行器进行港口海床勘测的覆盖路径规划。《海洋学报》，IEEE Sydney，澳大利亚新南威尔士州悉尼，2010 年 5 月 24-27 日；第 1-8 页。[ Google 学术搜索] [ CrossRef ]
  34. Mannadiar, R.；Rekleitis, I. 已知任意环境的最佳覆盖范围。在 IEEE 国际机器人与自动化会议 (ICRA) 论文集上，美国阿拉斯加州安克雷奇，2010 年 5 月 3-7 日；第 5525-5530 页。[ Google 学术搜索] [ CrossRef ]
  35. Cabreira, TM；Brisolara, LB；Paulo, RF 无人机覆盖路径规划调查。无人机 2019，3，4。[ Google 学术搜索] [ CrossRef ]
  36. Bochtis, DD；Vougioukas, SG 最小化在田头田模式下运行的机器的非工作距离。生物系统工程。2008 年，101，1-12。[ Google 学术搜索] [ CrossRef ]
  37. Hameed, I.A.; Bochtis, D.D.; Sorensen, C.G. Driving Angle and Track Sequence Optimization for Operational Path Planning Using Genetic Algorithms. Appl. Eng. Agric. 2011, 27, 1077–1086. [Google Scholar] [CrossRef]
  38. Yu, X.; Roppel, T.A.; Hung, J.Y. An Optimization Approach for Planning Robotic Field Coverage. In Proceedings of the IECON 2015—41st Annual Conference of the IEEE Industrial Electronics Society, Yokohama, Japan, 9–12 November 2015; Institute of Electrical and Electronics Engineers Inc.: Piscataway, NJ, USA, 2015; pp. 4032–4039. [Google Scholar] [CrossRef]
  39. Dubins, L.E. On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents. Am. J. Math. 1957, 79, 497–516. [Google Scholar] [CrossRef]
  40. Büskens, C.; Knauer, M. From WORHP to TransWORHP. In Proceedings of the 5th International Conference on Astrodynamics Tools and Techniques, Noordwijk, The Netherlands, 29 May–1 June 2012. [Google Scholar]
  41. Büskens, C.; Wassel, D. The ESA NLP Solver WORHP. In Modeling and Optimization in Space Engineering; Springer: Berlin/Heidelberg, Germany, 2013; pp. 85–110. [Google Scholar]
  42. Jin, J.; Tang, L.; Uk, A. Optimal Coverage Path Planning for Arable Farming on 2D Surfaces. Transact. ASABE 2010, 53, 283–295. [Google Scholar] [CrossRef]
  43. Piegl, L.; Tiller, W. The NURBS Book; Springer: Berlin/Heidelberg, Germany, 1997. [Google Scholar]
  44. Lowther, J.; Shene, C.K. If you know B-splines well, you also know NURBS! ACM SIGCSE Bull. 2004, 36, 343–347. [Google Scholar]
  45. Geem, Z.W.; Kim, J.H.; Loganathan, G. A New Heuristic Optimization Algorithm: Harmony Search. Simulation 2001, 76, 60–68. [Google Scholar] [CrossRef]
  46. Dorigo, M.; Gambardella, L.M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1997, 1, 53–66. [Google Scholar] [CrossRef]
  47. Zhang, X.; Jiang, K.; Wang, H.; Li, W.; Sun, B. An Improved Bean Optimization Algorithm for Solving TSP. In Proceedings of the Advances in Swarm Intelligence: Third International Conference, ICSI 2012, Shenzhen, China, 17–20 June 2012; Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Springer: Berlin/Heildeberg, Germany, 2012; Volume 7331 LNCS, pp. 261–267. [Google Scholar]
  48. Guo, P.; Hou, M.; Ye, L. MEATSP: A Membrane Evolutionary Algorithm for Solving TSP. IEEE Access 2020, 8, 199081–199096. [Google Scholar] [CrossRef]
  49. Zhang, H.; Gao, Y. Solving TSP based on an Improved Ant Colony Optimization Algorithm. In Journal of Physics: Conference Series; IOP Publishing: Bristol, UK, 2021; Volume 1982. [Google Scholar]
  50. Pop, C. Chapter 3. The Generalized Traveling Salesman Problem (GTSP). In Generalized Network Design Problems; De Gruyter: Berlin, Germany; Boston, MA, USA, 2012; pp. 60–99. [Google Scholar]
  51. Silberholz, J.; Golden, B. The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach. In Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies; Baker, E.K., Joseph, A., Mehrotra, A., Trick, M.A., Eds.; Springer: Boston, MA, USA, 2007; pp. 165–181. [Google Scholar]
  52. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. 2023. Available online: https://www.gurobi.com/documentation/current/refman/index.html (accessed on 1 September 2023).
  53. Bestuzheva, K.; Besançon, M.; Chen, W.K.; Chmiela, A.; Donkiewicz, T.; van Doornmalen, J.; Eifler, L.; Gaul, O.; Gamrath, G.; Gleixner, A.; et al. The SCIP Optimization Suite 8.0. arXiv 2021, arXiv:2112.08872. [Google Scholar]
  54. NEXAT GmbH. Available online: https://www.nexat.de/ (accessed on 29 August 2023).
Figure 1. Exemplary visualization of the four key steps of the CCPP workflow. (a) ROI decomposition with headland area (yellow) and interior field (green) split up into cells. (b) Generation of the headland (orange) and interior (green) guidance tracks. (c) Route planning: computing the cell traversing order (numbers) and entry (red) and exit (green) tracks. (d) Planning a smooth interior path (red).
Agriculture 13 02112 g001
Figure 2. CCPP workflow established in this work, comprising the four key components: ROI decomposition (purple), guidance track generation (blue), route planning (red), and smooth path planning (green), together with the input parameters (grey) and output paths (orange). The focus in this work deals with the right arc of this flow, resulting in interior coverage paths, whereas the left part handles the headland paths, as in [11].
Agriculture 13 02112 g002
Figure 3. Sweepline-based decomposition: Sweepline (red) sweeps (here from left to right) over the region with one obstacle (gray), detects events (green), and decomposes the region with lines (red) parallel to the sweepline, reprinted with permission from [15] (2023, Höffmann, M.). (a) Initial region. (b) Decomposition into 4 cells. (c) Examplary decomposition of more complex region into 10 cells.
Agriculture 13 02112 g003
Figure 4. Different sweepline-based decomposition techniques with the considered events (green), assuming a vertical sweepline, reprinted with permission from [15] (2023, Höffmann, M.) (a) Trapezoidal [27]. (b) Boustrophedon [28].
Agriculture 13 02112 g004
Figure 5. Distinction between the intra-region (red) and inter-region (blue) paths. The intra-region paths cover each cell, whereas the inter-region paths connect the different intra-region paths, using the headland guidance tracks (orange).
Agriculture 13 02112 g005
Figure 6. Visualization of the key components in the Dubins model (1): The position (x,y), the orientation θ, the curvature κ (as the inverse of the resulting turning radius), and the velocity v, as well as the steering angle φ and the wheelbase b.
Agriculture 13 02112 g006
Figure 7. Exemplary start pose (x1, y1, q1) and end pose (x1, y1, q1) of two interior guidance tracks (blue) and a sketched turning maneuver (red).
Agriculture 13 02112 g007
Figure 8. Selection of the most common agricultural turn types, traversing in the headland area from one interior guidance track to the other, reprinted with permission from [15] (2023, Höffmann, M.). (a) U. (b) Flat U. (c) Ω. (d) Hook.
Agriculture 13 02112 g008
Figure 9. Visualization of the computation of a piecewise linear inter-region path (combination of red dotted and solid line). The tracks corresponding to the start and end points (purple) are expanded (black dashed line), and the intersections (red dots) with the headland tracks (orange) are calculated. Afterwards, (1) the path is refined along the headland tracks, (2) the path is aligned along the interior tracks (green), and (3) the two sub-paths are connected using their shared headland track (red dotted line).
Agriculture 13 02112 g009
Figure 10. Four different ways to cover a cell due to different start (green) and end (red) positions. (a) Odd number of tracks. (b) Even number of tracks.
Agriculture 13 02112 g010
Figure 11. Phaseplot and curvature profile of regular Dubins (blue) and CC Dubins (orange) turns for the two most common turning maneuvers. (a) Flat U-turn. (b) Ω-turn.
Agriculture 13 02112 g011
Figure 12. Flat U-turn for different turning radii rmin<w2 with κmax=rmin−1 and σmax=20. (a) Phaseplot. (b) Curvature profile.
Agriculture 13 02112 g012
Figure 13. Ω-turn for different turning radii rmin>w2 with κmax=rmin−1 and σmax=10. (a) Phaseplot. (b) Curvature profile.
Agriculture 13 02112 g013
Figure 14. Exemplary visualization for inter-region paths with different turning radii rmin based on the piecewise linear path (black). (a) Phaseplot. (b) Curvature profile along the (normalized) path.
Agriculture 13 02112 g014
Figure 15. Field 1. Given field boundaries (black), boustrophedon decomposition (gray), and resulting guidance track system containing headland tracks (green) and interior tracks (blue). Optimal cell-traversing sequence (numbers) together with the entry (red) and exit (green) points for each cell. Resulting smooth coverage path (red).
Agriculture 13 02112 g015
Figure 16. Field 2. Given field boundaries (black), boustrophedon decomposition (gray), and resulting guidance track system containing headland tracks (green) and interior tracks (blue). Optimal cell-traversing sequence (numbers) together with the entry (red) and exit (green) points for each cell. Resulting smooth coverage path (red).
Agriculture 13 02112 g016
Figure 17. Field 3. Given field boundaries (black), boustrophedon decomposition (gray), and resulting guidance track system containing headland tracks (green) and interior tracks (blue). Optimal cell-traversing sequence (numbers) together with the entry (red) and exit (green) points for each cell. Resulting smooth coverage path (red).
Agriculture 13 02112 g017
Figure 18. Field 4. Given field boundaries (black), boustrophedon decomposition (gray), and resulting guidance track system containing headland tracks (green) and interior tracks (blue). Optimal cell-traversing sequence (numbers) together with the entry (red) and exit (green) points for each cell. Resulting smooth coverage path (red).
Agriculture 13 02112 g018
Table 1. Field and path specifications of example fields from Figure 15, Figure 16, Figure 17 and Figure 18.
Field# Cells# TracksInner Field Areaw