关于RRT与RRT*时空复杂度及两类增量算法性能对比的技术问询

一、RRT与RRT*的时间、空间复杂度 #

咱先把这俩算法的复杂度拆解清楚：

• RRT：
  时间复杂度：如果用kd树这类数据结构加速最近邻搜索，每次迭代的最近邻查找耗时O(log n)（n为已采样的节点数量），整个算法迭代n次后，总时间复杂度为O(n log n)。
  空间复杂度：需要存储所有采样节点和连接它们的边，因此是O(n)，和节点数量呈线性相关。
• RRT*：
  时间复杂度：RRT*在RRT基础上多了重布线步骤——每次新增节点后，要在一定半径内查找邻居节点并重新优化路径。用kd树的话，邻居查找耗时O(k log n)（k为半径内的邻居数，在d维空间中k通常是常数级或O(log n)），整体渐进时间复杂度为O(n log n)（非理想场景下可能达到O(n²)，但主流分析以渐进复杂度为准）。
  空间复杂度和RRT一致，也是O(n)，重布线不会带来额外的大规模空间开销。

二、增量采样类算法 vs 基于图的增量启发式算法 #

增量采样类算法（比如RRT、RRT*）和基于图的增量启发式算法（比如D* Lite、增量A*）的性能差异，核心看应用场景：

• 采样类算法更占优的场景：
  • 高维构型空间：比如7自由度机械臂、6自由度无人机的运动规划，基于图的算法会因状态空间爆炸导致图规模不可控；而采样类算法通过随机采样探索，能快速覆盖空间找到可行路径。
  • 缺乏启发式信息：如果没有合适的引导性启发式函数，基于图的启发式算法效率会暴跌，而采样类算法无需依赖启发式，随机探索就能逐步靠近目标。
  • 复杂障碍物环境：当障碍物形状不规则、分布零散时，采样类算法无需预先建模全空间连通性，采样过程中自然能避开障碍物。
• 基于图的算法更占优的场景：
  • 低维、规整空间：比如2D平面路径规划，基于图的增量启发式算法（如D* Lite）能借助启发式快速找到最优路径，且路径质量稳定；采样类算法的路径常偏“曲折”，即使是RRT*要收敛到最优也需要大量采样，耗时更久。
  • 频繁动态更新的环境：当环境频繁变化时，基于图的算法可复用原有图结构，仅更新变化部分，响应效率更高；而采样类算法往往需要重新采样或大量调整，响应速度较慢。
  • 对路径最优性要求极高：若需要严格最优路径，基于图的启发式算法在有合适启发式的前提下，能更快收敛到最优解；RRT*虽理论上能收敛到最优，但需要极多采样点，实际应用中很难达到理论最优。

内容的提问来源于stack exchange，提问作者J.Dow