【强化学习与最优控制】笔记（三）动态规划求解实际问题举例

王源

分类：机器学习

发布时间 2021.12.15阅读数 4131 评论数 0

上一期笔记，忘记的小伙伴可以复习一下：

王源：【强化学习与最优控制】笔记（二）随机性问题的动态规划

本笔记对应教材中1.3节的内容，这一章所有的例子都围绕前面二节所讲的动态规划算法的核心公式：

$J_{N}^{*}\left( x_N \right) = g_N(x_N)$

$J_{k}^{*}\left( x_k \right) =\underset{u_k}{\min}g_k\left( x_k,u_k \right) +J_{k+1}^{*}\left( x_{k+1} \right)$

前两期的回顾，没有看或者忘记的童鞋可以复习一下：

王源：【强化学习与最优控制】笔记（一）确定性问题的动态规划

王源：【强化学习与最优控制】笔记（二）随机性问题的动态规划

1 最短路问题

最短路问题定义：在一个图中求2个节点之间最短的路径。

最短路问题一般需要假设图中所有的圈的路径非负。因为如果有负的圈的话一直在这个圈子里绕就可以让路径趋于无穷小。

如上图中（a）所示是给出的无向图，节点5是我们的终点，节点1,2,3,4是起点。在这个最短路问题中比较关键的问题是如何定义stage？

$J^*_k(i)$ 定义为从节点 $i$ 出发经过N-k个节点到终点 $t$ 的最优路径长度，其中N为总节点数， $i=1,2,...N, k=0,1,...,N-1$

由此可得DP的递推公式

$J_{k}^{*}\left( i \right) =\underset{All arcs (i,j)}{\min}[a_{ij}+J_{k+1}^{*}\left( j \right) ]$ （1.1）

$J^*_{N-1}(i)=a_{it}, i=1,2,...,N$ （1.2）

这里需要注意的是因为最短路径所经过的节点数我们事先并不知道，如果拿经过节点数目作为stage的数目的话是比较困难的。因此我们在式（1.1）的 $Allarc(i,j)$ 集合中除了要包含和节点 $i$ 相连的所有节点 $j$ 之外，也要包含节点 $i$ ，也就是说我们可以停在原地不动。这样就可以表示出经过节点数小于 $N$ 的路径。

1.1 代码实现

代码主要分为两部分，其中第一部分是输入图的数据。networkx是一个图论计算的包，用它来做一些图论方面的计算非常方便。我们先通过networkx建立一个无向图，然后添加节点，添加边（包含每条边上的权值），对应下面代码 G.add_weighted_edges_from([(0,1,6),(0,2,5),(0,3,2),(0,4,2),(1,2,0.5),(1,3,5),(1,4,7),(2,3,1),(2,4,5),(3,4,3)])，其中（0,1,6）就表示节点0和节点1直接有边连接，并且其权值为6，以此类推，我们按照教材中如图1.1所示把图的边的权值输入进去。Adjacency Matrix矩阵表示图的领接矩阵，对应代码中就是A矩阵，A矩阵中（i,j）的元素就是节点 $i$ 到节点 $j$ 的距离，也就是我们公式（1.1）中的 $a_{ij}$

import networkx as nx 
import numpy as np
G = nx.Graph()
G.add_nodes_from(range(0,5))
G.add_weighted_edges_from([(0,1,6),(0,2,5),(0,3,2),(0,4,2),(1,2,0.5),(1,3,5),(1,4,7),(2,3,1),(2,4,5),(3,4,3)])
A = nx.adjacency_matrix(G)
A = A.todense()
print(A)

第二部分是根据公式 $(1.1)-(1.2)$ 计算 $J^*_k(i)$ ，需要注意的是我们要计算的是对所有stage和所有状态的 $J^*_k(i)$ ，因此 $J^*_k(i)$ 在这里是一个二维数组，其维数为阶段数*状态数，对应代码第二行的costToGoValue。代码第三行的t表示终点为节点4。然后就先按照公式（1.2）把最后一个阶段的costToGoValue直接赋值。之后再用循环的方式，依据式（1.1）把所有阶段的costToGoValue递推得到。

nStage, nState = nx.number_of_nodes(G), nx.number_of_nodes(G)
costToGoValue = np.zeros((nStage, nState))
t = 4
costToGoValue[:,-1] = A[:,t].reshape((5))
for k in range(nStage-2,-1,-1):
    for i in range(nState):
        costToGoValue[i,k] = min([A[i,j] + costToGoValue[j,k+1] for j in range(nState)]) 
print(costToGoValue)

其实到这来还不算真正的完结，我们仅仅是算出了 $J^*_k(i)$ 。我们真正最终想要的是最优的Policy: $u^*_k$ ，这个留作大家的homework思考一下，怎么根据 $J^*_k(i)$ 算出 $u^*_k$ 。提示一下在前两节笔记中都有相关内容，想不起来的童鞋可以复习一下。已经熟悉的童鞋可以再代码实现一下加深理解。

2 组合优化问题

很多组合优化问题都可以采用动态规划的框架来求解，关于组合优化问题采用动态规划/强化学习的求解大家可以看一下这个回答，我这边就不赘述了。

现在研究强化学习+组合优化的paper不少了（几十篇+），但方法似乎就这么几种，对此您怎么看？

当然需要强调的是采用动态规划直接暴力求解组合优化问题依然是NP-hard的，但是很多时候我们只需要近似求解即可。尤其是对cost to go function的近似，可以把数学优化里边的各种Programming，各种Relaxation方法，各种Cut的方法，各种启发式算法与动态规划/强化学习结合起来，个人感觉未来将会是组合优化问题有所突破的地方。AlphaGo的成功其实某种程度上已经证明了这一点。对这方面感兴趣的童鞋可以参考这篇文章：Bertsekas D. Rollout algorithms for discrete optimization: A survey[J]. Handbook of Combinatorial Optimization, D. Zu and P. Pardalos, Eds. Springer, 20，随着后续章节的展开，我们会在后边详细介绍这部分内容，此处就不过多展开介绍了。

感谢Yuchao提出的建议，补充一篇新的参考文献关于Rollout算法方面的：Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm

3 Linear Quadratic Optimal Control

我们以钢铁生产中的加热炉为例来讲解 Linear Quadratic Optimal Control，如下图所示是钢铁材料在加热炉中的示意图：

从图中可以看到，钢铁材料有一个初始问题，然后经过了2个加热炉（本问题中设定N=2）后会得到最终的温度。由此我们可以定义

$x_0$ : 初始温度

$x_k$ : 在第k个炉子的出炉温度

$u_k$ : 第k个炉子所用的燃料量

动态系统：

$x_{k+1}=\left( 1-a \right) x_k+au_k,\ \ \ \ k=0,1,...,N-1$ （3.1）

其中 $a\in(0,1)$

目标函数有两项，一是让最终出炉的温度 $x_N$ 尽量接近给定的目标温度 $T$ ，二是让所有炉子消耗的总燃料量最小。由此可得目标函数为

$\underset{u_0,u_1,...u_{N-1}}{\min}r\left( x_N-T \right) ^2+\sum_{k=0}^{N-1}{u_{k}^{2}}$ （3.2）

其中 $r>0$ 为权值。

我们先暂时不考虑其它的约束条件，可以看出目标函数是一个二次项，而动态系统是一个线性系统，所以这个问题被称为 Linear Quadratic Optimal Control，请记住这个问题的形式，因为很多的复杂的控制问题可以转化为 Linear Quadratic Optimal Control

易知 $g_2(x_2)=r(x_2-T)^2$ （3.3）

$J_{2}^{*}\left( x_2 \right) =r\left( x_2-T \right) ^2$ （3.4）

$J_{1}^{*}\left( x_1 \right) =\underset{u_1}{\min}\left[ g\left( x_1,u_1 \right) +J_{2}^{*}\left( x_2 \right) \right] =\underset{u_1}{\min}\left[ u_{1}^{2}+J_{2}^{*}\left( x_2 \right) \right]$ （3.5）

$=\underset{u_1}{\min}\left[ u_{1}^{2}+r\left( x_2-T \right) ^2 \right] =\underset{u_1}{\min}\left[ u_{1}^{2}+r\left( \left( 1-a \right) x_1+au_1-T \right) ^2 \right]$ （3.6）

将上式对 $u_1$ 求导令导函数等于0 即可得到最优解的充要条件（因为目标函数是关于 $u_1$ 的凸函数）：

$2u_1+2ra\left[ \left( 1-a \right) x_1+au_1-T \right] =0$ （3.7）

由此可得：

$\mu _{1}^{*}\left( x_1 \right) =\frac{ra\left[ T-\left( 1-a \right) x_1 \right]}{1+ra^2}$ （3.8）

将最优的policy（3.8）反带回到（3.5）中可得

$J_{1}^{*}\left( x_1 \right) =\frac{r\left[ \left( 1-a \right) x_1-T \right] ^2}{1+ra^2}$ (3.9)

然后进入到前一阶段可得：

$J_{0}^{*}\left( x_0 \right) =\underset{u_0}{\min}g_0\left( x_0,u_0 \right) +J_{1}^{*}\left( x_{1} \right)$ (3.10)

$J_{0}^{*}\left( x_0 \right) =\underset{u_0}{\min}\left[ u_{0}^{2}+\frac{r\left[ \left( 1-a \right) x_1-T \right] ^2}{1+ra^2} \right]$

$=\underset{u_0}{\min}\left[ u_{0}^{2}+\frac{r\left[ \left( 1-a \right) ^2x_0+(1-a)a u_0-T \right] ^2}{1+ra^2} \right]$ (3.11)

同理对 $u_0$ 求导可得最优的policy，这里直接给出结果：

$\mu _{0}^{*}\left( x_0 \right) =\frac{r\left( 1-a \right) a\left[ T-\left( 1-a \right) ^2x_0 \right]}{1+ra^2\left[ 1+\left( 1-a \right) ^2 \right]}$ ， (3.12) $J_{0}^{*}\left( x_0 \right) =\frac{r\left[ \left( 1-a \right) ^2x_0-T \right]}{1+ra^2\left[ 1+\left( 1-a \right) ^2 \right]}$ , (3.13)

这个例子告诉我们非常重要的一个结论就是目标函数是凸二次的（Bertsekas书中原文写的是二次的，没有特别强调凸，我觉得是要加上凸才能满足全局最优的条件），动态系统是线性的，也就是我们所说的 Linear Quadratic Optimal Control，这个问题的性质比较好可以直接得到 $\mu^*$ 的解析形式（closed form）

例如对无人车的控制（车的位置，速度，加速度显然也是一个动态系统）

视频见原文：【强化学习与最优控制】笔记（三）动态规划求解实际问题举例

LQR+PID

所以Linear Quadratic Optimal Control和动态规划不只是有干巴巴的理论推导也都有着十分广泛的应用。最后想学习强化学习和最优控制但还没购买教材的童鞋可以戳

下一期笔记：

王源：【强化学习与最优控制】笔记（四）强化学习与最优控制的关联与对比

建模仿真强化学习自动控制最优控制动态规划

打赏 0

上一篇：【强化学习与最优控制】笔记（二）随机性问题的动态规划

下一篇：【强化学习与最优控制】笔记（四）强化学习与最优控制的关联与对比

【强化学习与最优控制】笔记（三）动态规划求解实际问题举例

王源

1 最短路问题

1.1 代码实现

2 组合优化问题

3 Linear Quadratic Optimal Control

为你推荐

正则化逻辑回归-python实现

公开课丨MATLAB玩转深度学习和无人驾驶

macOS 搭建ESP8266编译环境

强化学习环境：ubuntu18.04 MUJOCO安装记录（2021年4月8日）

深度强化学习专栏 —— 1.研究现状

学习笔记——支持向量机svm（3）kernel trick（核函数）

关于作者

王源

10

0

0

1

【强化学习与最优控制】笔记（七） Rollout 与 Policy Improvement

【强化学习与最优控制】笔记（四）强化学习与最优控制的关联与对比

【强化学习与最优控制】笔记（十）无限时间动态规划和随机最短路问题

相关推荐

(7) 信息论 Information Theory : 信息熵，熵的物理意义，相对熵，互信息 - PRML && CS229

《Composite Structures》人体冲击防护复合材料结构

精选【Yolov5+Deepsort】训练自己的数据集（3）| 目标检测&追踪 | 轨迹绘制 | 报错分析&解决

（十三）通俗易懂理解——Adaboost算法原理

MobileNetV1 V2 V3网络理解+pytorch源码

【AllenNLP入门教程】: 1、基于Allennlp2.4版本的文本分类

热门泡泡

30积分失眠，聊聊自己搞ROS的心得体会吧

ros学习路线

30积分 TF_REPEATED_DATA ignoring data错误

各位大佬，有什么ROS定位算法推荐吗

5积分想买能用ROS2的开发套件。或者开发板

5积分 ros中启动gazebo时报错

给作者打赏

【强化学习与最优控制】笔记（三）动态规划求解实际问题举例

王源

1 最短路问题

1.1 代码实现

2 组合优化问题

3 Linear Quadratic Optimal Control

为你推荐

正则化逻辑回归-python实现

公开课丨MATLAB玩转深度学习和无人驾驶

macOS 搭建ESP8266编译环境

强化学习环境：ubuntu18.04 MUJOCO安装记录（2021年4月8日）

深度强化学习专栏 —— 1.研究现状

学习笔记——支持向量机svm（3）kernel trick（核函数）

评论（0）

关于作者

王源

10

0

0

1

【强化学习与最优控制】笔记（七） Rollout 与 Policy Improvement

【强化学习与最优控制】笔记（四）强化学习与最优控制的关联与对比

【强化学习与最优控制】笔记（十）无限时间动态规划和随机最短路问题

相关推荐

(7) 信息论 Information Theory : 信息熵，熵的物理意义，相对熵，互信息 - PRML && CS229

《Composite Structures》人体冲击防护复合材料结构

精选【Yolov5+Deepsort】训练自己的数据集（3）| 目标检测&追踪 | 轨迹绘制 | 报错分析&解决

（十三）通俗易懂理解——Adaboost算法原理

MobileNetV1 V2 V3网络理解+pytorch源码

【AllenNLP入门教程】: 1、基于Allennlp2.4版本的文本分类

热门泡泡

30积分 失眠，聊聊自己搞ROS的心得体会吧

ros学习路线

30积分 TF_REPEATED_DATA ignoring data错误

各位大佬，有什么ROS定位算法推荐吗

5积分 想买能用ROS2的开发套件。或者开发板

5积分 ros中启动gazebo时报错

给作者打赏

忘记密码

修改头像

添加你感兴趣的标签

举报类型（必选）

举报详情（选填）

30积分失眠，聊聊自己搞ROS的心得体会吧

5积分想买能用ROS2的开发套件。或者开发板