MDP Based 基于马尔科夫决策的路径规划( 二 ) _机器人

Worst-Case
假设已知了一个MDP的Model，求解MDP的问题，给定了起始点到终止点的这个Plan，来寻找一个最优的Plan，使得整体的Cost最小。在这个Nd的Model之下，机器人并不知道自然会给自身施加什么影响，所以一般假设，自然动作空间会最大程度上去对机器人进行干扰（贪婪最大化，使得机器人处于最不利的情况），以下便是Worst-Case 的执行流程，其服从以下的这个公式，
G π ? ( x s ) G_{\pi*}(x_{s}) Gπ??(xs?)的解释，就是先选用最差的一种情况的Cost，即 m a x [ L ( x ~ , u ~ , θ ~ ) ] max[{{L(\{x},\{u},\{\theta})}]} max[L(x,u,θ)]，之后再用这个最差的Cost，去进行Cost to go，定义了每一个 π {\pi} π的cost to go之后，我们再进行筛选，找到Cost to go当中最小的那一组 π {\pi} π，这样，就相当于找到了最优的那一Plan 。直接的去求，会很困难，因为要用枚举法枚举所有的 π {\pi} π，枚举每一个 π {\pi} π诱导的那些路径，去计算Cost 。这是一个组合爆炸的问题。目前求解这类方法常用的问题就是动态规划，通过第 k 、 k + 1 k、k+1 k、k+1之间的递归关系，来求得最优的Plan 。
动态规划
Cost to go 对于最终的状态是 G F ? = l F ( x F ) {G}_{F*}={l}_{F}(x_{F}) GF??=lF?(xF?)这样的从 K {K} K一直到最终的 K + 1 {K+1} K+1的Cost，就是由以上两部分组成可以把第 K {K} K步的分解成第 K + 1 {K+1} K+1步的形成递归关系
Nd
基本思想就是动态规划思想，从最后一个节点出发，往前推，计算前继节点到终点的距离（Cost），然后因为每走一步就考虑一步，所以所得的路径是最优的路径，也是Cost最少的路径。
阶段总结
Cost
其主要是求解Pb Model的问题，与上方不同的是ECP在做之前会有一个估计，我们能大体知道当机器人做一个动作后，这个自然大体上会做什么动作来干扰。行为具体上是具备了一些可预测性。
现在的评估是通过Set当中的平均表现，作为评估 π {\pi} π的一个指标。
解法还是动态规划，不过这次解法要加上权重的条件概率。
阶段总结
RTDP算法
RTDP是对 Cost 解法的一种补充，加速。
首先初始化G ，这里的与上方是一样的，一般来说这个数值要小于实际的Cost to go的数值。然后我们按照初始化的G 去贪婪的选择动作，直到到达终点。这样就可能找到一条路径，但是这条路径可能不是最优的，是冗余的。
RTDP伪代码