1. 课程导入

路径规划（Path Planning）是智能体在给定环境中，从起始状态到目标状态寻找一条满足约束条件（如无碰撞、最短距离、最小能耗或最高效率）的可行路径的过程。它不仅是机器人学、自动驾驶和游戏AI的核心底层技术，更是连接感知、决策与控制三大模块的“大脑中枢”。在真实工程中，路径规划并非孤立算法，而是与地图表示、状态空间建模、动态障碍物预测、运动学约束以及实时性要求紧密耦合。本章作为整个课程的开篇，将首先厘清路径规划的本质定义与数学表述，随后剖析其在三大核心领域的典型应用形态，最后给出本课程从基础算法到工程实战的完整学习路径，帮助读者建立全局视野。

上图展示了路径规划问题的核心要素与课程学习路径的宏观映射。从工程视角看，路径规划本质上是一个约束优化问题：给定环境模型（栅格地图、拓扑图或路网）、智能体状态（位置、速度、航向）以及目标状态，算法需要在满足无碰撞、运动学可行、实时性等硬约束的前提下，最小化或最大化某个性能指标（如路径长度、时间、能耗、舒适度或风险值）。值得注意的是，不同应用场景对“最优”的定义截然不同——仓储机器人追求最短时间，自动驾驶强调安全与舒适，而游戏NPC则更关注行为自然度与计算开销的平衡。

1.1 路径规划的定义与数学表述

从形式化角度，路径规划可表述为：设状态空间为 X，其中 X_free 为无障碍自由空间，X_obs 为障碍物占据空间。给定初始状态 x_start 和目标区域 X_goal，寻找一条连续映射 τ: [0,1] → X_free，使得 τ(0) = x_start 且 τ(1) ∈ X_goal。在此基础上，引入代价函数 J(τ)（如弧长积分、能量消耗或风险累积），路径规划即求解 τ* = argmin J(τ)。在实际工程中，还需额外考虑微分约束（如车辆最小转弯半径）、时间约束（动态障碍物）以及不确定性（感知噪声）。

1.2 三大核心应用领域深度解析

机器人领域：从工业机械臂的避障路径到移动机器人的自主导航，路径规划是机器人智能化的基石。在仓储物流场景中，Kiva机器人（现Amazon Robotics）通过集中式路径规划算法协调数百台AGV，避免碰撞并优化整体吞吐量。在服务机器人领域，SLAM（同步定位与建图）与路径规划紧密耦合——机器人先构建环境地图，再基于地图进行全局规划，同时结合局部规划器应对动态行人。值得注意的是，机械臂的路径规划通常涉及6-7自由度的关节空间搜索，其状态空间维度远高于地面移动机器人，这对算法的实时性和内存占用提出了严苛要求。

自动驾驶领域：自动驾驶的路径规划呈现明显的分层架构。全局路径规划（Route Planning）基于高精地图计算从起点到终点的宏观道路序列，通常采用A*或Dijkstra算法在车道级路网上搜索。局部路径规划（Motion Planning）则负责在数十米范围内生成可执行的轨迹，常用方法包括：基于采样的RRT*、基于优化的二次规划（QP）或模型预测控制（MPC）。以百度Apollo为例，其EM Planner（基于动态规划的决策+基于样条曲线的优化）在结构化道路上表现优异，而Lattice Planner则更适合高速公路场景。关键挑战在于：车辆必须满足非完整约束（如阿克曼转向模型），且规划周期需控制在100ms以内以应对突发情况。

游戏AI领域：游戏中的路径规划与机器人/自动驾驶有显著差异——它更强调实时性和行为多样性。经典A*算法在网格地图上表现良好，但面对开放世界的大规模地图时，需要引入层次化寻路（HPA*）或跳点搜索（JPS）来加速。此外，游戏NPC的路径规划还需考虑群体行为（如RTS游戏中的编队移动）、视线遮挡（潜行机制）以及环境交互（破坏障碍物）。例如，《塞尔达传说：旷野之息》中的NPC寻路系统结合了导航网格（NavMesh）与动态障碍物规避，实现了自然流畅的移动效果。游戏AI的另一个特点是允许“非最优”路径——只要行为看起来合理且不破坏游戏体验，计算开销往往比路径质量更重要。

1.3 课程目标与学习路径规划

本课程旨在帮助学习者建立从算法原理到工程落地的完整能力闭环。课程共30章，分为四大阶段：

1. 基础算法篇（第1-8章）：系统讲解图搜索（BFS/DFS/Dijkstra/A*）、采样算法（PRM/RRT/RRT*）、智能优化算法（遗传算法/蚁群算法）以及轨迹平滑方法。每章均包含算法伪代码、复杂度分析和可视化演示。
2. 工程优化篇（第9-16章）：聚焦工程实现中的关键问题——地图表示与数据结构优化、碰撞检测加速（空间哈希/包围盒树）、路径平滑与插值（B样条/贝塞尔曲线）、动态环境下的重规划策略。
3. 场景实战篇（第17-24章）：针对机器人、自动驾驶、游戏AI三大领域，分别设计完整项目案例。例如：基于ROS的移动机器人导航系统、自动驾驶高速公路变道规划、开放世界游戏NPC寻路系统。
4. 系统调优篇（第25-30章）：深入探讨多目标优化、并行计算加速、机器学习辅助路径规划（如模仿学习）、以及真实系统中的鲁棒性设计。

1.4 常见误区与课程学习复盘

在多年教学与工程实践中，我们发现初学者常陷入以下误区：

• 误区一：认为A*就是路径规划的全部。实际上，A*仅适用于静态、离散、低维空间。面对连续空间、高维关节或动态障碍物，必须引入采样方法或优化方法。
• 误区二：忽视运动学约束。很多初学者在几何路径规划后直接输出路径点，导致机器人或车辆无法跟踪。正确的做法是：在规划阶段就考虑最大曲率、加速度限制等约束，或在后处理阶段进行轨迹平滑与重映射。
• 误区三：混淆全局规划与局部规划。全局规划负责宏观路径，局部规划负责微观避障。两者需要协同工作——全局路径提供“导航方向”，局部规划器在遇到动态障碍物时进行临时绕行，但必须确保绕行后能回到全局路径上。
• 误区四：忽略计算资源限制。在嵌入式平台（如NVIDIA Jetson、STM32）上，算法的时间复杂度和内存占用至关重要。例如，RRT*虽然能生成渐进最优路径，但在资源受限平台上可能无法满足实时性要求，此时需要降级为RRT或引入双向搜索策略。