基于质心Voronoi图理论的Hilbert规划算法的多UUV系统任务规划研究

《International Journal of Advanced Robotic Systems》：Research on mission planning for multi-UUV systems using the Hilbert-planning algorithm based on centroidal Voronoi diagram theory

　　

随着海洋资源开发日益受到重视，多UUV系统相比单UUV作业表现出更高的效率。然而，整体运动规划仍然面临环境不确定性和运动学约束的挑战。本文提出了一种统一的、全覆盖搜索与探测规划框架。核心创新在于混合优化区域分配方法(HPSO-CVD)与自适应可变精度覆盖的Hilbert规划算法的协同编排。定量基准测试表明，所提出的改进A*算法相比传统A*算法计算开销减少约52.09%，相比RRT*算法减少69.35%。此外，最小加加速度(Minimum Jerk)平滑的集成确保了所生成路径对于欠驱动UUV动力学具有运动学可行性。

**基于质心Voronoi图理论的Hilbert规划算法的多UUV系统任务规划研究——论文解读**

**一、研究背景与问题提出**

随着海洋资源开发与安全保障日益成为全球关注焦点，无人水下航行器(UUV)凭借低成本、强隐蔽性、操作灵活和高智能化等优势，成为海洋探测、水下目标搜索与环境监测的关键装备。随着单UUV技术日趋成熟，UUV系统正朝着集群化方向发展。相比单UUV，多UUV集群通过协作能够实现更广的覆盖范围、更高的效率和更强的抗干扰鲁棒性，并在个别单元失效时仍能保持任务连续性，是未来智能海洋作业的核心系统。然而，要完成全覆盖搜索与探测任务，需要涵盖任务区域划分、集群间分配、单UUV路径规划、局部避障和轨迹平滑等全流程设计，以构建完整的全覆盖运动规划框架。

现有研究虽在多UUV任务分配与路径规划领域取得了诸多成果，但仍存在三方面研究空白：(1)缺乏综合性集成规划框架，多数研究仅关注单环节优化，未能实现任务分配与路径规划的协同优化；(2)任务分配方法无法同时实现全局路径优化与负载均衡，容易出现严重的任务分配失衡；(3)全覆盖路径规划方法无法实现无冗余的可变精度自适应覆盖。此外，任务分配研究虽改善了通信鲁棒性、异构处理能力或组合搜索性能，但其目标仍然碎片化——集中式聚类和拍卖方法仍依赖协调器级状态交换，未联合最小化机群级路径成本与最差航行器工作量；遗传算法和自组织映射方法可容纳多类约束，但通常止步于任务节点分配，未将分配结果与自适应区域覆盖、局部重规划和动力学平滑相连接。路径规划方法方面，预测势场法计算量轻但对参数整定和局部几何构型敏感；A*-势场混合方法改善了可跟踪性，而基于采样的RRT变体虽能处理复杂空间，却存在运行变异性和缺乏确定性覆盖的缺陷。元启发式方法虽提供广泛的全局搜索能力，但收敛质量对种群初始化、参数调度和计算预算敏感，且不能内在保证完整的无冗余覆盖。基于学习的协调方法虽可捕获机器人间交互，但引入训练成本、奖励设计依赖以及泛化不确定性。分形覆盖虽提供确定性空间组织，但以往研究很少将其与负载均衡任务分配和动态可行的局部避障集成。

**二、研究内容与核心方法**

针对上述问题，研究人员提出了一种混合方法用于多UUV路径规划。首先利用初始任务点对目标海域进行粗粒度Voronoi划分；采用混合粒子群-遗传算法(HPSO)解决受约束的多旅行商问题(MTSP)任务分配；随后通过改进的质心Voronoi图(CVD)算法进行精细区域均分；全局覆盖路径由基于分形理论的层次化Hilbert规划(HP)算法生成以提高效率；对于局部避障，采用带路径简化的改进A*算法降低计算量；最后通过最小加加速度(Minimum Jerk)算法结合安全验证机制生成运动学平滑轨迹。

研究采用的关键技术方法包括：(1)混合粒子群优化(HPSO)算法求解受约束MTSP，融合遗传算法(GA)的全局探索能力与粒子群优化(PSO)的快速收敛特性；(2)层次化Voronoi-CVD区域划分策略，实现从粗粒度任务区域界定到细粒度负载均衡划分的递进；(3)基于分形几何的Hilbert规划算法生成自适应可变精度全覆盖路径；(4)改进A*算法集成对角距离启发函数、平局打破(tie-breaker)机制与路径简化，用于实时避障；(5)最小加加速度五次多项式轨迹平滑，通过边界-中间值问题(BIVP)求解确保轨迹的运动学可行性。仿真验证在ROS/RViz平台进行，地图环境配置为50m×50m工作空间，随机生成30个障碍物，UUV感知范围设定为半径9m的半圆形区域。

**三、研究结果**

**3.1 任务分配与区域划分结果**

通过Voronoi镶嵌(Delaunay三角剖分对偶结构)对任务节点进行粗粒度空间划分，计算复杂度为O(n log n)。在此基础上，HPSO算法以目标函数min J=ω?∑D?+ω?(max|D??D?|)同时优化机群总路径成本和最重/最轻负载UUV之间的路径长度差异，在满足每个任务节点恰好被一个UUV访问一次、单UUV航程不超过最大续航等约束条件下实现均衡任务分配。仿真表明，Voronoi预处理产生的结构化20节点、四UUV分队分配问题使PSO更新能快速利用低成本排列，GA交叉和变异在剩余迭代中持续保持种群多样性。随后采用CVD算法，以UUV实时位置为生成节点，通过迭代计算Voronoi多边形质心并持续调整UUV位置趋近质心，逐步均衡各UUV单元的Voronoi单元面积分布，并将能耗指标纳入优化参数，使高能量储备UUV能够被策略性部署至更远或更广阔的区域。

**3.2 Hilbert规划算法全覆盖路径生成结果**

Hilbert曲线作为一种具有空间填充和自相似特性的分形曲线，能够100%遍历整个二维平面，严格保证UUV全覆盖规划的区域覆盖要求；曲线结构在不同分辨率下保持一致，可实现无冗余路径的可变精度覆盖；与Peano曲线和Z曲线等其他分形曲线相比，Hilbert曲线转弯次数更少、无路径交叉、轨迹端点固定在区域边界，便于多UUV任务完成后的撤离与协作连接。仿真结果证实HP算法满足全覆盖要求，相比传统覆盖策略具有显著优势：在等效覆盖率下，HP算法比“3”字形覆盖模式减少42.7%的冗余路径；在保持与“2”字形方法相当的覆盖密度下实现29.1%的路径长度缩减；虽与螺旋覆盖效率相近，但HP算法确保终点定位在区域边界而非内部，便于任务后的撤离。

**3.3 局部避障与轨迹平滑结果**

改进A*算法的基准测试在50个随机场景中进行，与传统A*和RRT*算法对比：改进A*平均访问节点数18.3个(传统A*为38.2个，RRT*为59.7个)，平均CPU时间0.07ms(传统A*为0.13ms，RRT*为0.15ms)，平均路径长度12.57m(与传统A*相同，但RRT*为15.61m)，累计转弯角度1.29rad(传统A*为3.38rad，RRT*为8.8rad)。定量基准测试显示，改进A*算法计算开销相比传统A*减少约52.09%，相比RRT*减少69.35%。在统计分布方面，改进A*算法展现出显著更高的稳定性，其狭窄的四分位距(IQR)表明在不同障碍物配置下具有稳健性能，而RRT*则表现出高方差和频繁的离群值。最小加加速度插值使急转弯(>45°)数量从传统A*的平均4.3个和RRT*的4.9个降至1.6个，减少了80%，显著改善了物理UUV驱动的运动学可行性。仿真结果证明UUV实现了动态实时避障并具有显著的轨迹平滑效果。安全验证机制在检测到拟合轨迹与障碍物碰撞时，在轨迹中点插入路径点并进行递归细化，直至所有多项式轨迹实现无碰撞构型。

**四、讨论与结论**

关于实际部署的挑战，研究人员指出物理UUV在高度动态和非结构化环境中运行，受不可预测的洋流和涡流等深水动力扰动影响，需要将几何规划层与鲁棒的底层六自由度动态控制器耦合以最小化湍流水域中的轨迹跟踪误差。CVD和HPSO从根本上依赖UUV间的无缝数据交换，而水声通信固有地受高延迟、有限带宽和频繁丢包限制，严重通信退化可能破坏CVD算法连续位置调整所需的实时状态共享。当前仿真将前视声呐理想化为确定性占据区域，而实际声学传感器受热跃层或海洋生物引起的散斑噪声和虚假回波影响，此类感知不确定性可能触发A*算法中的冗余局部重规划周期或产生幻影局部极小值。执行连续优化算法和高频可变精度Hilbert网格生成对物理UUV嵌入式处理器的有限时钟速度和能量约束提出严格计算要求，需进一步轻量化优化。

研究的具体贡献包括：(1)构建了集成的多UUV任务规划框架，实现从任务点到可执行轨迹的端到端协同优化；(2)提出混合PSO-GA算法结合层次化Voronoi-CVD划分，解决了多UUV任务分配中的局部最优和区域划分不平衡问题，显著改善了负载均衡性和收敛速度；(3)提出了自适应可变精度Hilbert-Planning路径规划算法，与改进A*和最小加加速度平滑集成，实现了低冗余、高效率且具有运动动力学可行性的全覆盖导航，大幅降低了路径冗余和计算成本。

值得继续研究的方向包括：(1)增强动态海洋环境下的避障算法；(2)开发补偿算法以应对严重通信延迟并维持集群稳定性；(3)将仿真框架扩展到三维环境以提高真实性；(4)将运动规划与集群控制机制集成以实现综合仿真和物理实验验证；(5)研究集成仿生机器学习和鲁棒故障观测器的容错规划算法，用于UUV执行器和传感器受损场景，以增强系统故障场景下的任务容错能力。

论文发表于《International Journal of Advanced Robotic Systems》，由黑龙江省自然科学基金资助(Grant No. JJ2025YX0012)。