太原模板建站系统,广州网站建设高端,福州男同性做基网站,网络工程主要学什么就业方向决策过程 0. 前言1.决策过程的引入1.1有了planning#xff0c;为什么还需要decision-making#xff1f;1.2 决策规划的一些思考 2.马尔可夫决策过程及其关键要素2.1 马尔可夫过程2.1.1 什么是随机过程#xff1f;2.1.2 什么是马尔科夫性#xff1f;2.1.3 马尔可夫决策过程 … 决策过程 0. 前言1.决策过程的引入1.1有了planning为什么还需要decision-making1.2 决策规划的一些思考 2.马尔可夫决策过程及其关键要素2.1 马尔可夫过程2.1.1 什么是随机过程2.1.2 什么是马尔科夫性2.1.3 马尔可夫决策过程 MDP2.1.4 决策问题要素2.1.5 决策问题要素以无保护左转为例2.1.6 策略定义Policy2.1.7 MDP目标和策略2.1.8 无保护左转场景示例MDP的目标及策略定义贝尔曼方程求解过程简单代码实现 2.2 价值迭代与策略迭代2.2.1 价值迭代价值迭代Value Iteration的解释价值迭代的伪代码主要的难点和瓶颈 2.2.2 价值迭代举例Gridworld说明迭代过程迭代1次后的结果迭代2次后的结果迭代3次后的结果1000次迭代后趋于稳定自动驾驶场景举例 2.2.3 策略迭代基本概念策略迭代举例 3. 参考 0. 前言 本文主要记录课程《自动驾驶预测与决策技术》的学习过程难免会有很多纰漏感谢指正。 课程链接https://www.shenlanxueyuan.com/my/course/700 相关笔记链接 Part1_自动驾驶决策规划简介 Part2_基于模型的预测方法 Part3_路径与轨迹规划 Part4_时空联合规划 1.决策过程的引入
1.1有了planning为什么还需要decision-making
keypoint交互、不确定性
Geometric World几何世界– Probabilistic World概率世界几何世界关注的是空间的静态性质而概率世界关注的是动态的、不确定的过程。
在自动驾驶系统中planning规划和decision-making决策虽然紧密相关但它们各自扮演着不同的角色都是确保自动驾驶车辆安全、高效运行的重要组成部分。
a.Planning规划
规划通常指的是自动驾驶系统中的路径规划功能。它的核心任务是基于车辆的当前位置、目标位置以及周围环境信息生成一条从起点到终点的最优路径。这包括 全局路径规划在高层次上规划出从起点到目标地点的最佳路径这可能涉及跨越多个道路段、交叉口等。 局部路径规划在每个时刻根据当前环境和交通状况调整并优化行驶路径。这通常涉及对最近几米至几百米的路线进行细化处理。 避障处理动态障碍物如行人、其他车辆和静态障碍物如路障的问题确保路径的安全性和有效性。
b.Decision-Making决策
决策涉及在复杂的交通环境中做出具体的驾驶决策。这包括 交通规则遵循遵守交通信号灯、标志、限速等规则。 交互决策与其他交通参与者的互动例如在复杂交叉口时如何选择合适的行驶策略或者如何应对突发状况如另一辆车突然变道。 优先级处理决定在某些情况下的优先权问题比如在遇到紧急车辆时的让行策略。
c.为什么都需要 复杂性和动态性虽然路径规划可以为车辆提供一条理想的路线但现实世界中情况复杂且不断变化。决策系统需要实时处理各种动态因素如其他车辆的行为、交通信号的变化等。 安全性决策系统确保车辆在实际道路上安全行驶通过对各种复杂情况的判断调整规划结果以应对意外和突发事件。 交通规则和法规规划可能无法完全满足所有交通规则的要求决策系统负责确保车辆在遵守交通法规的同时执行适当的行驶策略。 用户体验决策系统可以优化驾驶体验使得车辆在各种情况下能够平稳、舒适地运行而不仅仅是按照静态的路径规划进行行驶。
d.总结
规划主要关注从起点到目标的静态路径生成适合处理较为稳定和已知的环境但对于动态和复杂的情况适应性较差。决策则侧重于实时应对不确定性和动态变化确保车辆在实际行驶过程中能够适应各种突发情况和环境变化从而更灵活地实现目标。
1.2 决策规划的一些思考
在运动规划和控制模块的基础上为什么还需要决策过程
每个障碍物有一定的不确定性且对手车也会根据自车的决策做出不同的action。
每种方案实际上对应一种决策每种决策实际上对应一簇规划。
智能驾驶决策的应用场景路径规划、交通行为预测、避障决策、交叉路口处理、自主停车、道路选择等等。
关键问题决策问题如何定义决策空间如何求解 2.马尔可夫决策过程及其关键要素
2.1 马尔可夫过程 2.1.1 什么是随机过程
随机过程Stochastic Process是一个数学对象它描述了一个系统的状态如何随着时间演变其中系统的状态是随机的。具体来说随机过程是一个随时间变化的随机变量的集合每个时间点都有一个对应的随机变量。 状态空间 随机过程的状态空间是系统可能的所有状态的集合。状态空间可以是离散的如有限个状态的集合或连续的如实数集。 时间参数 随机过程可以在离散时间或连续时间上定义。离散时间随机过程在一系列离散的时间点上定义状态如每天、每月而连续时间随机过程在连续的时间段内定义状态如每秒钟。 样本路径 随机过程的一个可能的状态序列称为样本路径或轨迹。每个样本路径表示在给定随机过程下系统可能的行为模式。 典型例子 布朗运动Brownian Motion一种描述粒子在液体或气体中随机运动的过程。马尔科夫链Markov Chain状态转移只依赖于当前状态而与过去无关的离散时间随机过程。泊松过程Poisson Process用于描述稀疏事件的到达时间如电话呼叫的到达或事故发生的次数。
2.1.2 什么是马尔科夫性
马尔科夫性Markov Property是指一个过程的未来状态只依赖于当前状态而与过去的历史状态无关。这个概念源自于马尔科夫过程Markov Process它在概率论和统计学中扮演着重要角色。 定义 马尔科夫性强调的是记忆无关性memorylessness。即系统的未来状态只取决于当前状态而不依赖于系统的过去状态。形式上对于一个马尔科夫过程给定当前状态 ( S t S_t St)未来状态 ( S t 1 S_{t1} St1) 的条件概率分布不依赖于过去的状态序列 ( S t − 1 , S t − 2 , … , S 0 S_{t-1}, S_{t-2}, \ldots, S_0 St−1,St−2,…,S0)。 数学表示 设 ( { S t } t ≥ 0 \{S_t\}_{t \geq 0} {St}t≥0) 为一个随机过程若对所有的 ( t ≥ 0 t \geq 0 t≥0) 和所有的状态 ( s 0 , s 1 , … , s t , s t 1 s_0, s_1, \ldots, s_t, s_{t1} s0,s1,…,st,st1)有 P ( S t 1 s t 1 ∣ S t s t , S t − 1 s t − 1 , … , S 0 s 0 ) P ( S t 1 s t 1 ∣ S t s t ) P(S_{t1} s_{t1} \mid S_t s_t, S_{t-1} s_{t-1}, \ldots, S_0 s_0) P(S_{t1} s_{t1} \mid S_t s_t) P(St1st1∣Stst,St−1st−1,…,S0s0)P(St1st1∣Stst) 则称该过程具有马尔科夫性。 类型 离散时间马尔科夫链Discrete-Time Markov Chain在离散时间步骤中发生的马尔科夫过程状态的转移依赖于当前状态和固定的转移概率矩阵。连续时间马尔科夫过程Continuous-Time Markov Process在连续时间中发生的马尔科夫过程状态的转移通常由到达率或强度来描述。
2.1.3 马尔可夫决策过程 MDP 马尔科夫决策过程Markov Decision Process, MDP是一种用于描述和解决涉及决策的随机过程的数学框架常用于优化决策策略。在MDP中决策者在每个时间步骤选择一个行动根据所选行动和当前状态系统转移到一个新的状态并获得相应的奖励。
关键要素 状态空间 S t a t e S p a c e State Space StateSpace 设 ( S S S ) 为所有可能状态的集合。系统在每个时间步骤都处于状态 ( s ∈ S s \in S s∈S )。 动作空间 A c t i o n S p a c e Action Space ActionSpace 设 ( A A A) 为所有可能动作的集合。决策者可以在每个状态下选择一个动作 ( a ∈ A a \in A a∈A)。 转移概率 T r a n s i t i o n P r o b a b i l i t y Transition Probability TransitionProbability 转移概率 ( P ( s ′ ∣ s , a ) P(s \mid s, a) P(s′∣s,a)) 表示在当前状态 ( s s s) 下采取动作 ( a a a ) 后转移到状态 ( s ′ s s′) 的概率。 奖励函数 R e w a r d F u n c t i o n Reward Function RewardFunction 奖励函数 ( R ( s , a ) R(s, a) R(s,a)) 表示在状态 ( s s s ) 下采取动作 ( a a a) 所获得的即时奖励。 策略 P o l i c y Policy Policy 策略 ( π \pi π) 是一个映射将每个状态 ( s s s) 映射到一个动作 ( a a a)。策略可以是确定性的即在每个状态下选择一个特定的动作或随机的即在每个状态下选择动作的概率分布。 价值函数 V a l u e F u n c t i o n Value Function ValueFunction 状态价值函数 ( V π ( s ) V^\pi(s) Vπ(s)) 表示在策略 ( π \pi π) 下从状态 ( s s s) 开始的预期总奖励。动作价值函数 ( Q π ( s , a ) Q^\pi(s, a) Qπ(s,a)) 表示在策略 ( π \pi π) 下从状态 ( s s s) 开始采取动作 ( a a a) 的预期总奖励。
目标
在MDP中决策者的目标通常是找到一个最优策略 ( π ∗ \pi^* π∗)使得从任何状态 ( s s s) 开始的预期总奖励最大化。这个最优策略可以通过以下方法求解
动态规划使用贝尔曼方程Bellman Equation递归地计算价值函数。强化学习通过与环境的交互来学习最佳策略如Q学习Q-learning和策略梯度方法Policy Gradient Methods。
2.1.4 决策问题要素
交互主体 Agent、Environment
交互内容Action、 State、Reward MDP 五元组 马尔可夫决策过程MDP在自动驾驶中的使用可以帮助自动驾驶系统做出最佳的驾驶决策。MDP 可通过以下五个关键元素来描述决策过程的
状态集合 ( S S S )代表环境的所有可能状态。在自动驾驶中状态可以包括车辆的位置、速度、道路状况、周围车辆和行人的位置等。动作集合 ( A A A)代表系统可以采取的所有可能动作。在自动驾驶中这些动作可以包括加速、刹车、转向等。奖励函数 ( R R R)对于每一个状态-动作对 ( ( s , a ) (s, a) (s,a))奖励函数定义了执行该动作后的即时奖励。在自动驾驶中奖励可以反映驾驶的安全性、舒适性、效率等例如避开碰撞、保持车道、减少油耗等。状态转移概率 ( P s a P_{sa} Psa)定义了在当前状态 ( s s s) 下采取动作 ( a a a ) 后转移到下一个状态 ( s ′ s s′ ) 的概率分布。在自动驾驶中这个概率可以表示在不同路况下不同驾驶动作的结果。例如在湿滑路面上转向的结果可能不如在干燥路面上那么可预测。折扣因子 ( γ \gamma γ)用于计算累积奖励的折扣因子反映未来奖励的相对重要性。折扣因子通常用于平衡短期和长期的奖励。
在自动驾驶中的具体使用
感知和建模环境自动驾驶系统首先通过传感器感知环境识别当前的状态 ( s t s_t st)。策略选择系统根据当前状态 ( s t s_t st) 和决策策略通常是通过强化学习训练得出选择一个动作 ( a t a_t at)如转向、加速或刹车。执行动作并反馈系统执行选择的动作并通过感知更新环境状态 ( s t 1 s_{t1} st1)。同时系统会得到即时的奖励 ( r t r_t rt )。学习和优化系统通过不断地进行状态-动作-奖励-新状态的循环从而学习最优策略以最大化累积奖励。
关键应用场景
路径规划MDP 可以帮助自动驾驶车辆在复杂的道路环境中规划出一条最优路径同时避免障碍物、遵循交通规则。避障在动态环境中例如有行人或其他车辆突然出现时MDP 帮助系统快速做出安全的决策。驾驶行为优化MDP 可以用于优化驾驶行为如节能驾驶或平稳驾驶从而提高乘坐体验和车辆效率。
MDP 的动态过程 2.1.5 决策问题要素以无保护左转为例
无保护左转是指在没有专用信号灯保护的情况下车辆需要在流动的对向车流中找到合适的时机进行左转。这是自动驾驶中的一个复杂场景要求系统能够在动态环境中做出及时且安全的决策。
状态集合 ( S S S )
在无保护左转的场景中状态集合包括车辆自身的位置和速度、对向车流的状况如对向车辆的速度和距离、路口的几何信息如车道宽度、信号灯状态、行人和其他潜在的障碍物。
动作集合 ( A A A )
在这个场景下的动作集合包括
等待保持当前位置不动开始左转根据环境情况调整转向角度和速度适时停止或减速在发现潜在危险时停止或减速
奖励函数 ( R R R)
奖励函数在无保护左转中主要考虑以下因素
正向奖励成功完成左转或者在合适时机内安全完成左转。负向奖励发生危险行为如与对向车辆过于接近、紧急刹车、或者不得不在危险情况下强行左转。
奖励函数会根据这些因素给予相应的奖励或惩罚。
状态转移概率 ( P s a P_{sa} Psa)
状态转移概率描述了在执行某个动作后环境状态如何变化。对于无保护左转系统需要根据对向车辆的速度和距离、行人的动态行为、以及自身动作的效果如加速、转向预测下一个可能的状态。例如
如果对向车流速度较慢且距离较远左转可能是安全的系统会转移到成功完成左转的状态。如果对向车流突然加速或有车辆突然出现系统可能需要重新评估是否继续左转或者进入紧急停止的状态。
折扣因子 ( γ \gamma γ)
折扣因子在这里用于平衡短期与长期的决策。例如系统可能会更关注即刻的安全性短期奖励而不是过于冒险以求快速完成左转长期奖励。通常折扣因子会设定在一个相对较高的值以确保系统优先考虑立即的安全。
动态过程描述 初始状态识别 车辆接近路口自动驾驶系统通过感知模块识别当前状态 ( S 0 S_0 S0)包括自身的位置、速度对向车流的状况以及路口的结构信息。 策略选择 系统通过计算在当前状态下选择最优动作 ( A 0 A_0 A0)。假设此时对向车流较密系统选择保持等待状态继续观察对向车流的变化。 状态更新 随着对向车辆的变化如某辆车减速或通过路口状态 ( S 1 S_1 S1) 更新。系统重新评估并选择新的动作 ( A 1 A_1 A1)例如开始缓慢左转。 动作执行与反馈 系统执行左转动作并实时监控对向车流和自身车辆的动态。此时如果检测到安全系统会继续加速完成左转否则会减速或停止以避免碰撞。 迭代决策 在整个过程中系统不断地根据新的感知数据更新状态迭代地选择最优动作直到成功完成左转或决定暂停操作以等待更好的机会。 奖励评估 一旦左转完成系统根据整个过程中的决策结果计算最终的奖励。如果操作安全且顺利完成系统将获得正向奖励如果中途出现危险操作或需要紧急避险则相应地减少奖励。
2.1.6 策略定义Policy
确定型策略求解 -- 三板斧采样、搜索、优化
随机型策略求解MDP/POMDP -- Bellman 原理 -- optimal solution -- reward 奖励函数 以无保护左转为例
在无保护左转的场景中随机型策略Stochastic Policy 是指在每一个状态下自动驾驶系统不确定地选择动作而是根据某种概率分布来选择动作。与确定性策略每个状态下只选择一个固定动作不同随机型策略允许系统在同一个状态下有多个可能的动作选择每个动作都有一定的概率。
随机型策略的定义
随机型策略通常用 ( π ( a ∣ s ) \pi(a|s) π(a∣s)) 表示它定义了在状态 ( s ) s) s) 下选择动作 ( a a a) 的概率分布。对于无保护左转场景策略 ( π ( a ∣ s ) \pi(a|s) π(a∣s)) 可以这样理解
在特定状态 ( s s s ) 下如车辆正在接近路口且对向车流较稀疏策略可能定义以下概率分布 等待 ( a 1 a_1 a1) ( π ( a 1 ∣ s ) 0.3 \pi(a_1|s) 0.3 π(a1∣s)0.3 )30% 的概率保持等待左转 ( a 2 a_2 a2) ( π ( a 2 ∣ s ) 0.7 \pi(a_2|s) 0.7 π(a2∣s)0.7 )70% 的概率尝试左转
这种随机性允许系统在相似的状态下尝试不同的动作探索不同的策略组合。
求解随机型策略
求解随机型策略通常依赖于强化学习中的策略梯度方法或动态规划方法。这里介绍一些常见的求解方法
a. 策略梯度方法
策略梯度方法直接优化策略的参数化表示通常用于深度强化学习场景。它通过最大化累计奖励的期望来更新策略参数。 策略参数化假设策略由参数 ( θ \theta θ) 表示即 ( π θ ( a ∣ s ) \pi_{\theta}(a|s) πθ(a∣s)) 是依赖于参数 ( θ \theta θ ) 的概率分布。 目标函数定义累积奖励的期望 ( J ( θ ) E π θ [ R ] J(\theta) \mathbb{E}_{\pi_{\theta}} [R] J(θ)Eπθ[R])其中 ( R ) R) R) 是累积奖励。目标是最大化 ( J ( θ ) J(\theta) J(θ))。 策略梯度使用策略梯度算法如 REINFORCE 算法更新参数 θ ← θ α ∇ θ J ( θ ) \theta \leftarrow \theta \alpha \nabla_{\theta} J(\theta) θ←θα∇θJ(θ) 其中( α \alpha α ) 是学习率梯度 ( ∇ θ J ( θ ) \nabla_{\theta} J(\theta) ∇θJ(θ)) 可以通过样本估计得到。 更新策略每次通过梯度上升方法更新参数 ( θ \theta θ )并调整策略 ( π θ ( a ∣ s ) \pi_{\theta}(a|s) πθ(a∣s))使得在状态 ( s s s ) 下选择最优动作的概率更高。
b. 动态规划方法
如果状态和动作空间有限且有已知的模型如状态转移概率 ( P s a ) P_{sa} ) Psa)可以使用动态规划方法求解最优随机型策略。 贝尔曼方程构建贝尔曼期望方程描述状态值函数 ( V π ( s ) ) V^{\pi}(s) ) Vπ(s)) V π ( s ) ∑ a π ( a ∣ s ) ∑ s ′ P s a ( s ′ ) [ R ( s , a , s ′ ) γ V π ( s ′ ) ] V^{\pi}(s) \sum_{a} \pi(a|s) \sum_{s} P_{sa}(s) \left[ R(s, a, s) \gamma V^{\pi}(s) \right] Vπ(s)a∑π(a∣s)s′∑Psa(s′)[R(s,a,s′)γVπ(s′)] 或者动作值函数 ( Q π ( s , a ) Q^{\pi}(s, a) Qπ(s,a)) Q π ( s , a ) ∑ s ′ P s a ( s ′ ) [ R ( s , a , s ′ ) γ ∑ a ′ π ( a ′ ∣ s ′ ) Q π ( s ′ , a ′ ) ] Q^{\pi}(s, a) \sum_{s} P_{sa}(s) \left[ R(s, a, s) \gamma \sum_{a} \pi(a|s) Q^{\pi}(s, a) \right] Qπ(s,a)s′∑Psa(s′)[R(s,a,s′)γa′∑π(a′∣s′)Qπ(s′,a′)] 或者动作值函数 ( Q π ( s , a ) Q^{\pi}(s, a) Qπ(s,a)) 策略迭代通过以下步骤反复进行 策略评估在当前策略 ( π \pi π) 下计算状态值函数 ( V π ( s ) V^{\pi}(s) Vπ(s)) 或动作值函数 ( Q π ( s , a ) ) Q^{\pi}(s, a)) Qπ(s,a))。
策略改进根据状态值或动作值函数更新策略 ( π \pi π )以增加最优动作的选择概率。
收敛条件策略迭代直至策略收敛即不再有改进为止得到的策略即为最优随机型策略。
在无保护左转场景中的应用 策略探索随机型策略允许系统在类似状态下探索不同的左转决策从而避免因单一策略可能导致的潜在问题例如过于保守或过于激进的驾驶行为。 风险管理在高风险场景下如对向车流密集随机型策略可以分配一定的概率给“等待”动作从而减少因冒险左转可能带来的风险。
2.1.7 MDP目标和策略
目标选择能够最大化累积奖励期望的动作
奖励函数 R 收益函数 Gt
奖励函数的时间序列 动作价值函数 2.1.8 无保护左转场景示例
在无保护左转场景中使用不确定型随机型策略的马尔可夫决策过程MDP可以帮助自动驾驶系统应对环境中的不确定性。、 MDP的目标及策略定义 MDP的目标 MDP的目标是最大化期望累计奖励即使得车辆在无保护左转过程中尽可能成功地完成左转并避免事故。公式化的目标函数为 maximize E π [ G 0 ] E π [ ∑ t 0 ∞ γ t R t 1 ] \text{maximize} \quad \mathbb{E}_{\pi} \left[ G_0 \right] \mathbb{E}_{\pi} \left[ \sum_{t0}^{\infty} \gamma^t R_{t1} \right] maximizeEπ[G0]Eπ[t0∑∞γtRt1] 其中 ( E π \mathbb{E}_{\pi} Eπ ) 是在策略 ( $\pi $) 下的期望值。( G 0 G_0 G0) 是从初始状态 ( $S_0 $) 开始的累计奖励。( γ \gamma γ) 是折扣因子反映了未来奖励的重要性。 随机型策略定义 随机型策略 ( π ( a ∣ s ) \pi(a|s) π(a∣s) ) 定义了在状态 ( s s s) 下采取动作 ( a a a) 的概率。它允许在同一状态下选择不同的动作并通过概率的方式平衡不同动作之间的权重。 策略表示 π ( a ∣ s ) P ( A t a ∣ S t s ) \pi(a|s) P(A_t a \mid S_t s) π(a∣s)P(Ata∣Sts) 在无保护左转场景中可能的动作包括“等待”例如 ( a 1 a_1 a1)和“尝试左转”例如 ( a 2 a_2 a2 )。 策略示例 等待( a_1 ) ( π ( a 1 ∣ s ) 0.7 ) ( \pi(a_1|s) 0.7 ) (π(a1∣s)0.7)尝试左转( a 2 a_2 a2)( p i ( a 2 ∣ s ) 0.3 pi(a_2|s) 0.3 pi(a2∣s)0.3 ) 贝尔曼方程求解过程 使用贝尔曼方程求解涉及到递归计算值函数并通过策略迭代最终找到最优策略。以下是具体步骤 a. 状态和值函数定义 状态 ( s s s)包括车辆在路口时的位置信息、对向车辆的速度和距离、交通灯状态等。动作 ( a a a)在每个状态下可采取的动作例如“等待”或“尝试左转”。奖励 ( R ( s , a , s ′ ) R(s,a,s) R(s,a,s′))即时奖励例如成功左转会带来正奖励碰撞则带来负奖励等待则可能带来小的负奖励。 b. 贝尔曼期望方程用于策略评估 策略评估是指在给定策略 ( π \pi π) 的情况下计算每个状态的值函数 ( V π ( s ) V^{\pi}(s) Vπ(s))。 贝尔曼期望方程 V π ( s ) ∑ a ∈ A π ( a ∣ s ) ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ V π ( s ′ ) ] V^{\pi}(s) \sum_{a \in A} \pi(a|s) \sum_{s \in S} P(s|s,a) \left[ R(s,a,s) \gamma V^{\pi}(s) \right] Vπ(s)a∈A∑π(a∣s)s′∈S∑P(s′∣s,a)[R(s,a,s′)γVπ(s′)] 其中 ( P ( s ′ ∣ s , a ) P(s|s,a) P(s′∣s,a)) 是从状态 ( s s s) 采取动作 ( a a a) 后转移到状态 ( s ′ s s′) 的概率。( R ( s , a , s ′ ) R(s,a,s) R(s,a,s′) ) 是从 ( s s s) 到 ( s ′ s s′) 所获得的即时奖励。 步骤 初始化值函数 ( V π ( s ) V^{\pi}(s) Vπ(s))通常初始为0或小的随机值。迭代更新值函数使用贝尔曼期望方程计算每个状态的值函数直到 ( V π ( s ) V^{\pi}(s) Vπ(s)) 收敛。 c. 贝尔曼最优方程用于策略改进 策略改进是指在策略评估之后利用状态值函数来更新策略使得在每个状态下都选择最优动作即能够带来最大值函数的动作。 贝尔曼最优方程 V ∗ ( s ) max a ∈ A ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ V ∗ ( s ′ ) ] V^*(s) \max_{a \in A} \sum_{s \in S} P(s|s,a) \left[ R(s,a,s) \gamma V^*(s) \right] V∗(s)a∈Amaxs′∈S∑P(s′∣s,a)[R(s,a,s′)γV∗(s′)] 步骤 策略改进利用贝尔曼最优方程更新策略 ($ \pi(s) $)以使每个状态下选择最优动作的概率更大。 π ′ ( a ∣ s ) arg max a ∈ A ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ V π ( s ′ ) ] \pi(a|s) \arg\max_{a \in A} \sum_{s \in S} P(s|s,a) \left[ R(s,a,s) \gamma V^{\pi}(s) \right] π′(a∣s)arga∈Amaxs′∈S∑P(s′∣s,a)[R(s,a,s′)γVπ(s′)] 重复策略评估和策略改进直到策略 ($ \pi $) 收敛即策略不再变化。 d. 示例无保护左转的决策过程 假设我们在无保护左转的场景中使用贝尔曼方程进行求解 状态 当前车辆的位置和速度。对向车辆的速度和距离。环境信息如是否有其他车辆在进行左转。 动作 ( a_1 )等待。( a_2 )尝试左转。 奖励 成功左转 ( R ( s , a 2 , s ′ ) 10 R(s,a_2,s) 10 R(s,a2,s′)10)。发生碰撞 ( R ( s , a 2 , s ′ ) − 100 R(s,a_2,s) -100 R(s,a2,s′)−100 )。等待 ( R ( s , a 1 , s ′ ) − 1 R(s,a_1,s) -1 R(s,a1,s′)−1)消耗时间。 贝尔曼期望方程求解 初始状态值函数设为 0 0 0。根据贝尔曼期望方程反复计算每个状态下的值函数评估当前策略的表现。 策略改进 根据贝尔曼最优方程调整策略增加选择成功左转的动作概率减少选择等待的概率假设在特定情况下左转是安全的。 迭代 重复策略评估和策略改进直到值函数和策略收敛。 简单代码实现
此代码实现了状态表示、动作空间的扩展并通过贝尔曼方程进行策略评估和改进。
导入必要的库并定义常量
#include iostream
#include vector
#include map
#include cmath
#include algorithm
#include tuple
#include limitsconst double GAMMA 0.9; // 折扣因子
const double THRESHOLD 1e-6; // 策略评估中的收敛阈值定义状态和动作
// 定义动作类型
enum Action { WAIT, // 等待ACCELERATE_WAIT, // 加速等待DECELERATE_WAIT, // 减速等待TURN_LEFT, // 左转ACCELERATE_TURN_LEFT,// 加速左转DECELERATE_TURN_LEFT // 减速左转
};// 定义状态结构体
struct State {double car_position; // 车辆到十字路口的距离double car_speed; // 当前车辆的速度double oncoming_car_position; // 对面来车到路口的距离double oncoming_car_speed; // 对面来车的速度// 重载 运算符以用于在 map 中作为 keybool operator(const State other) const {return std::tie(car_position, car_speed, oncoming_car_position, oncoming_car_speed) std::tie(other.car_position, other.car_speed, other.oncoming_car_position, other.oncoming_car_speed);}
};定义策略和奖励函数
// 策略结构体包含每个状态下动作的概率分布
struct Policy {std::mapState, std::mapAction, double actionProbabilities;double getProbability(const State s, Action a) const {return actionProbabilities.at(s).at(a);}void setProbability(const State s, Action a, double prob) {actionProbabilities[s][a] prob;}
};// 奖励函数定义
double getReward(const State s, Action a, const State s_prime) {// 根据不同的状态和动作对奖励函数进行设定if (a TURN_LEFT s_prime.car_position 0 s_prime.oncoming_car_position 5) return 10; // 成功左转if (a TURN_LEFT s_prime.car_position 0 s_prime.oncoming_car_position 5) return -100; // 发生碰撞if (a WAIT) return -1; // 等待if (a ACCELERATE_WAIT || a DECELERATE_WAIT) return -0.5; // 等待时加速/减速略有惩罚return 0;
}定义状态转移概率
// 状态转移函数定义
double getTransitionProbability(const State s, Action a, const State s_prime) {// 根据动作定义不同的状态转移概率if (a TURN_LEFT) {if (s_prime.car_position 0 s_prime.oncoming_car_position 5) return 0.8; // 成功左转的概率if (s_prime.car_position 0 s_prime.oncoming_car_position 5) return 0.2; // 发生碰撞的概率}if (a WAIT) {if (s_prime.car_position s.car_position - s.car_speed) return 1.0; // 继续等待}// 加速/减速等待的状态转移概率if (a ACCELERATE_WAIT) {if (s_prime.car_speed s.car_speed 1) return 1.0;}if (a DECELERATE_WAIT) {if (s_prime.car_speed s.car_speed - 1) return 1.0;}// 加速/减速左转的状态转移概率if (a ACCELERATE_TURN_LEFT || a DECELERATE_TURN_LEFT) {// 这里可以进一步细化转移概率}return 0.0;
}贝尔曼方程的实现
void policyEvaluation(const std::vectorState states, Policy policy, std::mapState, double V) {double delta;do {delta 0;for (const State s : states) {double v V[s];double newValue 0.0;for (Action a : {WAIT, ACCELERATE_WAIT, DECELERATE_WAIT, TURN_LEFT, ACCELERATE_TURN_LEFT, DECELERATE_TURN_LEFT}) {double actionValue 0.0;for (const State s_prime : states) {double prob getTransitionProbability(s, a, s_prime);actionValue prob * (getReward(s, a, s_prime) GAMMA * V[s_prime]);}newValue policy.getProbability(s, a) * actionValue;}V[s] newValue;delta std::max(delta, std::fabs(v - V[s]));}} while (delta THRESHOLD); // 迭代直到值函数收敛
}void policyImprovement(const std::vectorState states, Policy policy, const std::mapState, double V) {bool policyStable true;for (const State s : states) {Action bestAction;double bestActionValue -std::numeric_limitsdouble::infinity();for (Action a : {WAIT, ACCELERATE_WAIT, DECELERATE_WAIT, TURN_LEFT, ACCELERATE_TURN_LEFT, DECELERATE_TURN_LEFT}) {double actionValue 0.0;for (const State s_prime : states) {double prob getTransitionProbability(s, a, s_prime);actionValue prob * (getReward(s, a, s_prime) GAMMA * V.at(s_prime));}if (actionValue bestActionValue) {bestActionValue actionValue;bestAction a;}}// 更新策略if (policy.getProbability(s, bestAction) ! 1.0) {policyStable false;}policy.setProbability(s, bestAction, 1.0);for (Action a : {WAIT, ACCELERATE_WAIT, DECELERATE_WAIT, TURN_LEFT, ACCELERATE_TURN_LEFT, DECELERATE_TURN_LEFT}) {if (a ! bestAction) {policy.setProbability(s, a, 0.0);}}}if (policyStable) {std::cout Policy is stable. std::endl;}
}策略迭代的完整过程
void policyIteration(std::vectorState states, Policy policy) {std::mapState, double V;for (const State s : states) {V[s] 0.0; // 初始化值函数}bool policyStable false;while (!policyStable) {policyEvaluation(states, policy, V); // 策略评估policyImprovement(states, policy, V); // 策略改进}
}int main() {// 定义状态集假设有几个离散状态State s0 {10, 1, 15, 1}; // 初始状态车与路口距离10米速度1 m/s对面车距路口15米State s1 {0, 0, 0, 0}; // 左转成功状态State s2 {5, 1, 5, 1}; // 危险状态车距路口5米对面车也距路口5米std::vectorState states {s0, s1, s2};// 初始化策略假设初始时每个动作均等概率Policy policy;for (const State s : states) {policy.setProbability(s, WAIT, 1.0 / 6);policy.setProbability(s, ACCELERATE_WAIT, 1.0 / 6);policy.setProbability(s, DECELERATE_WAIT, 1.0 / 6);policy.setProbability(s, TURN_LEFT, 1.0 / 6);policy.setProbability(s, ACCELERATE_TURN_LEFT, 1.0 / 6);policy.setProbability(s, DECELERATE_TURN_LEFT, 1.0 / 6);}// 执行策略迭代policyIteration(states, policy);// 输出最终的策略for (const auto pair : policy.actionProbabilities) {const State s pair.first;std::cout State: (pos s.car_position , speed s.car_speed , oncoming_pos s.oncoming_car_position , oncoming_speed s.oncoming_car_speed )\n;for (const auto action_prob : pair.second) {std::cout Action: action_prob.first - Prob: action_prob.second std::endl;}}return 0;
}代码解析
状态与动作表示使用了结构体 State 表示状态Action 表示动作。状态包含了车辆与对面车辆的位置信息和速度信息。策略表示使用 Policy 结构体来表示策略每个状态下的动作有相应的概率。贝尔曼方程实现通过 policyEvaluation 函数实现值函数的迭代更新并使用 policyImprovement 函数进行策略改进。策略迭代在 policyIteration 函数中循环进行策略评估和策略改进直到策略稳定。
运行说明
在该代码中假设我们只有三个离散状态和一套初始策略通过策略迭代最终会得出一个收敛的最优策略。你可以根据实际需求增加状态集和定义更精细的状态转移概率及奖励函数。
2.2 价值迭代与策略迭代
2.2.1 价值迭代 价值迭代Value Iteration的解释
价值迭代是一种动态规划算法用于求解马尔可夫决策过程MDP的最优策略。与策略迭代不同价值迭代直接通过更新值函数来逼近最优值函数并从中导出最优策略。它不需要在每个迭代步骤中显式地评估和改进策略而是通过贝尔曼最优方程的迭代来收敛到最优值函数。
贝尔曼最优方程
贝尔曼最优方程定义了最优值函数 ( V ∗ ( s ) V^*(s) V∗(s)) 的递推关系 V ∗ ( s ) max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ V ∗ ( s ′ ) ] V^*(s) \max_{a} \sum_{s} P(s|s,a) \left[ R(s,a,s) \gamma V^*(s) \right] V∗(s)amaxs′∑P(s′∣s,a)[R(s,a,s′)γV∗(s′)] 其中
( V ∗ ( s ) V^*(s) V∗(s)) 是状态 ( s s s) 的最优值函数。( a a a) 是在状态 ( s s s) 下可采取的动作。( P ( s ′ ∣ s , a ) P(s|s,a) P(s′∣s,a)) 是从状态 ( s s s) 经过动作 ( a a a) 转移到状态 ( s ′ s s′) 的概率。( R ( s , a , s ′ ) R(s,a,s) R(s,a,s′)) 是采取动作 ( a a a) 后从状态 ( s s s ) 转移到状态 ( s ′ s s′) 所获得的即时奖励。( γ \gamma γ) 是折扣因子控制未来奖励的重要性。
价值迭代的过程
价值迭代的核心是将贝尔曼最优方程转化为一种更新规则直接对值函数进行迭代计算直到收敛为止。具体步骤如下 初始化为每个状态 ( s s s ) 设定初始值 ( V ( s ) V(s) V(s))通常可以设置为 0 或一个任意值。 值函数更新对于每个状态 ( s s s )更新其值函数 ( V ( s ) V(s) V(s) ) V ( s ) ← max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ V ( s ′ ) ] V(s) \leftarrow \max_{a} \sum_{s} P(s|s,a) \left[ R(s,a,s) \gamma V(s) \right] V(s)←amaxs′∑P(s′∣s,a)[R(s,a,s′)γV(s′)] 收敛检查重复步骤 2直到 ($ V(s) $) 的变化在所有状态 ( $s $) 上都小于预定的阈值如 ( $\epsilon $)即认为值函数已收敛。 提取策略当值函数 ( V ( s ) V(s) V(s)) 收敛后可以根据最优值函数从每个状态 ( s s s) 选择最优动作 ( a ∗ a^* a∗) π ∗ ( s ) arg max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ V ( s ′ ) ] \pi^*(s) \arg\max_{a} \sum_{s} P(s|s,a) \left[ R(s,a,s) \gamma V(s) \right] π∗(s)argamaxs′∑P(s′∣s,a)[R(s,a,s′)γV(s′)] 价值迭代将贝尔曼最优方程转为更新规则
价值迭代的关键在于将贝尔曼最优方程转化为一种迭代更新规则。具体来说价值迭代通过反复应用贝尔曼最优方程的右侧部分来更新值函数。每次迭代中值函数 ( V ( s ) V(s) V(s)) 在每个状态下都被更新为其当前值和未来预期奖励的最大可能值。通过这种迭代值函数逐渐逼近最优值函数 ( V ∗ ( s ) V^*(s) V∗(s))。
这一过程可以看作是“修正”当前值函数使其更接近最优值函数。当值函数不再发生显著变化时价值迭代收敛到最优解从而得到最优策略。
价值迭代的伪代码
通过反复更新值函数来逼近最优值函数并从中提取最优策略。
输入:S: 状态空间A: 动作空间P(s|s,a): 状态转移概率函数R(s,a,s): 奖励函数γ: 折扣因子 (0 ≤ γ 1)θ: 收敛阈值 (一个很小的正数)输出:V: 状态值函数V(s) 是状态 s 的最优值π*: 最优策略初始化:对于所有 s ∈ S, V(s) ← 0重复执行 (迭代):Δ ← 0对于每个状态 s ∈ S:v ← V(s) // 存储当前状态 s 的旧值V(s) ← max_a Σ_s P(s|s,a) * [R(s,a,s) γ * V(s)] // 更新值函数Δ ← max(Δ, |v - V(s)|) // 记录值函数的最大变化量如果 Δ θ, 则退出循环 (值函数已收敛)提取策略:对于每个状态 s ∈ S:π*(s) ← argmax_a Σ_s P(s|s,a) * [R(s,a,s) γ * V(s)] // 提取最优策略返回:V, π* // 返回最终的最优值函数和最优策略伪代码说明 初始化: 将所有状态的值函数 ( V(s) ) 初始化为 0 或者任意一个初始值。 主循环: 通过一个重复执行的循环逐步更新每个状态的值函数 ( V(s) )。在每次迭代中对于每个状态 ( s )计算可能采取的所有动作的期望值并将当前状态的值函数更新为这些期望值的最大值。记录值函数变化的最大差异 ( Δ )如果这个差异小于阈值 ( θ )则认为值函数已经收敛停止迭代。 策略提取: 在值函数收敛后针对每个状态 ( s )选择使期望值最大的动作作为最优策略 ( π ∗ ( s ) π^*(s) π∗(s))。 返回: 返回最终的最优值函数 ( V ) 和最优策略 ( π ∗ ( s ) π^*(s) π∗(s))。
价值迭代的核心
伪代码展示了价值迭代的两个关键部分值函数更新和策略提取。值函数更新是通过贝尔曼最优方程的递归形式来实现的而策略提取则基于已经收敛的值函数来选择最优动作。
主要的难点和瓶颈
在自动驾驶中使用马尔可夫决策过程MDP和价值迭代方法来解决决策问题尤其是像无保护左转这样复杂的交通场景时存在几个主要的难点和瓶颈 状态空间的复杂性和维度问题 难点无保护左转场景涉及大量的变量如自车的速度和位置、对向车辆的速度和位置、交通信号状态、行人等。每个变量都增加了状态空间的维度使得状态空间呈指数增长。这种联合状态空间使得枚举和计算每个状态变得不切实际遍历 s嵌套遍历action。瓶颈需要离散化状态空间但这会损失精度。更为复杂的连续状态空间则需要函数逼近方法如深度强化学习这增加了计算复杂性。 实时性要求 难点自动驾驶系统必须实时处理复杂的决策问题尤其是在动态、不可预测的环境下。无保护左转涉及快速变化的交通状况算法必须在极短的时间内做出准确的决策。瓶颈价值迭代等方法通常需要多次迭代才能收敛难以满足实时决策的要求。在实际应用中可能需要使用近似算法或剪枝技术来减少计算量。 不确定性处理 难点交通环境充满不确定性其他车辆的行为无法完全预测。无保护左转过程中系统需要处理对面来车的不确定性以及潜在的突发情况如行人突然出现。瓶颈MDP 假设状态转移概率已知但在实际应用中精确地建模这些概率很困难。系统可能需要实时学习和更新这些概率分布或依赖于历史数据的统计分析但这在动态场景中具有挑战性。 复杂的奖励函数设计 难点无保护左转需要平衡多个目标如安全性、效率、舒适性等。这些目标可能是相互冲突的。例如过度关注安全可能会导致过于保守的决策从而影响驾驶效率。瓶颈设计合理的奖励函数来平衡这些目标十分困难。奖励函数的细微变化可能导致完全不同的行为策略。找到适合所有情境的通用奖励函数几乎不可能必须针对不同的场景进行调试和优化。
2.2.2 价值迭代举例 Gridworld说明
网格世界Gridworld是强化学习中的经典环境用于演示如何通过价值迭代、策略迭代等方法来求解马尔科夫决策过程MDP。它的含义和用途如下
a.网格世界的定义
环境网格世界通常是一个二维的网格每个格子代表一个状态。状态每个格子都可以视为一个状态state通常用 (x, y) 坐标来表示。动作在每个状态智能体Agent可以执行一组动作例如上、下、左、右移动也有可能会移动失败停留在原地使它从一个状态转移到另一个状态。转移概率动作通常具有一定的不确定性即执行某个动作可能不会100%导致预期的结果。可能会有噪声导致智能体移动到不同的状态。奖励某些状态可能带有奖励如 1-1表示在到达这些状态时智能体获得的即时奖励。
b.网格世界的具体含义 状态图中的每一个方块代表一个状态。比如左上角的状态右下角的状态等。 终端状态Terminal State 绿色方块1达到这个状态表示任务成功获得 1 奖励。红色方块-1达到这个状态表示任务失败获得 -1 惩罚。一旦智能体进入终端状态它将无法再进行进一步的移动。 动作和转移概率 智能体在网格中的每个状态都可以选择向上、向下、向左、向右移动。执行动作时由于存在噪声图中的噪声参数为 0.2实际的移动可能不会按照预期进行。例如如果选择向上移动有 0.8 的概率真的向上移动但有 0.1 的概率会向左或向右移动。 价值迭代的过程 初始化一开始所有非终端状态的值 ( V(s) ) 都初始化为 0。迭代通过价值迭代算法逐步更新每个状态的值。这种更新基于贝尔曼方程用以估计在该状态下采取最佳策略时的预期长期回报。收敛随着多次迭代状态的值会逐渐收敛到一个稳定的值即最优值函数。此时可以通过最大化这个值来得出最优策略。
迭代过程 贝尔曼方程描述了一个状态的值价值如何基于该状态下采取的动作和随后的状态值来更新。一般形式为 V ( s ) max a ∑ s ′ P ( s ′ ∣ s , a ) [ R ( s , a , s ′ ) γ ⋅ V ( s ′ ) ] V(s) \max_a \sum_{s} P(s | s, a) \left[ R(s, a, s) \gamma \cdot V(s) \right] V(s)amaxs′∑P(s′∣s,a)[R(s,a,s′)γ⋅V(s′)]
具体计算
噪声 noise 0.2折扣因子 γ 0.9并且有两个终止状态其中一个的回报是 1绿色另一个的回报是 -1红色。
迭代1次后的结果
在图的左侧所有非终止状态的初始价值为 0。两个终止状态的价值分别为 1.00 和 -1.00。第1次迭代结束后所有非终止状态的价值仍然为 0.00这是因为这是第一次迭代状态的价值更新还没有传播到周围的状态。
迭代2次后的结果
在第2次迭代之后非终止状态的价值开始更新。对于第一行第三列的状态 V ( 1 , 3 ) 0.72 V(1, 3) 0.72 V(1,3)0.72。
为了计算出该状态的价值我们需要考虑所有可能的行动及其对应的回报。 向右移动: 直接进入终止状态 1, 所以回报为 ( γ × 1.00 0.9 × 1.00 0.9 \gamma \times 1.00 0.9 \times 1.00 0.9 γ×1.000.9×1.000.9 )由于噪声 0.2有一定概率移动失败可能上下移动这些方向的回报仍然是 0。 因此总期望回报为 0.8 × 0.9 0.2 × 0 0.72 0.8 \times 0.9 0.2 \times 0 0.72 0.8×0.90.2×00.72 所以这个状态的价值在第二次迭代时为 0.72。
迭代3次后的结果 第一行第三列的值计算 V ( 1 , 3 ) 0.78 V(1, 3) 0.78 V(1,3)0.78 向右移动 0.8 × 0 0.9 × 1 0.72 0.8 \times 0 0.9 \times 1 0.72 0.8×00.9×10.72 20%概率向下或向下移动 往下移动reward 为0 往上走仍有10%的一定概率留在原地且留在原地的reward 为0.72 0.1 × 0 0.9 × 0.72 0.06 0.1\times 0 0.9 \times 0.72 0.06 0.1×00.9×0.720.06 向右移动的总期望值为 0.72 0.06 0.78 0.72 0.06 0.78 0.720.060.78
第二行第三列的值计算 V ( 2 , 3 ) 0.43 V(2, 3) 0.43 V(2,3)0.43
对于这一状态主要有以下几个可能的移动方向
1. 向右移动
移动到终止状态 -1.00 0.8 × ( − 1.00 ) − 0.8 0.8 \times (-1.00) -0.8 0.8×(−1.00)−0.8移动到上方的状态 0.72 0.1 × 0.72 × γ 0.1 × 0.72 × 0.9 0.0648 0.1 \times 0.72 \times \gamma 0.1 \times 0.72 \times 0.9 0.0648 0.1×0.72×γ0.1×0.72×0.90.0648移动到下方的状态 0.00 0.1 × 0.00 0 0.1 \times 0.00 0 0.1×0.000
向右移动的期望值为 − 0.8 0.0648 0 − 0.7352 -0.8 0.0648 0 -0.7352 −0.80.06480−0.7352
2. 向上移动
移动到上方的状态 0.72 0.8 × 0.72 × γ 0.8 × 0.72 × 0.9 0.5184 0.8 \times 0.72 \times \gamma 0.8 \times 0.72 \times 0.9 0.5184 0.8×0.72×γ0.8×0.72×0.90.5184移动到左侧的状态灰色障碍或右侧终止状态 0.1 × 0 0.1 × ( − 1.00 ) × γ 0.1 × − 0.9 − 0.09 0.1 \times 0 0.1 \times (-1.00) \times \gamma 0.1 \times -0.9 -0.09 0.1×00.1×(−1.00)×γ0.1×−0.9−0.09
向上移动的期望值为 0.5184 − 0.09 0.4284 0.5184 - 0.09 0.4284 0.5184−0.090.4284
3. 向左移动
移动到灰色障碍的状态价值为0 0.8 × 0 0 0.8 \times 0 0 0.8×00移动到上方的状态 0.72 0.1 × 0.72 × γ 0.1 × 0.72 × 0.9 0.0648 0.1 \times 0.72 \times \gamma 0.1 \times 0.72 \times 0.9 0.0648 0.1×0.72×γ0.1×0.72×0.90.0648移动到下方的状态 0.00 0.1 × 0.00 0 0.1 \times 0.00 0 0.1×0.000
向左移动的期望值为 0 0.0648 0 0.0648 0 0.0648 0 0.0648 00.064800.0648
4. 向下移动
移动到下方的状态 0.00 0.8 × 0.00 0 0.8 \times 0.00 0 0.8×0.000移动到左侧的状态灰色障碍或右侧终止状态 0.1 × 0 0.1 × ( − 1.00 ) × γ − 0.09 0.1 \times 0 0.1 \times (-1.00) \times \gamma -0.09 0.1×00.1×(−1.00)×γ−0.09
向下移动的期望值为 0 − 0.09 − 0.09 0 - 0.09 -0.09 0−0.09−0.09
最终结果
在所有可能的移动中向上移动有最大的期望值0.4284因此第二行第三列 V ( 2 , 3 ) V(2, 3) V(2,3) 状态的值更新为 $ 0.43$。
第一行第二列的值 V ( 1 , 2 ) 0.52 V(1, 2) 0.52 V(1,2)0.52
对于这一状态主要有以下几个可能的移动方向 向右移动 80%的概率移动到第一行第三列状态其价值为 0.72。 10%的概率由于噪声上下移动到第一行第一列或者第二行第二列这两个位置的初始价值都是 0。 因此向右的期望回报为 0.8 × 0.72 0.1 × 0 0.1 × 0 0.576 0.8 \times 0.72 0.1 \times 0 0.1 \times 0 0.576 0.8×0.720.1×00.1×00.576
向上或向下移动
由于第一行第二列的上方和下方都是边界因此移动失败回到原状态价值依然为 0。 向左移动 由于左侧的状态第一行第一列初始价值为 0因此移动到该状态的价值为 0。
考虑到 0.9 的折扣因子 γ选择向右移动的期望价值是 V ( 1 , 2 ) γ × 0.576 0.9 × 0.576 0.5184 ≈ 0.52 V(1, 2) \gamma \times 0.576 0.9 \times 0.576 0.5184 \approx 0.52 V(1,2)γ×0.5760.9×0.5760.5184≈0.52
1000次迭代后趋于稳定 自动驾驶场景举例
对应到自动驾驶场景中可以理解为不同的驾驶策略和风险管理决策。以下是每种情况的解释
1. ( γ 0.1 \gamma 0.1 γ0.1), 噪声 0.5
场景描述: 自动驾驶系统优先考虑较短期的目标如到达最近的目的地并且有较高的不确定性噪声 0.5。这种情况下自动驾驶系统可能会选择一条看似较快的路径但这条路径存在较高的风险比如拥堵、不确定的道路状况或可能遇到障碍物。
场景举例: 在城市道路中行驶时自动驾驶系统选择了一条可能更快但道路状况复杂如有建筑施工或临时障碍物的路线。这种决策可能会导致系统在风险较高的情况下行驶。
2. ( γ 0.99 \gamma 0.99 γ0.99), 噪声 0
场景描述: 自动驾驶系统优先考虑长期目标如安全到达更远的目的地并且道路上几乎没有不确定性噪声 0。系统会选择最安全、最确定的路径尽管这条路径可能较长但保证不会遇到风险。
场景举例: 自动驾驶系统在选择路线时选择了经过已知没有障碍物和风险的高速公路尽管这条路线可能比其他路线稍微远一点但确保了行驶的安全性和可靠性。
3. ( γ 0.99 \gamma 0.99 γ0.99), 噪声 0.5
场景描述: 自动驾驶系统考虑长期目标如到达远方的目标但同时有一定的道路不确定性噪声 0.5。系统在这种情况下可能会冒险选择一条更短的路径尽管这条路径存在一些不确定性或风险。
场景举例: 在长途驾驶时自动驾驶系统决定通过一条可能有些风险但较快的路线例如一条在天气状况不稳定的山路上。系统希望通过冒险来节省时间但仍然考虑了最终的长期目标。
4. ( γ 0.1 \gamma 0.1 γ0.1), 噪声 0
场景描述: 自动驾驶系统优先考虑短期目标并且选择没有任何不确定性或风险的路径噪声 0。系统在这种情况下会选择最稳妥、最安全的路径即便这条路径可能较长。
场景举例: 在市区内短距离行驶时自动驾驶系统选择了一条最安全、没有任何风险的路线即便这条路线需要绕行但可以完全避免拥堵或潜在的危险。
总结
高 ( γ \gamma γ) 值表示系统更注重长期回报如长途驾驶中的最终目标。低 ( γ \gamma γ) 值表示系统更注重短期回报如市区内的快速到达。噪声高表示路径选择过程中存在较大的不确定性和风险。噪声低表示路径选择过程中几乎没有不确定性路径更为安全和确定。
2.2.3 策略迭代
基本概念
策略迭代Policy Iteration是一种求解马尔可夫决策过程MDP的经典算法它结合了策略评估Policy Evaluation和策略改进Policy Improvement两个步骤以便找到最优策略Optimal Policy。与价值迭代相比策略迭代通常收敛更快。
策略迭代的基本步骤 策略评估Policy Evaluation 给定一个策略 ( π \pi π )计算在该策略下每个状态的价值函数 ( V π ( s ) V^\pi(s) Vπ(s) )。这个过程通过贝尔曼方程反复计算直到收敛。贝尔曼方程描述了当前状态的价值是基于执行策略后所获得的即时奖励以及未来状态的折扣价值的加权和。 策略改进Policy Improvement 使用当前的价值函数 ( V π ( s ) V^\pi(s) Vπ(s) ) 来更新策略 ( π \pi π )。具体做法是对于每个状态选择能使得 ( Q ( s , a ) Q(s, a) Q(s,a) ) 最大的动作 ($ a$ )其中 ( Q ( s , a ) Q(s, a) Q(s,a) ) 是在状态 ($ s$ ) 执行动作 ( a a a ) 后的总价值。这会生成一个新的策略 ( π ′ \pi π′ )。 策略更新 如果新的策略 ( π ′ \pi π′ ) 与旧的策略 ( π \pi π ) 相同则算法终止否则用 ( π ′ \pi π′ ) 替换 ( π \pi π ) 并返回第一步继续进行策略评估。
贝尔曼原理与策略迭代的关系
贝尔曼原理Bellman Principle是动态规划的核心思想它描述了在最优策略下任意一个状态的最优价值等于当前选择的最优动作所带来的即时奖励加上该动作后进入的状态的折扣价值和。即 V ∗ ( s ) max a [ R ( s , a ) γ ∑ s ′ P ( s ′ ∣ s , a ) V ∗ ( s ′ ) ] V^*(s) \max_{a} \left[ R(s, a) \gamma \sum_{s} P(s | s, a) V^*(s) \right] V∗(s)amax[R(s,a)γs′∑P(s′∣s,a)V∗(s′)]
在策略迭代中贝尔曼原理起着至关重要的作用 策略评估通过贝尔曼方程来计算在当前策略 ( π \pi π ) 下每个状态的价值函数 ( V π ( s ) V^\pi(s) Vπ(s) )。这一过程利用了贝尔曼期望方程 V π ( s ) ∑ a π ( a ∣ s ) [ R ( s , a ) γ ∑ s ′ P ( s ′ ∣ s , a ) V π ( s ′ ) ] V^\pi(s) \sum_{a} \pi(a | s) \left[ R(s, a) \gamma \sum_{s} P(s | s, a) V^\pi(s) \right] Vπ(s)a∑π(a∣s)[R(s,a)γs′∑P(s′∣s,a)Vπ(s′)] 策略改进通过贝尔曼最优方程来找到最优动作从而更新策略。这一步的更新规则是选择能够使得 ( Q ( s , a ) Q(s, a) Q(s,a) ) 最大的动作 π ′ ( s ) arg max a [ R ( s , a ) γ ∑ s ′ P ( s ′ ∣ s , a ) V π ( s ′ ) ] \pi(s) \arg\max_{a} \left[ R(s, a) \gamma \sum_{s} P(s | s, a) V^\pi(s) \right] π′(s)argamax[R(s,a)γs′∑P(s′∣s,a)Vπ(s′)] 策略迭代举例 3. 参考
《自动驾驶预测与决策技术》 Markov Decision Processes 马尔可夫决策过程原理与代码实现 Part1_自动驾驶决策规划简介 Part2_基于模型的预测方法 Part3_路径与轨迹规划 Part4_时空联合规划
