自动寻路算法（共5篇）
自动寻路算法 篇1
现今随着手机3D游戏开发技术的日渐成熟, 游戏玩家对游戏品质的要求也越来越高。玩家对游戏品质的评价一般主要取决于游戏的操控性是否灵活、游戏的虚拟环境是否逼真以及游戏的运行是否流畅等方面。设计开发3D游戏, 怎样在各个性能指标间实现平衡, 则属于核心问题。
1 AI自动寻路功能概述
在游戏中, AI (即人工智能) 系统主要是用于实现游戏角色的某种智能行为, 使用户的游戏体验更加逼真, 增加游戏的趣味性[1]。例如在射击游戏中敌人的子弹可以自动追踪攻击玩家;在NPC游戏中敌人可以自动的避开障碍物寻找最短路径到达玩家所在目的地对玩家进行攻击, 这些智能行为的实现就是通过AI系统中的智能寻路功能来完成的。
在技术实现方面, 本文所研究的寻路算法设计主要是基于一种经过变异的贪心算法———A Star算法框架构建的[2]。通过对游戏场景中预先设置的路径节点进行分析计算找出最优路线, 实现游戏角色的智能寻路。
2 3D游戏中AI算法的设计原理
A Star算法简称A*算法, 其基本原理是通过创建的开放式列表与封闭式列表对游戏场景中的所有路径节点进行比对和筛选, 从而计算出最短的路径, 为了节省游戏在这方面的计算开销, 该算法采取的是模糊比对, 省略了贪心算法中的回溯计算部分。
2.1 A*算法的基本原理
如图1所示, 将游戏角色的起始位置设为开始节点, 要到达的目的地设为目标节点, 黑色区域是障碍物标志, 白色区域为可通行路径。
A*算法的基本设计原理如图2所示, 首先将所有需要检测的路径节点读入到开放式列表, 从起始节点开始中选取距离目的节点最近的节点依次与目标节点进行比对, 所得到路径即为最优路径。该算法通过一定的择优策略选择场景中节点进行比对, 例如将图1中的路径起始节点设为A, 目标节点设为B, 当前计算出的最优路径节点为C, 在仅考虑节点间的几何距离前提下其节点代价的计算可由公式 (1) 得出:
通过计算的各个节点代价, 选择代价最小的节点优先进行比对。最坏的情况是遍历了所有的节点才得到结果, 因此该算法的计算效率与游戏场景中的节点数量有直接关系, 如果游戏场景较为复杂, 包含有大量的路径节点信息, 会严重增加算法开销, 要解决这些问题就需要对A*算法做进一步的优化。
2.2 A Star寻路算法的优化
首先, 从节点列表的结构优化上着手, 改进A*算法的性能。主要是将所有节点按照计算出的节点代价由小到大进行排序并建立相应的结构列表, 根据节点的变化动态维护该数据结构, 从开放式列表中选择最优节点时可直接通过该数据列表读取到当前的最优节点, 该方法适用于复杂的游戏场景寻路, 以增加游戏占用的系统存储空间为代价减少寻路算法的系统开销。
其次是在动态场景中对寻路算法进行优化调整。当在游戏中有多个对象同时进行寻路移动时, 优化策略可分为以下几步来实现动态的路径调整:
1) 为每个对象建立一个碰撞列表用于记录该对象发生过碰撞的路径信息;
2) 根据各个对象之间的优先级进行排序, 当检测到碰撞后, 将选择优先级别最高的对象重新进行节点定位和路径选择, 同时停止其他对象的移动, 直到优先级最高的对象通过再继续原路径的移动;
3) 将上一步碰撞检测到的路径信息记录到碰撞列表中, 每次检测到碰撞后, 都先在碰撞列表中进行查询。如果路径信息是重复的则要更新路径选择策略, 如果路径信息无重复则要对碰撞列表进行更新。这主要是为了避免对象的路径重复, 反复与同一对象发生碰撞。
3 3D游戏开发中AI寻路算法的具体实现
本文采用了目前在移动平台上较为流行的一款游戏开发引擎———Unity3D来进行AI寻路算法的设计。
3.1 3D游戏开发软件———Unity3D游戏引擎中AI系统的设计框架
Unity3D游戏引擎本身就提供有AI寻路系统, 主要采用的是路径节点 (Way Point) 算法进行路径选择。Way Point算法是基于A*算法框架由Unity3D引擎自行开发的寻路策略, 其设计框架可以简述为:
首先通过调用Unity3D游戏引擎中的Navigation路径导航系统对场景中的地形进行分析计算, 建立节点信息列表;
其次进行寻路者的设置, 为寻路者添加AI寻路组件 (Nav Mesh Agent) 计算寻路者的节点位置、运动速度、旋转速度等信息;
初始化节点信息, 通过Way Point算法在游戏场景中标记出所有的路径节点, 并在各个节点间建立连接路径, 在确定了的起始节点与目的节点之间每次任取两个分别与起始节点和目的节点临近的节点计算路径代价, 并优先选择其中代价最小者来获取最短路径;
编写寻路控制脚本用于实现寻路者的动态寻路控制, 当目的节点发生改变, 通过寻路脚本控制可动态更新追踪目的节点并进行路径的调整控制。
3.2 三维游戏场景中AI寻路功能的实现与控制
Unity3D游戏引擎主要支持C#、Java及boo三种脚本的编程开发, 这里对自动寻路的控制实现编程采用的是C#脚本, 其核心代码示例如下:
4 结论
本文针对目前3D游戏开发中的研究热点———AI寻路功能的优化进行了一些研究和尝试。通过对A Star寻路算法的应用分析, 再进一步优化了算法, 并通过Unity3D平台进行了实现。但为了兼顾游戏的运行效率, 算法设计中未能提高现有寻路机制的精确性, 在一些特殊情况下会影响到用户的游戏体验, 在这一方面还有待进行更加深入的研究。
参考文献
[1]梁毅, 周刚.基于定位点和路径复用的大型多人在线游戏寻路算法[D].成都:四川大学, 2013.
[2]杨科选.人工智能寻路算法及其在游戏中的应用研究[D].长沙:中南大学, 2013.
A*算法在游戏寻路中的应用 篇2
1 广度优先搜索算法在游戏中的应用
“连连看”游戏规则是:在有限的时间内,将图案相同的两张牌用三根以内的直线连在一起就可以消除,只要把所有的图案全部消完即可获得胜利[1]。
采用广度优先搜索,将目标函数修改为从一个点到另一个点的转弯次数,首先把图形Start (x1,y1)压入队列。然后扩展图形Start(x1,y1)可以直线到达的节点,用集合S0=Find(x1,y1)表示这些节点都可通过转弯数为0的路径到达,如果图形Target(x2,y2)包含在集合S0中,结束搜索。
否则,继续扩展集合S0中空格可以直线到达的节点,用集合S1={Find(p)|p∈S0}表示,令S1’=S1-S0(S1包含了S0),表示S1’中的节点和图形Start(x1,y1)之间可以通过转弯数目为1的路径连起来。如果图形B(x2,y2)在S1’中,则图形S,T之间可以用转弯数目为1的路径连接,结束搜索。
否则,继续展开S1’集合中的空格可以直线到达的节点,用集合S2=Find{Find(p)|p∈S1’}表示,令S2’=S2-S0-S1=S2-S0-S1’(S2包含了S0和S1),集合S2’是图形A(x1,y1)可以通过转弯数目为2的路径到达的格子。如果图形T(x2,y2)在集合S2’中,则图形A,B之间可以用转弯数目为2的路径连接,否则图形A,B之间不能通过转弯小于3的路径连接。
2 A*算法的估价函数设计
A*算法具备很多优点。首先,如果起点和终点之间存在有效路径,A*就一定能够找到;其次,只要H(n)是可纳的,它就一定能找到一条最短路径;第三,A*算法是启发式搜索算法中搜索状态最少的一种算法,它使启发式函数得到了最有效的应用[2]。
启发式搜索的核心是估价函数F(n),“连连看”中连线不能从尚未消去的图案上经过,节点只能在四个方向移动,两个相同图案之间的连线不能超过两个弯。
因此估价函数中,需要考虑当前格Current到目标格Target的移动耗费,当前格Current与开始格Start的转弯数,用估价函数表示为[3]:
F(n)=G(n)+H(n)+C(n) .
在“连连看”游戏中,格子S的移动方向分水平上、水平下、竖直上、竖直下四个方向,每个格子对应着有图案、无图案两种状态。
设计二维数组map[Rows][Cols]表示对应的方格是否有图状态,当数组元素值取1表示该位置有图,取0表示无图。
估价函数F(n)的取值设定:
G(n):移动的距离。结合游戏的要求,这里设定沿着四个方向移动,移动位置上有图则距离值为无穷大,这样的格子不考虑扩展,如果无图距离值为1,如图1所示。
H(n):指定格子到目标格横向走的步数与纵向走的步数和;例如T(Tx,Ty)是终点,C(Cx,Cy)是当前点,则:h(n)=|Tx-Cx|+|Ty-Cy|。
C(n):起点Start到指定格子的转弯数,直线连接C取值为0,转一次弯,C值为1;转两次弯,C值为2;转弯数为3,估价函数无穷大。
例如:开始点S与终点T在一条横线上,周围的格子状态如图1所示;计算S点的四方向节点的F(n),上方和左方的节点估价函数无穷大,右方节点的f(n)=1+3+0,下方节点的f(n)=1+5+0;计算过程如图2-图4所示。
展开右方F值=4的点,计算其右节点估价函数f=4+(1+2+0)=7,如图5所示。
展开F值=7的节点,计算出其右节点估价函数f=7+(1+1+0)=9,如图6所示。
展开F=9的节点,终点就在它的展开节点中了,完成了最短路径工作。
3 A*算法的应用设计
A*算法是一种典型的启发式搜索算法,它除了利用上述的启发函数来对搜索过程中的每一个节点进行评估,另外它还必须有两个表:Open表和Close表[4]。
Open表由未考察的结点组成,保存了打开节点的F值;每次从Open表中取F值最小的节点展开后续节点。
Close表由已考察的结点组成,将已展开的节点加入其中(不包括终点)。
结合“连连看”的要求,A*算法实现的过程可以用伪代码描述,假设起始节点为Start,目标节点为Target,其中Current是每次被考察的节点,临时节点Temp代表Current的四方向上的有效子结点,所谓有效子结点就是指在“连连看”中没有图案的格子。当Current等于Target时搜索成功。
A*算法作为“连连看”中的寻路算法,用伪代码表示如下:
4 A*算法在“连连看”中的应用
4.1 数字化运动方向
A*算法的数据结构设置,程序设计有其一定的模式,这里针对“连连看”,给出A*算法的实现代码。
“连连看”中节点的运动方向是4个,可以设置一个常量数组,把每个方向的移动坐标变动量存入数组,定义类的方法,传入参数:起始点坐标和目标点坐标:
int Move[4][2]={{-1,0},{0,1},{1,0},{0,-1}}//数字化运动方向
展开节点前,有些数据需要初始化,如:
Int OpenListCount=1; //定义变量记录OpenList中的展开节点数
Int NewOpenNodeID=1; //定义变量记录节点的ID号,初值为1
ifOpenStadus=1; //变量为1表示节点打开状态
4.2 计算转弯
“连连看”中计算节点的转弯数很关键,因此定义类方法GetCrossing,传递节点的ID号,返回起点到节点的转弯数。
4.3 寻路设计
展开节点后,定义类方法FindPath传递相关参数计算节点坐标,记录节点ID号,增加节点到OpenList,计算G、H、E、F值,然后把展开的节点加入到whichNode中。
5 算法分析
假设游戏地图n行m列,设N=m*n,由于每个节点做为扩展节点进入Open表最多一次,因此Open表中最多处理N个展开节点。扩展每个节点需要O(1)的时间,因此算法最多耗时O(N)。构造相应的最短路径需要O(L)的时间,L是最短路径的长度。当节点数为N时,广度优先搜索算法的复杂度为O(N*N),A*算法的复杂度为O(N+L),计算量不会随着节点的展开迅速增加,只要起点和终点之间存在有效路径,A*算法就能够快速找到。
6 总结
本文将A*算法应用在“连连看”游戏寻路搜索上,给出了改进的估价函数、算法运行流程,能够用O(N+L)的时间完成最短路径搜索,很好地适应游戏的要求。A*算法结合了启发式方法和形式化方法,为许多即时战略游戏所用到,可以修改方向参数,对于游戏中八方向移动搜索路径也具有一定的实际应用价值。
摘要：寻路问题是游戏设计解决的基本问题,通常采用广度优先搜索算法完成。针对“连连看“游戏的路径搜索特点,详细地分析了A*算法在其中的应用,确认最初估价函数的构成,结合实际应用情况,给出了A*算法的改进及实现。
关键词：广度优先搜索,A*算法,估价函数
参考文献
[1]胡正红.一种寻路算法在游戏中的应用[J].山西电子技术,2009(6):53-54.
[2]陈和平,张前哨.A算法在游戏地图寻径中的应用与实现[J].计算机应用与软件,2005(12):118-120.
[3]Hu zhenhong,Jinli.Application and Implementation of A*Algorithm in Picture Matching Path-finding[G].In:2010 International Conference on Computer Applicationand System Modeling(ICCASM 2010),Taiyuan,China,2010:224-227.
寻路观后感 篇3
革命题材电视剧《寻路》，聚焦了1927年”4.12”大屠杀至1932年10月宁都会议五年的时间里，毛泽东和他的战友们在斗争摸索革命新道路的艰苦历程。剧集非常真实而又从容地加以呈现，尤其细腻地刻画了毛泽东、周恩来等革命领袖的喜怒哀乐，把革命领袖当做普通人加以描写，让观众看到在残酷斗争的岁月中，革命先辈是如何闯出一条走向胜利的道路。
《寻路》是靠细节取胜的，而在以前的影视剧中很少看到这样的细节描写。
比如，在第一集描写“ 4·12”大屠杀当天，周恩来只身去见蒋介石，冒着杀头的危险，不惧个人生死，大义凛然痛斥蒋介石，然后昂首阔步走出了国民党军的司令部。这一幕，就相当地惊心动魄。
从“4·12”到“7·15”，周恩来同志是如何指挥上海白区反蒋斗争的，过去所有重大革命历史题材影视剧都没有系统表现过，而在寻路这部电视剧却写得很详细。蒋介石命陈立夫建立特务机关，收买共产党内变节分子，疯狂暗杀中共领导人。周恩来大力加强中央特科，派人打入敌人内部，设法变敌为我耳目，严惩叛徒。
陈赓为了保护周恩来，在路边开枪扰乱视听，然后周公跳车隐蔽，陈赓趁着界面上乱做一团的时候，拔掉敌人摩托车的钥匙，然后又开车跑掉……这种反击的细节化凸显了周公和中共地下工作者的过人胆略和气魄。
还有，毛泽东受中央委托，去湖南浏阳发动秋收起义，途中遇到几个土鳖地主武装抓捕，毛泽东机智周旋，先是递过银元，后又装作解手逃跑，最后纵身跳进池塘，逃过一劫，但是脚受伤了，鲜血直流，他不得不忍着剧痛，一瘸一拐地赶往起义地点。
《寻路》立足这样一个高度，从一开始就提出了这个尖锐的问题：大革命失败了怎么办？走城市暴动还是走另外的道路？从这个意义上说，以毛泽东为代表的“农村包围城市，武装夺取政权”的道路，不论在中国共产党内，还是从鸦片战争以来中华民族复兴之路的探索来看，都是一次很大的思想解放，而且从国际共运史来看，也是一次伟大的思想解放运动。
当时共产国际指导着全世界各国的共产党革命，就是要求走城市暴动的道路，准确地说是走中心城市暴动道路。中共中央领导机构在上海，从莫斯科回来的、从法国回来的中央领导人，他们也只知道有一个中心城市暴动的道路。因为无产阶级第一次夺取国家政权是巴黎公社，第二次是十月革命，不但是在城市暴动，而且是在中心城市暴动，是在首都暴动，在国际共运史上这是唯一的经验。
上海党中央机关不断地发动城市暴动，不断地失败，还不断地派人到苏区去，对毛泽东展开批判，毛泽东一次又一次被剥夺军事指挥权，不断受到批评和压制，但是他不计个人得失荣辱，顽强不屈地和错误路线作斗争。最后中央机关自己也在上海呆不下去了，只能撤到苏区；但是井冈山的斗争，中央苏区的斗争，反围剿的斗争却是不断地走向胜利。
这两方面强烈的细节对比，说明了正确道路的探索必须从实践出发，实践是检验真理的唯一标准。
剧名《寻路》就是讲述以毛泽东为代表的中国共产党人通过一次次的尝试总结出“农村包围城市，武装夺取政权”这条胜利法则，这不仅是用鲜血换来的斗争经验，也是奠定了中国共产党最后胜利的基调。路，的确是人走出来的，但寻找路径的千辛万苦也不能忘记。
自动寻路算法 篇4
随着互联网的普及,网络娱乐产业迅猛的发展, 网络游戏已经成为人们日常生活中的重要组成部分,越来越多的研究开始侧重于如何寻求游戏角色更优的路径搜索上来。A* 算法作为一种高灵活的、高性价比的寻路算法,一直被游戏行业广泛地采用[1,2]。
目前,很多学者对A* 算法都有过比较深入的研究,同时也取得了很多成果。文献[3]将A* 算法与单个物体寻路算法相结合,文献[4]将A* 算法与光线跨域算法相结合,都在一定程度上缩短了算法的时间消耗; 文献[5]提出了m - A* 算法,算法是在A* 的基础上,结合四叉树的地图划分方法, 对A* 算法在动态搜索资源耗费大的缺陷进行了改进; 文献[6] 提出了m - LPA * 算法,算法对m - A* 算法与基于增量搜索的LPA* 算法进行了结合,降低了LPA* 算法搜索时的资源耗费; 文献 [7]对路径平滑进行了一定的研究,但在游戏中并不适用,没有考虑游戏本身的特点。
游戏地图中的路径搜索是一个比较复杂的问题,很多数时候都需要结合多种解决方法,然后再根据实际的游戏开发需求,最后得到一个比较好的适合该款游戏的解决方案。本文采用并行搜索法对普通A* 算法进行优化,该算法能够有效的缩短路径搜索时间,提高游戏的可玩性。
1A算法
A* 算法是一种静态路网中求解最短路径最有效的方法。常用于游戏中的NPC( 非玩家控制角色) 和线上游戏中BOT( 机器人) 的移动计算上[4]。 该算法像Dijkstra算法一样,可以找到一条最短路径; 也像BFS( Breadth First Search,BFS) 算法一样, 可以进行启发式的搜索[3]。
该算法公式表示为: F ( n) = G ( n) + H( n) ,G( n) 表示从起始节点S到目标节点D的搜索路径的过程中,到达当前节点n己经花费的代价,H( n) 表示从当前节点n到目标节点D的最优路径的估价值,即从当前节点n,估计到达目标节点D将要花费的估计代价,F( n) 代表节点n的估价函数,是G( n) 和H( n) 总和的估价值。保证找到最短路径的条件,关键在于H( n) 的选取,若H( n) ≤n到目标节点的距离的实际值,则搜索的点数多,搜索范围大, 效率低,但能得到最优解; 若H( n) > n到目标节点的距离的实际值,则搜索范围小,效率高,但不能保证得到最优解。
A * 算法主要 用两个列 表OPEN列表和CLOSED列表来存储相关节点信息,OPEN列表用来保存将要搜索的节点,CLOSED列表用来保存通过计算得出 的OPEN列表的适 合算法要 求的节点[8,9]。在搜索时对OPEN列表中的节点按照启发函数值进 行排序,选择F值最小的 节点压入CLOSED列表,并产生此节点的所有后继压入OPEN中,作为下次 的扩展对 象。在搜索中 不断更新OPEN和CLOSED列表,以确保当前保存的是已扩展的起始节点到目标节点的最优路径上的节点。
2改进的A*算法
普通的A* 算法只是从起始节点出发,开始搜索周围节点,并逐步延伸,直到找出最佳路径。文中考虑同时从起始节点和目标节点搜索,当在某块区域有相同的延伸子节点时,结束算法。设节点坐标为( X,Y) ,则起始节点S和目标节点D的启发函数H( S) 用两点间的最小距离表示为公式( 1) 。
但考虑到计算机在处理开平方根运算会增加计算量,用一个近似的公式( 2) 取代公式( 1) 。
改进的A* 算法的主要步骤如下:
1设起始节点为S,目标节点为D,创建四个列表,两个开启列表OPEN1、OPEN2表,两个关闭列表CLOSED1、CLOSED2表,并初始化CLOSED1、 CLOSED2表为空。
2把节点S、D分别放入OPEN1、OPEN2表中。
3搜索OPEN1、OPEN2表中的节 点,如果OPEN1、OPEN2表均为空,则失败退出,表示没有路径。
4如果OPEN1表或OPEN2表不为空,则分别从OPEN1、OPEN2表中找出f ( N) 值最小的节点N1、N2。
5把节点N1、N2从OPEN1、OPEN2表中移出, 分别放入CLOSED1、CLOSED2表中。
6判断节点N1、N2是否为同一节点,如果是, 则成功退出,找到最优路径。
7如果节点N1、N2不是同一节点,扩展节点N1、N2上下左右四个方向的子节点,则对于节点N1的每一个子节点M1和节点N2的每一个子节点M2,计算F( M1) 和F( M2) 的值。
( a) 如果节点M1不在OPEN1表中,也不再CLOSED1表中,则把节点M1添加到OPEN1表中; 如果节点M2不在OPEN2表中,也不再CLOSED2表中,则把节点M2添加到OPEN2表中。
( b) 如果节点M1已经在OPEN1表中,比较刚计算的F( M1) 新值与该节点在OPEN1表中的F ( M1) 值,如果F( M1) 新值较小,表示找到一条更佳路径,则用此F( M1) 新值替换OPEN1表中F( M1) 旧值; 如果节点M2已经在OPEN2表中,对节点M2做相同的操作。
( c) 如果节点M1在CLOSED1表中,则跳过此节点,返回7继续扩展节点N1的其他子节点。
( d) 如果节点M2在CLOSED2表中,则跳过此节点,返回7继续扩展节点N2的其他子节点。
8跳到步骤3,继续循环,直到找出最优解或无解退出为止。
3改进的A*算法的实现
改进的A* 算法的程序实现主要包含三个大模块,分别是主模块,Draw模块和Map Mode模块。现将各模块简单介绍如下:
在主模块中定义并初始化网格地图,主要语句如下:
int[,] map = new int[30,30 ]{ 初始化部分, 用数字1表示通路,数字255表示障碍} 。
在Draw模块中,主要实现绘制起点、终点、障碍、路径并给它们赋予不同的颜色。
在Map Mode模块中,定义Grid数据结构,语句如下:
在实现过程没有创建表,而是在网格节点中包含字段open( 表示当前节点是否在计算列表中) 和字段close( 表示当前节点是否在行走路径中) ,语句如下:
Map Grid[id]. open = false; 表示当前节点不在OPEN表中
Map Grid[id]. close = false; 表示当前节点不在CLOSE表中
通过计算节点相邻的上 下左右4个节点的F( n) 的值,并维护节点的字段open、close,在字段open为true的所有节点中选择F( n) 值最小的节点为下一步网格,实现路径搜索。同样的在网格结点中包含字段f( 表示当前节点的估价函数) 、字段g ( 表示初始节点到当前节点的实际路径消耗值) 和节点h( 表示当前节点到目标节点的估计消耗值) , 估价函数的计算语句如下:
Map Grid [id]. f = Map Grid[id]. h + Map Grid [id]. g;
在本文改进的算法实现过程中,定义两个广泛型用于输出最终的路径,其语句如下:
List < Point > my Point List = new List < Point > ( ) ;
List < Point > my Point1List = new List < Point > ( ) ;
在输出过程中,首先对my Point1List执行翻转操作,将其中元素 逆序排列,然后依次输 出myPoint List和my Point1List中元素,即为最终路径。
4实验和对比分析
为了准确的分析改进的算法的性能,本文将其与普通的A* 算法进行实验比较。实验的硬件环境: Pentium( R) Dual - Core CPU T4200 @ 2. 00GHz,内存为2GB。软件环境: 操作系统为Microsoft Windows 7旗舰版。开发平台为. NET,开发语言为C#。
普通的A* 算法和改进的A* 算法运行结果如图1 - 2所示,通过单击界面右边的按钮完成相应的操作,其中黑色区域代表障碍。分别选取不同的起点和终点进行十次实验,记录每次实验两种算法的寻路时间,实验结果见表1,其中寻路时间单位为毫秒。
通过计算表1中的数据可以得出,普通的A* 算法平均寻路时间为23. 8ms,本文改进的A* 算法平均寻路时间为16. 1ms,实验证明,在相同的硬件和软件环境下,改进的A* 算法比普通的A* 算法平均寻路时间提高了32. 35% 。
5结束语
自动寻路算法 篇5
避障寻径问题被证明是一类NP-Hard问题, 一直以来都是计算机科学人工智能领域的热门话题, 渗透于我们日常生产生活的各个领域, 如无人机器侦察兵、无人驾驶运输车、城市内的车辆自动导航、游戏开发等。其求解算法的研究, 近年来受到广泛关注。
Bob回家游戏从本质上来讲, 是避障寻径模型的一个趣味数学描述。由于思想和方法的局限性, 在现存算法中, 人们主要考虑比较简单的静态环境下的理想情况, 对于复杂的动态情景仍涉及未深, 有些甚至根本没有探讨。然而, 在实际环境中遇到的问题并不如想象的简单, 往往随时间、地点的不同而产生变化。目前对动态系统变化的研究大多是在环境变化统一的动态环境中, 并不能体现算法对环境变化的适应能力, 而且遗传算法因本身的不足而使算法收敛速度变慢、性能不稳定等。因此, 对动态环境下问题的研究更加具有现实意义。
二、背景
Bob回家游戏是在给定一个具有许多障碍物的迷宫式地图中为虚拟机器人Bob寻找一条从入口避开障碍物到出口路径的问题。图1是一个迷宫式地图, 入口、出口用灰色表示, 指定迷宫的左边为入口, 右边为出口, 也可以理解为出口位置就是Bob的“家”。障碍物用黑色的矩形表示, 没有障碍物的位置用白色的矩形表示。图2是一条Bob回家路线, 即为该问题的一个可行解 (非最优可行解) 。图示中由带交叉线的矩形块组成。
环境的变化由变化的频率、复杂度、预测性和周期的长度或准确度4种要素来体现。对于Bob回家游戏, 从广义上说, 可以认为任何基于时间的地图变化问题都是动态的。Bob回家游戏采用小生境技术, 通过将每一代个体划分为若干类, 每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群, 在种群中以及不同种群中之间杂交、变异产生新一代个体群, 找到全部最优解。
免疫进化算法是通过由免疫学理论和观察到的免疫功能、原理和模型启发而构造出免疫操作, 并和进化计算相结合的一类智能优化算法, 被应用在迷宫游戏中解决一些复杂优化问题。
三、算法
标准遗传算法对于静态优化问题是一种有效且实用的工具, 然而却难以解决动态环境的求解问题。这主要有3个原因:遗传算法具有进化惯性、群体具有“集中”功能、个体本身没有“识别”功能。
(一) 小生境免疫遗传算法的步骤
针对动态环境下Bob游戏的求解要求, 结合上面对相关技术的总结和分析, 提出一种小生境免疫遗传算法。这种算法在标准遗传算法中加入具有记忆优秀路径片的免疫算法和保证群体多样性和小生境算法, 其步骤为:
1.初始化群体, 初始化动态环境参数;
2.评价群体的适应度;
3.若不满足停机条件则循环执行步骤4～10;
4.选择操作;
5.重组操作;
6.更新动态环境;
7.免疫接种疫苗和免疫选择操作;
8.小生境操作;
9.评价群体的适应度;
10.用上一代的最优个体替代种群中最差个体;
11.输出种群中的最优个体。
其中步骤7由以下2个小步骤组成。
(1) 免疫接种疫苗操作。作为局部搜索机制, 按免疫接种方式加入进化计算中, 以概率PI进行免疫接种疫苗操作。
(2) 免疫选择。如果Δf1<0, 则老个体被新个体替代, 否则按概率exp (-Δf1/Tk) 进行替代。在本文中, Tk取为Tk=1/ln (k+1) , k是进化代数。
(二) 疫苗提取方法
对Bob回家问题, 提取路径疫苗是找出最优解的关键。本文探索和总结出一种疫苗提取方法:当检测到环境发生变化时, 将原来路径中与障碍物不交的路线段取出, 给每一段长度赋予一个评价值, 依照评价值的大小进行概率分布, 按“适者生存”原则选择一个路线段, 作为个体的疫苗。
以图3为例, 在环境变化前获取了一条可行路线, 当环境发生一些变化时, 这条路线已经不通, 但这条路线上的一些路线段是依然有用的, 因为重新使用遗传算法等计算这个变化后的地图上的路线时, 图4中右下部分打上了粗线条的路线段仍然会是优化路线上的一部分。如果将打上了粗线条的路线段作为疫苗, 在此基础上进行计算, 速度会快很多。然而, 如果将左边打上了细线条的路线段作为疫苗, 在此基础上进行计算, 速度不会有提高。这个方法存在的难点在于计算机不能决定这2个路线段中哪一条更好。因此, 在算法中, 都要给它们机会, 并在进化过程学习积累, 淘汰差的, 保留好的。
四、实验结果及分析
对标准遗传算法、小生境遗传算法和小生境免疫遗传算法进行动态环境的实验对比, 为这3种算法分别建立了基于弹性壁原理的动态障碍物地图模型、周期性呈现动态障碍物地图模型、随机小扰动动态障碍物地图模型, 并进行仿真, 将这3种算法的多次运行情况进行记录。
由于算法不一样, 运行每代所耗机器时间也会有差异, 不能单纯用环境变化后找到新满意解所需的进化代数作为动态算法的评价指标, 而是记录每种算法在检测到新环境后进行响应并找到新环境下满意解的平均代数, 再除以该算法在同一机器上每秒钟的平均可执行代数, 得到的一个系统自动计算的响应时间, 这个响应时间直接决定该算法的优劣。
本文将求解动态的Bob回家问题的“及时响应”指标定为0.5秒 (算法效率改进之后可再缩短该标准) ;表1、表2和表3分别是基于弹性壁原理的动态障碍物、周期性呈现动态障碍物、随机小扰动动态障碍物的情况下, 3种算法的运行结果。
表中的“算法A”代表改进的遗传算法;“算法B”代表小生境遗传算法;“算法C”代表本章节提出的小生境免疫遗传算法。表中的变化次数表示环境变化次数, 而表中是否达到及时响应标准是用某次变化多次求解的平均响应时间对比标准得来的, 这样是为了在一定程度上消除随机性, 更准确地分析算法的性能。
从表1和表2来看, 标准遗传算法对动态环境的Bob回家问题基本不适用, 成功率很低。分析其原因, 是因为在静态环境中的进化后期, 种群已经收敛, 群体中大部分个体都往一个方向发展, 甚至存在很多相似个体, 而动态环境的变化调整了进化方向, 而这个进化方向不一定与原来一致。从表3看, 结果也得到了证实。对于动态环境, 采用小生境技术的算法B和算法C的成功率比单纯采用标准遗传算法的算法A高很多。
以随机小扰动动态环境为例, 用图加以说明。在第三类动态环境中, 迷宫正中间的障碍物上移一个距离, 原来的地图 (如图5) 变成了如图6所示。标准遗传算法因为上述分析原因而使在图5所示地图下优秀的路径 (或者相似路径) 大量保留, 如图7所示。很难出现如图8所示的碰壁路径还被保留的情况。而当地图产生变化时, 标准遗传算法的历史最优解被障碍物堵的严严实实 (如图9和图10所示) , 而曾经被认为不好的路径却成为了当前环境的最优路径。
通过对实验结果的综合分析, 不难看出, 保持种群多样性, 即解集空间的均匀分布度, 对种群进化特别是动态环境的进化起着至关重要的作用。
五、结论
本文对动态环境进行了深入分析研究, 为Bob回家问题建立了符合现实或游戏玩家需要的动态模型。结合小生境算法和免疫算法, 解决遗传算法求解动态优化问题时出现的易陷入局部最优、实时响应能力差等不足, 着重提高种群个体在整个空间的分布度和记忆能力。迷宫出现障碍物弹性移动、周期移动和随机移动的, 帮助Bob快速调整自己的行走路线, 找到出口的最优行走方案。
参考文献
[1]Mat Buckland.游戏编程中的人工智能[M].吴祖曾, 沙鹰, 译.北京:清华大学出版社, 2006.
[2]J.Branke.Envolutionary optimization in dynamic environments[M].Springer, 2002.