自动驾驶中的路径规划分为 pipeline planning 和 end-to-end planning

pipeline planning：基于规则的规划方式，需要和其他自动驾驶任务一起完成，比如感知、定位和控制。好处是可以理解的，当某个流程出问题后能够很快确认。

end-to-end planning：基于学习的规划方式，整个的自动驾驶流程就如同一个单独的从原始感知数据到控制指令的机器学习任务。驾驶模型可以通过强化学习或者并行学习持续自我优化。难以找到错误行为的原因。

pipeline planning

也可以叫做模块化的方法。由例如感知、定位、规划和控制等组成。框架计算一连串轨迹点，给低级车辆控制器跟踪，包括全局路线规划、局部行为规划和局部轨迹规划。全局路线规划提供地图上的从起点到终点的道路路径。

局部代表时间上和空间上短的轨迹。传感器的测量范围决定了规划未来的行为。局部行为规划和局部轨迹规划界定起来比较模糊，直接用Local Behav-ior/Trajectory Planning代表。

A. 全局路线规划

用来在路网上寻找最佳的道路级别的路径，使用边和节点组成的有向图。路线规划搜索器根据起始节点和终止节点搜索最小代价的序列。代价由查询时间、预处理复杂度、内存占用、鲁棒性等因素决定。Dijkstra类算法通常用来解决这个问题。

B. 局部行为/路径规划

路径规划是指在道路网络中找到最佳的道路级别路径，以便车辆从起点到终点行驶。而轨迹规划则是指根据车辆的动力学模型和环境信息，计算出车辆在行驶过程中需要采取的具体控制命令序列，以实现安全、平稳、高效的行驶。

局部路径规划通常通过解决OCP1问题来实现，局部路径规划分为两个部分

1 状态网格识别

将环境分割成一组离散的状态，以便于路径规划和轨迹生成

通过搜索、选择、优化或势能最小化2完成。基于搜索的的方式把连续状态空间和OCP关联到一个图里面，从里面找寻状态连接。

基于搜索的方法包括 A* 搜索和动态编程（DP）。还有其它很热的算法比如混合A*、双向A*，半优化A*和LQG3框架。

基于选择的方法决定了状态网格的下一步或几步，根据优化的代价函数寻找。通常使用贪婪选择和马尔可夫决策过程4。

基于优化的方法把原始OCP离散化为数学规划（MP），其解就是高分辨状态网格。数学规划问题又分为基于梯度信息的和不基于梯度信息的方法。基于梯度信息的方法通常解决非线性规划5、二次规划6、带二次约束的二次规划7和混合整数规划8。不基于梯度信息的方法通常的代表为元启发式算法9。

2 基元生成

生成一组简单的轨迹/路径段，这些段可以被连接起来形成完整的轨迹

基元生成通常表现为闭式规则、模拟、插值和优化等形式。其中，闭式规则指使用解析方法计算基元的方法，通常包括Dubins/Reeds-Shepp曲线、多项式和理论最优控制方法等；模拟方法通过前向模拟生成轨迹/路径基元，由于没有自由度，因此运行速度较快；插值方法通常使用样条或参数化多项式等技术来生成基元；优化方法通过数值求解小规模的最优控制问题来连接两个状态网格，从而生成高分辨率的状态网格。

基于优化的方法解决小型OCP数值地连接两个状态网格

3 其他方法

状态网格识别和基元生成是构建轨迹的两个基本操作。

解释

  1. OCP指的是Optimal Control Problem（最优控制问题），它是指在给定动力学模型和约束条件的情况下，寻找一种最优的控制策略，使得系统能够在满足约束条件的前提下，达到某种性能指标的最优值。在自动驾驶领域中，OCP通常用于轨迹规划和控制器设计中。 ↩︎

  2. 一种常用的路径规划方法，它通过将道路网络抽象为一个图形结构，并将每个节点看作一个势能场，从而实现路径规划。具体来说，该方法通过计算每个节点的势能值，并在势能最小的路径上进行搜索，以找到最优路径。 ↩︎

  3. LQG是线性二次型高斯控制（Linear-Quadratic-Gaussian Control）的缩写，是一种常用的控制理论方法。该方法通过建立系统的状态空间模型，并将控制目标表示为一个二次型性能指标，从而实现对系统的控制。 ↩︎

  4. 马尔可夫决策过程（Markov Decision Process）是一种常用的强化学习方法。该方法通过建立一个状态转移模型和一个奖励函数，从而实现对智能体在环境中的决策和行动。 ↩︎

  5. 目标函数或约束条件中包含非线性项的优化问题 ↩︎

  6. 目标函数为二次型的优化问题 ↩︎

  7. 约束条件为一组二次不等式或等式的优化问题 ↩︎

  8. 同时包含连续变量和离散变量的优化问题 ↩︎

  9. 元启发式算法（metaheuristics）是一类基于启发式搜索的优化算法，通常用于求解复杂的优化问题。与传统的数学规划方法不同，元启发式算法通常不依赖于问题的具体结构和性质，而是通过对搜索空间进行探索和评估来寻找最优解。元启发式算法包括遗传算法、模拟退火、蚁群算法、粒子群优化等多种方法。 ↩︎