人工智能学习笔记之——在不确定环境中的决策（Planing under uncertainty）

之前的文章写了好多关于机器学习经典算法的介绍，对于AI来说，学(Learning)很重要但是做(Planning)更重要，这里的做就是指的是决策和规划。比如机器人如何不确定的环境下如何规划自己的路线，这也是人工智能需要解决的问题。

我在人工智能 学习笔记的第一篇文章就介绍了两个总要概念，全感知 vs 部分感知（Full vs Partially Observable）以及确定性的vs随机性的（Deterministic vs Stochastic）。第二篇文章中提到的导航路径算法，无论是“最短步数优先”还是“Cheapest First” 算法都是在全感知的确定环境下而做出的规划。

在全感知随机性的环境中呢，这里就要提到马可夫决策过程(英语：Markov Decision Processes，缩写为 MDP)。

一、MDP中的基本概念

MDP 有点类似于当年在大学里面学习的数字电路中的有限状态机，其中包括
状态（States）S1 S2……Sn
行动（Actions）a1 a2 ……ak
状态转移矩阵(State transition matrix) 等于之前在概率中介绍的，状态转移概率（state transition probability）
T(S, a, S') = P(S'| a, S) （通过行动a从S到S' 状态的概率）
激励函数（Reward function） R(S) 是指在每个状态的奖励，比如上图S1是10美元，S2是0美元，S3是100美元。
策略（Policy） π(s) ——到达目标的策略。

二、传统决策算法的局限性

举一个例子，如下图，机器人从C1到达目的地a4, a4的R(S)是100，与a4相邻的b4的R(S)是-100，每当命令机器人向一个方向，比如向北走的时候，他有80%的概率会到达北边的状态，同时也分别有10%的概率到达东西两个状态。

如果用传统的方法，将每个行动和状态结果表达出来是很难的，将会遇到分支太多，树枝太深，以及很有可能机器人会在原地打转的情况

三、MDP 和 Cost(代价)

定义R(S)除了100和-100其他地方都是-3。正如下图式子，我们要做的就是找到一个Policy使得走完这个Policy 之后的R总和的期望最大。当然R是一个时间的函数，而γ是让R随着时间衰减。（走的越多当然R就会越小）

四、数值迭代(Value Iteration)

跟所有机器学习的算法一样，MDP也是通过不断迭代而算出最优策略的。而迭代也通常是从目标状态回推，进而得到每个状态的数值(value)V(S)，通过V(S)就可以找到到达目标的最优策略。打个比方，如果登山要找到最短的路径，那么有一个简单的方法就是从山顶倒水，水流通过的路径就是最短路径。

比如上图，目标是a4，从a4倒推，a3到a4的数值计算方式就是找到a3 到每个方向的最大期望再加上R(S)。比如a3只有向东到达a4的期望最大0.8100=80, 二其他方向，比如向西到a2 是0.80=0，就不予考虑了。如果这样不停地递归迭代就能算出每个状态的数值，从而在每个状态的运动策略就自然而然地出来了。而这个迭代函数就叫做Back-up 函数。
总结一下，V(S)是Back-up 函数找到每个状态的数值V，策略π就是根据状态函数计算出来的。

Thanks for reading my posts and welcome to comment. If you like my post , please upvote , resteem and follow me @hongtao
感谢您的阅读，欢迎留言，如果您喜欢我的帖子，请帮忙点赞、推送及关注我 @hongtao