面向視力障礙乘客的地鐵站內路徑規劃算法研究*

李 勝 鄭成龍 劉 源 孫 強 邢宗義

(1. 南京理工大學自動化學院， 210094， 南京；2. 中車青島四方機車車輛股份有限公司， 266111， 青島∥第一作者， 副教授)

路徑規劃指的是在有障礙物的環境下根據某種指標尋找一條從起點到目標點的無碰撞路徑[1]。規劃的目的是為了找到起點和目標點之間在時間上或距離上的最短路徑，目前主流的最短路徑算法包括Dijkstra算法、Floyd算法[2]、A*算法[3]等。

在地鐵站封閉復雜環境內，常規的最短路徑規劃算法并不適用于視力障礙(以下簡稱“視障”)人群。視障人士在室內環境下的移動不僅要考慮起點和目標點之間距離的遠近，循著路標的無障礙路徑更為適用。因此，應選取影響視障乘客通行能力的因素作為路徑權值的定量。

1 視障乘客通行影響因素及當量表示

1.1 視障乘客通行影響因素

根據調查，影響視障乘客在地鐵站內通行的因素如下：

1) 路徑的沿墻長度。在路徑權值計算中，路徑長度占據了重要地位。而對于視障乘客而言，沿墻行走是其傾向的行走方式，因此引入沿墻長度因子k1。

2) 路徑的非沿墻長度。非沿墻路徑也是決定視障乘客室內路徑權值的重要因素，引入非沿墻長度因子k2。

3) 路徑中的直角彎。視障人群對角度沒有清晰的概念，他們更加傾向直角彎，故對其進行量化，引入直角彎因子k3。

4) 路徑的非直角彎。路徑中的非直角彎對視障人群會產生負面的影響，因此同時引入非直角彎因子k4。

5) 路徑的樓扶梯。通過對盲校同學的調查，他們對樓扶梯的信任度很低，因而引入樓扶梯因子k5，使其區別于普通路徑。

6) 路徑的垂直電梯。無障礙電梯通常配有盲文提示，可認為是視障乘客出行的不二選擇，因而在路徑選擇時將乘坐垂直電梯考慮在內，引入垂直電梯因子k6。

7) 路徑的特殊地形和障礙物。地鐵站內存在凸起、斜坡、凹陷等特殊地形，路徑上存在垃圾桶等障礙物，這些對視障乘客的行走不利。因此，引入路徑的障礙物和特殊地形因子k7。

1.2 視障乘客通行影響因子的當量表示

上文歸納出影響視障乘客站內通行的7個影響因子，但這些影響因子的單位不盡相同，因此要用當量對其進行表示，設矩陣P=[k1,k2,k3,k4,k5,k6,k7]，ni、nj分別為拓撲模型中第i個、第j個頂點。a=(ni，nj)，a表示連接這2個頂點的邊。

1.2.1 沿墻長度和非沿墻長度的當量表示

設d(ni，nj)為2個頂點ni、nj之間的歐幾里得距離。若邊a沿墻，則k1=d(ni，nj)；若邊a不沿墻，則k2=d(ni，nj)。

1.2.2 直角彎和非直角彎的當量表示

若邊a連接的2個頂點方向與a的上一條路徑呈直角，則k3=2；若呈非直角，則k4=5。

1.2.3 樓扶梯、垂直電梯的當量表示

若a的端點連接樓扶梯或垂直電梯，則給邊a賦予樓扶梯或電梯當量。如果a邊有一端為路徑的終點，則k5=10，k6=4。如果a邊的端點均不是終點，則此樓扶梯或垂直電梯為站臺層和站廳層的連接點，為了避免站臺層和站廳層對樓扶梯和電梯的重復計算，此時的當量應減半，即k5=5，k6=2。

1.2.4 不規則地形和障礙物的當量表示

給不規則地形的不規則程度賦值，如較平坦、較粗糙、上下坡分別賦予危險指數2、4、6。典型障礙物柱子、垃圾桶、自動售貨機、椅子的危險指數分別為5、2、4、3。由此可得：

(1)

式中：

m——邊a中不規則地形和障礙物的總個數；

rp——第p個對象的危險指數。

2 多目標決策

計算最優路徑，其本質屬于多目標決策問題。解決此類問題的主要方法有：① 直接加權法；② 間接加權法，包括 VEGA算法、有序比較與隨機比較法、概率向量選擇法[4]、層次分析法等；③ 基于Pareto最優解集的方法。

本文的最優路徑計算是個典型的最優目標決策問題，所選用的層次分析法[5]是在對決策問題的本質、影響因子及其內在關系等進行深入分析的基礎上，使決策的思維過程數學化，為難于完全定量的復雜決策問題提供了簡便的決策方法。

2.1 層次分析法

采用層次分析法來解決視障乘客在地鐵站內的路徑規劃計算，其具體步驟如下。

2.1.1 確定指標

根據上文，確定視障乘客路徑選擇時的影響因子。

2.1.2 建立層次結構模型

本文所建立的層次結構模型如圖1所示,分為4個層次，其中：目標層為路徑權值；指標層Q為路徑長度和路徑不安全性；指標層K為上述的7個影響因子；方案層則為具體的站內走行路徑設計方案。

圖1 層次結構模型Fig.1 Hierarchical structure model

2.1.3 構造判斷矩陣

根據層次結構模型，構建目標層、指標層2個層次的判斷矩陣。判斷矩陣的值通過兩兩互比來設置。針對路徑的總加權目標W，構造出目標層的判斷矩陣WQ：

(2)

同理，針對指標層Q的q1、q2指標，分別構建出指標層指標Q的2個判斷矩陣Q1,K和Q2,K：

(3)

(4)

2.1.4 計算單排序權向量并做一致性檢驗

根據正互反矩陣和一致性矩陣定義,WQ、Q1,K和Q2,K均為正互反矩陣，但WQ是一致性矩陣，Q1,K和Q2,K不是一致性矩陣，故需對這3個矩陣的不一致程度進行衡量，定義一致性指標IC的計算式為：

(5)

式中：

λmax——對應于判斷矩陣的最大特征根；

n——判斷矩陣的階數。

如果IC=0，則說明該判斷矩陣完全一致；IC越接近0，則該判斷矩陣的一致性越高；IC的值越大，則該判斷矩陣的一致性越低。

引入隨機一致性指標IR，用以衡量IC的大小。IR由隨機構造的500個成對比較矩陣所得，其值可查表獲得，表1給出了判斷矩陣不同階數下所對應的IR值。

表1 不同階數對應的IR值Tab.1 IR values corresponding to different orders

定義一致性比率RC為:

RC=IC/IR

(6)

一般地，當RC≤0.1時，認為矩陣的不一致程度在合理范圍之內，可用歸一化特征向量作為權向量；如果RC>0.1，則認為矩陣的不一致程度過高，需要重新構造成對比較矩陣。

2.1.4.1WQ單排序權向量與一致性檢驗

WQ是一致性矩陣，設nQ為WQ的特征值，ωQ為WQ的單排序權向量，根據一致性和正互反矩陣性質可得：

WQωQ=nQωQ

(7)

2.1.4.2Q1,K單排序權向量與一致性檢驗

矩陣Q1,K不是一致性矩陣，需將Q1,K的列向量進行量剛一化，由此可得：

(8)

設λQ1,K為Q1,K對應的最大特征值，對Q1,K進行一致性檢驗，則有：

(9)

Q1,KωQ1,K=λQ1,KωQ1,K

(10)

(11)

計算可得IC=0.006 7。查表1可得，n=4時，IR=0.90。將IC、IR代入式(6)，可得RC=0.007 4。由于計算所得RC小于0.1，矩陣Q1,K通過一致性檢驗。

2.1.4.3Q2,K單排序權向量與一致性檢驗

同理，設ωQ2,KQ1,K對應的最大特征值，將矩陣Q2,K列向量量綱一化, 按行進行量綱一化后，可得ωQ2,K=[0.027 0.095 0.047 0.013 7 0.310 0.074 0.310]T。

對Q2,K做一致性檢驗，可得RC=0.015<0.100，矩陣Q2,K通過一致性檢驗。

2.1.5 層次總排序權重及其一致性檢驗

層次總排序權重是指計算某一層次所有因素對于總目標相對重要性的權值。設指標層K的第x個因子kx對于總目標的權值為wkx,Q，其計算式為：

(12)

式中：

wQ,l——指標層Q中第l個元素對總目標的單排序權值；

wKp,Ql——指標層K層中第p個元素對指標層Q中第l個元素的單排序權值；

m——自然數序列。

由式(12)可得層次總排序權重如表2所示。

表2 層次總排序權重Tab.2 Calculation result of the total ranking weight wKp,Ql of hierarchy

層次總排序權重的一致性檢驗方法為：設wa為指標層Q第y個元素qy對總目標的單排序權值,設指標層K第i個因子kx對qy的層次一致性指標為ICq，隨機一致性為IRq，則層次總排序的一致性比率RC,z為：

(13)

當RC,z<0.1時，認為層次總排序通過一致性檢驗。根據式(13)，可得RC,z=0.023 6，由此可認為層次總排序通過一致性檢驗。

綜上，指標層Q的層次總排序權重wQ=[0.031 1 0.102 5 0.041 8 0.121 8 0.346 1 0.081 1 0.275 6]T。

2.2 綜合權值計算

設邊a的權值為w(ni,nj)，P為影響因子的當量矩陣，則其計算式為：

w(ni,nj)=Pω

(14)

3 Dijkstra算法的計算步驟

大部分的位置服務系統都采用Dijkstra算法作為路徑規劃算法的基礎。該算法分為以下7個步驟。

步驟一：初始化。為頂點集N中的所有頂點g生成兩個屬性：d(g)和p(g)。其中：d(g)表示為從起點到g點的最短距離值；p(g)表示g點的父節點。若該頂點為起點，則此時的d(g)=0，p(g)等于起點本身。

步驟二：生成1個空集S，用于存放所有已求出的到起點最短距離的節點。

步驟三：生成1個集合T，將頂點集中的所有節點都放到T集合中。

步驟四：從T集合中找出d(g)最小值對應的節點U，將U作為當前的選中節點，將其從T中移出后，移入到S集合中。

步驟五：判斷U是不是目的地。如果U是目的地，則算法結束；如果不是，則繼續進行步驟六。

步驟六：令d(V)表示從起點到V點的最短距離值，d(U)表示從起點到U點的最短距離值，p(V)表示V點的父節點，w(U,V)表示連接U、V兩個節點之間的權值。計算所有節點U指向的節點V的最短距離值。若d(V)>d(U)+w(U,V)，則d(V)=d(U)+w(U,V)，p(V)=U。

步驟七：本輪計算結束。返回步驟四，開始下一輪的計算。

4 仿真分析

本文對視障乘客在地鐵站內的通行能力影響因素進行分析，得到各邊的權值后，基于Dijkstra算法，將各邊的權值由距離變為本文所求得的綜合權值，進而得到相應的最優路徑。在地鐵站模型基礎上得到的站臺層部分路徑規劃結果如圖2所示。從圖2可看出，相對于最短路算法，綜合了路線距離和乘客安全性所得到的通行路徑更加符合視障乘客的行走習慣。

圖2 路徑規劃仿真結果Fig.2 Simulation results of path planning

5 結語

本文首先分析了在地鐵站內影響視障乘客通行能力的因素，并給出各因素的當量表達。在分析視障乘客通行影響因素的基礎上，提出了一種基于層次分析法的多目標決策方法，該方法綜合了路徑距離和乘客安全性兩個指標，得到了拓撲模型各個邊的權值。利用基于綜合權值的Dijkstra算法對最優路徑進行了驗算，結果證明，該方法更適用于視力障礙人群。