大型油庫消防救援尋路算法改進①

李克文,朱虹吉

(中國石油大學 計算機與通信工程學院,青島 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