面向視力障礙乘客的地鐵站內(nèi)路徑規(guī)劃算法研究*

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

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

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

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

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

1.1 視障乘客通行影響因素

根據(jù)調(diào)查，影響視障乘客在地鐵站內(nèi)通行的因素如下：

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

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

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

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

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

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

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

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

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

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

設(shè)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邊的端點均不是終點，則此樓扶梯或垂直電梯為站臺層和站廳層的連接點，為了避免站臺層和站廳層對樓扶梯和電梯的重復計算，此時的當量應(yīng)減半，即k5=5，k6=2。

1.2.4 不規(guī)則地形和障礙物的當量表示

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

(1)

式中：

m——邊a中不規(guī)則地形和障礙物的總個數(shù)；

rp——第p個對象的危險指數(shù)。

2 多目標決策

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

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

2.1 層次分析法

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

2.1.1 確定指標

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

2.1.2 建立層次結(jié)構(gòu)模型

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

圖1 層次結(jié)構(gòu)模型Fig.1 Hierarchical structure model

2.1.3 構(gòu)造判斷矩陣

根據(jù)層次結(jié)構(gòu)模型，構(gòu)建目標層、指標層2個層次的判斷矩陣。判斷矩陣的值通過兩兩互比來設(shè)置。針對路徑的總加權(quán)目標W，構(gòu)造出目標層的判斷矩陣WQ：

(2)

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

(3)

(4)

2.1.4 計算單排序權(quán)向量并做一致性檢驗

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

(5)

式中：

λmax——對應(yīng)于判斷矩陣的最大特征根；

n——判斷矩陣的階數(shù)。

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

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

表1 不同階數(shù)對應(yīng)的IR值Tab.1 IR values corresponding to different orders

定義一致性比率RC為:

RC=IC/IR

(6)

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

2.1.4.1WQ單排序權(quán)向量與一致性檢驗

WQ是一致性矩陣，設(shè)nQ為WQ的特征值，ωQ為WQ的單排序權(quán)向量，根據(jù)一致性和正互反矩陣性質(zhì)可得：

WQωQ=nQωQ

(7)

2.1.4.2Q1,K單排序權(quán)向量與一致性檢驗

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

(8)

設(shè)λQ1,K為Q1,K對應(yīng)的最大特征值，對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單排序權(quán)向量與一致性檢驗

同理，設(shè)ωQ2,KQ1,K對應(yīng)的最大特征值，將矩陣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 層次總排序權(quán)重及其一致性檢驗

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

(12)

式中：

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

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

m——自然數(shù)序列。

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

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

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

(13)

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

綜上，指標層Q的層次總排序權(quán)重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 綜合權(quán)值計算

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

w(ni,nj)=Pω

(14)

3 Dijkstra算法的計算步驟

大部分的位置服務(wù)系統(tǒng)都采用Dijkstra算法作為路徑規(guī)劃算法的基礎(chǔ)。該算法分為以下7個步驟。

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

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

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

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

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

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

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

4 仿真分析

本文對視障乘客在地鐵站內(nèi)的通行能力影響因素進行分析，得到各邊的權(quán)值后，基于Dijkstra算法，將各邊的權(quán)值由距離變?yōu)楸疚乃蟮玫木C合權(quán)值，進而得到相應(yīng)的最優(yōu)路徑。在地鐵站模型基礎(chǔ)上得到的站臺層部分路徑規(guī)劃結(jié)果如圖2所示。從圖2可看出，相對于最短路算法，綜合了路線距離和乘客安全性所得到的通行路徑更加符合視障乘客的行走習慣。

圖2 路徑規(guī)劃仿真結(jié)果Fig.2 Simulation results of path planning

5 結(jié)語

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