关于寻路算法的一些思考(12):AI 技术

本系列:


AI技术

寻路问题常常会和人工智能(AI) 联系在一起,原因是 A*算法和许多其他寻路算法是由 AI 研究者开发出来的。一些生物启发式的 AI 技术目前十分流行,我也收到一些为何不使用这类技术的咨询。神经网络是依据实例的大脑学习建模——给定一个正解的集合,它会学习出一个一般的解决问题模式。强化学习是依据经验的大脑学习建模——给定一些行为的集合和最终奖惩结果,它会学习出哪种行为是正确或错误的。遗传算法根据自然选择的进化规律建模——给定一些agent 集合,优胜劣汰。通常情况下,遗传算法不允许 agent 在他们的生存时间内进行学习。强化学习则不但允许 agent 在生存时间内学习,还可以和其他 agent 分享知识。(译注:agent:智能体,正文保留未翻)

神经网络

神经网络是这样构建的:它受到训练,来对输入进行模式识别。他们是一种用来处理函数近似的方法:给定 y1 = f(x1),y2 = f(x2), …, yn = f(xn),构建一个函数 f’使得 f’逼近 f。近似函数 f’一般都是光滑的:对于接近 x 点的 x’,我们希望 f’(x)也能接近f’(x’)。

函数近似方法可以满足以下两个目的:

  •     规模:近似函数的表达可以明显小于真实的函数规模。
  •     泛化:未知函数值的输入数据可以使用近似函数

神经网络典型做法是使用一组输入值向量,产生一组输出值向量。在算法内部,训练“神经元”(neurons)的权重。神经网络使用监督学习,即输入和输出都是已知的,学习的目标是建立一个可以近似输入输出映射的函数表达。

在寻路问题中,函数 f(start,goal)=path。我们并不知道输出路径是什么。我们可以使用一些方法,可能是 A*算法,来计算它们。但是如果我们能根据(start, goal)计算路径,那么我们就已经知道了函数 f,那么为什么还要自找麻烦的找它的近似函数呢?因为我们已经完全知道了函数 f,再归纳 f 就没有用了。用函数近似的唯一潜在的好处可能会降低 f 的表达规模。但f 表达的是个相当简洁几乎不占用空间的算法,所以我认为神经网络在这里也没有什么用。另外,神经网络输出规模是固定的,而寻路问题规模是可变的。

但另一方面,函数近似可能对构建寻路的一些组成部分有用。比如移动的成本函数是未知的。例如,没有实际移动操作和战役的情况下,穿越怪兽聚集森林的成本,我们可能并不知道。使用函数近似的方法的话,每次穿越森林时,移动成本函数f(number of orcs, size of forest)可以测量出来并装入神经网络模型中(注:这里移动成本f的自变量是怪兽数量和森林规模)。对于未来的寻路部分,根据算出的未知移动成本,我们可以找到更好的路线。

另一个可以从归功于近似计算的函数是启发式函数。A*算法中的启发式函数可以计算到达目的地的最小成本,如果一个单元沿着路径 P=p1,p2,…,pn移动,当每穿过一段路径的时候,我们可以更新 n到近似函数 h 中,其中g(pi,pn)=(从i到 n 的实际移动成本)。当启发函数优化了,A*算法也会运行的更快。

神经网络尽管对于寻路算法本体不太实用,但对 A*算法使用的函数可以起到作用。移动函数和启发式函数都可以测算,因此能给函数近似反馈。

遗传算法

根据适应度函数(fitness function),遗传算法允许开发参数空间来求得效果良好的解。他们是一种用来处理函数优化的方法:给定一个函数g(x)(x 是一组典型的参数值向量),求得能最大化(或最小化)g(x)的 x 值。这是一种非监督学习——问题的正确答案预先并不知道。

对于寻路问题,给定一个起始位置和一个目标位置,x 是这两点间的路径,g(x)是穿越这路径的成本。简单的优化方法,比如爬山算法会以增加g(x)为代价的方法改变 x。不幸的是,在一些问题中,会遇到“局部最大值”,x 值周围没有点 具有更大的对应g值,但是某个离x 值比较远的点表现更好。遗传算法改善了爬山算法,它保留了 x 的多样性,使用比如变异和交换的进化-启发式方法更新 x。

爬山算法和遗传算法可以用来学习出 x 的最优值。然而对于寻路问题,我们已经有了 A*算法找到最优的 x ,因此函数优化的方法就不需要了。

遗传编程是遗传算法的更深层次,它把程序当做参数。例如,你可以输入的是寻路算法而不是寻路路径,你的适应值函数会根据表现测算每个算法。对于寻路问题来说,我们已经有个很好的算法,我们无需在进化出一个新的算法。

也许在和神经网络结合的情况下,遗传算法可以应用于寻路问题的某个部分。但是,在这篇文章中我还不知道有何用处。相反,如果问题解是已知的,估计会有一个更有前途的方法作为许多可行工具之一,在寻路问题中优化 agent。

强化学习

和遗传算法一样,强化学习是一种非监督学习。然而,和遗传算法不同的是,agent 可以在他们的生存时间内学习;没必要等着观察他们的存活情况。并且,多 agents 同时参与到不同部分中分享各自学习成果是可能的。强化学习和 A*的核心部分有着一些相似的地方。

在 A*中,到达结束目标后会沿着经过的路径追溯回去,标记到目前为止所有路径的选择;其他选择就被去掉了。在强化学习中,可以测算每个状态时的情况,并且当前的奖(惩)都可以追溯回导致这个状态之前的所有选择。使用一个值函数表达这个追溯的过程,这有点像 A*中的启发式函数,但随着 agent 尝试新路径并对这过程进行学习的更新,这一方面两者是不同的。

相比于更简单的算法来说,强化学习和遗传算法的一个关键的优势是:在探求新解和利用目前学到的信息两者间是可以做出选择的。遗传算法,通过变异寻找(新解);强化学习,通过明确给出选择新行为的概率寻找(新解)。

即使和遗传算法结合,我认为强化学习也不会在寻路问题本身上使用。但是相对来说,它却可以作为一个向导,指导agent 在游戏世界中如何表现。

注: 函数近似方法可以变形为函数优化问题。为了找到最逼近 f(x)的f'(x),令 g(f’)=∑(f’(x)-f(x))^2(即在所有输入 x 上(f’(x)-f(x))^2的和)。

参考

作者写这个系列的参考文章在这里。我们翻译组的工作,基本结束了此为止咯,欢迎大家保持关注伯乐在线的其他文章 :)

1 4 收藏 评论

关于作者:土豆粉ss

兴趣:算法,人工智能,机器学习 个人主页 · 我的文章 · 13 ·   

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部