SHARP：一种基于混合元启发式算法的智能机器人路径规划方法

《Scientific Reports》：SHARP: a hybrid metaheuristic approach for intelligent robotic path planning

　　

机器人路径规划是自主导航的基本需求，机器人须在避开障碍物的同时到达目标点并产生可行、平滑且高效的轨迹。本文提出SHARP——一种基于粒子群优化(Particle Swarm Optimization, PSO)、正弦余弦搜索(Sine Cosine Algorithm, SCA)及轻量级Nelder–Mead单纯形(Nelder–Mead Simplex)局部精化的混合元启发式规划框架。该框架引入两层基于标量化(scalarization)的多准则决策(multi-criteria decision making, MCDM)层用于机器人路径规划：Priority-PSN优先最小化路径长度并对障碍物和边界违例施加惩罚；No-Preference-PSN通过最小化归一化目标空间内到理想点(ideal point)的距离来选取折中解。研究人员进一步采用三次样条插值(cubic-spline interpolation)将优化所得途经点转换为平滑可执行轨迹。该方法在具不同障碍物密度和运动模式的静态及动态二维环境中进行了验证。在六组静态基准环境中，PSN所产生的无碰撞路径持续短于PSO、灰狼优化器(Grey Wolf Optimizer, GWO)及正弦余弦算法(SCA)。额外的消融实验及按函数评价次数(function-evaluation-normalized)归一化实验表明，完整混合策略可提升密集障碍物地图中的平均路径质量，但伴随较高计算成本。在动态重规划实验中，PSN在各对比变体中取得最高成功率，但延迟有所增加。SHARP为静、动态约束下的智能机器人路径规划提供了一个实用且可适配的基于优化的框架。

论文解读：《SHARP: a hybrid metaheuristic approach for intelligent robotic path planning》

本文发表于《Scientific Reports》。机器人路径规划要求自主移动机器人在含障碍物的工作空间中从起始点到达目标点，同时满足最短路程、最高安全性及轨迹平滑性等相互竞争的目标，属于典型的多目标优化(multi-objective optimization, MOO)问题。传统启发式搜索算法（如A*）依赖精确环境建模且对感知噪声敏感；基于强化学习(reinforcement learning, RL)的方法需大量训练且存在sim-to-real差距；而经典群智能(swarm intelligence, SI)元启发式算法如标准粒子群优化(PSO)易早熟收敛且多采用固定加权求和将多目标简化为单目标，权重选择高度依赖经验，在障碍物密集环境中易陷入局部最优或产生不可行路径。为解决上述问题，研究人员提出了SHARP混合元启发式规划框架，在共享PSO+SCA+Nelder–Mead Simplex(PSN)搜索机制上叠加两种标量化多准则决策层——Priority-PSN与No-Preference-PSN，并在静态与动态二维环境中验证其有效性。研究结论表明：PSN混合算法在静态复杂环境中能稳定生成更短的无碰撞路径，在动态重规划中成功率最高，但计算延迟高于单一PSO或PSO+SCA基线，体现了路径质量与实时性之间的权衡。

主要关键技术方法

研究人员设计了一种混合元启发式搜索策略PSN，每轮迭代依次执行：(1)PSO更新粒子速度与位置实现全局探索；(2)正弦余弦算法(SCA)利用三角函数进行扰动以增强探索与开发平衡；(3)轻量级Nelder–Mead单纯形(Nelder–Mead Simplex, NMS)启发的反射(reflection)、扩张(expansion)、收缩(contraction)操作进行局部精细化。在此基础上设置两个标量化多准则决策层——Priority-PSN采用惩罚标量化S_P(x)=J₁(x)+βJ₂(x)，以归一化路径长度J₁=L/‖g?s‖₂为主、障碍物及边界违例J₂为辅并施以惩罚系数β；No-Preference-PSN采用到理想点[1,0]^T的欧氏距离S_NP(x)=‖[J₁(x),J₂(x)]^T?[1,0]^T‖₂选取折中解。优化所得途经点经自然三次样条插值(cubic spline interpolation)生成C²连续平滑轨迹供执行。实验在六组静态2D圆形障碍物场景及含运动障碍物和运动目标的动态场景中开展，对比基线含标准PSO、GWO、SCA；设置固定迭代数与等函数评价次数(NFE, Number of Function Evaluations)两组对照，并进行节点数敏感性分析与消融实验(PSO vs PSO+SCA vs 全PSN)。

研究结果

Experiment 1: robot path planning in static environment

研究人员在六组含3至20个静止圆形障碍物的2D静态地图中对比PSN、PSO、GWO及SCA。结果表明PSN在所有环境中均获得最低路径代价（如环境1为8.59，PSO为13.02；环境2为8.45，PSO为20.22；环境6为9.91，PSO为20.28等），证明混合策略通过SCA防早熟及NMS局部精化可有效逃离局部极小并获得更短无碰路径。

Sensitivity study: the impact of path node count

研究人员变化中间途经点数目N=1~10进行敏感性测试。结果显示N=2或N=3时路径效率最佳，过多节点并不改善解质量反而增加搜索复杂度，据此选定后续实验使用5个内部节点。

Additional computational evaluation, ablation, and NFE-normalized comparison

消融实验显示：在较简单地图(Map-S1)PSO+SCA与PSN均值路径长度及成功率相当，在复杂地图(Map-S2)全PSN获最佳均值路径长13.596及最高成功率66.7%，但运行时间最长。按约9000次NFE归一化后PSN在Map-S2仍获最佳均值路径长13.589，但PSO+SCA在硬地图上成功率略高，说明混合改进了平均路径质量但额外局部搜索在同等评价预算下并非全面占优。阶段耗时分解显示PSO阶段占16.3%、SCA三角探索占34.1%、单纯形局部精化占49.6%。

Experiment 2: robot path planning in dynamic environment

在含8个匀速随机运动障碍物及运动目标之动态场景中做在线重规划测试（种群18，每控制周期30次迭代，5个路径节点，β=80）。PSN取得最高成功率40%及最低碰撞率60%，但平均重规划延迟达88.96 ms，显著高于PSO+SCA(30.16 ms)及PSO(14.79 ms)，明确揭示路径质量提升以计算开销为代价。

讨论与结论翻译

本文提出SHARP——一种融合PSO全局探索、SCA方向性扰动及Nelder–Mead启发局部精化之混合元启发式机器人路径规划框架，并叠加两种标量化多准则规划变体Priority-PSN（侧重路径长度并惩罚违例）与No-Preference-PSN（最小化到理想点之归一化距离）。三次样条插值用于将优化途经点转为平滑可执行轨迹。实验表明SHARP可有效处理静态杂物环境下更短无碰路径规划，动态重规划中具最高成功率与最低碰撞率，但伴随更高延迟。未来工作将聚焦通过自适应精化步数控制、早停策略、并行化及动态惩罚调参以提升实时性，并在非圆障碍物、含传感不确定、非完整约束及三维工作空间中评估，并最终部署于实体机器人平台验证。