The Forward Recurrent Method for Dynamic Programming

Abstract

Backward recurrent method is usually adopted in seeking optimal solution by dynamic programming. A forward recurrent method to find optimal solution by dynamic programming is presented on the basis of an instance. The fundamental equation of dynamic programming and Millton-Jacobi's equation are also derived. It's an exploratory study on optimal solution of dynamic programming. An amount of work is reduced in calculating by using forward recurrent method, while applied range of the method is expanded.

Content

《1 引言》

1 引言

20世纪50年代初, 美国数学家贝尔曼提出了最优性原理和动态规划方法, 它和前苏联数学家庞里亚特金同期提出的最大值原理共同构成现代控制理论的重要的定理^[1], 引起了控制理论的重大变革。从此、控制理论由频域法转为时域法;由经典控制理论时代进入现代控制理论时代。

动态规划现今在许多技术领域, 特别是在管理科学、运筹学、经济学等方面得到了广泛的应用, 它是处理控制变量限制在一定闭集内的最优控制问题的有效的数学方法, 它把复杂的控制问题变为多级决策过程的递推函数关系^[2,3], 其基础和核心是最优原理, 动态规划的求解过程是一个反向递推的求解过程, 很多文献中有详尽的求解过程^[4,5], 近几年, 人们从各方面对动态规划的求解过程进行了探讨, 取得了一定的成果^[6,7,8], 由于求解过程是反向递推的, 从终端开始, 所以在多级决策过程中, 无论实际解决的问题是多少, 都要求解全部过程, 这使动态规划的计算量大大增加, 限制了它的应用, 笔者用正向递推方法求解动态规划的最优值, 并推导出哈密尔顿-雅可比方程, 是对动态规划求最优解方法的探讨。

《2 多级决策的正向求解》

2 多级决策的正向求解

多级决策是指把一个过程按时间或空间顺序分成若干级, 然后对每一级做出决策, 以使整个过程取得最优结果。动态规划是解决多级决策过程优化问题的强有力的工具, 传统动态规划的求解方法是从终端开始, 用反向递推的办法。下面以行车问题为例, 说明动态规划的正向求解过程。

设汽车从A城出发到B城, 途中需经过三条河流, 它们各有两座桥P, Q可供选择通过, 如图1, 各段间的行车时间 (h) 见图中标注, 现在确定一条最优路线, 使从A城到B城的行车时间最短。

《图1》

图1 段间行车时间

Fig.1 Running time between segments

动态规划正向求解的原则——所选择的最优路线必须保证其前部子路线是最优的。在图1中, 如果AQ₁P₂Q₃B是最优路线, 那么从起始点到这条路线上任一中间点的子路线必定也是最优的, 否则AQ₁P₂Q₃B就不是最优路线了。

根据这一原则求解最优路线, 从起点开始, 按时间最短为目标, 逐步向后, 求出起点至各中间站的最优值, 直至求出至终点的最优值。

第一段, 起点A的后一站是P₁, Q₁, 无论汽车到终点B的路径如何, 总要经过P₁或Q₁, 到P₁和Q₁都只有一条路线, 所以到P₁的最优路线是AP₁, 历时3 h;到Q₁的最优路线是AQ₁, 历时4 h。

第二段, P₁, Q₁的后一站是P₂, Q₂, 到P₂有两条路线, 从P₁到P₂——AP₁P₂, 历时10 h;从Q₁到P₂——AQ₁P₂, 历时8 h, 其最短历时8 h。到Q₂也有两条路线, 从P₁到Q₂——AP₁Q₂, 历时9 h;从Q₁到Q₂——AQ₁Q₂, 历时12 h, 其最短历时9 h。

第三段, P₂, Q₂的后一站是P₃, Q₃, 到P₃有两条路线, 从P₂到P₃, 要使历时最短, 从A到P₂一定走路线AQ₁P₂, 即AQ₁P₂P₃, 历时10 h;从Q₂到P₃, 要使历时最短, 从A到Q₂一定走路线AP1Q₂, 即AP₁Q₂P₃, 历时12 h, 其最短历时10 h。到Q₃也有两条路线, 从P₂到Q₃, 要使历时最短, 从A到P₂一定走路线AQ₁P₂, 即AQ₁P₂Q₃, 历时10 h;从Q₂到Q₃, 要使历时最短, 从A到Q₂一定走路线AP₁Q₂, 即AP₁Q₂Q₃, 历时12 h, 其最短历时10 h。

第四段, P₃, Q₃的后一站是终点站B, 到终点站B有两条路线, 从P₃到B, 要使历时最短, 从A到P₃一定走路线AQ₁P₂P₃, 即AQ₁P₂P₃B, 历时14 h;从Q₃到B, 要使历时最短, 从A到Q₃一定走路线AQ₁P₂Q₃, 即AQ₁P₂Q₃B, 历时12 h, 其最短历时12 h。

所以最优路线是AQ₁P₂Q₃B, 最优值是12 h。图2为正向递推求解的图示过程。

《图2》

图2 正向递推求解过程

Fig.2 Recursion solution process in positive direction

动态规划传统的反向递推求解原则:所选择的最优路线必须保证其后部子路线是最优的。在图2中, 如果AQ₁P₂Q₃B是最优路线, 那么这条路线上从任一中间点到终点的子路线必定也是最优的, 否则AQ₁P₂Q₃B就不是最优路线了。求解过程是从终点开始, 按时间最短为目标, 逐步向前, 求出各中间点到终点的最优值, 直至求出起始点至终点的最优值。详见文献^[4,5], 图3是传统反向递推求解的图示过程, 从图3中可以看出:传统反向递推求解与正向递推求解其结果完全一致。

《图3》

图3 反向递推求解过程

Fig.3 Recursion solution process in reverse direction

《3 离散系统动态规划的正向递推方法》

3 离散系统动态规划的正向递推方法

设离散系统 (见图4) 的状态方程为

$x_{k + 1} = f [x_{k}, u_{k}] k = 0, 1, \ :, Ν - 1$ $x_{k + 1} = f [x_{k}, u_{k}] k = 0, 1, \ :, Ν - 1$

式中x_k+1=x (k+1) 为n维状态矢量在 (k+1) T时刻的值, u_k=u (k) 为r维控制矢量在kT时刻的值, f为n维矢量函数。

《图4》

图4 离散系统多级决策求解

Fig.4 Multistage decision solution to discrete systems

状态初值 x (0) = x₀,

控制约束 g[x_k, u_k] ≤ 0,

性能泛函 $J = Φ [x_{Ν}] + \sum_{k = 0}^{Ν - 1} L [x_{k}, u_{k}]$ $J = Φ [x_{Ν}] + \sum_{k = 0}^{Ν - 1} L [x_{k}, u_{k}]$ ,

式中Φ[x_N]是对终端状态x_N=x (N) 的要求。

寻求一个最优控制序列{u^*_k} (k = 0, 1, \:, N-1) , 使上述性能泛函取极值。

根据多级决策的正向求解的方法, N段最优决策过程中, 前k段决策一定是最优决策。

J^*_k (x_k) = min {J^*_k-1[x_k-1]+L[x_k-1, u_k-1]}

x_k = f[x_k-1, u_k-1],

即 J^*₀ (x₀) =Φ[x_N],

J^*₁ (x₁) = min {J^*₀ [x₀]+L[x₀, u₀]}

x₁ = f[x₀, u₀],



J^*_N (x_N) = min {J^*_N-1[x_N-1]+L[x_N-1, u_N-1]}

x_k = f[x_k-1, u_k-1]。

对于一个多段决策的最优求解过程, 其初始值和终端状态都是给定的, 利用正向求解, 很容易求出前k段的最优值。

《4 连续系统动态规划的正向递推方法设连续系统 (见图5) 的状态方程为》

4 连续系统动态规划的正向递推方法设连续系统 (见图5) 的状态方程为

x = f[x, u, t],

状态初值 x (t₀) = x₀,

终端约束 N[x (t_f) , t_f] = 0,

性能泛函 J[x, t] =Φ[x (t_f) ]+

∫ $_{0}^{t_{f}}$ $_{0}^{t_{f}}$ , L[x, u, t]dt,

寻求一个最优控制u^* (t) , 使上述性能泛函取极值。

根据多级决策正向求解的方法, 如果x^* (t) 是以x (t₀) 为初始状态, 以x (t_f) 为终端状态的最优轨线, 那么以x (t′) 为终端状态的前半段一定是最优轨线。

《图5》

图5 连续系统多级决策求解

Fig.5 Multistage decision solution to continuous systems

若取t_f=t, t′=t_f-Δt 则最优性能泛函

$\begin{array}{l} J^{*} [x (t) ‚ t] = \\ \min {Φ [x (t)] + \int_{t_{0}}^{t} L [x, u, t] d t} = \\ \min {Φ [x (t)] + \int_{t_{0}}^{t - Δ t} L [x, u, t] d t + \\ \int_{t - Δ t}^{t} L [x, u, t] d t}, \\ J^{*} [x (t - Δ t) ‚ t - Δ t] = \\ \min {Φ [x (t)] + \int_{t_{0}}^{t - Δ t} L [x, u, t] d t} 。 \end{array}$ $\begin{array}{l} J^{*} [x (t) ‚ t] = \\ \min {Φ [x (t)] + \int_{t_{0}}^{t} L [x, u, t] d t} = \\ \min {Φ [x (t)] + \int_{t_{0}}^{t - Δ t} L [x, u, t] d t + \\ \int_{t - Δ t}^{t} L [x, u, t] d t}, \\ J^{*} [x (t - Δ t) ‚ t - Δ t] = \\ \min {Φ [x (t)] + \int_{t_{0}}^{t - Δ t} L [x, u, t] d t} 。 \end{array}$

当Δt很小时

$\begin{array}{l} \int_{t - Δ t}^{t} L [x, u, t] d t \approx L [x, u, t] Δ t ‚ \\ x (t - Δ t) = x - Δ t d x / d t + \dots = \\ x - Δ x + \dots \approx x - f [x, u, t] Δ t ‚ \\ J^{*} [x (t - Δ t), t - Δ t] \approx J^{*} [x - Δ x, t - Δ t] = \\ J^{*} [x (t), t] - [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} Δ x - \frac{\partial J^{*} (x, t)}{- \partial t} Δ t 。 \end{array}$ $\begin{array}{l} \int_{t - Δ t}^{t} L [x, u, t] d t \approx L [x, u, t] Δ t ‚ \\ x (t - Δ t) = x - Δ t d x / d t + \dots = \\ x - Δ x + \dots \approx x - f [x, u, t] Δ t ‚ \\ J^{*} [x (t - Δ t), t - Δ t] \approx J^{*} [x - Δ x, t - Δ t] = \\ J^{*} [x (t), t] - [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} Δ x - \frac{\partial J^{*} (x, t)}{- \partial t} Δ t 。 \end{array}$

所以

$\begin{array}{l} J^{*} [x (t), t] = \min {J^{*} [x (t - Δ t), t - Δ t] + \\ L [x, u, t] Δ t} = \min {J^{*} [x (t), t] - \\ [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} Δ x - \frac{\partial J^{*} (x, t)}{\partial x} Δ t + L [x, u, t] Δ t} = \\ J^{*} [x (t), t] - \frac{\partial J^{*} (x, t)}{- \partial t} Δ t + \\ \min {- [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} f [x, u, t] Δ t + \\ L [x, u, t] Δ t} ‚ \end{array}$ $\begin{array}{l} J^{*} [x (t), t] = \min {J^{*} [x (t - Δ t), t - Δ t] + \\ L [x, u, t] Δ t} = \min {J^{*} [x (t), t] - \\ [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} Δ x - \frac{\partial J^{*} (x, t)}{\partial x} Δ t + L [x, u, t] Δ t} = \\ J^{*} [x (t), t] - \frac{\partial J^{*} (x, t)}{- \partial t} Δ t + \\ \min {- [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} f [x, u, t] Δ t + \\ L [x, u, t] Δ t} ‚ \end{array}$

整理得

$\begin{array}{l} - \frac{\partial J^{*} (x, t)}{\partial t} = \\ \min {L [x, u, t] + [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} f [x, u, t]} ‚ \end{array}$ $\begin{array}{l} - \frac{\partial J^{*} (x, t)}{\partial t} = \\ \min {L [x, u, t] + [\frac{\partial J^{*} (x, t)}{- \partial x}]^{Τ} f [x, u, t]} ‚ \end{array}$

这就是连续系统动态规划基本方程, 即贝尔曼方程。

令哈密尔顿函数

$\begin{array}{l} Η [x, u, λ, t] = \\ L [x, u, t] + [\frac{\partial J^{*} (x, t)}{\partial x}]^{Τ} f [x, u, t] = \\ L [x, u, t] + λ^{Τ} f [x, u, t] λ = \frac{\partial J^{*} (x, t)}{\partial x} ‚ \end{array}$ $\begin{array}{l} Η [x, u, λ, t] = \\ L [x, u, t] + [\frac{\partial J^{*} (x, t)}{\partial x}]^{Τ} f [x, u, t] = \\ L [x, u, t] + λ^{Τ} f [x, u, t] λ = \frac{\partial J^{*} (x, t)}{\partial x} ‚ \end{array}$

得密尔顿-雅可比方程

$- \frac{\partial J^{*} (x, t)}{\partial t} = Η [x, u, λ, t]$ $- \frac{\partial J^{*} (x, t)}{\partial t} = Η [x, u, λ, t]$

《5 结论》

5 结论

笔者以实例说明为依据, 用正向递推的方法求解动态规划的最优值, 并推出动态规划的基本方程和密尔顿-雅可比方程, 是对动态规划求最优解方法的探讨。利用动态规划的正向递推方法, 在应用中不仅可以大大减少计算量, 而且使一些很难利用反向递推求解的问题得到解决, 扩大了动态规划的应用范围。在实际技术领域中, 尤其对于离散的控制系统, 如何充分的利用动态规划的正向递推方法, 简化最优值的求解过程, 解决传统动态规划方法难以解决的问题, 还有待于进一步探讨。

Show More