增强型SIRRT*：一种结合混合平滑技术和双向重连结构的结构感知RRT*

《IEEE Aerospace and Electronic Systems Magazine》：Enhanced SIRRT*: Structure-Aware RRT* With Hybrid Smoothing and Bidirectional Rewiring

　　摘要：基于采样的运动规划器，如快速探索随机树（RRT*），被广泛用于最优运动规划，但由于随机初始化，它们通常存在收敛速度慢和运行间方差大的问题。结合了确定性环境结构和基于采样优化的骨架化感知RRT*（SIRRT*），通过提供运行间方差较低的初始解来提高可靠性。然而，由此产生的路径往往在几何上不规则，这限制了后续优化的效率以及最终路径的质量。本文提出了增强型SIRRT*（E-SIRRT*），该框架通过引入两种优化前的改进来克服这一限制：混合路径平滑和双向重连。平滑模块使用样条拟合和碰撞感知校正，在占用网格图上生成几何上更平滑且无碰撞的初始路径。随后，双向重连重新塑造了树及其成本值，以实现更有效的成本传播。这些改进建立在现有的平滑和重连原理之上；其贡献在于它们与SIRRT*的基于自由空间骨架的确定性初始化的集成，保持了 refined 路径和底层树之间的一致性。在三个二维基准环境中，与SIRRT*相比，E-SIRRT*将确定性初始路径成本降低了12.3%-34.5%，同时保持了零方差初始化。在真实世界的激光雷达地图基准测试中，E-SIRRT*在固定时间限制下，最终路径成本分别比批量感知树（BIT*）和高级BIT*（ABIT*）低1.36%和1.68%。真实机器人实验进一步验证了生成路径的可执行性。CCBY - IEEE 并非该材料的版权所有者。请通过 https://creativecommons.org/licenses/by/4.0/ 遵循说明以获取全文文章和API文档中的规定。

第一节 引言
全局路径规划对于工业系统中的自主移动机器人应用至关重要，它使机器人能够在给定地图中找到从起点到目标位置的无碰撞路径。在各种方法中，基于采样的规划器（如快速探索随机树及其最优变体RRT*）因其处理复杂障碍物的有效性而被广泛采用。RRT 通过逐步扩展树来快速构建可行路径[1],[2]，但它缺乏最优性保证。为了解决这个问题，RRT* [3]引入了一个重连过程，以最小化路径成本，从而趋向于最优解。尽管在理论上是渐进最优的，但RRT*在复杂环境或通道狭窄的环境中往往收敛速度较慢。为了缓解这一问题，提出了感知RRT*（IRRT*），一旦找到初始解，就会将采样限制在更有希望的区域[4],[5]。然而，IRRT*仍然依赖于随机采样来获得该初始解，因此在大型走廊式环境中存在几个实际缺陷。首先，初始解通常需要经过广泛的随机探索才能获得，这可能导致初始路径成本高和规划时间长。其次，除非进行足够多的优化迭代，否则生成的路径可能包含明显的之字形段和急转弯，这使得它们对于受运动学和动态约束的物理机器人来说可能不可行或不理想。此外，由于初始解完全是通过随机采样生成的，即使在固定起点和目标配置的情况下，每次运行的初始解决时间和相应的路径成本也可能会有很大差异，从而导致性能方差大。为了缓解这些问题，引入了骨架化感知RRT*（SIRRT*）[6]作为一个鲁棒的混合规划器，它将确定性结构组件与基于采样的优化相结合。SIRRT*从占用网格图中提取自由空间的骨架，计算该骨架上的最小生成树（MST），并使用得到的MST路径作为确定性初始解，然后通过感知RRT*采样阶段进行细化。因为这个初始路径是由网格图和查询决定的，而不是随机采样，所以规划时间和初始路径成本在独立运行中具有很高的可重复性，同时保持了RRT*的渐进最优性。第三节中对SIRRT*进行了更详细的描述。

然而，当在物理机器人上执行计划的路径时，SIRRT*仍然存在重要的限制。初始路径直接来自离散骨架上的MST，经常包含几何上不规则的转弯和短之字形段，特别是在交叉口和狭窄通道附近。这些不规则性可能导致优化起点不佳，延缓向平滑轨迹的收敛，并且生成的路径对于物理机器人的执行效率低下。本文提出了增强型骨架化感知RRT*（E-SIRRT*），它在感知优化阶段之前改进了确定性初始解的质量。E-SIRRT*保留了SIRRT*基于骨架的初始化和低方差特性，同时增加了两种预优化改进：(i) 使用样条拟合和碰撞感知校正的混合路径平滑方法，生成几何上更优的路径；(ii) 双向重连机制，重新调整树结构及其成本值，以促进更有效的成本传播。这些改进旨在促进更快、更稳定的收敛，同时不牺牲原始SIRRT*框架的鲁棒性。图1简化了E-SIRRT*流程，并强调了在感知优化阶段之前应用的两个改进模块。

第二节 相关工作
IRRT* [5]通过将采样限制在由当前最佳解成本和启发式界限定义的椭球形感知集内来提高RRT*的收敛速度。然而，IRRT*中的感知采样只有在获得初始可行解后才会开始，通常是通过均匀随机采样获得的。这种依赖性在通道狭窄的复杂环境中会显著延迟收敛。为了缓解这一问题，提出了感知RRT*（IRRT*），在找到初始解后将采样限制在更有希望的区域[4],[5]。然而，IRRT*仍然依赖于随机采样来获取初始解，因此在大型走廊式环境中存在几个实际缺陷。首先，初始解通常需要经过大量的随机探索才能获得，这可能导致初始路径成本高和规划时间长。其次，除非执行足够多的优化迭代，否则生成的路径可能包含明显的之字形段和急转弯，这可能使其对受运动学和动态约束的物理机器人来说不可行或不可接受。此外，由于初始解是纯随机采样生成的，即使在固定的起点和目标配置下，每次运行的初始解决时间和相应的路径成本也可能有很大差异，从而导致性能方差大。为了缓解这些问题，引入了骨架化感知RRT*（SIRRT*）[6]作为一个鲁棒的混合规划器，它将确定性结构组件与基于采样的优化相结合。SIRRT*从占用网格图中提取自由空间的骨架，计算该骨架上的最小生成树（MST），并使用得到的MST路径作为确定性初始解，然后通过感知RRT*采样阶段进行细化。因为这个初始路径是由网格图和查询决定的，而不是随机采样，所以规划时间和初始路径成本在独立运行中具有很高的可重复性，同时保持了RRT*的渐进最优性。

第三节 原始SIRRT*算法概述
SIRRT* [6]算法利用从二维网格图中提取的确定性结构信息来高效生成初始解。这里简要总结了整个流程。给定一个二值占用网格图，SIRRT*提取自由空间的骨架，并使用Harris角点检测器选择一组代表性的骨架节点（图2(a)）。这些骨架节点与起点和终点位置一起构成了图的顶点集，图的边遵循骨架。图2. SIRRT*算法概述。(a) 二值占用网格图的骨架化；Harris角点标记为黄色。(b) 使用提取的角点、起点（黄点）和终点（红点）位置通过MST构建的初始树（蓝节点和线条）和初始路径（青色线条)。(c) 在椭球形区域内通过感知采样进行优化（绿色椭圆）；最终的优化路径用红色显示。

第四节 提出的方法通过在二维（2-D）网格图环境和真实移动机器人实验中的广泛验证来证明其有效性。E-SIRRT*与IRRT*、SIRRT*以及最近的最优规划器批量感知树（BIT*）[7]和高级BIT*（ABIT*）[8]进行了比较，后者代表了最先进的基于图的分批感知方法。比较重点是初始和最终路径成本、收敛行为、鲁棒性（方差）以及优化所需的迭代次数等计算工作量。本文的主要贡献总结如下：提出了一种针对自由空间骨架上MST派生路径的混合路径平滑方案。该方案将三次样条拟合到离散的MST路径上，并应用碰撞感知校正以保持障碍物 clearance，从而减少之字形伪影和急转弯，同时不牺牲无碰撞可行性。三次样条拟合本身并不被视为新颖的贡献；贡献在于系统地将这种成熟的平滑技术与基于采样的规划器及其树结构结合，使得细化的路径和底层树保持一致。引入了一种基于沿平滑路径的双向重连的初始树细化程序。通过在正向和反向两个方向上传播成本更新，将初始RRT*树与细化的路径主干重新对齐，从而在后续的感知优化阶段实现更低的初始成本和更快的收敛速度。在多个基准环境和真实机器人平台上进行了全面的实证评估，包括与IRRT*、SIRRT*、BIT*和ABIT*的比较。

第五节 本文的其余部分组织如下。第二节回顾了基于感知的采样规划的相关工作。第三节提供了原始SIRRT*算法的概述。第四节详细介绍了提出的E-SIRRT*框架，第五节提出了比较实验分析。最后，第六节总结了本文并讨论了未来的研究方向。第四节：推荐方法：Enhanced-SIRRT*E-SIRRT* 对原始的SIRRT*算法引入了两项改进：混合路径平滑和双向重连。这些改进在智能优化之前应用，有助于实现更快、更稳定的收敛。

A. 通过混合路径平滑进行初始路径优化
如前几节所述，从MST得到的原始路径通常在几何上不规则，不适合机器人直接执行。为了解决这个问题，应用了下面详细介绍的混合路径平滑过程。
1) 混合路径平滑
混合路径平滑过程作用于初始路径，即一个有序的顶点序列PMST=(v0,v1,…,vn)，其中vstart=v0 且 vgoal=vn。让Imap表示用于碰撞检测的二进制占用网格图（图中的空闲/占用单元格）。目标是将PMST转换为一个新的路径Psmooth，使其在几何上平滑且无碰撞。该过程如下所述，在算法1中总结。第一阶段，使用固定的间隔d对初始MST路径PMST进行稀疏采样，以创建一系列控制点Psub（第2行）。接下来，使用CubicSplineFit子程序（算法2）对Psub的坐标序列拟合两个独立的三次样条函数（第4-5行）。该程序计算每个区间[ui,ui+1]上的样条系数ai、bi、ci和di，使得
si(u)=ai+bi(u?ui)+ci(u?ui)2+di(u?ui)3（1）
一旦获得了样条系数，就在N+1个均匀分布的参数值处评估路径，得到密集采样的样条插值路径Pspline。

算法1 混合路径平滑
算法2 三次样条拟合
在第二阶段，该路径在Imap上验证其是否能够避免碰撞（第14行）。CollisionAwareCorrection子程序（算法3）用PMST中的安全替代路径替换任何无效路径段。最终得到无碰撞的平滑路径Psmooth。

2) 三次样条拟合
选择三次样条进行路径平滑是因为它们提供了C2连续性，与分段线性插值相比，可以产生更平滑的曲率轮廓。请注意，这一步骤纯粹是几何上的：仅C2连续性并不能保证动态可行性，因为本文没有强制执行针对机器人的特定约束（例如，曲率/曲率率的限制和时间参数化限制）。
CubicSplineFit子程序（算法2）计算一个自然三次样条的系数，该样条在均匀分布的参数域{u0,u1,…,um}上插值一系列标量值{z0,z1,…,zm}。目标是计算如（1）中定义的逐段样条系数，以确保在所有子区间[ui,ui+1]上的平滑插值。
假设均匀间距h=u1?u0（第2行），该方法构建一个三对角线性系统AM=r来求解节点处的二阶导数，M=[M1,…,Mm?1]T（第3-4行）。通过设置M0=Mm=0来施加自然边界条件，强制在端点处的二阶导数为零（第5行）。矩阵A∈R(m?1)×(m?1)是对称且三对角的，它是基于相邻样条段的一阶和二阶导数的连续性约束得出的。对于均匀间距，其标准化结构如下：
A=????????????4
10?0
141??0
14?0????
100?14
???????????（2）
其中每一行都确保了内部节点处的二阶导数连续性。该系统可以使用Thomas算法[17]高效求解。
一旦获得了二阶导数，就为每个段计算样条系数{ai,bi,ci,di}m?1i=0（第7-11行）。这些系数确保了在整个域上的C2连续性，并定义了一个平滑的、可二次微分的插值函数。

3) 碰撞感知校正
CollisionAwareCorrection子程序（算法3）改进了样条化的初始路径Pspline，以确保所有段都无碰撞。虽然样条插值提高了几何连续性，但它没有考虑障碍物，可能会生成不可行的段。该子程序逐段进行验证，并使用原始MST路径PMST中的点进行回退校正。
校正后的路径Psmooth从Pspline的第一个点开始（第2-3行）。然后算法遍历剩余的样条点（第4-8行），检查最后一个有效点之后的段是否无障碍物（第6行）。如果路径有效，则将当前点追加到路径中（第7-8行）。如果不是，则触发回退程序（第9-17行），该程序从PMST中搜索最近的可行点（第11-14行）。在所有有效候选点中，选择与当前样条点欧几里得距离最小的那个（第14行），并将其追加到路径中（第15-17行）。这个过程在可能的情况下保留了样条的几何形状，同时确保了可行性。

a: 样条样本之间的碰撞检测
在N+1个样本点处评估拟合的样条，并在对连续样本进行连接的折线段上逐段进行碰撞检测。对于每对连续样本(pi,pi+1)，ObstacleFree(pi,pi+1,Imap)沿着直线段pipi+1ˉˉˉˉˉˉˉˉˉˉˉˉˉ进行离散网格遍历（例如，Bresenham线遍历[18]），如果所有遍历的单元格都是空闲的，则返回true。因为实验中样条的采样密度很高（N+1=5|Psub|），所以得到的段很短，这使得在地图分辨率下进行碰撞检测时比较保守。

B. 通过双向重连进行初始树的细化
尽管平滑后的初始路径Psmooth在几何质量上有改进，但从MST构建的初始树T在其连通性或成本结构上尚未反映这一改进。因此，树可能与平滑路径的优越几何形状不对齐，这可能会阻碍有效的成本传播。为了解决这个问题，使用双向重连策略对树进行细化，具体过程在算法4中总结。

算法4 双向重连
为了正式描述重连过程，定义以下符号：搜索树是一个图T=(V,E)，其中V是顶点集，E是有向边集。
对于任何顶点v∈V，从起始顶点vstart到v的独特路径的成本to-come，用g(v)表示。
边的成本c(va,vb)是欧几里得距离∥va?vb∥。
平滑路径Psmooth是一个有序的点序列{p1,…,pk}，这些点依次插入到V中。
点p的邻域是Vnear(p,T,r)={v∈V∣c(p,v)≤r}，其中r是一个预定义的重连半径。
ObstacleFree(va,vb,Imap)是一个布尔函数，如果直线段vavbˉˉˉˉˉˉˉˉˉ在占用网格Imap上无碰撞，则返回true。

1) 双向重连过程
细化过程在每个点p插入树后迭代（算法4，第2行）。对于每个点，在半径r范围内识别一组相邻顶点Vnear（第3行）。然后如图3所示，在两个方向上进行重连。图3. 围绕平滑路径节点p进行双向重连的示意图。(a) 正向重连：如果新路径的成本更低且无碰撞，则将邻居q的父节点更改为p。(b) 反向重连：在相同条件下，p采用q作为新的父节点。实线箭头表示父节点到子节点的方向，红色箭头显示新的连接，虚线圆表示重连半径。
在正向重连阶段（第4-8行），算法评估p是否可以作为任何相邻顶点q的更好的父节点。如果通过p到q的路径比当前的路径更短且无碰撞，则重连该连接（第5行）。如果是这样，q的父节点将被更新为p，并通过其子树传播成本（第6-8行）。
在反向重连阶段（第9-13行），算法评估是否有任何邻居q能够提供通往p的更低成本的路径。这允许细化的路径更有效地集成到树中。如果通过q连接到p的成本更低且无碰撞（第10行），则q成为p的新父节点（第11-13行）。

a: 重连后的成本更新
当一个顶点v被重连（即其父节点改变）时，其to-come成本更新为g(v)←g(Parent(v))+c(Parent(v),v)。因为这种变化影响v的所有后代节点的独特路径成本，算法调用UpdateCost(v)将更新通过以v为根的子树传播。具体来说，对于v的每个子节点u，成本更新为g(u)←g(v)+c(v,u)，并递归地应用于所有后代（例如，通过深度优先遍历子节点链接）。

2) 细化过程的分析
这种细化过程是一种启发式方法，旨在通过提高初始解的质量来加速收敛。

a: 对理论保证的影响
双向重连步骤是一个有限的预处理启发式方法，它只修改初始的父节点关系和to-come值，而后续的智能RRT*扩展和重连保持不变。因此，在标准假设下，E-SIRRT*保留了与底层RRT*/IRRT*框架相同的概率完备性和渐进最优性属性。特别是，在任何有限迭代中，报告的解决方案都是当前树中包含的最低成本起点到终点路径（即，在探索的树中是最佳的），随着样本数量的增加，解决方案成本几乎肯定会收敛到所选度量的全局最优路径成本。

b: 计算复杂性
这一步的复杂性由沿平滑路径的每个点的重连过程决定。设k=|Psmooth|和n=|V|。对于k个点中的每一个，主要操作是邻居搜索（第3行）。使用高效的空间数据结构（如k-d树），这个搜索可以在大约O(logn)时间内完成[16]。这使得整个过程的计算效率很高，复杂度约为O(k?logn)。

C. Enhanced SIRRT*算法
算法5总结了所提出的E-SIRRT*规划器的完整流程。该过程包括三个主要阶段：初始树生成（第2-5行）、预优化细化（第6-8行）和主要的智能优化循环（第9-17行）。
首先，从环境骨架生成初始的MST和路径PMST（第2-5行）。本文的核心贡献在于随后的细化阶段（第6-8行）。在这里，使用HybridPathSmoothing改进路径，并通过依次将路径点作为新节点插入树中来保持路径连续性（第7行）。然后使用BidirectionalRewiring进一步细化树。这个过程通过局部更新高质量平滑路径节点与更广树之间的父子关系来改进成本传播，确保沿着平滑路径找到的较低成本有效地分配给附近的分支。这个细化的树和嵌入的路径为最终阶段提供了更好的起点：一个标准的智能RRT*优化循环，逐步改进解决方案同时保持渐进最优性（第9-17行）。
E-SIRRT*流程的关键阶段如图4所示。最初从环境骨架构建的树首先通过合并混合平滑路径Psmooth（洋红色）（图4(a)）得到增强。然后通过正向（图4(b)）和双向重连（图4(c)）改进树的连通性，受影响的区域用虚线矩形标出。这个过程产生了细化的初始路径（绿色），为后续优化提供了种子（图4(d)）。图4(e)展示了智能优化后的最终结果，包括优化后的路径（红色）、椭球形采样区域（绿色椭圆）和扩展的树结构（蓝色线条）。

第五节：实验结果与分析
本节在三个2-D基准环境和真实移动机器人上评估了所提出的E-SIRRT*规划器。表2总结了测试案例、评估目标和报告的性能指标。实验设置
比较实验在三种不同的二维环境中进行。第一个环境是公开可用的基准地图Freiburg-079 [19]的修改版本（1633×595像素），包含多个房间和走廊（图4）。第二个环境是“狭窄通道”，这是一个模拟环境（210×210像素），设计有狭窄的通道以专门挑战采样效率（图5）。第三个环境是LiDAR网格地图，这是一个复杂室内环境的网格地图（930×975像素），由实验机器人使用Cartographer SLAM [20]从现实世界LiDAR数据构建而成，展示了在真实场景中的性能。图5显示了实验#2的E-SIRRT*结果：(a) 初始树结构（蓝色节点和边）以及提取的最小生成树（MST）路径（青色线条）和其混合平滑版本（洋红色线条）；(b) 双向重连后的重连树结构和优化后的初始路径（绿色线条）；(c) 在有信息采样后得到的最终优化路径（红色线条）以及采样椭圆（绿色）。

图6显示了实验#1中IRRT*、SIRRT*和增强型SIRRT*（E-SIRRT*）在初始迭代后路径成本的收敛情况。对于SIRRT*和E-SIRRT*，第0次迭代的路径成本代表它们确定性生成的初始解，而IRRT*仅在找到随机解后才开始计算。(a) 最佳情况性能；(b) 中位情况性能；(c) 最坏情况性能。

图7显示了实验#2中IRRT*、SIRRT*和增强型SIRRT*（E-SIRRT*）在初始迭代后路径成本的收敛情况。对于SIRRT*和E-SIRRT*，第0次迭代的路径成本代表它们确定性生成的初始解，而IRRT*仅在找到随机解后才开始计算。(a) 最佳情况性能；(b) 中位情况性能；(c) 最坏情况性能。

图8显示了实验#3中IRRT*、SIRRT*和增强型SIRRT*（E-SIRRT*）在初始迭代后路径成本的收敛情况。对于SIRRT*和E-SIRRT*，第0次迭代的路径成本代表它们确定性生成的初始解，而IRRT*仅在找到随机解后才开始计算。(a) 最佳情况性能；(b) 中位情况性能；(c) 最坏情况性能。

图9显示了在实验#3-SOTA中BIT*、ABIT*和E-SIRRT*的路径成本随时间的收敛情况。每条曲线都是基于60秒的运行得到的，但为了便于阅读只显示了前10秒，因为成本在这个初始阶段之后迅速收敛，曲线在之后基本趋于平稳。表7中报告的最终成本对应于完整的60秒时间限制。(a) 最佳情况性能；(b) 中位情况性能；(c) 最坏情况性能。

图10展示了使用真实世界LiDAR网格地图的E-SIRRT*结果：(a) 从LiDAR数据构建的占用网格地图；(b) 带有Harris角节点的提取骨架；(c) 显示原始MST路径（青色）和混合平滑后的路径（洋红色）；(d) 在半径r=3η的双向重连后优化后的树和路径（绿色）；(e) 在半径r=5η的双向重连后优化后的树和路径（绿色）；(f) 在结果椭圆内进行有信息采样后得到的最终优化路径（红色）。

图11使用真实机器人验证了E-SIRRT*的性能。黑色背景插图显示了E-SIRRT*在安全地图上计算出的三条全局路径。主灰色背景图显示了机器人执行这些路径的相应真实世界轨迹（红色、绿色和蓝色线条），这些轨迹在网格地图中进行了定位。

在所有环境中，所提出的规划器都与原始的SIRRT*和广泛使用的IRRT*进行了比较。每个规划器都经过了100次独立试验的评估。所有实验都是用C++实现的，并在配备128GB RAM的Intel Core i9-14900K CPU上执行。对于IRRT*、SIRRT*和E-SIRRT*，收敛情况是在固定数量的初始迭代后报告的，这提供了一个与硬件无关的算法效率度量标准。

对于更复杂的LiDAR网格地图，还与最先进的规划器BIT* [7]和ABIT* [8]进行了额外的比较。因为这些规划器遵循批量信息图搜索范式，与RRT*变体的迭代比较没有直接意义；因此，它们在固定的墙钟时间限制下进行评估。因此，这种最先进的比较仅针对LiDAR网格地图进行，因为在这一点上时间评估最具信息量，且基准复杂度最能反映实际性能。

关键超参数是通过实验经验选择的，以实现路径质量和计算效率之间的良好平衡，并且在每个实验中的所有规划器中保持不变，以便进行公平比较。有信息优化阶段的最大边扩展长度η设为25像素。对于混合平滑，算法1中的子采样距离d在较大环境中（实验#1、#3和#3-SOTA）设为100像素，在狭窄通道情况下（实验#2）设为70像素。算法1中的样条评估间隔N根据子采样点的数量设置为N+1=5|Psub|。算法4中的双向重连半径r设为r=5η，因为这在性能和计算之间提供了稳健的折中，这一点在图10(d)和10(e)中得到了验证。

1) 预处理开销
为了量化由细化阶段引入的额外计算成本，分别测量了(i) 通过MST路径提取的确定性初始化（算法5，第2-5行），(ii) 混合路径平滑（第6行）以及(iii) 平滑路径插入和双向重连（第7-8行）的预处理时间。表3报告了在评估平台上的测量时间。在测试的地图中，细化阶段（混合平滑+双向重连）在实验#1中仅增加了0.15毫秒，在实验#2中增加了12.75微秒，在实验#3中增加了0.52毫秒，所有情况下都低于确定性初始化时间的1.2%。这些结果表明，E-SIRRT*的细化模块相对于SIRRT*的基线确定性初始化只引入了轻微的预处理开销。

表3显示了算法5的确定性初始化和细化阶段的预处理时间。“初始MST”时间对应于第2-5行（骨架化、角点检测、初始树构建和MST路径提取）。“混合路径平滑”对应于第6行，“双向重连”对应于第7-8行（平滑路径的插入和双向重连）。

2) 性能指标
路径成本是每个规划器返回的解决方案路径的欧几里得长度。(i) 初始迭代（仅IRRT*），即获得第一个可行解决方案所需的迭代次数；(ii) 初始成本，即初始优化阶段开始时的初始解决方案成本（图6-8中的第0次迭代；对于IRRT*，这对应于第一个可行的路径）；(iii) 最终成本，即在运行限制结束时获得的最佳路径成本；以及(iv) 鲁棒性统计，表示100次独立试验的平均值和标准差。在与BIT*和ABIT*的时间比较中，报告的初始和最终成本分别对应于在固定墙钟时间限制内的第一个可行解决方案和最佳解决方案。表中的括号值表示100次试验中的最小值和最大值。

B. 定量比较
1) 在模拟环境中的性能（实验#1和#2）
在Freiburg环境中，所有规划器都运行了20000次初始迭代（表4和图6）。收敛图展示了初始优化阶段的路径成本。每个图表中的第0次迭代的成本对应于表4中报告的“初始成本”值，表示迭代优化开始之前的解决方案质量。IRRT*在找到初始解决方案方面表现出相当大的变异性，迭代次数从356到7162不等。即使起点和终点位置相同，这种高变异性仍然存在，突显了其对随机采样的敏感性。在鲁棒性至关重要的实际应用中，这种不可预测性尤其成问题。相比之下，E-SIRRT*不仅提供了一个确定的初始解决方案，而且其成本（1301.84）显著低于SIRRT*（1484.38）和IRRT*的平均值（1531.91）。

这种优势在狭窄通道环境中也很明显，该环境运行了1500次初始迭代（表5和图7）。尽管所有规划器在收敛后的最终成本相似（约145），E-SIRRT*再次提供了高度一致的初始解决方案。图5显示了E-SIRRT*在这个实验中的一个代表性结果，展示了从初始路径生成到最终优化路径的各个阶段。

2) 在真实世界环境中的性能（实验#3）
在真实世界LiDAR地图上的结果，运行了20000次初始迭代，进一步突显了所提出方法与IRRT*和SIRRT*相比的优势（表6和图8）。基本的SIRRT*在这个复杂环境中表现不佳，产生了高成本的初始路径（1471.78）。然而，E-SIRRT*的细化模块产生了显著更好的初始路径（963.98），并且没有方差，甚至优于IRRT*的平均情况。在优化阶段之后，E-SIRRT*始终能找到这三个规划器中成本最低的最终路径。这一过程的关键阶段，包括不同重连半径的比较，在图10中进行了可视化。

3) 与最先进规划器BIT*和ABIT*的比较（实验#3-SOTA）
为了将所提出的方法与最先进的方法进行对比，E-SIRRT*在真实世界LiDAR地图上与开放运动规划库（OMPL）[21]中的BIT*和ABIT*进行了比较，时间限制为60秒，因为这些基于批量的规划器最适合在墙钟时间内进行评估（表7和图9）。正如预期的那样，基于批量的规划器几乎瞬间就收敛到了低成本的解决方案。然而，结果突显了E-SIRRT*的两个关键优势。首先，在可靠性方面，E-SIRRT*提供了高质量的初始解决方案且没有方差，而基于批量的规划器表现出显著的变异性。其次，在最终路径质量方面，E-SIRRT*在60秒后收敛到的最终路径成本明显更低。这些结果表明，在路径最优性至关重要的应用中，E-SIRRT*的结构化细化方法找到了更好的解决方案。此外，这表明了一个有吸引力的未来方向：E-SIRRT*的细化模块可以作为“热启动”为基于批量的规划器提供高质量的初始种子， potentially结合了两种范式的优势。

C. 使用移动机器人的验证
为了提供物理实验验证，所提出的E-SIRRT*规划器被部署在一个配备了Hokuyo UTM-30LX 2-D LiDAR扫描器的差动驱动机器人上。机器人的任务是通过遵循E-SIRRT*生成的路径在复杂的室内环境（大约60米×40米）中导航。E-SIRRT*使用一个考虑了机器人半径的安全地图成功计算出了可导航和安全路径。图11中的黑色背景插图显示了安全地图和三条规划的E-SIRRT*路径。使用了之前工作[22]中的分层导航框架进行路径执行，其中E-SIRRT*作为全局规划器。

实验包括环境中的三个关键位置之间的三条路径规划任务：从S1到S2、S2到S3以及S3到S1。图11展示了机器人的真实世界轨迹（红色、绿色和蓝色线条）叠加在网格地图上。为了定量评估路径跟踪性能，计算了机器人实时航向与规划全局路径方向之间的余弦相似度。该指标直接衡量了轨迹跟随质量，其中接近1.0的值表明路径遵循准确且可执行性高。

结果如图12所示。机器人成功导航了所有三条路径，余弦相似度值始终保持稳定且接近1.0。轻微的短暂偏离发生在机器人反应性局部规划器暂时调整航向以安全避开尖锐角落时，确保了足够的间隙。这些偏差在图11中的青色虚线区域中突出显示。这种实验验证表明，E-SIRRT*生成的几何上更优的路径不仅在理论上合理，而且对于物理机器人系统来说也非常实用且高效。

第六部分 结论
本文介绍了增强型SIRRT*（E-SIRRT*），该框架通过提高其确定性生成的初始路径的质量来改善原始SIRRT*算法的实际性能。E-SIRRT* 克服了 SIRRT* 的一个关键局限性，即原始最小生成树（MST）路径的几何质量较差的问题，通过应用两种预优化改进方法来实现：混合路径平滑技术和双向重连技术。混合路径平滑模块生成了一条平滑且无碰撞的初始路径，而双向重连阶段则根据这条优化后的路径重新调整树结构和代价函数，从而获得一个在几何上可靠且能高效融入搜索树的初始解。在多个二维网格地图环境以及对真实移动机器人的实验中表明，E-SIRRT* 持续提供了更可靠的初始解，并且与 IRRT* 和原始 SIRRT* 相比，最终路径成本更低。在三个基准测试环境中，E-SIRRT* 将初始路径成本降低了 12.3–34.5%，同时保持零方差初始化。在所有三个基准测试中，E-SIRRT* 实现了最低的平均最终成本（比 IRRT* 低 0.10%，比 SIRRT* 低 0.06%），并且通过使用确定性的初始种子避免了 IRRT* 在多次迭代中路径成本的大幅波动。此外，在固定的 60 秒时间限制下，E-SIRRT* 的最终路径成本分别比 BIT* 和 ABIT* 低 1.36% 和 1.68%。这些结果证实，将基于骨架的确定性初始化与原理性的几何和结构改进结合起来，可以开发出一种稳健、低方差且高性能的运动规划算法。未来的工作将集中在将 E-SIRRT* 扩展到更高维的规划问题和更复杂的机器人模型上。更广泛地说，这里提出的改进模块可以作为通用的“热启动”技术，来提升其他允许使用初始树的采样基规划算法的性能。最后，由于优化的初始路径可以快速计算且已经提供了高质量的解，因此可以直接应用于需要快速、可靠路径的轻量级工业应用中，而无需进行完整的优化，这为研究开辟了另一个有前景的方向。

致谢
作者感谢匿名审稿人的宝贵时间和建设性反馈，这些反馈有助于提高本文的质量。本研究、实现、实验和手稿的准备工作均由作者本人完成。