大型油库消防救援寻路算法改进①

李克文,朱虹吉

(中国石油大学 计算机与通信工程学院,青岛 266580)

大型油库消防救援寻路算法改进①

李克文,朱虹吉

(中国石油大学 计算机与通信工程学院,青岛 266580)

大型油库区的地形不同于城市、山地等复杂的地形,虽然范围较大,但是油库区地形十分规整,油罐等建筑排列整齐,且在储油罐区的道路是笔直畅通的.根据这些特点,将标准的A*寻路算法进行改进.一方面,根据油库地形结构简单,搜索节点相对少的特点,对A*算法中搜索Open表中节点的数据结构进行改进,采用排序算法提高了搜索效率;另一方面,根据储油罐区道路笔直畅通的特点,将道路分为有障碍路段和无障碍路段,分而治之,提高整体的寻路效率.实验证明,将两种改进方法进行结合,寻路时间明显缩短,平均搜索效率提高6.86%.

油库火灾;人工智能;A*算法;快速排序;分层寻路

强劲的工业增长和不断提升的国内水平近一步加大了中国对能源的需求,而在这些能源中,石油扮演着不可或缺的重要角色.油库区则是最重要的生产和储备场所,是危险物质的集中地,火灾事故则是油库安全问题的重中之重.一旦发生油气泄漏,甚至是起火爆炸,其造成的危害不可估量.所以,当事故发生时,救援人员、车辆如何能以最快最有效最合理的方式进入到事故现场就成了应急救援中十分关键的一个环节.在三维模拟演练系统中,电脑控制的角色能否最快找到最佳路径成为了能否完成灭火救援任务的关键.当下主流的最短路径搜索算法主要定位在贪心算法上,研究更加有效的数据结构和搜索算法,从而降低算法的时间和复杂度.贪心算法的主要代表是Dijkstra算法,其思想是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法虽然能够算出路径的最优解,但是由于其建立计算节点过多,所以效率很低.A*算法则是当下游戏中非玩家控制角色(NPC)在地图中智能寻路应用最广泛的算法.二者相比: Dijkstra算法计算原点到其他所有点的最短路径长度,而A*算法目标在于点与点的最短路径;其次Dijkstra算法更多建立在抽象的图论层面,A*算法则可以更有效的应用在实际地图的寻路中;除此而外,Dijstra算法的本质是广度优先搜索,所以空间复杂度和时间复杂度都比较高,而A*是通过计算到原点的代价和目标点的估计代价,是一种启发式算法.A*算法引入的启发信息提高了搜索的效率.

目前的A*寻路算法存在一些不足之处:当搜索地形复杂,搜索节点的数量会非常巨大,这样就会降低A*算法的效率;另一方面,在搜索的地形中,部分道路是笔直且无障碍物的,如果此时继续调用A*算法寻路,也会影响到整体的寻路效率.本文分析A*算法,针对大型油库区的地形的特点,结合前人所提出的方法,我们对A*算法提出改进,并在油库火灾三维模拟演练系统中进行验证.

1 A*算法

1.1 A*算法的基本原理

二十世纪六十年代,经典的A*算法在P.E.Hart等人发表的一篇关于启发式搜索算法的文章中被提出.到目前为止,A*算法是最有效的路径寻优算法,也是被人们应用最为广泛的人工智能寻路算法.

A*算法的基本思想:核心为一个估价函数F(n)= G(n)+H(n),其中F(n)代表当前节点n的启发函数,其值为从起始节点经过n节点到达终点的总代价,G(n)是从起始节点到达当前n节点的实际消耗代价,H(n)则表示从当前节点n到达终点的估计消耗代价.由此函数能得到每个节点的代价,通过该启发函数,在当前节点计算下一步能到达节点的F值,通过搜索,找到具有最小估价值F的点,然后继续往下搜索.A*算法中有两个表,Open表和Closed表,分别存放未扩展节点和已扩展的节点.A*寻路算法的基本过程为:

第一步:把起始点加入到Open表中.

第二步:查找Open表:

如果Open表为空,则表示寻路失败;寻找Open表中F值最低的节点作为当前节点,并将其存入到Closed表中.

如果当前点为目标节点,则寻路成功,转到第四步.

第三步:对相邻的每个节点进行如下操作:

如果该节点不可通过或者已经在Closed表中,放弃该节点.

如果该节点不在Open表中,把它添加进去,并记录F,G和H值.

如果该节点已经在Open表中,进行F值的比较,选择具有较小F值的节点,并重新计算该节点的G值和F值.

如果相邻节点搜索完毕,则转向第二步;否则,转向第三步.

第四步:保存路径,根据Closed表中节点信息,进行逆向提取,从而得到路径.

经典的A*算法中Open表采用保存当前节点相邻的可以作为下一个节点的节点,也就是将要搜索的节点;Closed表用来保存通过计算得出来的Open表中适合算法要求的节点.

2 A*算法的改进

2.1 对Open表搜索速度优化

在标准的A*算法中,Open表中搜索具有最小F值的节点是路径搜索过程中最缓慢的部分.特别是当搜索的地形复杂时,搜索节点的数量会大大增加,这时候进行A*算法搜索,会反复搜索这个庞大的Open表,此时A*算法中搜索Open表的效率会明显的下降,从而影响到整体的搜索效率.标准A*算法的Open表中节点通常是无序的,这样就给搜索增加了难度.一个与搜索地形相匹配的存储方式,可以提高搜索效率;不匹配的存储方式,使得搜索效率降低,将严重影响路径搜索的时间.

大型油库区的地形通常情况下是十分规整的,油罐、厂房等建筑物排列整齐.网格化以后的油库区地图跟大部分复杂的游戏地图比较,搜索节点较少.针对该特点,本文对Open表中节点存储方式进行改进,根据表中F值的大小对节点进行排序来提高搜索效率.比如,Open表中F值按照从小到大的顺序进行排列,每次想要找到最小的F值节点,只要选取Open表中的第一个节点即可.目前,有很多的排序方法可以应用到Open表的节点排序.

本文采用快速排序方法对Open表中节点进行排序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分数据要小,然后再按照此方法对这两部分数据进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.对于A*算法中Open列表来说,从比较新元素的F值和列表中元素的F值开始,如果新元素的F值较小,则让新元素与1/4处的节点进行比较;如果比1/4处节点的F值还小,那就和1/8处的F值进行比较;以此类推,不断进行折半比较,直到找到合适的位置,进行插入.如果一开始F值比中间节点的值大,则以同样的方法向后比较.

从上述分析中可以看出,由于大型油库区地形规整,建筑物排列整齐的特点,大大降低了搜索节点的数量,不存在搜索节点过多,而导致搜索效率下降的情况,所以使用快速排序算法对Open列表进行排序,可以有效地提高对Open列表的搜索速度.本文中我们将对此进行实现,并通过实验进行证明其有效性.

2.2 油库的储油罐区分层寻路方法

大型油库的储油罐区地形的特点:罐体周围道路是笔直且无障碍的.如果此时继续调用A*算法进行路径搜索然后再通过此路段,无疑会降低整体的寻路效率.故本文结合该特点,提出改进:即对储油罐区没有障碍物且笔直的道路进行标记,我们称其为无碍路段,当我们进行路径搜索,到达一个无碍路段时,且要通过此无碍路段,此时我们放弃调用A*寻路算法,让寻路者直接通过该区域,到达此无碍路段的另一个端点,继续寻路;当寻路者到达障碍物附近区域时,为有碍路段,我们继续调用A*算法寻找最优路径,从而构成无碍路段和有碍路段分而治之的寻路思想,提高路径寻路的效率.图1为该分层算法的流程图.

图1 分层寻路算法流程图

3 改进寻路算法在油库火灾三维模拟演练系统中的应用

3.1 算法在系统中的实现

本文以C++为编程语言,基于vs2010程序开发平台,引用第三方API函数库对三维油库火灾模拟演练系统进行了实现.在多人协同模拟演练模块,我们对本文所提出的改进A*算法进行了应用.本系统中的A*算法的估价函数H,我们采用曼哈顿距离进行估价,即:

其中,X代表目标节点在地图中的横坐标,Y代表目标节点在地图中的纵坐标;X’代表当前节点在地图中的横坐标,Y‘代表当前节点在地图中的纵坐标.图2为系统中油库区的俯视图;图3为网格化后的地图,其中黄色区域为障碍物区域不能穿过,绿色为起始点,红色为目标节点,蓝色最优路径.在图3路径的基础上,假设部分路段在施工,禁止通行的情况下,在图4中我们以黑色表示,重新搜索后的路径为图4中所示.

图2 油库区俯视图

图3 网格化的油库区地图

3.2 改进寻路算法与标准A*算法的对比实验

本节内容将三种算法:标准A*算法、采用快速排序优化Open表后的A*算法、采用分层搜索A*算法以及综合了两次改进后的寻路算法,比较这几种算法的搜索时间.网格化以后的油库区地图为34*18的网格图形.实验中,我们选择10组不同的起始点与终点作为实验路径,路径长度逐渐增长,每组路径我们进行10次运算,记录搜索时间并取其平均值,通过比较搜索时间来证明改进后的寻路算法提高了搜索效率.其中一次搜索结果如图5,输出了本次搜索的最优路径所经过的节点坐标以及搜索时间.图5中:0为通路,1为由起始点搜索后得到的路径,2为终点,3为障碍物.

图4 设置障碍物后的新路径

图5 搜索的路径和时间数据

实验一:在系统中调用标准A*算法来进行实验,记录其搜索时间,并算出每组数据的平均值.

实验二:由于标准A*算法中,影响搜索速度比较大的因素就是对Open表中F值的查找,本文采用了快速排序对Open表进行优化,使Open表中的节点按照F值从一开始就由小到大的顺序进行排列.本部分我们用优化Open表的方法进行实验,与实验一采用相同10组路径进行实验,记录时间并算出每组数据平均值.实验三:针对油库区储油罐区道路笔直且无障碍的特点,提出分层搜索的改进方法,将道路分为无碍路段和有碍路段,当寻路体到达该路段,且需要通过该路段时,我们放弃调用A*算法,使其直接通过.如图6,绿色路段为无碍路段.本部分用分层搜索算法进行实验,与实验一采用相同10组路径,记录时间并算出每组数据平均值.

图6 分层设计后的地形图

实验四:本部分我们综合上述两种改进方法,即在对Open表进行快速排序的基础上进行分层路径搜索,对比标准A*算法的搜索时间,实验方法同上.

通过四组实验,得到的搜索时间表1,对比折线图7.

通过实验数据,我们得出以下结论:

① 实验过程中,通过分析实验数据,结果表明在起始点和终点相同的情况下,如图3、图4,在地形相对复杂的图4中,搜索得到的路径长度增加,搜索时间也随之增加,由此可以分析得出,随着地形越复杂程度的增加,寻路算法的搜索效率会降低.

② 对Open表进行排序后的A*算法搜索时间相对于标准A*算法有了提高.分析其原因,我们对标准A*算法中无序的Open进行排序,F值最小的节点即为Open表的第一个节点,从而减少了对Open表搜索的花费.

③ 采用分层搜索后,明显提高了路径搜索的速度.分析其原因,由于在无碍路段上,我们放弃使用A*算法进行搜索,故减少了搜索的节点数量,从而提高了搜索的效率,有效减少了路径搜索时间.

④ 我们从实验数据中可以看到综合了两次改进的寻路算法,路径搜索时间明显缩短,通过数据计算得出采用综合改进后的寻路算法进行寻路,最优路径搜索效率平均提高6.86%.

表1 各组实验平均搜索时间对比

图7 各组实验搜索时间对比折线图

4 总结

A*寻路算法是当下应用最广泛的智能寻路算法,但是当搜索地形复杂,随着搜索节点数量的增加,A*算法的搜索效率将受到影响,其中,搜索最缓慢的部分是对Open表中无序节点的搜索.本文结合大型油库区地形规整,结构简单的搜索节点相对少特点,对Open表进行了排序,优化了节点的存储方式,提高了Open表的查找效率;另外,本文针对油库的储油罐区道路笔直无障碍的特点提出了分层搜索的思想,进一步提高了整体的搜索效率.目前对A*算法的改进主要集中在对A*算法搜索节点的数据结构和估价函数上,本文结合了实际搜索地形特点,不同路段影响搜索效率因素不同,分别进行了改进,将改进办法相结合后应用到整体的路径搜索中,有效的提高了最短搜索效率.

笔者基于vs2010开发平台,用C++作为程序开发语言实现了油库火灾三维模拟演练系统,并在系统中的多人协同模拟演练模块中对本文所提出的改进算法进行了实现.结果表明,改进后的寻路算法效果明显,提高了救援队伍寻路运算的速度,且路径真实有效,搜索效率平均提高6.86%,为本系统提供了更加真实的训练效果,使油库消防救援寻路效率得到了有效的改善.

1张海涛,程荫杭.基于A*算法的全局路径搜索.微计算机信息,2007,204(17):238–239,308.

2 Cao W.Application of an improved A*algorithm in route planning.Proc.of WRI Global Congress on Intelligent Systems(GCIS’09).2009.253–257.

3 Qi MJ,Sun HN,Gao GF.Research on an improved algorithm for shortest path searching in urban traffic based on GIS. Proc.of Electrical and Control Engineering International Conference.2011.1184–1187.

4 Eriksson G,Kitok A.Automatic loading and dumping using vehicle guidance in a Swedish mine.Proc.of the First InternationalSymposium on MineMechanization and Automation.1991,6.15-33–15-44.

5贾庆轩,陈钢,孙汉旭,郑双奇.基于A～*算法的空间机械臂避障路径规划.机械工程学报,2010,46(13):109–115.

6刘浩,鲍远律.A*算法在矢量地图最优路径搜索中的应用.计算机仿真,2008,(4):253–257.

7李志建,郑新奇,王淑晴,杨鑫.改进A～*算法及其在GIS路径搜索中的应用.系统仿真学报,2009,21(10):3116–3119.

8熊壬浩,刘羽.A*算法的改进及并行化.计算机应用, 2015,35(7):1843–1848.

9顾青,豆风铅,马飞.基于改进A*算法的电动车能耗最优路径规划.农业机械学报,2015,46(12):316–322.

10张仁平,周庆忠,熊伟,王红旗.A～*算法改进算法及其应用.计算机系统应用,2009,18(9):98–100,107.

11陈刚,付少锋,周利华.A～*算法在游戏地图寻径中的几种改进策略研究.科学技术与工程,2007,7(15):3731–3736.

12张前哨.基于A*算法的地图寻径的研究[硕士学位论文].武汉:武汉科技大学,2005.

13马飞,杨皞屾,顾青,孟宇.基于改进A*算法的地下无人铲运机导航路径规划.农业机械学报,2015,46(7):303–309.

14王殿君.基于改进A～*算法的室内移动机器人路径规划.清华大学学报(自然科学版),2012,(8):1085–1089.

15张静,万书亭,陈海宏.基于改进路网分层和A～*算法的最优路径研究.华北电力大学学报(自然科学版),2012,39(5): 12–16.

16任波,周焘,于雷.基于改进A～*算法的飞行器三维航迹规划算法.系统工程与电子技术,2008,30(2):324–326.

17高庆吉,于咏生,胡丹丹.基于改进A*算法的可行性路径搜索及优化.中国民航学院学报,2005,23(4):42–45.

18单伟,孟正大.基于改进A～*算法的平滑路径设计.东南大学学报(自然科学版),2010,(S1):155–161.

19钱红昇,葛文锋,钟鸣,葛铭.基于分层的改进*算法在路径规划中的应用.计算机工程与应用,2014,50(7):225–229.

20周小镜.基于改进A*算法的游戏地图寻径的研究[硕士学位论文].重庆:西南大学,2011.

Improved Pathfinding Algorithm for the Rescue of Large Oil File

LI Ke-Wen,ZHU Hong-Ji

(College of Computer and Communication Engineering,China University of Petroleum,Qingdao 266580,China)

The large oil depot map is different from city and mountainous region whose maps are complex.The map of large oil depot is very regular,oil tanks and other buildings arranged neatly and the roads of the oil tank area are straight. On the basis,the classic A*algorithm is improved in this paper.On the one hand,according to the characteristics that the map of oil depot is simple and the number of search nodes is relatively small,the data structure of the Open table in the A*algorithm is improved,to accelerate the search speed and the ranking algorithm is used to improve the search efficiency.On the other hand,because roads in the oil depot are straight,so we divide roads into two parts:roads with obstacles and barrier free roads,to improve the search efficiency.Experimental results show that,with the combination of the two improved methods,the time of searching roads is declined definitely by 6.86%.

oil depot fire;artificial intelligence;A*algorithm;quicksort;hierarchical road search

2016-08-08;收到修改稿时间:2016-10-10

10.15888/j.cnki.csa.005759