基于方向啟發(fā)性的路徑查找模型研究

周 影0

淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，淮北，235000

?

基于方向啟發(fā)性的路徑查找模型研究

周 影0

淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，淮北，235000

提出了一種在起點(diǎn)和終點(diǎn)的方向關(guān)系已知的前提下的路徑查找模型。查找過(guò)程從起點(diǎn)開(kāi)始，計(jì)算其鄰接點(diǎn)與終點(diǎn)的方向關(guān)系，利用優(yōu)劣評(píng)價(jià)函數(shù)逐一計(jì)算出各經(jīng)歷頂點(diǎn)的最優(yōu)鄰接點(diǎn)，由若干最優(yōu)鄰接點(diǎn)組成的頂點(diǎn)序列就是所找路徑。結(jié)果表明：該模型依托的方向關(guān)系可以有效提高陌生環(huán)境的路徑查找效率，同時(shí)模型的穩(wěn)定性和準(zhǔn)確率也都較高。

路徑查找；優(yōu)劣評(píng)價(jià)函數(shù)；方向關(guān)系；模型；鄰接點(diǎn)

1 問(wèn)題的提出

路徑查找是確定出起點(diǎn)到終點(diǎn)之間的一條路徑，并沿路徑而行的心理過(guò)程，它的最終目標(biāo)是找到由起點(diǎn)到達(dá)終點(diǎn)的一條路徑[1]。對(duì)于路徑查找，很多國(guó)外的學(xué)者和專家提出了多種模型。Moise Busogi等提出一種人類理性行為基礎(chǔ)上的路徑查找建模方法，通過(guò)對(duì)人的行為評(píng)估，在執(zhí)行層面上感知物理環(huán)境[2]。Beatrix Emo提出并強(qiáng)調(diào)空間幾何角色對(duì)個(gè)人空間決策的重要性，并在城市環(huán)境中實(shí)現(xiàn)了路徑查找[3]。但國(guó)內(nèi)研究路徑查找模型的較少，齊平、李龍澍提出一種基于信任機(jī)制的動(dòng)態(tài)商拓?fù)淠Ｐ?，該模型拓?fù)浣Y(jié)構(gòu)在隨時(shí)間變化的情況下，使用貝葉斯方法評(píng)估節(jié)點(diǎn)可信度[4]。蘇加強(qiáng)、丁柳云基于遺傳算法，提出了查找最優(yōu)路徑的算法[5]。趙開(kāi)新、王東署等人提出基于蟻群遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃算法，旨在改進(jìn)初期搜索盲目性大等問(wèn)題[6]。

以上文獻(xiàn)都在實(shí)驗(yàn)中說(shuō)明方法的有效性，但均未針對(duì)方向啟發(fā)信息進(jìn)行路徑查找。為此，本文提出一種以方向啟發(fā)為前提的路徑查找模型，假設(shè)前提為已知起點(diǎn)和終點(diǎn)的方位，一步步找出起點(diǎn)到終點(diǎn)的最優(yōu)鄰接頂點(diǎn)，這些頂點(diǎn)組成了所找路徑。

2 方向關(guān)系和優(yōu)劣評(píng)價(jià)函數(shù)解析

此模型中,假設(shè)知道起點(diǎn)(SV)和終點(diǎn)(EV)的方向關(guān)系，從起點(diǎn)出發(fā)，找出起點(diǎn)的鄰接點(diǎn)(AV)，利用鄰接點(diǎn)和終點(diǎn)的方向關(guān)系是否接近于起點(diǎn)和終點(diǎn)的方向，進(jìn)而確定出最優(yōu)鄰接點(diǎn)。

2.1 方向關(guān)系

模型中的方向關(guān)系有8種，東、南、西、北為4個(gè)基本方位，東南、西南、西北、東北為4個(gè)輔助方位，其位置關(guān)系如圖1所示。

圖1 方向關(guān)系圖

2.2 優(yōu)劣評(píng)價(jià)函數(shù)

路徑查找的關(guān)鍵是通過(guò)計(jì)算找出最優(yōu)鄰接點(diǎn)，最優(yōu)鄰接點(diǎn)可使用優(yōu)劣評(píng)價(jià)函數(shù)計(jì)算得出。函數(shù)的定義：如果起點(diǎn)與當(dāng)前點(diǎn)(CV)的方向關(guān)系等于起點(diǎn)與終點(diǎn)的關(guān)系，那么該當(dāng)前點(diǎn)的評(píng)價(jià)函數(shù)值最大；如果起點(diǎn)與當(dāng)前點(diǎn)的方向關(guān)系和起點(diǎn)與終點(diǎn)的方向關(guān)系是相關(guān)的，它的評(píng)價(jià)函數(shù)值取中間值；如果起點(diǎn)與當(dāng)前點(diǎn)的方向關(guān)系和起點(diǎn)與終點(diǎn)的關(guān)系是無(wú)關(guān)的，那么它的評(píng)價(jià)函數(shù)值就是最小的。這里所說(shuō)的相關(guān)，應(yīng)理解為相近，比如起點(diǎn)與終點(diǎn)的方向關(guān)系是東南，起點(diǎn)與當(dāng)前點(diǎn)的方向關(guān)系是東或南，那么就認(rèn)為它們是相關(guān)的；相反，比如起點(diǎn)與終點(diǎn)的方向關(guān)系是正東，起點(diǎn)與當(dāng)前點(diǎn)的方向關(guān)系是東北或東南，此時(shí)也認(rèn)為它們是相關(guān)的。

Fun (SV,CV) {

If (Relation(SV,CV))∩(Relation(SV,EV))= Relation(SV,EV)) return max;

If (Relation(SV,CV))∩(Relation(SV,EV))∈Relation(SV,EV)) return middle;

If (Relation(SV,CV))∩(Relation(SV,EV))=?return min;

}；

如果起點(diǎn)與當(dāng)前點(diǎn)的方向關(guān)系和起點(diǎn)與終點(diǎn)的方向關(guān)系是一致的，且符合條件的當(dāng)前點(diǎn)不止一個(gè)頂點(diǎn)時(shí)，就按存儲(chǔ)時(shí)第一個(gè)存儲(chǔ)的當(dāng)前點(diǎn)作為最優(yōu)鄰接點(diǎn)。

2.3 假設(shè)場(chǎng)景解析

圖2為假設(shè)場(chǎng)景，場(chǎng)景中A是起點(diǎn)，B是終點(diǎn)，A1、A2、A3、A4是起點(diǎn)A的鄰接點(diǎn)，Relation(A,B)=WS。

圖2 假設(shè)場(chǎng)景

(1)分別計(jì)算三個(gè)鄰接點(diǎn)與A的方向關(guān)系：

Relation(A,A1)=WS, Relation(A,A2)=S, Relation(A,A3)=ES；

(2)計(jì)算三個(gè)鄰接點(diǎn)與起點(diǎn)的方向關(guān)系的評(píng)價(jià)函數(shù)：

Fun(A,A1)=max,Fun(A,A2)=middle,Fun(A,A3)=min;

(3)比較三個(gè)評(píng)價(jià)函數(shù)的大小，選取評(píng)價(jià)函數(shù)值大的點(diǎn)作為下一步需要訪問(wèn)的頂點(diǎn)，因?yàn)镕un(A,A1)>Fun(A,A2)>Fun(A,A3),所以A1的評(píng)價(jià)函數(shù)值最大，故A1是最優(yōu)鄰接點(diǎn)。

A1為起點(diǎn)之后的計(jì)算得到下一個(gè)的頂點(diǎn)，然后再以A1作為新的起點(diǎn)，計(jì)算A1的鄰接點(diǎn)中的最優(yōu)者，一步步執(zhí)行，直到頂點(diǎn)和終點(diǎn)相同結(jié)束。

3 基于方向啟發(fā)式的路徑查找模型

3.1 模型的實(shí)現(xiàn)步驟

模型的實(shí)現(xiàn)依托一個(gè)相對(duì)完整的環(huán)境，把環(huán)境轉(zhuǎn)換為道路圖，圖中有頂點(diǎn)集、邊集、圖層，算法步驟如下：

Step1 定義頂點(diǎn)Vertex的數(shù)據(jù)類型，定義與頂點(diǎn)類型相同的隊(duì)列，用于存儲(chǔ)路徑查找過(guò)程中的諸多最優(yōu)鄰接頂點(diǎn)；

Step2 初始化道路圖中所有頂點(diǎn)個(gè)數(shù)N(int N≥2)；

Step3 輸入起點(diǎn)SV和終點(diǎn)EV，和兩者的位置關(guān)系Relation (SV,EV)；

Step4 如果N=2,輸出SV→EV那條路徑；如果N>2，轉(zhuǎn)向Step5；

Step5 利用優(yōu)劣評(píng)價(jià)函數(shù)計(jì)算起點(diǎn)的每個(gè)鄰接點(diǎn)的函數(shù)值，從中選出最優(yōu)鄰接點(diǎn)作為下一個(gè)訪問(wèn)對(duì)象AV′，同時(shí)將此鄰接點(diǎn)存入隊(duì)列中；

Step6 如果AV′=EV,輸出隊(duì)列里的所有頂點(diǎn)，頂點(diǎn)序列就是所求的路徑；如果AV′!=EV,把AV′作為新的頂點(diǎn)，轉(zhuǎn)向Step5。

3.2 實(shí)驗(yàn)結(jié)果與分析

MapXtreme是MapInfo公司開(kāi)發(fā)的基于網(wǎng)絡(luò)的應(yīng)用服務(wù)器，它具有強(qiáng)大的地圖化功能，包括地圖編輯、地圖顯示、圖層控制等[7-8]。以下使用MapXtreme作為界面工具，以淮北師范大學(xué)校園為模擬環(huán)境。將校園平面圖構(gòu)造成由頂點(diǎn)和直線路徑組成的實(shí)驗(yàn)用圖，為了直觀，把各建筑物用類實(shí)物圖顯示。實(shí)驗(yàn)中，以學(xué)校大門(存儲(chǔ)名為node1)為起點(diǎn)，學(xué)生第二食堂(存儲(chǔ)名為node62)為終點(diǎn)，輸入兩者的方位關(guān)系為西南方向(WS),執(zhí)行界面如圖3所示，粗虛線即為所求路徑。

圖3 基于方向啟發(fā)的路徑查找模型實(shí)驗(yàn)圖

4 結(jié) 論

在起點(diǎn)和終點(diǎn)的方向關(guān)系已知的基礎(chǔ)上，從起點(diǎn)開(kāi)始，利用最優(yōu)評(píng)價(jià)函數(shù)計(jì)算出最優(yōu)鄰接點(diǎn)，直到找出到終點(diǎn)的路徑位置。該模型的實(shí)現(xiàn)是在學(xué)校環(huán)境里，經(jīng)過(guò)多次比較和測(cè)試，該模型在時(shí)間上是高效的，同時(shí)穩(wěn)定性和準(zhǔn)確率也都較高。從問(wèn)題的系統(tǒng)性上考慮，在今后的研究工作中可考慮增加頂點(diǎn)的信息存儲(chǔ)量、道路權(quán)值等信息，可提高問(wèn)題的精準(zhǔn)度。

[1]David M Mark,Christian Freksa,Stephen C.Hirtle,et al.Cognitive models of geographical space[J].International Journal of Geographical Information Science,1999,13(8):747-774

[2]Moise Busog,Namhun Kim,Dongmin Shin,et al.Bayesian Affordance-Based Agent Model for Wayfinding Behaviors in Evacuation Problems[C].Berlin：4th International Conference of HCI International,2013:297-306

[3]Beatrix Emo.Wayfinding in Real Cities:Experiments at Street Corners[C].Berlin：International Conference of Spatial Cognition,2012:461-477

[4]齊平,李龍澍.動(dòng)態(tài)商拓?fù)淠Ｐ图捌湓诼窂讲檎抑械膽?yīng)用[J].模式識(shí)別與人工智能,2014,24(7):337-344

[5]蘇加強(qiáng),丁柳云.基于遺傳算法的GIS輔助最優(yōu)路徑查找算法[J].遼寧科技學(xué)院學(xué)報(bào),2012,14(4):23-25

[6]趙開(kāi)新,王東署,徐立新.蟻群遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的綜合應(yīng)用研究，制造業(yè)自動(dòng)化，2014,36(9):70-72,84

[7]孫龍,曹菡.基于MapXtreme的候機(jī)樓導(dǎo)航和監(jiān)控系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)與發(fā)展,2011,21(5):183-186

[8]吳開(kāi)興,范周艷.MapXtreme下WebGIS的優(yōu)化研究[J].測(cè)繪通報(bào),2015,(7):109-112

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2017.04.032

2017-02-01

安徽省教育廳高校自然科學(xué)研究重點(diǎn)項(xiàng)目“安全協(xié)議的形式化分析方法研究”( KJ2017A848)。

周影(1981-)，女，安徽淮北人，碩士，講師，研究方向：GIS，信息安全。

TP301.6

A

1673-2006(2017)04-0115-03