1. 课程导论
路径规划是机器人学与自动驾驶领域的核心基础问题之一，其目标是在给定环境中寻找一条从起点到终点的可行路径，同时满足安全性、平滑性、动力学约束等要求。而“全额支付路径规划”（Full-cost Path Planning）并非一个简单的学术术语，它强调的是在规划过程中将计算资源、时间成本、能量消耗、执行代价等全部纳入考量，而非仅仅追求几何上的最短路径。RRT（Rapidly-exploring Random Tree，快速扩展随机树）与RRT Connect作为采样类规划算法的代表，因其在高维空间和复杂约束下的高效性，已成为工程实践中最常用的算法族。本章作为课程导论，将系统阐述全额支付路径规划的背景、典型应用场景、课程目标以及学习路径，为后续章节的算法推导与工程实现奠定基础。
全额支付路径规划的核心概念与背景
传统路径规划通常以“最短路径”或“最快到达”作为唯一优化目标，但在真实工程环境中，这种简化往往导致规划结果不可执行或代价过高。全额支付路径规划强调在规划阶段就全面考虑以下四类成本：计算成本（算法运行时间与内存占用）、执行成本（机器人运动所需的能量、时间、磨损）、风险成本（碰撞概率、不确定性带来的安全裕度）以及系统成本（传感器噪声、控制误差、通信延迟等）。RRT算法之所以在工程中广受欢迎，正是因为它能够以较低的计算成本快速探索高维空间，同时通过采样策略天然地处理复杂约束。
从理论背景看，RRT由Steven M. LaValle于1998年提出，其核心思想是通过随机采样逐步构建一棵覆盖自由空间的树形结构。RRT Connect则在此基础上引入双向搜索策略，从起点和终点同时生长两棵树，显著提升了搜索效率。这两种算法都属于概率完备算法——当采样点数量趋于无穷时，找到可行路径的概率趋近于1。然而，概率完备并不等于最优，因此后续章节将深入讨论RRT*、Informed RRT*等改进算法如何引入代价函数实现渐进最优。
典型应用场景与工程需求
全额支付路径规划在多个领域具有直接且迫切的应用需求，不同场景对算法的约束条件与优化目标差异显著。下表对比了四个典型场景的核心特征：
| 应用场景 | 维度 | 核心约束 | 主要代价 | RRT适用性 |
|---|---|---|---|---|
| 室内移动机器人 | 2D/2.5D | 静态障碍、窄通道 | 时间、能耗 | 高（快速探索） |
| 自动驾驶城市工况 | 3D+时间 | 动态障碍、交通规则 | 安全、舒适性 | 中（需改进） |
| 无人机三维巡检 | 3D | 风场、禁飞区 | 能量、风险 | 高（高维优势） |
| 工业机械臂抓取 | 6-7D | 关节限位、奇异位形 | 执行精度、节拍 | 极高（高维必选） |
以自动驾驶为例，城市工况中的路径规划需要在毫秒级时间内完成，同时必须考虑车辆的非完整约束（如最小转弯半径）、车道线约束以及周围交通参与者的预测轨迹。RRT Connect的双向搜索特性在此类场景中能够快速生成初始可行路径，再通过后续的平滑优化模块（如B样条或多项式拟合）生成满足舒适性要求的轨迹。而在工业机械臂场景中，7自由度机械臂的构型空间高达7维，传统网格搜索方法完全不可行，RRT系列算法几乎是唯一实用的选择。
课程目标与学习路径设计
本课程的目标是培养学员从算法原理到工程落地的完整能力。具体而言，完成本课程后，学员应能够：
- 深入理解RRT与RRT Connect的数学原理，包括采样策略、碰撞检测、树扩展规则以及概率完备性证明。
- 掌握全额支付代价函数的建模方法，能够根据具体应用场景设计合理的代价指标，并将代价函数嵌入RRT框架中。
- 具备工程实现能力，能够使用Python/C++实现RRT算法，并处理实际环境中的传感器噪声、地图不确定性等问题。
- 学会算法调参与性能评估，理解采样点数、步长、目标偏置概率等参数对规划结果的影响，并掌握常用的性能评价指标（如成功率、路径长度、计算时间）。
- 了解前沿扩展方向，包括RRT*、Informed RRT*、RRT-Connect与优化算法的结合，以及基于学习的采样策略。
学习路径按照“基础理论 → 核心算法 → 工程实践 → 前沿扩展”四个阶段递进。第一阶段（第1-5章）建立路径规划的问题定义、环境建模和碰撞检测基础；第二阶段（第6-15章）深入剖析RRT与RRT Connect的算法细节，包括伪代码、复杂度分析和变体改进；第三阶段（第16-24章）聚焦工程实现，涵盖代码框架、参数调优、仿真环境搭建和真实机器人部署；第四阶段（第25-30章）探讨算法在自动驾驶、无人机、机械臂等领域的专项应用，并介绍与深度学习、模型预测控制等技术的融合趋势。
常见误区与学习复盘
在多年教学与工程实践中，我们发现学员在学习RRT系列算法时经常陷入以下误区，需要特别警惕：
- 误区一：认为RRT一定能找到最优路径。基础RRT算法只保证概率完备性，不保证最优性。找到的路径往往曲折且包含大量冗余转折。必须引入RRT*或后处理优化才能获得高质量路径。
- 误区二：忽视碰撞检测的性能瓶颈。在复杂环境中，碰撞检测可能占据算法总运行时间的80%以上。初学者往往只关注树扩展逻辑，而忽略了碰撞检测的数据结构优化（如KD树、BVH树），导致算法实际运行极慢。
- 误区三：盲目调整采样点数。增加采样点数可以提高路径质量，但计算代价也线性增长。实际工程中应优先调整步长和目标偏置概率，而不是一味增加采样规模。
- 误区四：忽略动力学约束。基础RRT生成的是几何路径，不包含速度、加速度信息。在自动驾驶或无人机应用中，必须将动力学约束嵌入采样过程或通过后处理模块进行轨迹整形。
为了帮助学员建立系统化的复盘能力，我们建议每完成一个章节后，按照以下清单进行自我检查：
□ 是否能够用自己的语言复述本章核心算法的输入、输出与关键步骤？
□ 是否清楚算法的时间复杂度与空间复杂度，以及主要瓶颈在哪里？
□ 是否能够指出算法在哪些场景下会失效（如窄通道、高维空间）？
□ 是否理解算法中每个关键参数（如步长、偏置概率）对结果的影响趋势？
□ 是否能够对比本章算法与之前章节算法的优劣，并说明适用边界？