周 艷 ,陳 紅 ,張葉廷 ,黃悅瑩 ,張鵬程 ,楊衛(wèi)軍
(1.電子科技大學資源與環(huán)境學院,四川 成都 611731;2.電子科技大學大數據研究中心,四川 成都 611731;3.武漢大學測繪遙感信息工程國家重點實驗室,湖北 武漢 430072;4.廣州市城市規(guī)劃勘測設計研究院,廣東 廣州510060)
室內路徑規(guī)劃主要應用于室內導航[1-3]和應急疏散[4-5]等領域.近年來,隨著人們對復雜室內環(huán)境導航需求的日益增長,Google 地圖、必應地圖、百度地圖等眾多知名地圖服務供應商都已將室內導航作為地圖服務的必備功能之一.
相關研究為室內導航提供了不同的路徑規(guī)劃思路,主要可分為:基于三維模型語義信息[6-7]、增強用戶語義信息[8-9]和顧及上下文信息的3 類室內路徑規(guī)劃方法[10-11].這些方法的優(yōu)點是在規(guī)劃室內路徑時,不同程度上考慮了影響導航的語義信息,提高了路徑規(guī)劃的實用性.第1 類方法重點考慮了室內三維模型的幾何語義信息;第2 類方法將用戶信息及其行為語義納入導航路徑規(guī)劃中;第3 類方法考慮了環(huán)境上下文和用戶偏好語義,提供了以用戶為中心的個性化路徑規(guī)劃服務.上述方法的不足之處在于:現有的室內路徑規(guī)劃方法主要是針對單一目標的路徑規(guī)劃問題設計的(解決兩點之間的室內路徑規(guī)劃),而在現實生活中,用戶往往具有面向多目標的室內路徑規(guī)劃需求;此外,實際尋徑過程中的環(huán)境語義是動態(tài)變化的,現有方法在路徑規(guī)劃時往往將語義信息作為靜態(tài)約束條件,難以適應導航環(huán)境的動態(tài)變化.
為此,本文提出動態(tài)環(huán)境感知的多目標室內路徑規(guī)劃方法,考慮到室內動態(tài)環(huán)境信息是影響室內路徑規(guī)劃合理性與有效性的重要決定因素,將室內路徑復雜度、擁擠程度與阻斷事件等室內多維動態(tài)環(huán)境語義建模并量化,統一整合到室內導航路網模型中,基于Dijkstra 算法設計了顧及室內動態(tài)環(huán)境變化的室內路徑規(guī)劃方法,以滿足用戶個性化的多目標室內導航需求.
室內導航路網模型是實現室內路徑規(guī)劃和導航服務的基礎[12].目前的室內導航路網模型以幾何圖模型應用最為廣泛,這類模型可同時描述室內空間的幾何特征和拓撲特征,建模的方式主要有對偶圖模型[13]和門-門模型[14]兩種.本文提出顧及環(huán)境語義的室內導航路網模型,擴展節(jié)點-邊表示的室內導航圖模型,將室內路徑復雜度、擁擠程度與阻斷事件等動態(tài)環(huán)境語義建模并量化,統一整合到室內導航路網模型中,為實現動態(tài)環(huán)境感知的多目標室內路徑規(guī)劃提供導航路網模型支持.
基于圖模型的基本思想,室內導航空間可以抽象為節(jié)點-邊表達的幾何模型.其中,房間和門抽象為幾何中心,表示為節(jié)點,走廊以中心線的形式抽象表達為邊;節(jié)點與節(jié)點、節(jié)點與邊(即房間-門、門-走廊)之間根據實際路徑的連通性,建立節(jié)點-邊之間的連接,實現室內導航路徑連通,依此形成節(jié)點-邊表示的室內導航路網模型.為了滿足用戶個性化導航需求,本文對節(jié)點-邊表示的室內導航路網模型進行了擴展,如圖1所示.
圖1 擴展的室內導航路網模型Fig.1 Enhanced indoor navigation road network model
(1)增加了影響用戶室內路徑選擇的垂直組件,用于表達三維空間垂直方向上的可達路徑.垂直組件劃分為電梯、扶梯、樓梯3 類,以便于結合用戶偏好(如殘疾人輪椅更適宜選擇電梯等)合理規(guī)劃室內導航路徑,滿足用戶個性化室內導航需求.垂直組件在各樓層的出口表示為節(jié)點,垂直方向的連通性由垂直節(jié)點之間的連接邊表示;
(2)增加了影響用戶選擇路徑復雜程度的其它節(jié)點,如附加節(jié)點和拐彎節(jié)點.附加節(jié)點用于表示門與走廊之間、垂直組件與走廊之間的連接點,其數目一定程度上影響室內導航路網的復雜程度;拐彎節(jié)點表示導航過程中路徑方向發(fā)生變化的轉折點,導航路徑中過多的拐彎可能會增加用戶路徑認知障礙,降低導航路徑清晰性;
(3)房間細分為單門房間和多門房間.單門房間只有一個門節(jié)點連接走廊與房間,而多門房間有多個門節(jié)點與走廊連接,從而可以在路徑規(guī)劃時提供更多的室內導航路徑選擇;
(4)邊擴展為走廊、垂直邊和房間內連接邊.走廊以中心線的形式抽象表達為邊;垂直邊表示垂直方向上的連接邊,垂直邊與垂直組件的節(jié)點產生節(jié)點-邊關聯,用于表達樓層之間的垂直方向導航路徑;房間內連接邊表示房間節(jié)點與門節(jié)點之間的連接路徑,可用于多門房間內部的導航路徑規(guī)劃.
為直觀起見,本文以圖2所示的室內三維幾何模型為例,基于擴展的室內導航路網模型,構建由節(jié)點-邊表示的室內導航路網.圖2(a)表示的室內三維幾何模型共包含四層,鑒于各樓層導航路網建模過程大同小異,因而此處主要以第二層為例詳細說明.首先將圖2(a)中的房間和門分別按其二維投影的幾何中心抽象表達為節(jié)點,如R1、R2、R3、R4 等表示房間節(jié)點;D1、D2、D3、D4 表示相應房間的門節(jié)點.房間細分為單門房間(R1、R2、R3、R4 等)和多門房間(R12).對于單門房間,建立房間節(jié)點與門節(jié)點之間的連接邊(L1、L2、L3、L4 等);對于多門房間,建立房間節(jié)點與多個門節(jié)點(D11、D12、D13)之間的房間內連接邊(L12、L13、L14);同時在多門房間中建立門-門節(jié)點的房間內連接邊(L11、L15、L16).
圖2 室內導航路網建模實例Fig.2 An example for indoor navigation road network modelling
本文模型增加了垂直組件,垂直組件在各樓層的出口表示為節(jié)點,垂直方向的連通性用垂直節(jié)點之間的連接邊表示.本文將垂直組件劃分為電梯、扶梯和樓梯3 類,如圖3所示.垂直組件的出口與門類似,可以抽象表示為節(jié)點,相鄰樓層的垂直組件出口節(jié)點通過垂直邊(電梯)或斜邊(扶梯與樓梯)連接;樓梯的形態(tài)通常有兩種:樓梯直接連通樓層走廊和樓梯經層間轉折后連通樓層走廊,如圖3(c)所示.對于后一種樓梯,除了將樓梯連接走廊的出口視為節(jié)點以外,還需要將樓梯的層間轉折抽象為節(jié)點,建立節(jié)點-節(jié)點的斜邊連接.電梯和樓梯一般同時具有上行和下行方向語義,而扶梯通常具有單向上行或單向下行語義,圖3(b)表示了具有上行方向語義的扶梯路徑.通過增加垂直組件(電梯、扶梯、樓梯),可以在節(jié)點-邊表達的室內導航路網模型中引入方向語義約束,同時也為滿足特殊用戶(如乘坐輪椅用戶)的個性化路徑服務需求提供了可能性.
圖3 室內垂直組件導航路徑建模Fig.3 Navigation route modelling of indoor vertical components
室內導航路網模型中,在邊上添加附加節(jié)點,用于表示門與走廊的連接點,以及垂直組件與走廊的連接點.附加節(jié)點的位置均選擇走廊中心線上與連接節(jié)點距離最近的點,如圖2(b)中的A1、A2、A3、A4 表示門與走廊相連接的附加節(jié)點,A8、A9 表示垂直組件(分別對應樓梯V1、V2)連接走廊的附加節(jié)點.考慮到導航路徑中過多的拐彎會增加用戶路徑認知障礙,降低路徑清晰性,本文在模型中區(qū)分了拐彎節(jié)點.值得說明的是,拐彎節(jié)點并不是建模過程中物理生成的一類節(jié)點,而是在導航路徑規(guī)劃時產生的一類用于標識導航路徑方向發(fā)生變化的轉折點.當路徑中兩條連接邊斜率不同時,同時關聯兩條連接邊的節(jié)點被判定為拐彎節(jié)點.理論上而言,任何節(jié)點(包括門節(jié)點、房間節(jié)點和附加節(jié)點)都有可能成為拐彎節(jié)點,路網中的拐彎節(jié)點是動態(tài)變化的.比如,圖2(b)中,當從房間R1 到房間R4 規(guī)劃一條導航路徑時,門節(jié)點D1 與附加節(jié)點A1、附加節(jié)點A4 與門節(jié)點D4 依次被判定為拐彎點;但如果規(guī)劃一條從房間R1 到電梯V1 的路徑,此時A4 與D4 就不再是拐彎節(jié)點.因此,拐彎節(jié)點的作用主要是服務于導航路徑規(guī)劃,旨在判定拐彎數量從而輔助導航路徑決策,而不是直接用于構建室內導航路網模型.
綜上所述,圖2以一個樓層為例說明了室內導航路網的建模過程,其它樓層同理可得,不再贅述.
本文從以下三方面表達顧及環(huán)境信息的室內導航語義.
(1)路徑復雜度
室內導航路徑的復雜程度直接影響到解釋、說明和可視化表達導航路徑的難易程度,同時也影響到用戶理解、記憶以及執(zhí)行路徑導航指示的難易程度.相關認知研究表明,導航路徑復雜程度的重要性不亞于路徑長度,用戶在選擇路徑時,往往更愿意選擇較為簡單的導航路徑(即使其長度與最短路徑相比略有增加),因為它存在更少的認知障礙、更便于理解和導航[15-16].路徑復雜度表明了用戶理解、說明、記憶以及執(zhí)行路線導航指示的難易程度[17-18],尤其當用戶面對復雜建筑的陌生室內環(huán)境時,考慮導航路徑的復雜性顯得尤為必要.研究表明,拐彎數直接反映了路徑的復雜程度,在人類常用的數十種路徑選擇標準中,拐彎數是人們最常用的標準之一[19],導航路徑中的拐彎數越多,給用戶造成的導航體驗越復雜,即使是在用戶對路網十分熟悉的情況下仍然如此[20].鑒于拐彎數在路徑決策中的重要性,本文采用路徑拐彎數表達導航路徑的復雜程度,據此,路徑復雜度語義可以描述為
其中,number_turns為導航路徑中的拐彎數.
(2)擁擠程度
導航環(huán)境的擁擠程度是影響用戶導航體驗舒適性的重要因素.特別是在大型商場、火車站等人員密集的復雜室內導航環(huán)境中,路徑的擁擠程度成為影響用戶路徑選擇的重要決策因素之一.鑒于室內導航環(huán)境的擁擠程度直接影響到用戶室內導航體驗的舒適性,本文將室內導航環(huán)境擁擠程度的語義描述為
其中,crowd_type表示室內導航環(huán)境的擁擠程度.擁擠程度可以通過人群的通行速度來描述,擁擠程度不同對行人通行速度的影響也不同,通行速度可以通過人流密度反映,人流密度表明了單位面積上行人的數目.本文借鑒文獻[21]提出的通行速度(V,m/s)和人流密度(ρ,人/m2)的關系模式,使用表1定義的取值范圍對室內導航環(huán)境的擁擠程度劃分等級.據此,crowd_type可分為暢通、輕度、緩慢和堵塞4 種.crowd_range表示擁擠程度對應的區(qū)域長度;Tc表示擁擠程度對應的時間區(qū)間,由crowd_range與V之比得到.
表1 擁擠程度與人流量對應情況Tab.1 Degree of crowdedness and corresponding flow density
(3)阻斷事件
導航環(huán)境中的阻斷事件是導致路徑中斷、影響路徑可達性的主要因素.室內導航中常見的阻斷情況有設施故障、突發(fā)事故、人為阻斷等.為了描述阻斷事件對室內導航的影響,本文將導航環(huán)境中的阻斷事件語義表達為
其中,Tes為受阻斷事件影響的時間區(qū)間,event_range為阻斷事件的影響區(qū)域,描述室內導航路網中受阻斷事件影響的節(jié)點集合,event_range={v1,v2,···,vn},其中n為室內路網模型中受阻斷事件影響節(jié)點個數,v1、v2、 …、vn為室內路網模型中受阻斷事件影響的各節(jié)點,若該節(jié)點可達,取值為1,若該節(jié)點不可達,取值為0,此時,則可能導致相關節(jié)點也不可達.
將多維環(huán)境信息的導航語義引入室內導航路網模型中,可以使基于節(jié)點-邊表達的室內導航路網模型不僅具有路徑規(guī)劃需要的幾何信息,同時包含路徑復雜度、擁擠程度和阻斷事件等多維環(huán)境感知的室內導航語義信息,從而有效增強用戶室內導航的舒適性體驗.為此本文顧及室內環(huán)境語義信息,提出可量化的導航通行成本函數G為
式中:ωc為 擁擠程度 (C)的 權重系數;ωt為路徑復雜度 (T)的 權重系數;ωe為阻斷事件 (E)的權重系數;為節(jié)點vi、vj間路徑擁擠程度的成本函數;α為系數,可以根據表1的擁擠程度指定(暢通、輕度、緩慢和堵塞對應的 α分別取1.0、2.0、4.0和8.0);為vi和vj之 間的歐氏距離.fturn(Vm)為路徑復雜度的成本函數,可由導航路徑中的拐彎數計算決定,Vm為 導航路徑中的拐彎節(jié)點的集合;fevent(Vn)為阻斷事件的成本函數,Vn為受阻斷事件影響的節(jié)點集合,集合中節(jié)點可達,fevent(Vn)=1,節(jié)點不可達,fevent(Vn)→0.
ωc、 ωt和 ωe可以根據室內環(huán)境語義的重要程度進行權值分配,權值滿足式(3).
根據室內導航環(huán)境的動態(tài)變化可以不斷更新通行成本函數值,以節(jié)點間的導航通行成本作為室內導航路網的邊長,即可得到融合了動態(tài)環(huán)境語義的室內導航路網,此時,顧及室內環(huán)境語義的導航路徑規(guī)劃就轉化為基于室內導航路網求解室內導航路徑的最優(yōu)通行成本問題.
經典最優(yōu)路徑規(guī)劃算法主要有Dijkstra、A*、Floyd 和Bellman-Ford(BF)算法等,其特點如表2所示.與Floyd、BF 算法相比,Dijkstra 算法具有簡單易行的優(yōu)點,能夠獲得全局最優(yōu)解,雖然對于很長距離的路徑規(guī)劃效率不如A*,但就室內路徑規(guī)劃而言,Dijkstra 算法效率并無明顯差別,為此,本文基于擴展的節(jié)點-邊室內導航路網模型,將顧及室內動態(tài)環(huán)境語義的通行成本函數值作為室內導航路網的邊長,基于Dijkstra 經典尋徑算法實現室內多目標路徑規(guī)劃.
表2 經典最優(yōu)路徑規(guī)劃算法Tab.2 Classic optimal path planning algorithms
顧及室內動態(tài)環(huán)境語義的多目標尋徑方法如圖4所示.
圖4 室內多目標路徑規(guī)劃流程Fig.4 Flow chart of indoor multi-objective routing
(1)構建室內導航路網
基于本文擴展的節(jié)點-邊室內導航路網模型,構建用于尋徑的室內導航路網;設置室內導航路網中各邊長的初始值為 ∞;
(2)確定導航起始點和多目標點
設置用戶導航的起始點S和需要訪問的k個目標點的集合TargetList 為{T1,T2,···,Tk},Tk為多目標尋徑中的第k個目標點;設置CloseList 集合存放已遍歷的目標點,初始化為空;設置PathList 集合存放起始點到目標點的導航路徑,初始化為空;
(3)計算導航通行成本G*,更新室內導航路網
本文算法融合了室內導航環(huán)境語義信息,將節(jié)點間的G*作為室內導航路網的邊長.因此,基于當前的室內導航環(huán)境語義信息,通過計算節(jié)點間G*值,可以有效融合環(huán)境動態(tài)變化,實現室內導航路網更新;
(4)顧及環(huán)境語義信息的多目標尋徑方法
①利用Dijkstra 算法,尋找起始節(jié)點S到Target-List 中每個目標點的最短路徑(即最低通行成本路徑)D(T1)D(T2)···D(Tk),從中選取具有最短路徑的目標點TL滿 足:D(TL)=min{D(T1),D(T2),···,D(Tk)}.
②若D(TL)=∞,說明TargetList 當中所有目標點均不可達,跳轉至(6),算法結束;否則,將起始點S到目標點TL的導航路徑添加到PathList 集合,并將TL從TargetList 集合移動至已遍歷目標點集合CloseList;
③判斷TargetList 集合是否為空.如果TargetList非空,設置TL為 新的起始點,即S=TL,跳轉至(3);若TargetList 為空,說明目標點均已遍歷;
(5)輸出
多目標路徑集合PathList,算法結束.
本文實驗選用如圖5(a)所示建筑物三維幾何模型,以通行成本代價為邊長權值,構建顧及環(huán)境語義的室內導航路網,其對應四層樓的室內導航路網節(jié)點-邊拓撲結構如圖5(b)所示.通過設置擁擠情況和阻斷事件等不同的環(huán)境語義信息,分析比較環(huán)境語義對室內導航路徑規(guī)劃的影響,驗證說明顧及動態(tài)環(huán)境語義的多目標路徑規(guī)劃方法的可行性.
圖5 三維室內導航路網模型Fig.5 3D indoor navigation road network model
(1)導航環(huán)境擁擠情況對室內路徑規(guī)劃的影響
導航環(huán)境的擁擠程度是影響用戶路徑選擇的重要因素,為了說明導航擁擠情況對室內路徑規(guī)劃的影響,暫不考慮其它環(huán)境語義的影響,分別針對兩種典型的擁擠情況,模擬用戶請求規(guī)劃一條從起始節(jié)點S(節(jié)點編號為0)到多目標節(jié)點T1、T2、T3 和T4(節(jié)點編號分別為26、105、163 和234)的室內導航路徑,擁擠情況環(huán)境語義設置如表3所示.情景1規(guī)劃路徑如圖6(a)黑色路線所示;情景2 中,分別設定了輕度、緩慢和堵塞3 種擁擠程度的路段,室內多目標導航路徑的規(guī)劃結果如圖6(b)所示.
表3 實驗1 環(huán)境語義Tab.3 Environment semantics of experiment 1
圖6 擁擠情況對多目標室內路徑規(guī)劃的影響Fig.6 Impact of indoor multi-objective planning route with degree of crowdedness
為了說明導航環(huán)境擁擠情況對通行效率的影響,根據表1,取不同擁擠情況的通行速度中值(輕度、緩慢和堵塞的取值分別為1.24、0.69、0.30)測算不考慮避讓擁堵路段的Dijkstra 算法通行時間,并與本文避開擁堵路段的規(guī)劃路徑通行時間進行時間比較(暢通的通行速度取值1.40),其結果如圖7所示,3 種情況下本文方法的通行時間分別節(jié)約了19.7、124.3、23.7 s,節(jié)約的通行時間的百分比平均提升了17%,表明本文算法避開擁堵路段的導航時間通行成本更優(yōu).
圖7 路徑規(guī)劃的通行時間比較Fig.7 Comparison of travel time in path planning
對比情景1 和情景2 的路徑規(guī)劃結果可以看出,路徑規(guī)劃過程中針對導航環(huán)境擁擠程度的不同,本文算法通過感知環(huán)境信息避開了擁堵路段,因而用時更少,且改變了路徑規(guī)劃的節(jié)點訪問順序,得到了與無擁堵情況下不同的室內規(guī)劃路徑.根據本文多目標路徑導航算法原理分析可知,這是由于本文算法根據不同擁擠情況,對擁堵區(qū)域內受影響的導航路網邊權進行了G*的權值更新,使得擁堵路段的導航成本增高,因而有可能改變多目標節(jié)點之間的室內路徑規(guī)劃路線,實現顧及環(huán)境擁擠情況的合理室內路徑規(guī)劃.
(2)動態(tài)環(huán)境感知的多目標室內路徑規(guī)劃
為了驗證本文方法的有效性,綜合考慮環(huán)境擁擠程度、阻斷事件和路徑復雜性等多維環(huán)境因素影響,模擬用戶請求規(guī)劃一條從起始節(jié)點S(節(jié)點編號24)到多目標節(jié)點T1、T2、T3 和T4(節(jié)點編號依次為28、102、159 和234)的室內導航路徑.根據本文定義,多維環(huán)境語義中的路徑復雜度主要取決于路徑拐彎數,可由路網拓撲結構計算得到,因此表4主要針對環(huán)境擁擠程度和阻斷事件進行環(huán)境語義設置.假設情景1 中模擬所有區(qū)域均不存在擁擠情況和阻斷事件的理想路徑規(guī)劃情況;情景2 模擬方向語義約束的路徑規(guī)劃情況;情景3 中模擬多維導航環(huán)境中不同時刻、不同位置、不同擁擠程度和阻斷事件情況下的路徑規(guī)劃情況.實驗結果如圖8所示,情景1 中,多目標節(jié)點的室內規(guī)劃路徑如圖8(a)中黑色路線所示;為說明扶梯方向性語義的影響,情景2中,將3 樓到4 樓紅色虛線箭頭處的樓梯模擬為具有單向下行語義的扶梯,此時室內導航路徑規(guī)劃結果如圖8(b)所示.由圖8(a)和(b)可以看出,當垂直組件具有單向(上行或下行)方向語義約束時,規(guī)劃路徑發(fā)生了變化,這是由于在方向語義約束下,本文方法會將相關垂直組件設為不可用邊,從而避開不可用邊;情景3 中,假設t1時刻在圖8(c)1 樓黃色區(qū)域出現輕度擁擠,t2時刻在圖8(c)2 樓橘色區(qū)域出現緩慢程度的擁擠情況以及1 樓到2 樓的紫色節(jié)點處發(fā)生阻斷事件,t3時刻在圖8(c)4 樓紅色區(qū)域出現堵塞情況,t4時刻不存在任何的擁擠和阻斷情況,此時規(guī)劃的路徑如圖8(c)所示.由圖8(a)和(c)可以看出,兩者規(guī)劃的路徑存在較大差異.在t1時刻的輕度擁擠情況沒有影響路徑的規(guī)劃結果,但t2時刻擁擠程度變?yōu)榫徛约白钄嗍录陌l(fā)生直接導致訪問節(jié)點由102 變?yōu)?59,t3時刻的堵塞情況造成路徑規(guī)劃中以普通樓梯取代了電梯,使節(jié)點159 到節(jié)點234 的規(guī)劃路線發(fā)生了變化.可以看出,環(huán)境擁擠程度較輕時,由于對導航通行成本影響較小,因而沒有影響路徑規(guī)劃結果;環(huán)境擁擠程度加劇或出現阻斷事件時,環(huán)境語義的動態(tài)變化引起路網相關邊的導航通行成本函數動態(tài)更新,實驗結果說明本文方法能夠有效感知動態(tài)環(huán)境變化,規(guī)避環(huán)境擁堵和阻斷事件發(fā)生路段,能合理規(guī)劃室內導航路徑.
表4 實驗2 環(huán)境語義Tab.4 Environment semantics of experiment 2
圖8 顧及環(huán)境語義的多目標規(guī)劃路徑Fig.8 Multi-objective planning route with environment semantics
面向復雜室內環(huán)境中的用戶多目標導航需求,提出了綜合考慮室內路徑復雜度、擁擠程度和阻斷事件的多目標室內路徑規(guī)劃方法.實驗結果表明,本文方法能夠通過顧及環(huán)境語義的導航通行成本函數實現對室內導航環(huán)境變化的動態(tài)感知,從而規(guī)避環(huán)境擁堵路段和阻斷事件發(fā)生路段,為用戶提供具有易達性、安全性與舒適性的室內多目標路徑規(guī)劃結果.后續(xù)研究將考慮用戶個人行為語義與多維室內環(huán)境語義結合,為用戶提供更具個性化的多目標室內路徑規(guī)劃服務.
致謝:智慧廣州時空信息云平臺建設項目(GZIT 2016-A5-147)資助.