《Computers and Electronics in Agriculture》：Shell-based workspace decomposition for rapid multi-goal path planning in up-close fruit tree inspection
编辑推荐：
为解决配备机械臂的四旋翼无人机在复杂树冠环境中进行多目标（如水果）巡检时的路径规划难题，研究人员开展了基于凸壳工作空间分解的快速多目标航迹规划研究。通过将树冠的凸壳作为“壳空间”分解工作区域，该方法能够同时优化目标访问顺序并规划无碰撞、长度高效的路径。仿真结果表明，与基于PRM*的单体规划器相比，所提方法在相同计算量下规划的路径更短（在某些情况下缩短达30%），并能访问更多目标。这项研究为果园环境中的空中操控任务提供了有价值的算法基础。
在精准农业蓬勃发展的今天，人们对于高效、可持续的农业生产方式需求日益增长。然而，传统农业正面临着劳动力成本上升、人力短缺以及化学植保处理带来的环境和健康风险等多重挑战。在这些背景下，农业机器人技术，尤其是无人机（Unmanned Aerial Vehicles， UAVs）技术，被视为一个极具前景的解决方案。无人机已广泛应用于作物监测、表型分析、空中喷洒乃至直接采收等领域。一个特别引人关注的应用方向是，让配备机械臂的无人机能够飞入茂密的果树冠层，对多个目标点（如水果）进行近距离检查或操作。这听起来像是科幻小说的场景，但却真实地面临着两大核心算法难题：首先，如何在由树枝构成的复杂、杂乱的三维空间中，为这样一个高自由度（本研究中的机器人有7个自由度）系统规划出一条无碰撞的运动路径；其次，如何优化访问多个分散目标的顺序，以最小化总飞行时间，这本质上是一个带有邻域的旅行商问题（Traveling Salesperson Problem with Neighborhoods， TSPN）的机器人版本。这两大难题交织在一起，使得在果园环境中为无人机规划高效、精确的作业路径成为一个极具挑战性的任务。
为了应对这一挑战，来自荷兰乌得勒支大学罗斯福学院工程系的研究人员Werner Kroneman、Jo?o Valente和A. Frank van der Stappen提出了一种新颖的工作空间分解策略。他们的研究成果以《Shell-based workspace decomposition for rapid multi-goal path planning in up-close fruit tree inspection》为题，发表在农业信息学领域的知名期刊《Computers and Electronics in Agriculture》上。该研究的核心思想是利用果树冠层凸壳（Convex Hull）这一几何工具，对杂乱的工作空间进行智能分解，从而将复杂的全局路径规划问题，简化为局部的“进近路径”规划和围绕树冠的“壳路径”规划，最终实现了快速、高效的多目标运动规划。
为开展这项研究，作者们主要采用了以下几个关键技术方法：首先，他们构建了一个仿真的三维工作空间，包含单个果树模型和一个配备三关节旋转机械臂的四旋翼无人机模型。树模型来源于商业3D模型库，并进行了网格分割（木材、树叶、水果）和简化处理。其次，他们利用快速凸壳（QuickHull）算法计算树冠叶顶点云的凸壳，并通过与一个小球体的闵可夫斯基和（Minkowski sum）进行“平滑”处理，得到了一个具有连续法向的“壳表面”（Shell Surface S）。然后，基于此壳表面，他们定义了一个“壳构型空间”（Shell Configuration Space Cshell），这是一个连续的子空间，其中的每个构型都对应于机器人在壳表面上的一个特定位姿（机械臂伸直，基座朝向与壳表面法向水平投影一致）。最后，他们开发了完整的规划流程，包括利用壳表面测地线快速计算壳路径、使用基于PRM（Probabilistically Roadmap Method）的规划器为每个水果目标规划从壳空间到目标构型的短进近路径，并利用凸壳快速估算路径长度以求解优化的访问序列（TSP问题）。
2.1. 环境模型
研究在一个仿真的三维环境中进行，该环境始终包含一棵果树和一个配备机械臂的四旋翼无人机。机器人模型拥有7个自由度，包括基座平移、基座绕垂直轴旋转以及三个机械臂关节角度。树模型来自“3D Fruit Trees 3D Models Collection”，共使用了17个包含水果且水果数不超过600的模型，以测试算法的鲁棒性。目标点是每个水果网格包围盒的中心点。环境在MoveIt运动规划框架中建模为PlanningScene，并使用了基于Bullet物理引擎的CollisionEnvBullet进行连续碰撞检测。
2.2. 问题形式化
研究对机器人构型空间、自由构型空间、路径、目标区域等概念进行了严格的形式化定义。核心问题是：给定一组目标区域G和一个初始构型c0，找到一条从c0出发、访问所有可达目标区域Gi∈ G的短的无碰撞路径Π。
2.3. 基于壳的规划
这是本研究的主要贡献部分。研究人员首先构建了围绕树冠的凸壳壳表面S，将工作空间分解为“杂乱”的内部体积和“非杂乱”的外部体积。然后，通过函数Cshell: S → C 将壳表面上的每个点映射到一个特定的机器人构型，从而定义了壳构型空间Cshell。在这个子空间中，规划光滑、紧贴树冠的“壳路径”在计算上非常廉价。为了到达树冠内部的水果，机器人需要从壳空间规划一条相对较短的“进近路径”深入树冠。这种方法通过利用壳空间作为高效的“高速公路”网络，将复杂的全局规划问题分解为简单的局部进近规划和快速的壳上移动规划。
2.3.1. 工作空间壳S
通过计算树冠（叶顶点）的凸壳，并将其与一个小球体进行闵可夫斯基和，得到一个表面法向处处连续且明确定义的平滑凸表面S，作为分解边界。
2.3.2. 壳构型空间Cshell
对于壳表面S上的任意点p，Cshell(p)被唯一地定义为：机械臂三个关节角均为0（手臂伸直），基座旋转r使得无人机保持直立，且从基座平移向量t到末端执行器位置e(c)的射线与点p处S的法向量的水平投影平行（朝内）。这样就在C中嵌入了一个连续的二维子流形。
2.3.3. 壳路径
连接壳表面上两点的最短路径是沿该表面的测地线。通过在Cshell中映射这条测地线，可以直接得到一条在构型空间中、机器人紧贴树冠表面移动的无碰撞路径，其长度可以快速估算。
2.3.4. 进近路径
为了从壳空间到达树冠内部的目标（水果），需要规划一条从壳构型空间中的某个起点到目标区域（末端执行器靠近水果点的构型集合）的短路径。研究中采用基于PRM*的规划器，在有限的时间预算τp内为每个目标规划一条进近路径。
2.3.5. 壳上的旅行商问题
由于壳路径的长度可以快速计算（通过壳表面测地线长度近似），因此可以在所有目标对应的壳表面最近点之间建立一个距离矩阵。对这个矩阵求解旅行商问题，就能得到一个优化的、环绕树冠访问各个水果入口点的序列。
2.3.6. 完整的规划算法
算法整合了以上所有组件：首先构建壳表面S和壳构型空间Cshell；然后为每个水果目标规划进近路径，并记录其在壳上的接入点；接着，基于壳接入点间的测地线距离求解TSP，得到访问序列；最后，将进近路径与壳路径串联起来，形成完整的从起点访问所有目标的运动轨迹。
2.4. 基线算法：TSP-over-PRM*
作为对比基线，研究实现了一个更为“单体化”的算法。该算法首先在整个自由构型空间Cfree中使用PRM*算法在时间预算τPRM内构建一个路线图R；同时，为每个目标区域采样一组构型作为目标样本集H。然后，在路线图R上，为目标样本集H中的代表点计算两两之间的最短路径距离，形成距离矩阵，并求解TSP得到访问序列。最后，在路线图R上查询并连接这些路径，形成完整轨迹。
3. 结果
研究人员在17棵不同的果树模型上进行了仿真实验，将提出的凸壳方法与基线方法TSP-over-PRM*以及前期基于最小包围球的方法进行了比较。性能评估指标包括成功访问的目标数量、规划路径的总长度以及算法的运行时间。
实验结果表明，在相同的计算时间预算下，新的凸壳方法在大多数测试案例中都匹配或超越了基线方法的性能。具体而言，凸壳方法能够成功访问更多（或至少一样多）的水果目标。在路径长度方面，凸壳方法规划的路径通常更短，在一些情况下，其路径长度比基线方法缩短了高达30%。这说明利用凸壳进行工作空间分解的策略是有效的，它通过利用环境的结构特征（树冠密集、周围空间相对开阔），显著简化了规划问题的复杂度。与基于最小包围球的方法相比，凸壳方法因其更紧密的几何贴合而避免了不必要的绕行，尤其是在树冠形状非球形或较宽时，表现更为优越。
4. 讨论
论文讨论了凸壳方法的相对优势和局限性。优势在于：方法自动化程度高，能快速提供接近最优的路径估计，生成的壳路径自然光滑且紧贴树冠，计算效率高。局限性包括：对树冠凸性的假设在极端形状下可能不成立；壳路径虽然无碰撞，但未考虑动态约束（如无人机加速度限制）；当前研究假设环境完全静态且已知，未处理传感不确定性或动态障碍物。此外，树干的处理是一个特例，但因其是单一的线状障碍物，所以影响可控。
5. 结论
本研究针对配备机械臂的无人机在果园单棵树冠内进行多目标近距作业的路径规划问题，提出了一种基于凸壳工作空间分解的创新方法。该方法的核心贡献包括：（1）利用树冠凸壳自动将工作空间分解为杂乱与非杂乱区域；（2）基于凸壳构造了一个用于快速路径规划的“壳空间”；（3）利用凸壳快速估算路径长度，以确定目标访问顺序。仿真实验证明，与基于PRM*的单体规划方法相比，新方法在相同计算努力下，能规划出更短的路径（最高提升30%）并访问更多目标。尽管研究目前局限于组合问题仿真，但这些见解对于未来探索果园空中操控任务的研究具有重要价值。该方法不仅适用于果园，还可推广到具有类似障碍物分布特性的自然环境（如森林）或工业环境（如密集管道网络），为解决复杂杂乱环境中的多目标机器人运动规划问题提供了新的思路和有效的工具。
