3、动态规划与值迭代：策略评估、策略迭代、值迭代算法、在网格世界中的轨迹规划应用

动态规划，说白了就是解决「多步决策」问题的数学工具。我刚开始接触强化学习时，觉得这名字挺唬人，后来发现它核心就一句话：把一个大问题拆成小问题，然后记住小问题的答案。嗯，就这么简单。

在轨迹规划里，动态规划帮我们回答一个关键问题：站在当前格子，下一步往哪走，才能让未来累积的奖励最大？ 今天我们就来聊聊它的三个核心算法：策略评估、策略迭代、值迭代。

核心思想： 动态规划假设环境模型（状态转移概率）完全已知，通过自举（Bootstrapping）方式，用后继状态的值函数来更新当前状态的值函数。

3.1 策略评估：给定策略，算算它有多好

策略评估，就是给定一个固定的策略 π，计算每个状态的价值 Vπ(s)。

举个例子。假设你有一个机器人，它的策略是「遇到障碍就左转，否则直行」。策略评估要回答：按照这个傻策略，每个格子到底值多少分？

数学上，我们用贝尔曼期望方程来迭代计算：

V_{k+1}(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [r + γ V_k(s')]

说白了，就是不断用后继状态的价值，来更新当前状态的价值。迭代到收敛，V 就稳定了。

我的经验： 我在做仓储机器人路径规划时，策略评估经常用来做「策略体检」。比如机器人当前策略是「靠右行驶」，评估完发现某些角落状态价值极低，说明策略有坑。这时候不用急着改策略，先看看评估结果，心里有数。

收敛条件很简单：相邻两次迭代的 V 值变化小于某个阈值（比如 1e-6），我们就认为评估完成了。

3.2 策略迭代：评估 + 改进，循环直到最优

策略评估只是第一步。光知道策略好不好没用，我们得让它变得更好。这就是策略迭的事。

策略迭代分两步：

  1. 策略评估： 计算当前策略 π 的价值函数 Vπ
  2. 策略改进： 基于 Vπ，贪心地选择新策略 π'

贪心选择的意思是：在每个状态 s，选择能最大化未来回报的动作 a*：

π'(s) = argmax_a Σ_{s',r} p(s',r|s,a) [r + γ V^π(s')]

然后重复这两步，直到策略不再变化。

避坑指南： 我曾经在策略评估时迭代次数设得太多，导致计算量爆炸。后来发现，对于策略迭代，不需要把策略评估做到完全收敛。做几次迭代就够了，甚至只做一次（这就是值迭代的雏形）。你想想看，策略改进本身会修正误差，没必要在评估上死磕。

策略迭代的收敛速度通常很快，尤其当状态空间不大时。我习惯在网格世界（比如 10x10）里先用策略迭代，因为它直观、稳定。

3.3 值迭代：把评估和改进合并成一步

值迭代是策略迭代的「极限版」——它把策略评估和策略改进合并成一个步骤。

更新公式变成了：

V_{k+1}(s) = max_a Σ_{s',r} p(s',r|s,a) [r + γ V_k(s')]

注意看，这里直接取 max，不再依赖某个固定的策略。每次更新，我们都在问：如果我现在选最优动作，这个状态值是多少？

值迭代的收敛条件：当所有状态的 V 值变化小于阈值时，停止。然后从收敛的 V* 中提取最优策略：

π*(s) = argmax_a Σ_{s',r} p(s',r|s,a) [r + γ V*(s')]
我个人习惯： 值迭代适合状态空间大的情况。比如 50x50 的网格，策略迭代每次评估都要扫很多遍，而值迭代一次更新就搞定。不过要注意，值迭代的收敛速度是线性的，如果 γ 接近 1，收敛会变慢。我遇到过 γ=0.99 时，跑了 2000 轮才稳定。

3.4 网格世界中的轨迹规划应用

理论说完了，咱们来点实际的。假设有一个 5x5 的网格世界：

  • 起点在 (0,0)，终点在 (4,4)
  • 障碍物在 (2,2)、(2,3)、(3,2)
  • 每走一步奖励 -1，到达终点奖励 +100
  • 折扣因子 γ = 0.9

我们用值迭代来规划最优轨迹。

import numpy as np

# 网格参数
GRID_SIZE = 5
ACTIONS = ['up', 'down', 'left', 'right']
GAMMA = 0.9
THRESHOLD = 1e-4

# 障碍物和终点
obstacles = {(2,2), (2,3), (3,2)}
goal = (4,4)

# 初始化价值函数
V = np.zeros((GRID_SIZE, GRID_SIZE))

def step(state, action):
    """执行动作，返回下一个状态和奖励"""
    x, y = state
    if state == goal:
        return state, 0  # 终点不动
    
    if action == 'up':    x = max(0, x-1)
    if action == 'down':  x = min(GRID_SIZE-1, x+1)
    if action == 'left':  y = max(0, y-1)
    if action == 'right': y = min(GRID_SIZE-1, y+1)
    
    next_state = (x, y)
    if next_state in obstacles:
        next_state = state  # 撞墙不动
        reward = -1
    elif next_state == goal:
        reward = 100
    else:
        reward = -1
    
    return next_state, reward

# 值迭代
iteration = 0
while True:
    delta = 0
    for i in range(GRID_SIZE):
        for j in range(GRID_SIZE):
            state = (i, j)
            if state == goal or state in obstacles:
                continue
            
            # 计算所有动作的价值，取最大值
            values = []
            for a in ACTIONS:
                next_state, reward = step(state, a)
                values.append(reward + GAMMA * V[next_state])
            
            new_value = max(values)
            delta = max(delta, abs(new_value - V[state]))
            V[state] = new_value
    
    iteration += 1
    if delta < THRESHOLD:
        break

print(f"值迭代收敛于第 {iteration} 轮")
print("最终价值函数：")
print(np.round(V, 1))

运行这段代码，你会看到终点附近的价值最高，障碍物周围的价值被压低。从起点出发，沿着价值递增的方向走，就是最优轨迹。

关键洞察： 值迭代得到的 V* 其实是一张「势能图」。机器人就像水往低处流一样，沿着价值增加的方向走，自然就能到达终点。我在实际项目中，经常把 V* 可视化出来，给机器人做全局导航的参考。

3.5 三种算法的对比

算法 核心操作 收敛速度 适用场景
策略评估 固定策略下迭代计算 V 慢（需完全收敛） 策略分析、性能诊断
策略迭代 评估 + 改进交替 快（通常 < 10 轮） 中小规模状态空间
值迭代 直接 max 更新 V 中等（线性收敛） 大规模状态空间

我个人建议：先试值迭代，代码简单，不容易出错。如果发现收敛太慢，再换成策略迭代。至于策略评估，更多是作为调试工具来用。

3.6 本章知识体系

下面这张图总结了动态规划在轨迹规划中的核心逻辑：

动态规划在轨迹规划中的知识体系 策略评估 给定策略 → 计算 V 策略迭代 评估 + 改进 → 最优 值迭代 直接 max → 最优 V 应用场景：网格世界轨迹规划 状态空间建模 奖励函数设计 收敛判断 输出：最优价值函数 V* + 最优策略 π*
我的建议： 初学者先别急着调参。拿一个 5x5 的网格，手算一遍值迭代的前三轮，你就彻底懂了。我当年就是这么干的，虽然慢，但理解深刻。

动态规划是强化学习的基石。虽然它假设环境模型已知，这在很多真实场景中不成立，但它的思想——用后继状态更新当前状态——贯穿了整个强化学习领域。后面讲无模型方法时，你会发现很多算法都是动态规划的「变种」。

好了，这一章就到这里。记住：先跑通代码，再理解理论。动手做一遍，比看十遍书都管用。

← 上一章 📖 返回目录 下一章 →