李 胜 郑成龙 刘 源 孙 强 邢宗义

(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算法对最优路径进行了验算，结果证明，该方法更适用于视力障碍人群。