自动驾驶（六十一）---------蒙特卡洛搜索树

资源分类

2020-01-03 |

81 |

原标题：自动驾驶（六十一）---------蒙特卡洛搜索树

原文来自：CSDN 原文链接：https://blog.csdn.net/zhouyy858/article/details/103791439

首先祝我自己元旦快乐，也祝在这个日子里看我blog的粉丝元旦快乐，今天申请了加班所以有时间写blog，程序员的生活就是这么单纯.........在这个特殊的日子里，为了充实节日气氛，学习一个名字很长的知识--蒙特卡洛搜索树，如果要问和自动驾驶有什么关系，我想在决策的时候可以用到吧，只是博弈论暂时并没有引入进自动驾驶中。另外它和A*算法类似，在导航上也有应用的可能。

特别的自动驾驶进入冷静期，感知智能很快也接近极限，限制自动驾驶发展的关键是逻辑推理，所以我未来的方向将有可能涉及多方面，不会局限与深度学习方面，毕竟我已经落后很多了，需要弯道超车，现在的想法是认知智能、逻辑推理、迁移认知等等方面。总之一切的一切都是朝着自动驾驶方向前进。

1. 博弈树

首先介绍博弈树的概念，博弈树是一种树形结构，其中每一个节点表征博弈的确定状态。从一个节点向其子节点的转换被称为一个行动，节点的子节点数量被称为分支因子，树的根节点也就是博弈的初始状态，端节点也就是叶子节点，表示博弈的最终状态，从一个根节点到一个端节点的树遍历表征了单个博弈过程。

2. 极小极大策略

给定一个状态，并假定对手正在尝试最小化你的收益，你希望找到能最大化你的收益的动作。这正是该算法被称为极小极大的原因。我们需要做的就是展开整个博弈树，并反向传播由递归形式的规则得到的值。每一个层级的选择都是极小极大判断的最优结果。我们可以从底部的终端节点开始，其中的选择是很明显的。

3. 基本概念

蒙特卡洛树搜索算法分为四步，分别是选择（Selection）、扩展（Expansion）、模拟（Simulate）和反向传播。

1. 选择：从根节点开始，根据UCT函数选择一个最有潜力的子结点，直到当前节点的还有可扩展的子节点，UCT函数的定义如下：其中vi表示当前节点，v表示vi的父节点，表示vi节点胜利的次数，N（vi）表示访问vi节点的次数，N（v）表示访问v节点的次数，这些参数是通过第四步反向传播得到的。