基于上下文感知的室內路徑規劃研究

林 雕，宋 國 民，游 雄，賈 奮 勵，鄧 晨

(信息工程大學，河南 鄭州 450001)

基于上下文感知的室內路徑規劃研究

林 雕，宋 國 民，游 雄，賈 奮 勵，鄧 晨

(信息工程大學，河南 鄭州 450001)

為實現精細化的室內導航服務，綜合考慮室內空間特性以及上下文感知應用需求，定義了規范化的室內導航模型數據結構，設計了室內POI數據模型，并針對不同類型POI給出了對應的POI與導航模型的轉換方法。具體分析了時間、位置、用戶、擁擠、事件5類典型上下文信息對路徑規劃的影響并建立對應的描述模型。基于所提空間模型與上下文信息模型，提出了上下文感知的路徑規劃實現流程與方法，并針對擁擠情況、事件兩類上下文信息的特點建立了對應的權值更新方法。設計了兩組不同上下文背景條件下的室內路徑規劃模擬實驗，通過比較分析其最優路徑結果，驗證了本文所提模型與方法的有效性。

室內路徑規劃；室內POI建模；上下文建模；上下文感知；權值更新

0 引言

隨著城市的快速發展與擴張，大型建筑物逐漸成為人們生活中開展各類活動的基本場所。但建筑物內部構造復雜、功能分區多樣，加劇了空間認知負擔，使人們在商場、醫院等大型公共場所的尋路變得愈加困難[1]。因此，室內導航已成為當前GIS與位置服務領域的研究熱點。面向室內導航應用，當前已提出多種室內空間模型，其中以幾何圖模型應用最為廣泛，這類模型可同時描述空間的幾何以及拓撲特征，建模的方式主要有中軸變換[1-4]以及“門—門”[5-7]兩種。不同于幾何模型，語義模型[8,9]側重于空間的語義層次建模，通常采用本體的建模方法對空間進行描述，并可借助其推理功能實現以用戶為中心的室內導航。縱然目前在室內空間建模方面已取得較多成果，但路徑規劃本身仍以最短距離或時間為主要擇路條件，對路徑規劃中所受上下文影響因素考慮較為簡單(通常限于用戶上下文)。實際上，室外的智能交通應用中已將天氣、交通擁擠等上下文納入到導航應用的考慮當中[10-12]。

因此，面向個性化、智能化室內路徑導航服務需求，本文重點關注不同上下文背景下的室內路徑規劃。首先，在筆者先前所提語義導航模型[13]基礎上，對其數據結構進行擴展，并提出路徑規劃關鍵空間要素POI的數據結構及其與導航模型的關聯方法，以構建上下文感知的室內路徑規劃所需空間模型基礎。接著，以是否對用戶通行行為產生影響為上下文建模對象選取準則，重點對5種典型上下文要素的特點進行分析并構建其對應的上下文描述模型。然后，基于所提室內空間模型與上下文模型，提出上下文感知的室內路徑規劃的實現流程和關鍵算法。最后，通過實驗對所提模型與方法的有效性做出驗證。

1 面向上下文感知的室內空間數據模型設計

1.1 基于圖的室內導航數據模型

面向上下文感知應用需求，文獻[13]提出基于圖的語義室內導航概念模型及其對應的數據結構，但其所定義數據結構相對簡單，僅限于通用拓撲數據字段。為實現對上下文感知路徑規劃相關語義信息的描述，需對原有數據結構進行擴展與改進，定義便于統一存儲、管理及應用的數據結構。

分析該語義室內導航概念模型可知，其中節點和邊均可表示多類空間對象，但各種對象不同屬性對導航的影響有所差異。例如，通道材質的粗糙程度以及門檻的高低都將影響輪椅用戶的通行，此類屬性主要對不同類型用戶通行產生影響，而房間的公私屬性則主要影響不同身份用戶的通行。圖模型數據結構設計中，若將所有對象的所有屬性均作為對應節點或邊的屬性字段，勢必造成數據結構臃腫，增大數據管理和檢索的難度。本質上，導航圖模型屬性字段定義的目的是為了實現對導航相關語義信息的描述。因此，此處重點對限制用戶通行的語義信息進行描述，通過給邊額外增加 “受限用戶類型”、“受限用戶身份”、“通行方向”以及“開關時間”4個屬性項將不同對象不同屬性對用戶的通行限制進行統一描述，以實現對圖模型的簡潔、規范化的定義。改進后的節點與邊數據結構如表1與表2所示。其中，“受限用戶類型”、“受限用戶身份” 分別與下一節用戶上下文中的類型和身份相對應。

表1 節點數據結構Table 1 Node data structure

表2 邊數據結構Table 2 Edge data structure

1.2 室內POI數據模型

POI是用戶路徑規劃中重點關注的一類信息，目前對室內的POI分類與組成尚無統一定義。文獻[14]認為室內路徑規劃中的POI主要是指用戶尋路過程中可能的起始點或終止點，主要包括房間、建筑物出口以及服務設施(如飲水機)三類空間對象。由于概念模型中僅將建筑物出口抽象表示為節點，并未將房間和服務設施兩類POI抽象為獨立的圖元。因此，當選定某一POI作為路徑規劃的起點或終點時就涉及如何將POI轉換到路網中指定位置的問題。針對該問題，設計如表3所示POI數據結構，其字段有ID、類型、名稱、對應室內對象類型及ID、幾何邊界、定位點、語義位置以及關聯出口(包括類型和原始ID)。其中關聯出口主要包括門和窗戶兩類，房間關聯出口是指可進出該房間的門或窗戶；建筑物出口的關聯出口則為其自身；對服務設施而言，若處于房間內部則其關聯出口與所處房間相同，反之則為空。

表3 POI數據結構Table 3 POI data structure

基于該POI數據模型，當選定某一POI作為路徑規劃起點或終點時，其與圖模型轉換方法如下：1)選定POI類型為房間：將該POI所有關聯的出口作為備選的起始節點或終止節點，分別計算多條備選路線的權值，其中權值最小路線所對應的首節點或末節點即為當前的起始或終止節點。2)選定POI類型為建筑物出口：此時直接將其轉換為路網中對應的建筑物出口節點即可。3)選定POI類型為服務設施：首先判斷該POI關聯出口是否為空，若為空則表示該POI處于走廊內部，此時計算距該POI定位點最近的節點或邊，并將其與最近節點或者對應的最近邊垂足點相連動態加入路網。若不為空則將其與對應的關聯出口相連動態加入原有路網。

2 面向路徑規劃的上下文建模

上下文是一個非常寬泛的概念，通常需根據應用的特點，選取與當前應用關系最為密切的上下文信息并對其進行建模。借鑒文獻[15]對位置服務上下文的描述，本文上下文建模主要考慮用戶本身及所處環境中描述其狀態、影響其通行的上下文信息。進一步區分可將路徑規劃上下文分為客觀空間環境、用戶自身特性以及動態變化的外部環境。客觀環境主要指用戶所處的建筑物環境，上章室內空間建模的實質即為對客觀空間環境的單獨建模。因此，本章主要考慮對用戶自身特性以及動態變化的外部環境兩類上下文的描述。參照智能室外導航中上下文建模內容，結合對典型室內路徑規劃情況的分析，此處重點研究“擁擠”和“事件”兩類動態變化的外部環境上下文信息。另外，由于現實世界中的客觀實體與現象均具有時空屬性，本文將時間和位置作為基礎上下文要素也納入上下文的建模當中。下面以時間、位置、用戶、擁擠、事件5類典型上下文信息建模為案例，對面向室內路徑規劃的上下文建模進行分析。

2.1 時間

在情景中，時間是一個觸發變化的因素[16]。時間數據包括時間點、時間段兩種。對應數據結構如下：

時間點：TimePoint=(year,month,day,hour,minitue,second)

時間段：TimeSegment=(TimePointi,TimePointj)

其中，時間點是定義在特定時區下的某一時刻，通過年、月、日、時、分、秒來描述，路徑規劃中的特征時間點主要有用戶發出請求時刻，室內設施開關轉換時間點等。時間段由兩個時間點組合而成，如門的打開與關閉時間點共同組成門的打開時間段。

基于時間點發生的先后順序可推斷出時間點之間的關系，分別用“<”、“=”、“>”表示之前、同時、之后3種時間關系。基于時間點關系，可進一步判定時間點與時間段之間的包含關系，如某一門打開時間段為(TimePoint1,TimePoint2)，若當前的時間點TimePoint滿足TimePoint1≤TimePoint≤TimePoint2，則可判定該門處于可通行狀態。

2.2 位置

室內位置信息主要有幾何位置和語義位置兩種描述方式，幾何位置通過定義在笛卡爾坐標系下的三維坐標描述，語義位置則通過地址和屬性對其進行描述。對應數據結構如下:

坐標位置：CoordLocation=({(x1,y1,z1),…(xn,yn,zn)},reference)

語義位置：SecLocation=(adress(floor,num,name),attribute(function,owner))

其中，坐標位置分為點狀、線狀、面狀和體狀4種，不同類型位置對應坐標描述不同，reference表示該坐標位置對應的參考坐標系，既可是世界坐標系也可是局部坐標系。語義位置的地址包括樓層、房間號、名稱，屬性則內含功能與所屬兩個屬性項。

幾何位置與語義位置描述的側重點以及描述方式上存在較大差異。實際路徑規劃上下文信息中可能同時存在兩種不同形式的位置信息，但最終都需將其轉換到圖模型中對應的節點或邊上，從而用于支持路徑分析。路徑規劃中需重點對一些特征位置信息進行關注，如用戶當前位置、路徑規劃請求中的起點與終點位置以及事件和擁堵情況所發生的區域位置。

2.3 用戶

用戶是路徑規劃應用的主體與核心所在，不同用戶在通行能力、通行權限以及其他個體特征上均存在一定差異，定義用戶數據結構為：

User=(id,name,type,identity,preference,location,time)

id、name、type、identity、preference分別表示用戶標識、姓名、類型、身份、路徑偏好，location和time則表示用戶當前位置和用戶發出請求的時刻。其中，用戶類型主要包括普通用戶、聽覺障礙用戶、視覺障礙用戶、移動障礙用戶(輪椅用戶)等，不同類別的用戶對應的通行能力不同。用戶身份主要依據用戶的室內通行權限進行劃分，一般可將其分為工作人員和非工作人員兩類，也可根據實際情況對其進一步細化，如可將醫院工作人員劃分為醫生與護士。用戶的室內路徑偏好可初步劃分為垂直通道偏好和水平通道偏好兩類。其中垂直通道偏好主要由“不走樓梯”、“不走電梯”以及“不走扶梯”中的一項或多項組合描述。水平通道偏好主要通過“只走主通道”描述，選取該偏好表示不能將房間內部的路網作為最優路徑。

2.4 擁擠

交通擁擠狀況為室外車輛導航中重點考慮的一個上下文因素，主要通過車流量的大小來描述實時交通狀況。類似的，室內通行中也存在擁擠情況，特別是在大型商場、火車站等人員密集場所，人群的通行速度和擁擠狀況密切相關。

擁堵的發生與人們的生產、生活以及社會活動相關，具有周期性變化特征[17]。例如，商場一般在周末、節假日等時間容易出現擁堵，而工作日的人流量一般較小，同一天內通常上班時間人流量較小，下班時間人流量較大。因此，根據其周期性變化特點，將一年的日期分為不同類別，并針對某一類日期的特定情況，將一天的時間劃分為不同時段。實際應用中，可基于對某一類建筑物實測人流數據的統計分析對日期的類型和時段進行劃分，日期類別定義如下：

Type={ts1,…,tsn}

所有的類別構成類別集，具體的一天必定屬于類別集合中的某一特定類別。類別集定義為：

Typeset={p1，…,pm}

式中:m∈N表示類別數量；pi∈Type表示第i個類別(1≤i≤m)。

需指出的是，與室外不同，各類建筑環境下的時間分類分段有所區別。例如，火車站和商場的擁擠時間分段有所差異，商場的人流量主要與用戶休閑時間相關，火車站的擁擠時間則與列車的出發及到達時間密切相關。因此，針對不同類型的建筑物需建立對應的擁堵情況時間分類分段描述。

基于以上對時間分類分段的論述，定義擁擠情況數據結構：

Jam=(id,(p,ts),location,level)

id表示時間分類分段標識，組合(p,ts)中p表示該時間分區對應的日期類型，ts表示時間分區，location表示該時間分區對應的擁堵區域，level表示對應的擁擠程度。其中，定性地將level劃分為正常、輕度擁擠、中度擁擠、重度擁擠4類情況。

2.5 事件

事件是指環境中所發生的影響用戶通行的特殊情況，主要對通道的通行狀態產生影響，根據其特征將事件數據結構定義為：

Event=(id,type,time,location,level)

id表示事件標識，type表示事件類型，time表示事件的生命周期(包括發生與持續的時間)，location表示事件發生位置，通常為某一區域，level表示事件等級。其中，事件類型包括設施故障，計劃活動，突發事故3類，設施故障是指室內通行設施運營的突發情況，如電梯停運。計劃活動是指提前計劃將要發生的影響通道通行狀態的行為，如安全警戒區域設定、室內道路改造等。突發事故是指偶然發生的影響道路通行的事件，如火災。事件等級主要通過道路的影響程度定義，分為輕微、中等、嚴重、特別嚴重4級。

擁擠和事件的數據結構具有一定的相似性，也可將擁擠看作是一類特殊的事件。上文是對其數據結構進行單獨定義，而非對通道人流量的實時、定量建模，因為實際應用中難以完全實現對室內區域擁擠情況的實時處理、分析，而基于人流統計分析的定性建模方式則有利于提高上下文的感知效率。

3 上下文感知的路徑規劃算法

上下文感知的室內路徑規劃流程如圖1所示，不同階段所受上下文的影響有所差異。其中，權值初始化以通行時間為路網的初始權值；初始路網的構建則是根據起點和終點所在樓層動態構建用于路徑分析的樓層路網。下面重點對“確定起始與終止節點”、“確定可用路網”、“權值更新”3個關鍵階段進行分析。

圖1 上下文感知的室內路徑規劃流程Fig.1 Flow chart of context-aware indoor routing

(1)確定起始與終止節點。確定起始與終止節點是指將用戶原始路徑規劃請求中的起點和終點轉換到路網中對應的節點。原始路徑規劃請求中的起點和終點主要來源有：交互界面選擇、用戶輸入以及用戶當前位置3類，包括幾何和語義兩種位置表現形式。根據位置描述形式的不同，對應的轉換過程有所區別。若為語義位置，則將其與POI匹配，并利用1.2節所提POI到節點轉換方式確定其對應的起始或終止節點；若為坐標位置，首先判斷該坐標點位置是否位于某一房間內部，若成立則建立該點與房間對應出口之間的連接關系，進而動態加入到路網當中；反之則將該點與距離其最近節點或最近邊垂足點相連動態加入路網。

(2)確定可用路網。確定可用路網是指根據上下文背景條件排除初始路網中不可用的路徑。主要涉及用戶類型、用戶身份及用戶請求時間3類上下文信息，分別對應于導航模型數據格式中的“受限用戶類型”、“受限用戶身份”及“開關時間”3個字段。通過對初始路網中所有的邊進行遍歷，判斷當前各類上下文信息是否屬于其對應的受限范圍，若成立則將該邊權值設定為無窮大即可，反之則不作處理。

(3)權值更新。權值更新是指根據當前的上下文背景條件對可用路網的邊權值進行更新。首先將用戶的請求時間與擁擠以及事件上下文的時間信息進行匹配，確定當前時刻下兩類上下文對應的影響區域，然后對區域內受影響的邊進行加權處理。兩類上下文對應影響因子如下：

擁堵情況影響因子μ：不同的擁擠等級對行人的通行速度影響大小不同，一般用人流大小表示室內通道的擁擠程度，其重要衡量指標為人流密度(單位面積上人員的數目)。災害救援領域研究中已提出了多種行人速度和人流的關系公式[18,19]，借鑒文獻[18]中所提水平通道速度和人流的關系模型(式(1))，對不同道路擁堵等級下對應人流量大小以及平均速度做出規范，并通過平均速度除以正常速度(此處為1.4 m/s)確定其對應的μ值(表4)。

(1)

式中：V表示行人的通行速度(m/s)，ρ表示人流量大小(人/m2)。

表4 擁堵情況影響因子Table 4 Impact factor of congestion

事件影響因子λ：根據事件影響程度的大小設定相應的權值，此處側重于對于事件所產生影響的定性建模，主觀對其賦權：影響程度分為輕微、中等、嚴重和特別嚴重，對應賦值分別為0.9、0.6、0.3和0.01。權值越大表示所受事件影響越小，未受事件影響的區域的權值則為1。應用中，可根據實際情況對影響因子作相應調整。

確定上下文影響區域對應的影響因子后，即可進行權值的更新。擁擠與事件對應的權值更新公式分別為式(2)與式(3)，其中，ei、ej分別表示當前時間下擁堵區域與事件影響區域內的任意一條邊。

weightei′=weightei×(1/μ)

(2)

weightej′=weightej×(1/λ)

(3)

4 實例分析

根據第一章所提室內導航模型，選取鄭州某商場1、2層樓層平面圖為數據源，構建對應的室內拓撲路網(圖2)。以路徑通行時間為權值，對其進行初始賦權，在此基礎上展開不同情境下的路徑規劃實驗。

圖2 樓層1(左)和樓層2(右)的平面圖以及對應的路網Fig.2 Floor plan of the first floor (left) and second floor (right) with their indoor network

此處側重于方法的驗證，采用模擬、預設等方式構建路徑規劃上下文仿真實驗條件，分別設計兩組實驗，以證明本文所提模型與方法的有效性。實驗1主要是對不同用戶上下文背景的路徑規劃進行分析，實驗2則開展不同擁擠情況和事件兩類上下文背景條件下的路徑規劃實驗，兩組實驗中均不受其他未標明上下文的影響。

實驗1：實驗條件如表5所示，圖3為其對應結果。由圖3可知，情境2與情境3所規劃路線相同，但與情境1路線有所差異。其中情境2中由于房間143處于關閉狀態，因此計算所得最優路線未包含該房間內部路段，轉而途經141、142房間以及對應通道路段到達目的地。而情境3則由于145房間屬于工作人員專用區域，對普通顧客而言該房間對應門所關聯的水平邊均為不可用邊，進而導致其最優路徑并未通過房間145。情境4中則由于當前用戶偏好為“只走主通道”，使得其路線僅限于室內通道區域。

實驗2：實驗條件如表6所示，其對應結果見圖4。

表5 實驗1上下文背景Table 5 Context of experiment 1

圖3 實驗1最優路徑Fig.3 Optimal routes of experiment 1

由圖4可知，情景2與情境1路線差異較大，主要是由于在情景2中擁堵情況較為嚴重，從而使得樓層1和樓層2的路線均有所不同。對比情景2和情景3的路線可知，由于情景3中二樓事件發生區域與原有情景2的二樓最優路線部分恰好重合，因此路徑規劃過程中綜合考慮兩層樓路網的權值變化，重新推薦了一條與原有兩條路線均有所不同的路線。

表6 實驗2上下文背景Table 6 Context of experiment 2

圖4 實驗2最優路線Fig.4 Optimal routes of experiment 2

綜合對上述兩組實驗的分析可知，本文所提模型與路徑規劃方法能夠有效根據上下文背景條件推薦出適合當前應用情境的最優路徑。

5 結語

針對上下文感知的路徑規劃需求，本文分別建立了空間與上下文兩類信息的基礎模型。空間建模中對已有導航模型數據結構進行擴展與改進，以實現對導航相關語義信息的統一、規范化表達，并提出了室內POI的數據模型及其與導航模型的關聯方法；上下文建模部分提出了5類典型上下文信息的描述模型。結合上下文感知的路徑規劃流程具體分析了空間模型與上下文模型的結合方法，并給出其中路網權值更新的實現算法。通過實驗驗證了所提模型與方法能夠有效針對不同上下文背景得出合理有效的最優路徑。下一步工作將對上下文模型進行細化、擴展，并接入多源傳感器信息，發展面向實地的上下文感知的室內路徑導航系統。

[1] 溫永寧,張紅平,閭國年，等.基于房產空間數據的樓宇空間疏散路徑建模研究[J].地球信息科學學報,2011,13(6):788-796.

[2] GILLIERON P V,MERNINOD B.Personal navigation system for indoor applications[C].11th IAIN World Congress,2003.21-24.

[3] LEE J.A three-dimensional navigable data model to support emergency response in microspatial built-environments[J].Annals of the Association of American Geographers,2007,97(3):512-529.

[4] THILL J C,DAO T H D,ZHOU Y.Traveling in the three-dimensional city:Applications inte planning[J].Journal of Transport Geography,2011,19(3):405-421.

[5] YUAN W J,SCHNEIDER M.iNav：An Indoor Navigation Model Supporting Length-Dependent Optimal Routing[M].Geospatial Thinking.Berlin:Springer,2010.299-313.

[6] LIU L,ZLATANOVA S.A"door-to-door"path-finding approach for indoor navigation[C].Proceedings of GeoInformation for Disaster Management Conference,2011.3-8.

[7] DAVIDE R,ZLATANOVA S,CLEMENTINI E.Route directions generation using visible landmarks[C].Proceedings of the Sixth ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness.ACM,2014.1-8.

[8] TSETSOS V,ANAGNOSTOPOULO C,KIKIRAS P.Semantically enriched navigation for indoor environments[J].International Journal of Web and Grid Services,2006,4(2):453-478.

[9] DUDAS P M,GHAFOURIAN M,KARIMI H A.ONALIN:Ontology and algorithm for indoor routing[C].Tenth International Conference on Mobile Data Management:Systems,Services and Middleware,2009.720-725.

[10] 齊曉飛,王光霞,周小軍,等.導航地圖情境建模[J].地理信息世界,2014,21(2):6-12.

[11] 梁晶.上下文感知計算及其在智能交通中的應用[D].長春：吉林大學,2011.

[12] 王江晴,康立山.動態車輛路徑問題中的實時最短路徑算法研究[J].武漢理工大學學報(交通科學與工程版),2007,31(1):46-49.

[13] 林雕,宋國民,鄧晨.基于圖的語義室內導航模型構建研究[J].測繪工程,2015,24 (1):48-52.

[14] KARIMI H A,GHAFOURIAN M.Indoor routing for individuals with special needs and preference[J].Transactions in GIS,2010,14(3):299-329.

[15] 齊凌艷,陳榮國.位置服務的上下文信息模型[J].地球信息科學學報,2014,2:007.

[16] LIJDING M E M,BENZ H P,MERATNIA N,et al.Smart signs:Showing the way in smart surroundings[R].Technical Report TR-CTIT-06-20 Centre for Telematics and Information Technology,University of Twente,Enschede,2006.

[17] 鄭年波,陸鋒,李清泉.面向導航的動態多尺度路網數據模型[J].測繪學報,2010,39(4):428-433.

[18] LO S M,FANG Z,LIN P,et al.An evacuation model:The SGEM package[J].Fire Safety Journal,2004,39:169-190.

[19] PREDTECHENSKII V M,MILLILINSKII A I.Planning for Foot Traffic Flow in Buildings[M].India:Amerind Publishing Co,1983.

Study on the Context-Aware Indoor Path Planning

LIN Diao,SONG Guo-min,YOU Xiong,JIA Fen-li，DENG Chen

(InformationEngineeringUniversity,Zhengzhou450001,China)

To provide a more advanced and personalized indoor routing service for users in different scenarios,an refined indoor navigational data model is defined which provide a unified and concise description of the geometric,topological and semantic information of indoor space.As the significance of POI during the path planning,a POI data model is proposed,and classified into three types:room,building exit and services facility,then the conversion methods between each type and the navigational model are given respectively.Five typical contexts:time,location,user,congestion and event are selected as the components of the indoor routing context due to their significant influence on indoor routing,and corresponding descriptive model for each context is established along.Based on the proposed spatial and contextual models,the processes and methods of context-aware indoor routing are presented,which gives an elaborate interpretation on how to combine the two models together smoothly for the path planning.According to the features of congestion and events,two key weight updating algorithms are then built.Two simulated indoor routing experiments are designed for various preset indoor path planning scenarios,the results of which validated the effectiveness and efficiency of the proposed models and methods.

indoor path planning;indoor POI modeling;context modeling;context-aware;weight updating

2015-11-13；

2016-01-11

國家高技術研究發展計劃(863)基金項目(2013AA12A202)；國家自然科學基金項目(41371382)

林雕(1991-)，男，博士研究生，主要研究方向為室內導航及室內空間建模。E-mail：srlind213@126.com

10.3969/j.issn.1672-0504.2016.03.002

P208

A

1672-0504(2016)03-0008-06