文档章节

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

oschina_00
 oschina_00
发布于 2017/03/02 11:37
字数 2069
阅读 29
收藏 0

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的和)。

 

英文:theory.stanford.edu

译文:伯乐在线 - 土豆粉ss

链接:http://blog.jobbole.com/90681/

本文转载自:http://blog.jobbole.com/90681/

oschina_00
粉丝 5
博文 101
码字总数 0
作品 0
廊坊
私信 提问
A星寻路算法入门(Unity实现)

最近简单学习了一下A星寻路算法,来记录一下。 还是个萌新,如果写的不好,请谅解。 Unity版本:2018.3.2f1 A星寻路算法是什么 游戏开发中往往有这样的需求,让玩家控制的角色自动寻路到目标...

青空哲也
03/14
0
0
游戏中的人工智能之流场寻路

流场简介 流场,一般为网格图,网格中的每一个节点包含一个向量,该向量是物体在该位置时期望的速度。 流场寻路 利用流场的速度信息指导大量物体同时进行寻路。换句话说,如何生成可以寻路的...

RonTang
2016/04/20
0
0
【文集】寻路算法汇总

寻路是游戏开发中非常重要的一部分,能够让人物的操作更符合玩家想要的行为 先来一个在Unity3D中实现自动寻路的文章 Unity3D 自动寻路 在Unity3D中实现以及调试A*寻路算法 Unity3D A* 寻路...

CatherinePlans
2017/11/05
0
0
unity-AI设计理念和编程思想(三)

前两个模块大致讲了讲AI角色的感知和自主决策,决策之后呢?当然就要开始行动了。比如AI角色发现一个目标,并决定去攻击它,但它与目标之间可能还有一段距离,AI角色需要先到达目标点,这就需...

scopperil
2018/05/24
0
0
游戏开发与程序设计知识总结05——游戏前端开发

更新日志 每此对思维导图有改动或者在github中有了对应的实现,则增加一条更新日志。 前言 这是游戏开发与程序设计知识总结系列文章的第五篇游戏前端开发。本系列文章的初衷源于我正在找工作...

kashiwa
2017/09/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

可见性有序性,Happens-before来搞定

写在前面 上一篇文章并发 Bug 之源有三,请睁大眼睛看清它们 谈到了可见性/原子性/有序性三个问题,这些问题通常违背我们的直觉和思考模式,也就导致了很多并发 Bug 为了解决 CPU,内存,IO ...

tan日拱一兵
17分钟前
2
0
网络七层模型与TCP/UDP

为了使全球范围内不同的计算机厂家能够相互之间能够比较协调的进行通信,这个时候就有必要建立一种全球范围内的通用协议,以规范各个厂家之间的通信接口,这就是网络七层模型的由来。本文首先...

爱宝贝丶
21分钟前
2
0
Jenkins World 贡献者峰会及专家答疑展位

本文首发于:Jenkins 中文社区 原文链接 作者:Marky Jackson 译者:shunw Jenkins World 贡献者峰会及专家答疑展位 本文为 Jenkins World 贡献者峰会活动期间的记录 Jenkins 15周岁啦!Jen...

Jenkins中文社区
38分钟前
8
0
杂谈:面向微服务的体系结构评审中需要问的三个问题

面向微服务的体系结构如今风靡全球。这是因为更快的部署节奏和更低的成本是面向微服务的体系结构的基本承诺。 然而,对于大多数试水的公司来说,开发活动更多的是将现有的单块应用程序转换为...

liululee
53分钟前
7
0
OSChina 周二乱弹 —— 我等饭呢,你是不是来错食堂了?

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @ 自行车丢了:给主编推荐首歌 《クリスマスの夜》- 岡村孝子 手机党少年们想听歌,请使劲儿戳(这里) @烽火燎原 :国庆快来,我需要长假! ...

小小编辑
今天
581
10

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部