1 基础概念

动态规划是利用最优性原理来解决最优和最优控制问题的一个非常有用的工具。最优性原则可以表示为：“最优策略具有这样的性质:无论初始状态和初始决策是什么，其余决策都必须构成与第一个决策产生的状态相关的最优策略。”

动态规划有几个方面。人们可以考虑离散时间系统或连续时间系统，线性系统或非线性系统，时不变系统或时变系统，确定性系统或随机系统，等等。

1.1 举例说明

A.非线性离散时间(时变)动态(确定性)系统

(1)系统定义

\[x(k + 1) = F[x(k),u(k),k],k = 0,1, \cdots （1） \]

其中\(x \in {\mathbb{R}^n}\)代表系统的状态向量，\(u \in {\mathbb{R}^n}\)表示控制动作，\(F\)是系统函数。

(2)代价函数的定义（用于衡量控制控制系统的性能好坏，越小越好）

\[J(x(i),i)= \sum_{k=i}^{ \infty }{ \gamma ^{k-i}U[x(k),u(k),k] }(2) \]

其中\(U\)表示效用函数，\(\gamma\)为折扣因子，其取值范围为，\(0<\gamma\leq 1\)。这里代价函数依赖于初始时间\(i\)和初始状态\(x(i)\)。

(3)动态规划的目标

选择一个控制序列\(u(k),k=i,i+1,.....\)，使得代价函数\(J\)最小化

(4)贝尔曼最优方程

根据贝尔曼最优性原理，可以得出\(k\)时刻的最优代价等于：

\[J^\star(x(k))=\min_{u(k)} (U(x(k),u(k))+\gamma J^\star(x(k+1)))(3) \]

在\(k\)时刻的最优控制\(u^\star(k)\)是达到上述最小值的\(u(k)\)

\[u^\star(k)=\arg min_{u(k)}\{U(x(k),u(k))+\gamma J^*(x(k+1))\}(4) \]

方程(3)是离散时间系统的最优性原则。它的重要性在于，它允许通过回溯时间来一次优化一个控制向量。

B.在非线性连续时间的情况下

(1)系统定义

\[\dot{x}(t)=F[x(t),u(t),t],t\ge t_0 (5) \]

(2)代价函数

\[J(x(t))=\int_{t}^{\infty}U(x( \tau),u(\tau))d\tau(6) \]

(3)最优代价满足哈密顿-雅可比-贝尔曼方程(Hamilton-Jacobi-Bellman Equation)

\[-\frac{\partial J^\star(x(t))}{\partial t}=\min_{u\in U}(U(x(t),u(t),t)+(\frac{\partial J^\star(x(t))}{\partial x(t)}\big)^T \times F(x(t),u(t),t)) \]

\[=U(x(t),u^\star(t),t)+\big(\frac{\partial J^\star(x(t))}{\partial x(t)}\big)^T \times F(x(t),u^\star(t),t))(7) \]

方程(3)和(7)称为动态规划的最优性方程，是实现动态规划的基础。

如果系统采用线性动力学建模，且在状态和控制中需要最小化的代价函数是二次的，则最优控制是状态的线性反馈，其中增益通过求解标准Riccati方程获得。

另一方面，当系统采用非线性动力学模型或代价函数为非二次型时，最优状态反馈控制将依赖于Hamilton-Jacobi-Bellman (HJB)方程的解，该方程一般为非线性偏微分方程或差分方程。

然而由于最优性方程求解中需要反向数值过程，即“维数诅咒”，通常难以求解。近年来随着动态规划的发展，通过建立一个“Critic”网络模型来近似动态规划中的成本函数，从而解决上述问题，这种方法被称为自适应动态规划算法（Adaptive Dynamic Programming）。

2 ADP的基础结构

为了实现ADP算法，Werbos提出了一种利用近似动态规划公式来绕过这一数值复杂性的方法。他的方法是用一个离散的公式来近似原始问题，采用基于神经网络的自适应评判方法求解自适应规划公式。ADP的主要思想如下图所示。他提出了两个基本版本，即启发式动态规划(heuristic dynamic programming，HDP)和双启发式规划(dual heuristic programming，DHP)。

2.1 启发式动态规划（HDP）

HDP是一种估计代价函数的方法。估计给定策略的成本函数只需要从瞬时效用函数\(U\)中获取样本，而要找到与最优策略相对应的成本函数则需要环境模型和瞬时报酬模型。

在HDP方法中，Critic网络输出的是成本函数（2）的估计\(\hat{J}\)，这是通过最小化以下随时间变化的误差来实现的

\[||E_h||=\sum_{k}E_h(k)=\frac{1}{2}\sum_k[\hat{J}(k)-U(k)-\gamma \hat{j}(k+1)]^2(8) \]

其中\(\hat{J}(k)=\hat{J}[x(k),u(k),k,W_c]\)，\(W_c\)表示Critic网络的参数，当在所有的时刻\(k\)都有\(E_h=0\)表示：

\[\hat{J}(k)=U(k)+\gamma \hat{J}(k+1)(9) \]

并且和方程2一样\(\hat{J}(k)=\sum_{i=k}^{\infty} \gamma^{i-k}U(i)\)

2.2 双重启发式规划(DHP)

DHP是一种估计代价函数梯度的方法，而不是代价\(J\)本身。为此，需要一个函数来描述瞬时代价函数相对于系统状态的梯度。在DHP的网络结构中，action网络和HDP的作用相同，都是生成控制信号，但是Critic网络不同，生成代价函数相对于状态的梯度。

Critic网络的训练比HDP复杂，因为我们需要考虑所有相关的反向传播路径。它的训练是通过最小化下面的误差来实现的。

\[||E_D||=\sum_{k}E_D(k)=\frac{1}{2}\sum_{k}(\frac{\partial \hat{J}(k)}{\partial x(k)}-\frac{\partial U(k)}{\partial x(k)}-\gamma \frac{\partial \hat{J}(k+1)}{\partial x(k)})(10) \]

其中\(\partial \hat{J}(k)/\partial x(k)=\partial \hat{J}[x(k),u(k),k,W_c]/\partial x(k)\)，\(W_c\)表示的是Critic网络的参数。当在所有时刻\(k\)都有\(E_D\)=0表示

\[\frac{\partial \hat{J}(k)}{\partial x(k)}=\frac{\partial U(k)}{\partial x(k)}+\gamma \frac{\partial J(k+1)}{\partial x(k)}(11) \]

3 ADP的发展

Weibos进一步提出了两种不同结构的ADP算法，一种为action-dependent HDP（ADHDP）又被称为Q-learning算法，一种为ADDHP。在这两种算法中，控制信号也成为了Critic网络的输入。在此基础上Prokhorov等人提出了两种新的结构：全局二次启发式规划（Globalized DHP，GDHP）和控制依赖全局二次启发式规划（Action dependent globalized DHP，ADGDHP）。其特点是Critic网络不但估计系统的代价函数本身同时也估计代价函数的梯度。

Notes：所有ADP结构都能实现相同的功能，即获得最优控制策略，但计算精度和运行时间各不相同。一般来说，HDP的计算量较低，但计算精度较低;而GDHP精度较好，但计算过程耗时较长。

3.1 Forward-in-time approach and Backward-in-time approach

(1) Forward-in-time approach

在前向时间算法中，公式（8）中的\(\hat{J}(k)\)作为Critic网络的输出，并且选择\(U(k)+\gamma \hat{J}(k+1)\)作为训练目标。Note：\(\hat{J}(k)\)和\(\hat{J}(k+1)\)是在不同的时间实例中使用状态变量获得。

(2) Backward-in-time approach

在后向时间算法中，公式（8）中的\(\hat{J}(k+1)\)作为Critic网络的输出去训练，并且选择\((\hat{J}(k)-U(k))/\gamma\)作为训练目标。

3.2 single network adaptive Critic（SNAC）

SNAC算法消除了Action网络，作为结果，SNAC算法拥有三个潜在的优势：更简单的结构，更小的计算量以及消除了动作网络而没有近似误差。SNAC方法适用于一类广泛的非线性系统，其中最优控制(平稳)方程可以用状态和协状态变量显式表示。