0. 前言

本文主要记录课程《自动驾驶预测与决策技术》的学习过程，难免会有很多纰漏，感谢指正。
课程链接：https://www.shenlanxueyuan.com/my/course/700
相关笔记链接：
Part1_自动驾驶决策规划简介
Part2_基于模型的预测方法
Part3_路径与轨迹规划
Part4_时空联合规划
Part5_决策过程

1. 部分观测的马尔可夫决策过程

1.1 POMDP的思想以及与MDP的联系

1.1.1 MDP的过程回顾

1.1.2 POMDP定义

1.1.3 与MDP的联系及区别

在这个“开门与老虎”例子中，解释了 POMDP 和 MDP 的区别与联系。

POMDP 视角

在这个图中，智能体面对两扇门，一扇门后有老虎，另一扇门是逃生的出口。问题在于，智能体无法直接观察门后是什么，必须通过“listen”（听老虎的声音）来推测老虎的位置。

1. 状态（S0 和 S1）：老虎可能在左边（S0），或者在右边（S1）。状态的变化依赖于智能体的行为。
2. 动作集（A）：智能体可以选择听（listen）或直接开左边门（open left）或右边门（open right）。
3. 观察集：智能体不能直接知道老虎在哪里，但可以通过听老虎的声音获取部分信息。听到左边的声音意味着老虎可能在左边，听到右边的声音则相反。
4. 观察概率（Pr）：当老虎在左边（S0）时，听到左边的声音的概率是 0.85，而听到右边声音的概率是 0.15（有一定的不确定性）。同样，老虎在右边时的观察概率是对称的。
5. 奖励：开错门导致 -100 分的惩罚，开对门获得 +10 分的奖励，而“听”的行为有一个代价 -1。

在 POMDP 模型中，智能体只能通过“听”这种部分观察行为来推测当前的状态，它无法直接看到老虎的位置。这种不确定性体现了 POMDP 的核心特点——智能体不能完全观察到环境的真实状态，只能基于观察推测。

MDP 视角

如果我们假设智能体可以直接看到老虎的位置，那么这个问题就变成了一个 MDP 问题：

• 状态：智能体知道老虎的位置。
• 动作：智能体可以直接选择开哪扇门。
• 奖励与惩罚：仍然是开错门得到 -100 分，开对门 +10 分。

在 MDP 中，智能体能完全观察到当前状态，因此它可以立即根据观察作出正确的决策，比如看到老虎在左边时就开右边的门，没有不确定性。

决策次数对最优解的影响

在“开门与老虎”的 POMDP 问题中，决策次数的不同会影响如何寻找最优解。通过不同的决策时间范围（1次、2次、100次决策）来探索最优策略。

1. 只能做一次决策：

如果只能做一次决策，最优解比较简单，因为你没有时间去“听”并获得更多信息。在这种情况下，你无法改善对状态的认知，只能基于当前的信念状态做出决策。假设初始状态下老虎可能在左边或右边的概率是 50%。

• 最优策略：此时直接选择开门，因为“听”的行为会消耗 -1 的代价，且你没有足够的回合来平衡这个损失。由于没有任何信息提示，选择任意一扇门的期望是一样的：直接开门会带来 -45 的期望收益（50%概率开对门得到 +10，50%概率开错门得到 -100）。

2. 可以做两次决策：

如果有两次决策机会，策略会更加复杂，因为你可以选择“听”一次，然后根据听到的信息来做更明智的选择。

• 策略 1：首先执行“listen”行动，通过听到的老虎位置的信息更新你的信念状态。

  • 听到老虎在左边时，你推测老虎确实在左边的概率是 85%，在右边的概率是 15%。
  • 听到老虎在右边时，你推测老虎在右边的概率是 85%，在左边的概率是 15%。

• 最优策略：通过“listen”获得信息后，你的下一步决策（开左门还是开右门）基于更新后的信念状态。如果听到左边的老虎声音，你应开右门（85%的概率成功），听到右边的声音则开左门。

期望收益：

• 听到老虎在左边：85%概率开对门，期望为 $(0.85\times 10+0.15\times (-100)=-4$)。
• 听到老虎在右边：同理，期望为 -4。
• 听的代价是 -1，所以最终期望收益为 $(-4-1=-5)$。

相比于不听直接开门（期望收益 -45），听一次然后做决策的期望收益更好。

3. 可以做 100 次决策：

如果有 100 次决策机会，这就变成了长期规划的问题。你可以通过反复“听”来更新信念，并最大化未来决策的累积奖励。在这种情况下，你可以多次选择“listen”来降低不确定性，但每次“听”都有代价，因此需要平衡“听”的次数和总期望奖励。

• 策略：

  • 开始时先进行几次“listen”来逐渐提高对老虎位置的把握，直到信念状态足够明确（比如 95% 的信心）。
  • 然后再根据当前的信念选择开门。

• 最优策略：

  • 在较早阶段可以多听几次，但不宜过多，因为每次“listen”都会有 -1 的代价。
  • 在信念足够明确时，停止“listen”，选择开门。如果老虎位置的概率已经非常确定（例如 >95%），继续“听”的收益就不如直接开门的收益高。

在这种长期决策中，POMDP 的策略可以通过动态规划或贝尔曼方程来求解，这样可以在多次决策过程中找到最优的策略。

总结：

• 1次决策：直接开门，期望收益是 -45。
• 2次决策：先听一次再开门，期望收益是 -5。
• 100次决策：先听几次（逐渐增加对老虎位置的确定性），然后开门，期望收益可以更高，具体取决于使用的策略优化算法。

在多次决策问题中，通过不断获取信息来更新信念状态可以大幅提升期望收益，这也是 POMDP 的强大之处。

1.2 POMDP的3种常规解法

1.2.1 连续状态的“Belief MDP”方法

使用Belief MDP 方法在连续状态空间中的基本思路及求解过程：

1. 信念状态的定义

信念状态是对系统当前状态的概率分布。由于在 POMDP 问题中，状态不是完全可观测的，智能体需要根据历史信息（包括过去的动作和观测）推测当前系统的状态，这种推测即信念状态 $(b)$。

在经典 POMDP 问题中，由于状态是部分可观测的，智能体需要根据所做的观测推断出系统可能处于的状态分布，这个推断称为信念状态（Belief State）。

• 信念状态 $(b(s))$ 是一个概率分布，表示智能体对系统实际状态的估计。具体来说，信念状态是根据历史的观测、动作、奖励等信息，对当前状态的条件概率分布。对于每一个状态 $(s)$，信念状态 $(b(s))$ 表示智能体认为系统处于状态 $(s)$ 的概率。

• 将 POMDP 问题转化为信念 MDP 时，我们不再直接处理原始的部分可观测的状态，而是在信念空间上处理这个问题。因此，信念 MDP 具有完全可观测性。

2. Belief MDP 的过程

为了处理部分可观测性问题，POMDP 转化为Belief MDP 问题。Belief MDP的目标是找到在信念空间中的最优策略，即在当前的信念状态下采取什么动作能够最大化期望奖励。

• 动态模型：系统从信念状态 $(b_t)$ 转移到新的信念状态 $(b_{t+1})$，通过执行动作 $(a_t)$ 并观测到新的观测 $(o)$ 后，更新信念状态。

• 奖励函数：对于每一个信念状态，奖励 $(r(b_t,a_t))$ 是在信念 $(b_t)$ 下采取动作 $(a_t)$ 所带来的即时奖励。

3. 问题的求解

利用值迭代的方法求解信念 Belief MDP 的过程：

• 期望奖励函数 $(V^{\pi }(b_0))$：给定初始信念 $(b_0)$ 和策略 $(\pi )$，期望的回报是未来每一个时刻 $(t)$ 的奖励的加权和，即：
  $$V^{\pi }(b_0)=\sum _{t=0}^{\infty }{\gamma }^{t}E[R(s_t,a_t)|b_0,\pi ]$$
  其中 $(\gamma )$是折扣因子。

• 最优策略：通过优化该期望回报 $(V^{\pi }(b_0))$，可以找到一个最优策略 $({\pi }^{\ast })$，即：
  $${\pi }^{\ast }=\arg \underset{\pi }{\max }{V}^{\pi }(b_0)$$

4. 值迭代的递推公式

为了计算Belief MDP 中每个信念状态的值，可以使用值迭代算法，其递推公式为：
$$V^{\ast }(b)=\underset{a\in A}{\max }\left[r(b,a)+\gamma \sum _{o\in O}P(o|b,a)V^{\ast }(\tau (b,a,o))\right]$$
这个公式表示，在信念状态 $(b)$ 下，采取动作 $(a)$ 能带来的最大化的预期回报。这里包括：

• 即时奖励 $(r(b,a))$
• 未来奖励的加权和，未来的信念状态由信念更新公式 $(\tau (b,a,o))$ 计算得到。

5. 维度爆炸问题

Belief MDP 的核心问题是维度爆炸，因为信念状态空间是连续的，而每个信念状态都需要计算其值函数。这在处理高维度的信念空间时，计算量会变得极为庞大，因此通常需要采用近似算法进行求解。

1.2.2 有限前瞻深度策略

这种方法的核心思想是对未来的状态和动作进行有限深度的前瞻，并基于此进行优化，类似于模型预测控制 (MPC) 的思路。

1.方法概述

1. 有限前瞻：

   • 由于 POMDP 的状态空间通常非常大，完全求解的计算量巨大，因此该方法通过对动作序列和观测进行有限步的前瞻来简化问题。
   • 图中展示了一个状态-动作-观测的搜索树，在树中，智能体从根节点（当前状态）出发，通过一系列动作和观测进行扩展，每次前瞻 $(H)$步。

2. 剪枝策略：

   • 为了减少计算量，常常会对某些不太可能的观测进行剪枝，保留更有可能出现的观测结果。这使得状态空间不会呈指数增长，优化计算资源。

3. 树结构中的节点数：

   • 图右侧给出了有限前瞻过程中的节点数计算公式，节点数量随着动作 $(A)$ 和观测 $(O)$ 的种类，以及前瞻步数 $(H)$ 指数级增加。因此，通过剪枝和合理的搜索策略来减少需要评估的节点非常重要。

2.求解步骤

• 前瞻搜索：从当前状态出发，模拟未来可能的动作和观测序列。每个动作序列对应未来一系列的状态和奖励。
• 评估策略：在每个前瞻步长结束时，对不同的动作序列进行评估，根据预期回报选择最佳的动作序列。
• 执行最优动作：基于评估的结果，执行当前最优的第一个动作，并将该动作的观测结果作为下一步的输入，重复上述过程。

3.优化技巧

• ($\alpha$)-向量技巧：用于加速计算值函数，使得每一个信念状态可以用一个超平面表示。
• 蒙特卡洛树搜索（MCTS）：该方法可以从当前状态出发，逐步扩展状态和观测序列，通过模拟未来可能的动作结果，减少计算复杂度。

1.2.3 在MDP中规划

其核心思想是将概率最大的置信状态作为实际状态来处理，类似于假设系统的状态总是最有可能的那一个。

1.主要步骤

1. 置信状态假设：

   • 假设当前最可能的置信状态代表系统的真实状态，即我们并不处理所有可能的状态，而是聚焦在当前置信度最高的那个状态。

2. 通过滤波跟踪状态：

   • 使用类似于滤波的技术来不断更新和跟踪这个置信状态的概率分布。滤波器会根据新观测来调整系统对当前状态的估计，确保我们使用的状态是最可能的。

3. 选择最优动作：

   • 在每个时刻，根据当前估计的最可能状态，选择该状态下的最优动作（通常是基于预先定义的策略或价值函数）。

2.优缺点

• 优点：该方法在计算上较为高效，因为它简化了问题，将复杂的概率分布问题转化为一个确定性问题。
• 缺点：当系统不确定性较高时（即多种状态可能同时存在），这种方法可能会失败。因为它无法主动收集更多信息来提高置信度，只依赖于被动更新的置信状态。

这类方法适用于那些不确定性较小的场景，但在高度动态且不确定性较大的环境下，可能效果不佳。

2. EPSILON 系统解析

该部分只做general的介绍，详细的流程可以参考论文及以下链接：

• https://github.com/HKUST-Aerial-Robotics/EPSILON

• EPSILON: An Efficient Planning System for Automated Vehicles in Highly Interactive Environments

• EPSILON论文解读、代码ROS2-Carla重构、实车部署全记录
  

2.1 自动驾驶决策规划现存问题

2.2 系统概述

2.3 问题描述

2.4 整体流程

Efficient Behavior Planning – Motivating Example

Efficient Behavior Planning – Guided Action Branching


Efficient Behavior Planning – Multi-agent Forward Simulation

Efficient Behavior Planning – Safety Mechanism

Efficient Behavior Planning – Policy Selection

基于时空语义走廊的轨迹生成

3. MARC 解读—— Multipolicy and Risk-aware Contingency Planning for Autonomous Driving

该部分没有听太懂，还是要结合论文去看。可参考以下链接：

• MARC: Multipolicy and Risk-Aware Contingency Planning for Autonomous
  Driving
• MARC: Multipolicy and Risk-aware Contingency Planning for Autonomous
  Driving - 论文推土机的文章
• MARC：一种安全又高效的时空联合规划的方法

4. 参考链接

• 《自动驾驶预测与决策技术》

• Part1_自动驾驶决策规划简介

• Part2_基于模型的预测方法

• Part3_路径与轨迹规划

• Part4_时空联合规划

• Part5_决策过程

• https://github.com/HKUST-Aerial-Robotics/EPSILON

• EPSILON: An Efficient Planning System for Automated Vehicles in Highly Interactive Environments

• EPSILON论文解读、代码ROS2-Carla重构、实车部署全记录
  

• MARC: Multipolicy and Risk-Aware Contingency Planning for Autonomous
  Driving

• MARC: Multipolicy and Risk-aware Contingency Planning for Autonomous
  Driving - 论文推土机的文章

• MARC：一种安全又高效的时空联合规划的方法