临汾市网站建设_网站建设公司_外包开发_seo优化

动态规划：实例、变体与简化及相关术语解析

1. 状态与控制问题概述

在许多决策问题中，$f(x, y, u)$ 表示当状态为 $(x, y)$ 且应用控制 $u$ 时的棋盘位置（或终止状态）。尽管通过消除状态中不可控部分，动态规划（DP）算法得到了一定简化，但状态 $x$ 的数量仍然巨大，这类问题往往只能采用次优方法解决。

2. 部分状态信息与信念状态

在之前的假设中，控制器能够获取当前状态 $x_k$ 的精确值，策略由一系列函数 $\mu_k(x_k)$（$k = 0, \ldots, N - 1$）组成。然而在实际情况中，这个假设往往不现实。因为状态的某些组件可能无法测量，用于测量的传感器可能不准确，或者获取精确测量值的成本过高。

在这种情况下，控制器通常只能获取当前状态的部分组件信息，并且相应的测量值可能受到随机不确定性的影响。例如，在三维运动问题中，状态可能由位置和速度组件的六元组组成，但测量值可能只是包含噪声的三个位置组件的雷达测量值。

这就产生了部分或不完全状态信息的问题，这类问题在优化和人工智能文献中受到了广泛关注。虽然存在用于部分信息问题的 DP 算法，但这些算法的计算强度远高于完全信息对应的算法。因此，在没有解析解的情况下，实际中通常采用次优方法解决部分信息问题。

从概念上讲，部分状态信息问题与我们之前处理的完全状态信息问题并无本质区别。通过各种重新表述，我们可以将部分状态信息问题简化为完全状态信息问题。最常见的方法是用信念状态代替状态 $x_k$，信念状态是在时间 $k$ 之前，控制器根据所有观测值得到的 $x_k$ 的概率分布。这个概率分布原则上可以计算出来，并在适当的 DP 算法中作为“状态”使用。 </