動態(tài)環(huán)境感知的多目標(biāo)室內(nèi)路徑規(guī)劃方法

周 艷 ，陳 紅 ，張葉廷 ，黃悅瑩 ，張鵬程 ，楊衛(wèi)軍

（1.電子科技大學(xué)資源與環(huán)境學(xué)院，四川 成都 611731；2.電子科技大學(xué)大數(shù)據(jù)研究中心，四川 成都 611731；3.武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北 武漢 430072；4.廣州市城市規(guī)劃勘測設(shè)計研究院，廣東 廣州510060）

室內(nèi)路徑規(guī)劃主要應(yīng)用于室內(nèi)導(dǎo)航[1-3]和應(yīng)急疏散[4-5]等領(lǐng)域.近年來，隨著人們對復(fù)雜室內(nèi)環(huán)境導(dǎo)航需求的日益增長，Google 地圖、必應(yīng)地圖、百度地圖等眾多知名地圖服務(wù)供應(yīng)商都已將室內(nèi)導(dǎo)航作為地圖服務(wù)的必備功能之一.

相關(guān)研究為室內(nèi)導(dǎo)航提供了不同的路徑規(guī)劃思路，主要可分為：基于三維模型語義信息[6-7]、增強用戶語義信息[8-9]和顧及上下文信息的3 類室內(nèi)路徑規(guī)劃方法[10-11].這些方法的優(yōu)點是在規(guī)劃室內(nèi)路徑時，不同程度上考慮了影響導(dǎo)航的語義信息，提高了路徑規(guī)劃的實用性.第1 類方法重點考慮了室內(nèi)三維模型的幾何語義信息；第2 類方法將用戶信息及其行為語義納入導(dǎo)航路徑規(guī)劃中；第3 類方法考慮了環(huán)境上下文和用戶偏好語義，提供了以用戶為中心的個性化路徑規(guī)劃服務(wù).上述方法的不足之處在于：現(xiàn)有的室內(nèi)路徑規(guī)劃方法主要是針對單一目標(biāo)的路徑規(guī)劃問題設(shè)計的（解決兩點之間的室內(nèi)路徑規(guī)劃），而在現(xiàn)實生活中，用戶往往具有面向多目標(biāo)的室內(nèi)路徑規(guī)劃需求；此外，實際尋徑過程中的環(huán)境語義是動態(tài)變化的，現(xiàn)有方法在路徑規(guī)劃時往往將語義信息作為靜態(tài)約束條件，難以適應(yīng)導(dǎo)航環(huán)境的動態(tài)變化.

為此，本文提出動態(tài)環(huán)境感知的多目標(biāo)室內(nèi)路徑規(guī)劃方法，考慮到室內(nèi)動態(tài)環(huán)境信息是影響室內(nèi)路徑規(guī)劃合理性與有效性的重要決定因素，將室內(nèi)路徑復(fù)雜度、擁擠程度與阻斷事件等室內(nèi)多維動態(tài)環(huán)境語義建模并量化，統(tǒng)一整合到室內(nèi)導(dǎo)航路網(wǎng)模型中，基于Dijkstra 算法設(shè)計了顧及室內(nèi)動態(tài)環(huán)境變化的室內(nèi)路徑規(guī)劃方法，以滿足用戶個性化的多目標(biāo)室內(nèi)導(dǎo)航需求.

1 顧及環(huán)境語義的室內(nèi)導(dǎo)航路網(wǎng)模型

室內(nèi)導(dǎo)航路網(wǎng)模型是實現(xiàn)室內(nèi)路徑規(guī)劃和導(dǎo)航服務(wù)的基礎(chǔ)[12].目前的室內(nèi)導(dǎo)航路網(wǎng)模型以幾何圖模型應(yīng)用最為廣泛，這類模型可同時描述室內(nèi)空間的幾何特征和拓?fù)涮卣?，建模的方式主要有對偶圖模型[13]和門-門模型[14]兩種.本文提出顧及環(huán)境語義的室內(nèi)導(dǎo)航路網(wǎng)模型，擴展節(jié)點-邊表示的室內(nèi)導(dǎo)航圖模型，將室內(nèi)路徑復(fù)雜度、擁擠程度與阻斷事件等動態(tài)環(huán)境語義建模并量化，統(tǒng)一整合到室內(nèi)導(dǎo)航路網(wǎng)模型中，為實現(xiàn)動態(tài)環(huán)境感知的多目標(biāo)室內(nèi)路徑規(guī)劃提供導(dǎo)航路網(wǎng)模型支持.

1.1 室內(nèi)導(dǎo)航路網(wǎng)模型擴展

基于圖模型的基本思想，室內(nèi)導(dǎo)航空間可以抽象為節(jié)點-邊表達(dá)的幾何模型.其中，房間和門抽象為幾何中心，表示為節(jié)點，走廊以中心線的形式抽象表達(dá)為邊；節(jié)點與節(jié)點、節(jié)點與邊（即房間-門、門-走廊）之間根據(jù)實際路徑的連通性，建立節(jié)點-邊之間的連接，實現(xiàn)室內(nèi)導(dǎo)航路徑連通，依此形成節(jié)點-邊表示的室內(nèi)導(dǎo)航路網(wǎng)模型.為了滿足用戶個性化導(dǎo)航需求，本文對節(jié)點-邊表示的室內(nèi)導(dǎo)航路網(wǎng)模型進(jìn)行了擴展，如圖1所示.

圖1 擴展的室內(nèi)導(dǎo)航路網(wǎng)模型Fig.1 Enhanced indoor navigation road network model

（1）增加了影響用戶室內(nèi)路徑選擇的垂直組件，用于表達(dá)三維空間垂直方向上的可達(dá)路徑.垂直組件劃分為電梯、扶梯、樓梯3 類，以便于結(jié)合用戶偏好（如殘疾人輪椅更適宜選擇電梯等）合理規(guī)劃室內(nèi)導(dǎo)航路徑，滿足用戶個性化室內(nèi)導(dǎo)航需求.垂直組件在各樓層的出口表示為節(jié)點，垂直方向的連通性由垂直節(jié)點之間的連接邊表示；

（2）增加了影響用戶選擇路徑復(fù)雜程度的其它節(jié)點，如附加節(jié)點和拐彎節(jié)點.附加節(jié)點用于表示門與走廊之間、垂直組件與走廊之間的連接點，其數(shù)目一定程度上影響室內(nèi)導(dǎo)航路網(wǎng)的復(fù)雜程度；拐彎節(jié)點表示導(dǎo)航過程中路徑方向發(fā)生變化的轉(zhuǎn)折點，導(dǎo)航路徑中過多的拐彎可能會增加用戶路徑認(rèn)知障礙，降低導(dǎo)航路徑清晰性；

（3）房間細(xì)分為單門房間和多門房間.單門房間只有一個門節(jié)點連接走廊與房間，而多門房間有多個門節(jié)點與走廊連接，從而可以在路徑規(guī)劃時提供更多的室內(nèi)導(dǎo)航路徑選擇；

（4）邊擴展為走廊、垂直邊和房間內(nèi)連接邊.走廊以中心線的形式抽象表達(dá)為邊；垂直邊表示垂直方向上的連接邊，垂直邊與垂直組件的節(jié)點產(chǎn)生節(jié)點-邊關(guān)聯(lián)，用于表達(dá)樓層之間的垂直方向?qū)Ш铰窂?；房間內(nèi)連接邊表示房間節(jié)點與門節(jié)點之間的連接路徑，可用于多門房間內(nèi)部的導(dǎo)航路徑規(guī)劃.

為直觀起見，本文以圖2所示的室內(nèi)三維幾何模型為例，基于擴展的室內(nèi)導(dǎo)航路網(wǎng)模型，構(gòu)建由節(jié)點-邊表示的室內(nèi)導(dǎo)航路網(wǎng).圖2（a）表示的室內(nèi)三維幾何模型共包含四層，鑒于各樓層導(dǎo)航路網(wǎng)建模過程大同小異，因而此處主要以第二層為例詳細(xì)說明.首先將圖2（a）中的房間和門分別按其二維投影的幾何中心抽象表達(dá)為節(jié)點，如R1、R2、R3、R4 等表示房間節(jié)點；D1、D2、D3、D4 表示相應(yīng)房間的門節(jié)點.房間細(xì)分為單門房間（R1、R2、R3、R4 等）和多門房間（R12）.對于單門房間，建立房間節(jié)點與門節(jié)點之間的連接邊（L1、L2、L3、L4 等）；對于多門房間，建立房間節(jié)點與多個門節(jié)點（D11、D12、D13）之間的房間內(nèi)連接邊（L12、L13、L14）；同時在多門房間中建立門-門節(jié)點的房間內(nèi)連接邊（L11、L15、L16）.

圖2 室內(nèi)導(dǎo)航路網(wǎng)建模實例Fig.2 An example for indoor navigation road network modelling

本文模型增加了垂直組件，垂直組件在各樓層的出口表示為節(jié)點，垂直方向的連通性用垂直節(jié)點之間的連接邊表示.本文將垂直組件劃分為電梯、扶梯和樓梯3 類，如圖3所示.垂直組件的出口與門類似，可以抽象表示為節(jié)點，相鄰樓層的垂直組件出口節(jié)點通過垂直邊（電梯）或斜邊（扶梯與樓梯）連接；樓梯的形態(tài)通常有兩種：樓梯直接連通樓層走廊和樓梯經(jīng)層間轉(zhuǎn)折后連通樓層走廊，如圖3（c）所示.對于后一種樓梯，除了將樓梯連接走廊的出口視為節(jié)點以外，還需要將樓梯的層間轉(zhuǎn)折抽象為節(jié)點，建立節(jié)點-節(jié)點的斜邊連接.電梯和樓梯一般同時具有上行和下行方向語義，而扶梯通常具有單向上行或單向下行語義，圖3（b）表示了具有上行方向語義的扶梯路徑.通過增加垂直組件（電梯、扶梯、樓梯），可以在節(jié)點-邊表達(dá)的室內(nèi)導(dǎo)航路網(wǎng)模型中引入方向語義約束，同時也為滿足特殊用戶（如乘坐輪椅用戶）的個性化路徑服務(wù)需求提供了可能性.

圖3 室內(nèi)垂直組件導(dǎo)航路徑建模Fig.3 Navigation route modelling of indoor vertical components

室內(nèi)導(dǎo)航路網(wǎng)模型中，在邊上添加附加節(jié)點，用于表示門與走廊的連接點，以及垂直組件與走廊的連接點.附加節(jié)點的位置均選擇走廊中心線上與連接節(jié)點距離最近的點，如圖2（b）中的A1、A2、A3、A4 表示門與走廊相連接的附加節(jié)點，A8、A9 表示垂直組件（分別對應(yīng)樓梯V1、V2）連接走廊的附加節(jié)點.考慮到導(dǎo)航路徑中過多的拐彎會增加用戶路徑認(rèn)知障礙，降低路徑清晰性，本文在模型中區(qū)分了拐彎節(jié)點.值得說明的是，拐彎節(jié)點并不是建模過程中物理生成的一類節(jié)點，而是在導(dǎo)航路徑規(guī)劃時產(chǎn)生的一類用于標(biāo)識導(dǎo)航路徑方向發(fā)生變化的轉(zhuǎn)折點.當(dāng)路徑中兩條連接邊斜率不同時，同時關(guān)聯(lián)兩條連接邊的節(jié)點被判定為拐彎節(jié)點.理論上而言，任何節(jié)點（包括門節(jié)點、房間節(jié)點和附加節(jié)點）都有可能成為拐彎節(jié)點，路網(wǎng)中的拐彎節(jié)點是動態(tài)變化的.比如，圖2（b）中，當(dāng)從房間R1 到房間R4 規(guī)劃一條導(dǎo)航路徑時，門節(jié)點D1 與附加節(jié)點A1、附加節(jié)點A4 與門節(jié)點D4 依次被判定為拐彎點；但如果規(guī)劃一條從房間R1 到電梯V1 的路徑，此時A4 與D4 就不再是拐彎節(jié)點.因此，拐彎節(jié)點的作用主要是服務(wù)于導(dǎo)航路徑規(guī)劃，旨在判定拐彎數(shù)量從而輔助導(dǎo)航路徑?jīng)Q策，而不是直接用于構(gòu)建室內(nèi)導(dǎo)航路網(wǎng)模型.

綜上所述，圖2以一個樓層為例說明了室內(nèi)導(dǎo)航路網(wǎng)的建模過程，其它樓層同理可得，不再贅述.

1.2 顧及環(huán)境信息的導(dǎo)航語義表達(dá)

本文從以下三方面表達(dá)顧及環(huán)境信息的室內(nèi)導(dǎo)航語義.

（1）路徑復(fù)雜度

室內(nèi)導(dǎo)航路徑的復(fù)雜程度直接影響到解釋、說明和可視化表達(dá)導(dǎo)航路徑的難易程度，同時也影響到用戶理解、記憶以及執(zhí)行路徑導(dǎo)航指示的難易程度.相關(guān)認(rèn)知研究表明，導(dǎo)航路徑復(fù)雜程度的重要性不亞于路徑長度，用戶在選擇路徑時，往往更愿意選擇較為簡單的導(dǎo)航路徑（即使其長度與最短路徑相比略有增加），因為它存在更少的認(rèn)知障礙、更便于理解和導(dǎo)航[15-16].路徑復(fù)雜度表明了用戶理解、說明、記憶以及執(zhí)行路線導(dǎo)航指示的難易程度[17-18]，尤其當(dāng)用戶面對復(fù)雜建筑的陌生室內(nèi)環(huán)境時，考慮導(dǎo)航路徑的復(fù)雜性顯得尤為必要.研究表明，拐彎數(shù)直接反映了路徑的復(fù)雜程度，在人類常用的數(shù)十種路徑選擇標(biāo)準(zhǔn)中，拐彎數(shù)是人們最常用的標(biāo)準(zhǔn)之一[19]，導(dǎo)航路徑中的拐彎數(shù)越多，給用戶造成的導(dǎo)航體驗越復(fù)雜，即使是在用戶對路網(wǎng)十分熟悉的情況下仍然如此[20].鑒于拐彎數(shù)在路徑?jīng)Q策中的重要性，本文采用路徑拐彎數(shù)表達(dá)導(dǎo)航路徑的復(fù)雜程度，據(jù)此，路徑復(fù)雜度語義可以描述為

其中，number_turns為導(dǎo)航路徑中的拐彎數(shù).

（2）擁擠程度

導(dǎo)航環(huán)境的擁擠程度是影響用戶導(dǎo)航體驗舒適性的重要因素.特別是在大型商場、火車站等人員密集的復(fù)雜室內(nèi)導(dǎo)航環(huán)境中，路徑的擁擠程度成為影響用戶路徑選擇的重要決策因素之一.鑒于室內(nèi)導(dǎo)航環(huán)境的擁擠程度直接影響到用戶室內(nèi)導(dǎo)航體驗的舒適性，本文將室內(nèi)導(dǎo)航環(huán)境擁擠程度的語義描述為

其中，crowd_type表示室內(nèi)導(dǎo)航環(huán)境的擁擠程度.擁擠程度可以通過人群的通行速度來描述，擁擠程度不同對行人通行速度的影響也不同，通行速度可以通過人流密度反映，人流密度表明了單位面積上行人的數(shù)目.本文借鑒文獻(xiàn)[21]提出的通行速度（V，m/s）和人流密度（ρ，人/m2）的關(guān)系模式，使用表1定義的取值范圍對室內(nèi)導(dǎo)航環(huán)境的擁擠程度劃分等級.據(jù)此，crowd_type可分為暢通、輕度、緩慢和堵塞4 種.crowd_range表示擁擠程度對應(yīng)的區(qū)域長度；Tc表示擁擠程度對應(yīng)的時間區(qū)間，由crowd_range與V之比得到.

表1 擁擠程度與人流量對應(yīng)情況Tab.1 Degree of crowdedness and corresponding flow density

（3）阻斷事件

導(dǎo)航環(huán)境中的阻斷事件是導(dǎo)致路徑中斷、影響路徑可達(dá)性的主要因素.室內(nèi)導(dǎo)航中常見的阻斷情況有設(shè)施故障、突發(fā)事故、人為阻斷等.為了描述阻斷事件對室內(nèi)導(dǎo)航的影響，本文將導(dǎo)航環(huán)境中的阻斷事件語義表達(dá)為

其中，Tes為受阻斷事件影響的時間區(qū)間，event_range為阻斷事件的影響區(qū)域，描述室內(nèi)導(dǎo)航路網(wǎng)中受阻斷事件影響的節(jié)點集合，event_range={v1,v2,···,vn}，其中n為室內(nèi)路網(wǎng)模型中受阻斷事件影響節(jié)點個數(shù)，v1、v2、 …、vn為室內(nèi)路網(wǎng)模型中受阻斷事件影響的各節(jié)點，若該節(jié)點可達(dá)，取值為1，若該節(jié)點不可達(dá)，取值為0，此時，則可能導(dǎo)致相關(guān)節(jié)點也不可達(dá).

1.3 室內(nèi)環(huán)境語義感知的導(dǎo)航通行成本

將多維環(huán)境信息的導(dǎo)航語義引入室內(nèi)導(dǎo)航路網(wǎng)模型中，可以使基于節(jié)點-邊表達(dá)的室內(nèi)導(dǎo)航路網(wǎng)模型不僅具有路徑規(guī)劃需要的幾何信息，同時包含路徑復(fù)雜度、擁擠程度和阻斷事件等多維環(huán)境感知的室內(nèi)導(dǎo)航語義信息，從而有效增強用戶室內(nèi)導(dǎo)航的舒適性體驗.為此本文顧及室內(nèi)環(huán)境語義信息，提出可量化的導(dǎo)航通行成本函數(shù)G為

式中：ωc為 擁擠程度 (C)的 權(quán)重系數(shù)；ωt為路徑復(fù)雜度 (T)的 權(quán)重系數(shù)；ωe為阻斷事件 (E)的權(quán)重系數(shù)；為節(jié)點vi、vj間路徑擁擠程度的成本函數(shù)；α為系數(shù)，可以根據(jù)表1的擁擠程度指定（暢通、輕度、緩慢和堵塞對應(yīng)的 α分別取1.0、2.0、4.0和8.0）；為vi和vj之 間的歐氏距離.fturn(Vm)為路徑復(fù)雜度的成本函數(shù)，可由導(dǎo)航路徑中的拐彎數(shù)計算決定，Vm為 導(dǎo)航路徑中的拐彎節(jié)點的集合；fevent(Vn)為阻斷事件的成本函數(shù)，Vn為受阻斷事件影響的節(jié)點集合，集合中節(jié)點可達(dá)，fevent(Vn)=1，節(jié)點不可達(dá)，fevent(Vn)→0.

ωc、 ωt和 ωe可以根據(jù)室內(nèi)環(huán)境語義的重要程度進(jìn)行權(quán)值分配，權(quán)值滿足式（3）.

根據(jù)室內(nèi)導(dǎo)航環(huán)境的動態(tài)變化可以不斷更新通行成本函數(shù)值，以節(jié)點間的導(dǎo)航通行成本作為室內(nèi)導(dǎo)航路網(wǎng)的邊長，即可得到融合了動態(tài)環(huán)境語義的室內(nèi)導(dǎo)航路網(wǎng)，此時，顧及室內(nèi)環(huán)境語義的導(dǎo)航路徑規(guī)劃就轉(zhuǎn)化為基于室內(nèi)導(dǎo)航路網(wǎng)求解室內(nèi)導(dǎo)航路徑的最優(yōu)通行成本問題.

2 室內(nèi)多目標(biāo)路徑規(guī)劃方法

經(jīng)典最優(yōu)路徑規(guī)劃算法主要有Dijkstra、A*、Floyd 和Bellman-Ford（BF）算法等，其特點如表2所示.與Floyd、BF 算法相比，Dijkstra 算法具有簡單易行的優(yōu)點，能夠獲得全局最優(yōu)解，雖然對于很長距離的路徑規(guī)劃效率不如A*，但就室內(nèi)路徑規(guī)劃而言，Dijkstra 算法效率并無明顯差別，為此，本文基于擴展的節(jié)點-邊室內(nèi)導(dǎo)航路網(wǎng)模型，將顧及室內(nèi)動態(tài)環(huán)境語義的通行成本函數(shù)值作為室內(nèi)導(dǎo)航路網(wǎng)的邊長，基于Dijkstra 經(jīng)典尋徑算法實現(xiàn)室內(nèi)多目標(biāo)路徑規(guī)劃.

表2 經(jīng)典最優(yōu)路徑規(guī)劃算法Tab.2 Classic optimal path planning algorithms

顧及室內(nèi)動態(tài)環(huán)境語義的多目標(biāo)尋徑方法如圖4所示.

圖4 室內(nèi)多目標(biāo)路徑規(guī)劃流程Fig.4 Flow chart of indoor multi-objective routing

（1）構(gòu)建室內(nèi)導(dǎo)航路網(wǎng)

基于本文擴展的節(jié)點-邊室內(nèi)導(dǎo)航路網(wǎng)模型，構(gòu)建用于尋徑的室內(nèi)導(dǎo)航路網(wǎng)；設(shè)置室內(nèi)導(dǎo)航路網(wǎng)中各邊長的初始值為 ∞；

（2）確定導(dǎo)航起始點和多目標(biāo)點

設(shè)置用戶導(dǎo)航的起始點S和需要訪問的k個目標(biāo)點的集合TargetList 為{T1,T2,···,Tk}，Tk為多目標(biāo)尋徑中的第k個目標(biāo)點；設(shè)置CloseList 集合存放已遍歷的目標(biāo)點，初始化為空；設(shè)置PathList 集合存放起始點到目標(biāo)點的導(dǎo)航路徑，初始化為空；

（3）計算導(dǎo)航通行成本G*，更新室內(nèi)導(dǎo)航路網(wǎng)

本文算法融合了室內(nèi)導(dǎo)航環(huán)境語義信息，將節(jié)點間的G*作為室內(nèi)導(dǎo)航路網(wǎng)的邊長.因此，基于當(dāng)前的室內(nèi)導(dǎo)航環(huán)境語義信息，通過計算節(jié)點間G*值，可以有效融合環(huán)境動態(tài)變化，實現(xiàn)室內(nèi)導(dǎo)航路網(wǎng)更新；

（4）顧及環(huán)境語義信息的多目標(biāo)尋徑方法

①利用Dijkstra 算法，尋找起始節(jié)點S到Target-List 中每個目標(biāo)點的最短路徑（即最低通行成本路徑）D(T1)D(T2)···D(Tk)，從中選取具有最短路徑的目標(biāo)點TL滿 足：D(TL)=min{D(T1),D(T2),···,D(Tk)}.

②若D(TL)=∞，說明TargetList 當(dāng)中所有目標(biāo)點均不可達(dá)，跳轉(zhuǎn)至（6），算法結(jié)束；否則，將起始點S到目標(biāo)點TL的導(dǎo)航路徑添加到PathList 集合，并將TL從TargetList 集合移動至已遍歷目標(biāo)點集合CloseList；

③判斷TargetList 集合是否為空.如果TargetList非空，設(shè)置TL為 新的起始點，即S=TL，跳轉(zhuǎn)至（3）；若TargetList 為空，說明目標(biāo)點均已遍歷；

（5）輸出

多目標(biāo)路徑集合PathList，算法結(jié)束.

3 實驗與結(jié)果討論

本文實驗選用如圖5（a）所示建筑物三維幾何模型，以通行成本代價為邊長權(quán)值，構(gòu)建顧及環(huán)境語義的室內(nèi)導(dǎo)航路網(wǎng)，其對應(yīng)四層樓的室內(nèi)導(dǎo)航路網(wǎng)節(jié)點-邊拓?fù)浣Y(jié)構(gòu)如圖5（b）所示.通過設(shè)置擁擠情況和阻斷事件等不同的環(huán)境語義信息，分析比較環(huán)境語義對室內(nèi)導(dǎo)航路徑規(guī)劃的影響，驗證說明顧及動態(tài)環(huán)境語義的多目標(biāo)路徑規(guī)劃方法的可行性.

圖5 三維室內(nèi)導(dǎo)航路網(wǎng)模型Fig.5 3D indoor navigation road network model

（1）導(dǎo)航環(huán)境擁擠情況對室內(nèi)路徑規(guī)劃的影響

導(dǎo)航環(huán)境的擁擠程度是影響用戶路徑選擇的重要因素，為了說明導(dǎo)航擁擠情況對室內(nèi)路徑規(guī)劃的影響，暫不考慮其它環(huán)境語義的影響，分別針對兩種典型的擁擠情況，模擬用戶請求規(guī)劃一條從起始節(jié)點S（節(jié)點編號為0）到多目標(biāo)節(jié)點T1、T2、T3 和T4（節(jié)點編號分別為26、105、163 和234）的室內(nèi)導(dǎo)航路徑，擁擠情況環(huán)境語義設(shè)置如表3所示.情景1規(guī)劃路徑如圖6（a）黑色路線所示；情景2 中，分別設(shè)定了輕度、緩慢和堵塞3 種擁擠程度的路段，室內(nèi)多目標(biāo)導(dǎo)航路徑的規(guī)劃結(jié)果如圖6（b）所示.

表3 實驗1 環(huán)境語義Tab.3 Environment semantics of experiment 1

圖6 擁擠情況對多目標(biāo)室內(nèi)路徑規(guī)劃的影響Fig.6 Impact of indoor multi-objective planning route with degree of crowdedness

為了說明導(dǎo)航環(huán)境擁擠情況對通行效率的影響，根據(jù)表1，取不同擁擠情況的通行速度中值（輕度、緩慢和堵塞的取值分別為1.24、0.69、0.30）測算不考慮避讓擁堵路段的Dijkstra 算法通行時間，并與本文避開擁堵路段的規(guī)劃路徑通行時間進(jìn)行時間比較（暢通的通行速度取值1.40），其結(jié)果如圖7所示，3 種情況下本文方法的通行時間分別節(jié)約了19.7、124.3、23.7 s，節(jié)約的通行時間的百分比平均提升了17%，表明本文算法避開擁堵路段的導(dǎo)航時間通行成本更優(yōu).

圖7 路徑規(guī)劃的通行時間比較Fig.7 Comparison of travel time in path planning

對比情景1 和情景2 的路徑規(guī)劃結(jié)果可以看出，路徑規(guī)劃過程中針對導(dǎo)航環(huán)境擁擠程度的不同，本文算法通過感知環(huán)境信息避開了擁堵路段，因而用時更少，且改變了路徑規(guī)劃的節(jié)點訪問順序，得到了與無擁堵情況下不同的室內(nèi)規(guī)劃路徑.根據(jù)本文多目標(biāo)路徑導(dǎo)航算法原理分析可知，這是由于本文算法根據(jù)不同擁擠情況，對擁堵區(qū)域內(nèi)受影響的導(dǎo)航路網(wǎng)邊權(quán)進(jìn)行了G*的權(quán)值更新，使得擁堵路段的導(dǎo)航成本增高，因而有可能改變多目標(biāo)節(jié)點之間的室內(nèi)路徑規(guī)劃路線，實現(xiàn)顧及環(huán)境擁擠情況的合理室內(nèi)路徑規(guī)劃.

（2）動態(tài)環(huán)境感知的多目標(biāo)室內(nèi)路徑規(guī)劃

為了驗證本文方法的有效性，綜合考慮環(huán)境擁擠程度、阻斷事件和路徑復(fù)雜性等多維環(huán)境因素影響，模擬用戶請求規(guī)劃一條從起始節(jié)點S（節(jié)點編號24）到多目標(biāo)節(jié)點T1、T2、T3 和T4（節(jié)點編號依次為28、102、159 和234）的室內(nèi)導(dǎo)航路徑.根據(jù)本文定義，多維環(huán)境語義中的路徑復(fù)雜度主要取決于路徑拐彎數(shù)，可由路網(wǎng)拓?fù)浣Y(jié)構(gòu)計算得到，因此表4主要針對環(huán)境擁擠程度和阻斷事件進(jìn)行環(huán)境語義設(shè)置.假設(shè)情景1 中模擬所有區(qū)域均不存在擁擠情況和阻斷事件的理想路徑規(guī)劃情況；情景2 模擬方向語義約束的路徑規(guī)劃情況；情景3 中模擬多維導(dǎo)航環(huán)境中不同時刻、不同位置、不同擁擠程度和阻斷事件情況下的路徑規(guī)劃情況.實驗結(jié)果如圖8所示，情景1 中，多目標(biāo)節(jié)點的室內(nèi)規(guī)劃路徑如圖8（a）中黑色路線所示；為說明扶梯方向性語義的影響，情景2中，將3 樓到4 樓紅色虛線箭頭處的樓梯模擬為具有單向下行語義的扶梯，此時室內(nèi)導(dǎo)航路徑規(guī)劃結(jié)果如圖8（b）所示.由圖8（a）和（b）可以看出，當(dāng)垂直組件具有單向（上行或下行）方向語義約束時，規(guī)劃路徑發(fā)生了變化，這是由于在方向語義約束下，本文方法會將相關(guān)垂直組件設(shè)為不可用邊，從而避開不可用邊；情景3 中，假設(shè)t1時刻在圖8（c）1 樓黃色區(qū)域出現(xiàn)輕度擁擠，t2時刻在圖8（c）2 樓橘色區(qū)域出現(xiàn)緩慢程度的擁擠情況以及1 樓到2 樓的紫色節(jié)點處發(fā)生阻斷事件，t3時刻在圖8（c）4 樓紅色區(qū)域出現(xiàn)堵塞情況，t4時刻不存在任何的擁擠和阻斷情況，此時規(guī)劃的路徑如圖8（c）所示.由圖8（a）和（c）可以看出，兩者規(guī)劃的路徑存在較大差異.在t1時刻的輕度擁擠情況沒有影響路徑的規(guī)劃結(jié)果，但t2時刻擁擠程度變?yōu)榫徛约白钄嗍录陌l(fā)生直接導(dǎo)致訪問節(jié)點由102 變?yōu)?59，t3時刻的堵塞情況造成路徑規(guī)劃中以普通樓梯取代了電梯，使節(jié)點159 到節(jié)點234 的規(guī)劃路線發(fā)生了變化.可以看出，環(huán)境擁擠程度較輕時，由于對導(dǎo)航通行成本影響較小，因而沒有影響路徑規(guī)劃結(jié)果；環(huán)境擁擠程度加劇或出現(xiàn)阻斷事件時，環(huán)境語義的動態(tài)變化引起路網(wǎng)相關(guān)邊的導(dǎo)航通行成本函數(shù)動態(tài)更新，實驗結(jié)果說明本文方法能夠有效感知動態(tài)環(huán)境變化，規(guī)避環(huán)境擁堵和阻斷事件發(fā)生路段，能合理規(guī)劃室內(nèi)導(dǎo)航路徑.

表4 實驗2 環(huán)境語義Tab.4 Environment semantics of experiment 2

圖8 顧及環(huán)境語義的多目標(biāo)規(guī)劃路徑Fig.8 Multi-objective planning route with environment semantics

4 結(jié) 論

面向復(fù)雜室內(nèi)環(huán)境中的用戶多目標(biāo)導(dǎo)航需求，提出了綜合考慮室內(nèi)路徑復(fù)雜度、擁擠程度和阻斷事件的多目標(biāo)室內(nèi)路徑規(guī)劃方法.實驗結(jié)果表明，本文方法能夠通過顧及環(huán)境語義的導(dǎo)航通行成本函數(shù)實現(xiàn)對室內(nèi)導(dǎo)航環(huán)境變化的動態(tài)感知，從而規(guī)避環(huán)境擁堵路段和阻斷事件發(fā)生路段，為用戶提供具有易達(dá)性、安全性與舒適性的室內(nèi)多目標(biāo)路徑規(guī)劃結(jié)果.后續(xù)研究將考慮用戶個人行為語義與多維室內(nèi)環(huán)境語義結(jié)合，為用戶提供更具個性化的多目標(biāo)室內(nèi)路徑規(guī)劃服務(wù).

致謝：智慧廣州時空信息云平臺建設(shè)項目（GZIT 2016-A5-147）資助.