基于声学衍射搜索算法的果园运输机器人全局路径规划新方法

《Agriculture》：A Novel Acoustic Diffraction Search Algorithm for Global Path Planning of Orchard Transport Robots

　　

针对果园运输机器人的全局路径规划问题，提出了一种新型启发式搜索算法——声学衍射搜索算法（Acoustic Diffraction Search Algorithm，ADSA）。该算法通过模拟声波遇障碍物时的衍射特性，构建了以声波搜索策略、衍射节点识别规则以及衍射节点处声压衰减估计为核心的搜索方法。研究在不同规模和障碍物密度的随机栅格地图上开展了路径规划仿真实验，并将ADSA与A算法、Dijkstra算法及跳点搜索（Jump Point Search，JPS）算法进行了对比。仿真结果表明，在测试场景中，ADSA在生成相对较短规划路径的同时保持了相对较高的搜索效率。仅在障碍物密度为30%的大规模地图上，ADSA生成的路径比Dijkstra算法长0.24%，但其寻路时间仅为Dijkstra算法的0.18%。在两个试验场地的地图上开展的路径规划实验表明，ADSA通常能生成路径长度更短、累计转角更小的路径。具体而言，与Dijkstra算法相比，ADSA将平均路径长度缩短了3.95%；与A算法和JPS算法相比，平均路径长度缩短了6.30%。研究结果表明，ADSA在路径长度、累计转角和搜索效率方面均取得了良好的综合性能，为已知环境中果园运输机器人的全局路径规划提供了一种新的搜索途径。

论文解读

一、研究背景与问题提出

随着全球农业生产对作业效率和自动化水平要求的不断提高，以及劳动力成本上升和农业劳动力短缺问题日益突出，农业生产正逐步向机械化、智能化和无人化方向发展。农业机器人作为智慧农业的关键组成部分，在植保喷施、运输、环境巡检、除草、修剪和采摘等农业作业中具有广阔的应用前景。其中，果园运输机器人主要负责运输果实、农资等物料，能够有效降低果园运输作业中的人力需求。自主导航是果园运输机器人持续稳定运行的基础，而路径规划作为自主导航系统的核心技术之一，直接影响机器人在果园环境中的导航安全性、运输效率和运动稳定性。

路径规划旨在给定地图上找到从起点到目标点的安全无碰撞路径。根据环境信息的可用性，路径规划可分为基于完整先验信息的全局路径规划和基于传感器数据的局部路径规划。与道路和室内等通行边界相对清晰的结构化环境相比，果园通常具有一定的行距和株距，果树位置呈现一定规律性。然而，受树木生长、树冠扩展、树盘范围、灌木、农业设施等自然或人为障碍的影响，不同区域的实际障碍边界和可通行空间仍存在一定差异，导致部分区域通行条件较为复杂。因此，如何在完整环境地图中为果园运输机器人规划出安全、高效且较短的路径，是实现自主导航和高效运输作业的关键问题。

目前常用的全局路径规划算法包括Dijkstra算法、A算法、蚁群优化（Ant Colony Optimization，ACO）算法、跳点搜索（Jump Point Search，JPS）算法、快速扩展随机树（Rapidly-exploring Random Tree，RRT）算法和遗传算法（Genetic Algorithm，GA）等。这些算法各有优劣：Dijkstra算法逻辑简单且能保证找到可行路径，但需探索大量冗余节点，计算成本高；ACO算法全局搜索能力强但收敛速度慢；A算法因引入启发函数而具有较高搜索效率，但仍存在冗余节点多、路径安全性不足等问题。现有改进方法大多仍遵循既有算法的核心逻辑，主要优化节点扩展策略、修改启发函数或对规划路径进行后处理，核心框架未发生根本性变化，在路径长度和转弯特性方面仍有进一步改进空间。

二、研究内容与主要结论

针对上述问题，研究人员受声波衍射现象的启发，提出了一种新型启发式搜索算法——声学衍射搜索算法（Acoustic Diffraction Search Algorithm，ADSA）。该算法将声波传播的直线传播、绕障碍物衍射和传播过程中能量衰减等特性引入路径搜索过程，通过构建声波搜索策略、衍射节点识别规则和衍射节点声压衰减估计三个核心组件，实现了在已知环境地图中从起点到目标节点的路径搜索。研究通过随机栅格地图仿真和基于试验场地地图的路径规划实验验证了ADSA的性能，并与Dijkstra算法、A*算法和JPS算法进行了系统对比。研究结果表明，ADSA在大多数测试场景中能够生成较短的路径，同时保持较高的搜索效率，并通常产生较小的累计转角和更平滑的路径，为果园运输机器人的全局路径规划提供了一种新的搜索方法。

三、关键技术方法

研究人员采用了以下主要技术方法开展研究。其一，基于声波传播特性的搜索策略：将当前节点视为声源，以当前节点与目标节点的连线为基准线，通过坐标旋转公式生成多个发散搜索方向，并借鉴快速体素遍历算法实现沿搜索方向的栅格遍历，同时构建映射矩阵记录节点搜索状态以避免重复搜索。其二，衍射节点识别规则：包含衍射发生规则和衍射位置确定规则两部分，前者用于判断声波传播路径上是否在障碍物边缘发生衍射，后者基于惠更斯-菲涅耳原理确定障碍物边缘上衍射点的位置。其三，衍射节点声压衰减估计：基于菲涅耳数（Fresnel number）和Maekawa经验方法，利用Kurze和Anderson推导的公式计算衍射节点的声压衰减值，以最小声压衰减作为关键衍射节点的选择准则。此外，研究人员通过参数实验确定了搜索角增量（search angular increment）和搜索角范围（search angular range）在不同障碍物密度下的推荐取值。仿真实验在MATLAB R2020a平台上进行，硬件配置为Intel Core i5-9300H CPU、24 GB内存和NVIDIA GeForce GTX 1650显卡。实地试验中，研究人员使用配备Jetson Nano和STM32F407VET6的移动机器人平台，搭载2D激光雷达和深度相机，通过ROS系统利用Gmapping算法生成环境地图，并选取武汉市洪山区两个具有果园相似环境特征的室外场地作为试验场地。

四、研究结果

4.1 仿真实验与分析

研究人员在随机生成的小规模（25×25）、中规模（50×50）和大规模（100×100）栅格地图上开展了路径规划实验，障碍物密度分别为10%、20%和30%，评估了路径长度、累计转角、空间搜索点数和寻路时间四项指标。

在小规模地图上，ADSA在三种障碍物密度下均生成了最短路径。在10%障碍物密度下，ADSA相比Dijkstra、A和JPS算法分别缩短路径长度0.38%、2.38%和6.11%，累计转角分别降低30.39%、53.59%和44.31%。在20%障碍物密度下，路径长度均缩短3.68%。在30%障碍物密度下，路径长度分别缩短2.71%、5.79%和5.79%。ADSA的空间搜索点数和寻路时间与A和JPS算法处于同一数量级，但显著低于Dijkstra算法。

在中规模地图上，ADSA在三种障碍物密度下均生成了最短路径。在10%障碍物密度下，路径长度分别比Dijkstra、A*和JPS算法缩短2.17%、3.89%和3.89%，累计转角分别降低78.37%、83.78%和83.78%。在20%障碍物密度下，路径长度分别缩短0.33%、2.90%和10.43%。在30%障碍物密度下，路径长度分别缩短2.47%、15.68%和8.25%，累计转角分别降低31.08%、53.44%和40.59%。

在大规模地图上，ADSA在10%和20%障碍物密度下生成了最短路径，在30%障碍物密度下，ADSA生成的路径比Dijkstra算法长0.24%，但比A和JPS算法分别缩短7.05%和5.68%，且累计转角分别比Dijkstra、A和JPS算法降低31.18%、32.65%和37.93%。ADSA的寻路时间仅为Dijkstra算法的0.18%。

4.2 实地试验与分析

研究人员选取了两个具有果园相似环境特征的室外场地进行实地路径规划测试。试验场地1的障碍物密度为14.35%，环境特征类似于果园边缘区域；试验场地2的障碍物密度为12.73%，障碍物分布更为复杂，类似于障碍物较密集的果园区域。

在试验场地1的两个场景中，ADSA生成的路径长度分别为27.13 m和26.86 m，相比Dijkstra算法缩短3.35%和2.89%，相比A和JPS算法均缩短7.22%和5.72%。累计转角分别为81.87°和74.05%，相比Dijkstra算法降低69.68%和67.09%，相比A和JPS算法降低39.36%和67.09%。寻路时间分别为84.56 ms和77.38 ms，相比Dijkstra算法降低65.82%和68.56%。

在试验场地2的两个场景中，ADSA生成的路径长度分别为34.72 m和19.43 m，相比Dijkstra算法缩短5.21%和4.33%，相比A和JPS算法缩短5.21%和7.03%。在场景1中，累计转角比Dijkstra算法高0.81%，但比A和JPS算法低56.79%；在场景2中，累计转角分别比Dijkstra、A*和JPS算法低27.23%、37.63%和37.63%。寻路时间分别为98.74 ms和112.38 ms，相比Dijkstra算法降低96.92%和90.02%。

五、讨论与结论

讨论部分指出，ADSA并非对A*、JPS或Dijkstra等经典算法的进一步改进，而是一种模拟声波直线传播、绕障碍物衍射和传播能量衰减特性的新型全局路径规划算法。在某些场景中，ADSA的累计转角略大于部分其他算法，这可能归因于算法在路径评价中以路径长度为优先考虑。研究目前仍处于探索阶段，存在以下局限性：其一，ADSA目前主要适用于环境信息完全已知的静态环境，未来将优化搜索逻辑以增强动态环境中的路径规划能力；其二，目前研究主要在MATLAB平台上进行，未来将考虑果园运输机器人的运动学特性，在机器人平台上开展应用研究，并计划由外部计算机执行路径规划计算，将关键节点传输至机器人平台以降低其计算负担；其三，受实际条件限制，研究采用了环境特征与果园相似的试验场地进行实地验证，相关工作将在未来进一步完善。

研究结论可概括为以下三点：第一，提出了声学衍射搜索算法，该算法由声波搜索策略、衍射节点识别规则和衍射节点声压衰减估计三个核心组件构成，分别模拟了声波沿任意方向直线传播、绕障碍物衍射和传播过程中能量衰减的特性，为算法提供了全局搜索能力、绕障能力和关键节点选择依据。第二，仿真结果表明，ADSA能够在不同规模和障碍物密度的地图上有效生成从起点到目标点的无碰撞路径，在大多数测试场景中生成比Dijkstra、A和JPS算法更短的路径，同时保持较高的搜索效率，并通常产生较小的累计转角和更平滑的路径。第三，实地试验结果表明，ADSA在实地环境中取得了良好的路径规划性能，路径长度和累计转角总体较低，寻路时间与A和JPS算法处于同一数量级且显著低于Dijkstra算法，表明其生成的路径具有良好的平滑性。