1. 决策和搜索

上一章主要讲的是建图, 定位,利用贝叶斯理论. 介绍了基本的概率论, 状态估计, 如何根据观察和原有的状态来更新状态.

这一章, 注重于介绍搜索策略, 就是已经有了建图和定位之后怎么找到一条适合的路线

2. 1 概率部分

介绍了基本的概率论

2.1. 1.1 状态估计

当我们有许多概率分布时, 我们依然使用PCAP的方法来控制复杂性

Primitive 基本的概率分布: Delta\Uniform\Square\
Combination: 利用条件概率叠加

2.2. 1.2 随机状态机

通过贝叶斯理论来更新状态机, 这在机器人学中花了很多时间来学习

3. 2 搜索部分

3.1. 2.1 状态空间搜索

我们所要做的就是

定义状态集合
确定起始状态和期望的目标状态
一张地图, 或者说各个状态之间是如何连接在一起的, 以及如何从一个状态到另一个状态

3.1.1. Python实现: 一棵有很多点的树

我们定义一个类来表示节点, 这个类需要有以下属性

这个节点的状态state
用来到达这个节点所采取的action
这个节点可以到达的子节点

搜索算法:

输入是问题的描述(起点, 终点)
输出是所要求取的路径
具体的算法有不同的策略, 基本的有深度优先和广度优先

在上程序设计专题时, 我们选的设计目标是一个泡泡堂游戏. 其中一个功能就是路径搜寻, 那要怎么找到这个路我当时几乎没有任何相关的背景知识, 自己研究了一个礼拜终于想出了深度优先的算法. 在想出来之后觉得很简单, 但是在一开始探索时简直是不知所措, 当时也不会一些研究方法, 花了很多时间做了很多尝试. 也就是从那个时候我逐渐将编程理解成一种翻译, 将其他语言(逻辑\数学\物理)成翻译计算机能够理解的语言. 如果当时直接老师告诉我的话, 大概不会有那么深刻的印象

下面这个是一个比较通用的框架, 通过在这个框架上增添一些功能, 我们就可以实现深度优先\宽度优先等算法

def search(initialState,goalTest,actions,successor):
if goalTest(initialState):
return [(None,initialState)]
agenda=EmptyAgenda()
add(SearchNode(None,initialState,None),agenda)
while not empty(agenda):
parent=getElement(agenda)
for a in actions(parent.state):
newS=successor(parent.state,a)
newN=SearchNode(a,newS,parent)
if goalTest(News):
return newN.path()
else:
add(newN,agendas)
return None

简本的剪枝: 可以避免一些愚蠢的情况, 比如在两个点之间不断来回. 那么我们可以设置规则: 一条路径不走回头路

1 2	if parent.inPath(NewS): pass

深度优先: 每次都优先不断进入子节点, 直到到达末端点还没有到期望的终点, 再往回在向下

广度优先: 每次都先便利同一层上的节点, 没有遇到期望的终点就继续向下

动态规划: 可以用来计算最短路径. 记录所到达过的状态, 如果遇到新的状态, 就根据已有的距离和新的距离来更新, 列表中同样的节点只能出现一次

基于的原理: X到Z的最短路径=X到Y的最短路径+Y到Z的最短路径
动态规划还能大大减少所要遍历的路径

3.2. 2.2 数值搜索领域

如何通过数值来求解最优解. 比如在微积分中, 我们可以通过求导来梯度下降找到最优解

在优化的过程中, 我们还要考虑计算的复杂性, 时间复杂性, 空间复杂性. 使用动态规划可以大大降低复杂性

Only Truth Matters

MIT EECS 导论课 5