基于GIS与约束条件下的最优路径规划研究

王美玲， 潘允辉

(北京理工大学 自动化学院， 北京 100081)



基于GIS与约束条件下的最优路径规划研究

王美玲， 潘允辉

(北京理工大学 自动化学院， 北京 100081)

根据无人地面车辆自主导航的需求，提出一种给定任务点的约束条件下的最优路径实现方法. 首先基于地理信息系统(GIS)平台构建为车辆行驶提供先验信息的GIS数据库，并设计研究基于计算几何的路段匹配算法，同时结合A*算法进行全局路径规划. 然后根据无人地面车辆的运动特性和对路口识别的需求提出了新的路口模型，同时为保证无人地面车辆行驶轨迹的平滑性和对路口识别的精确性，对路口轨迹和U-turn轨迹进行了算法设计. 最后提出了动态重规划的行驶策略. 实际跑车实验证明了该设计算法的有效性.

路径规划；GIS；路口模型；路段匹配算法；动态重规划

无人地面车辆是未来智能交通系统与未来作战系统的重要组成，如何规划出可行驶的最优路径是无人地面车辆的核心技术之一. 路径规划为两点之间提供一条可行并且最优(或次优)的路径，这条可行路径通常会考虑路径的长度、行驶中的避障以及燃油消耗等因素[1-2].

目前基础性的路径规划研究主要针对全局路径规划和局部路径规划，然而路径规划时经常需要给定途经点，这样具有约束条件下进行最优路径规划同样是无人地面车辆行驶的重要应用.

SuperMap GIS是一款大型的地理信息系统软件平台，其网络编辑和分析功能既为路径规划算法提供所需的网络数据集， 同时也为路径规划算法的设计、实现和优化带来方便[3].

本文以无人地面车辆为载体，通过SuperMap平台构建GIS数据库，为无人地面车辆的安全快速行驶提供所需的先验信息和引导数据，结合约束条件和路口模型，利用道路匹配算法和路径生成算法设计一条从起点出发，经给定途径点，到达目标点的最优行驶路径.

1 GIS数据库的构建

通过分析无人地面车辆自主行驶的特点，根据对道路和环境等先验信息的应用需求，基于SuperMap平台，本文构建适用于无人地面车辆应用的GIS数据库，其组成框图如图1所示.

由图1可知，构建的GIS数据库主要由4部分组成：

① SuperMap平台. 此平台用于地图数据存储与编辑.

② 参照底图. 选取分辨率精度为0.3 m的卫星地图作为底图输入，作为绘制“道路网络”的参照底图.

③ 网络数据集. 由点数据集和线数据集构成. 点数据集提供道路网络中不同类型的节点，如十字路口点、交叉口入点、交叉口出点、车辆转向点等. 线数据集提供道路网络中不同类型的路段，这里的路段是指两个节点之间具有完全相同道路属性的一段道路. 此部分为无人地面车辆的路径规划提供基础数据构架.

④ 先验信息. 由道路属性、节点属性和交通信息构成. 道路属性主要包括道路ID号、长度、宽度、车道线数量、是否可以并线、顺行逆行方向以及变道信息等. 节点属性主要包括起点、终点、路口点、交叉口的入点和出点、立交桥的入点和出点、小区及学校的入点和出点、U-turn点、拐弯点、停车点以及节点的ID号. 交通信息主要包括各类交通标识、交通管制区域、交通灯位置和限速区域.

2 约束条件下的路径规划算法

路径规划算法主要由3部分组成：①基于计算几何的路段匹配算法；②关键点序列的产生算法；③A*算法.

2.1 基于计算几何的路段匹配算法

为了便于量测导航距离和导航时间，首先需要将任务点的大地坐标转换为WGS84-UTM投影坐标，然后利用下述基于计算几何的路段匹配算法完成各点的路段匹配.

假设正在匹配的任务点为P，构造一个以P为圆心，半径可调(半径越小，搜索时间越短)的圆形候选区域. 为了提高候选路段的置信度，同时方便后续算法的计算，本文选择一个以P为中心，以100边形模拟半径为200 m的圆的多边形作为候选区域. 利用垂直投影方式遍历候选区域内的所有路段，通过队列排序，输出点P匹配的路段信息.

路段匹配算法流程框图如图2所示.

在求解点P到当前候选路段的最短距离时，存在以下两种情况：

① 所作垂直投影点的坐标落在候选路段上. 此时直接取点P到候选路段的距离为最短距离；

② 所作垂直投影点的坐标落在候选路段外. 此时取点P到候选路段较近端点的距离为最短距离.

利用路段匹配算法找出道路网络中所有任务点对应的匹配路段，存储其相应信息.

2.2 关键点序列的产生算法

在规划出最短路径之前，需要先获得一串由所经路段的起点或终点组成的节点序列，本文称之为关键点序列，其算法步骤如下：

① 判断任务点的状态属性，若为起点或者终点，直接将此任务点加入到关键点序列中；若为途经点，则进行步骤2；

② 分别计算当前任务点与其匹配路段起点和终点的距离，若前者距离大于后者距离，则将该任务点的匹配路段终点视为候选关键点；反之，则将该任务点的匹配路段起点视为候选关键点；

③ 将步骤2中提取的候选关键点与当前关键点序列中最后加入的关键点作比较，若不为同一点，则将此候选关键点加入关键点序列中；若是同一点，则忽略此点，预防序列中存在重复关键点；

④ 对所有任务点重复以上步骤，生成关键点序列.

由于A*算法具有搜索深度较小，搜索的节点数少，占用的存储空间少等特点，因此本文基于此算法来完成整个行驶路径的全局规划.

3 路径生成

3.1 路口行车轨迹设计

随着城市建设的发展，城市道路日趋复杂，原有的交通电子地图的中心线模型已经不能表达城市道路网和行车规则[4-6]，为了使规划的路径能够更好地适用于无人地面车辆的行驶，本文提出一种带有路口距离属性的双线路口模型，如图3所示. 在道路网络中，通过线数据集只能计算当前点与路段节点的距离，在图4中，若车辆行驶方向为A到B，以传统道路模型算法，则当车辆行驶到点O1时才表示进入路口，在这种情况下相当于将路口滞后了，对于交通灯识别、行人避障等会产生很大影响. 因此本文提出利用GIS数据库提前存储先验信息，在计算路口距离时考虑斑马线外沿A点到路口节点O1的距离(若左转，则考虑图5中点A到路口节点O1的距离)，使得无人地面车辆在行驶到点A时即进入路口模式(此时距离为负)，直至行驶到下一个斑马线的外沿时距离值恢复为正，负距离值表示无人地面车辆行驶在路口内. 此模型使得最终生成的路径能够满足3个要求：一是符合并能表达现代城市道路的行车规则；二是保证无人地面车辆路口识别的准确性；三是生成的导航路线符合无人地面车辆的运动学特性[7-8].

从上述模型与传统道路模型的对比可以观察出上述模型为无人地面车辆提供的导航行驶轨迹不再是一个直角弯，而是由转弯半径限制出的一个圆弧，这对于无人地面车辆的控制有着十分重要的意义，提高了无人地面车辆行驶的流畅性；同时利用斑马线与路口中心点的距离属性将“路口内”和“路口外”两种情况区分得更加明确，由此属性经算法计算后得到的路口轨迹既能保证无人地面车辆对路口识别的精确性，同时又将转弯半径增大，更利于车辆的运动. 需要说明的是模型中只表示了双向路线，多条车道时需要根据GIS数据库存储的车道数量、车道宽度等属性，结合顶层决策命令和视觉感知信息共同确定的.

模型的算法实现如下：

以图4为例，假设前一个路口直行通过，当前路口拐弯(以右转为例). 设路口中心点O2坐标为(X，Y)；无人地面车辆所在当前道路R0和将要驶入的目标道路Ri；路口所有道路的方向角为{θi，i=1，2，…，n}；车辆最小转弯半径Rmin_turn；道路宽度属性Lwidth；斑马线中点至路口中心点的距离属性Dright(直行和右转，此时对应的路口中心节点为O2)和Dleft(左转，此时对应的路口中心节点为O1，如图4所示).

① 读取GIS数据库中点B和点C所在道路的道路宽度，取其小者，表示为Lwidth，若此时通过路口状态为右转则取Lwidth=0.75Lwidth(右转半径小于左转半径)；

② 由点O2、B和C分别确定点B和C所在道路方向，结合步骤1求得的Lwidth，确定在BO2连线上的点S1坐标和在CO2连线上的点S2坐标；

③ 由点S1、S2和其切线方向(即两点各自所在的道路方向)确定圆心点O坐标和半径大小R；

④ 根据无人地面车辆运动模型特点，转弯时存在最小转弯半径，用Rmin_turn来表示，若Rmin_turn

⑤ 选取合适的步长(即以多大的间隔生成路点)求取点B和点S1之间的路点坐标；

⑥ 读取GIS数据库中CO2的距离值，求取点C坐标，再以直线轨迹方式求取点S2和点C之间的路点坐标.

图5所示为连续两个路口转弯的情况，前一个路口左转，第二个路口右转.

对于不规则的路口，其构造的“道路网络”路线多、结点多，相对于正常路口模型较复杂，但是在路径生成算法中原理相同. 如图6所示为不规则路口中的“道路网络”，图7所示为所有可能行驶的路线.

3.2 U-turn轨迹设计

若在U-turn处的路径生成模式与路口路径的生成模式相同，则相当于在U-turn处将两段圆弧拼接在一起，在拼接处往往会出现“尖角”，如图8所示.

这样的“尖角”会影响无人地面车辆的运动控制，也会影响车辆行驶的平滑性，因此本文提出以Hermite插值的方式来生成U-turn轨迹.

Hermite插值方法能保证节点处的函数值相等，也就保证了函数的连续性，与其它插值方式相比，它又结合了函数的导数值，能够保证节点处的导数值相等，提高了插值的精度和光滑度.

以生成路口路径的方式找到U-turn的入弯点和出弯点，结合横向路段的中点，以此3点进行Hermite插值，生成的U-turn轨迹如图9所示.

在整个路径生成过程中，其耗费时间主要与全局搜索匹配到的路段个数有关，匹配到的路段数越多，则耗时越长，反之亦然. 由于本文的着重点并不是规划时间的长短，因此没有对此部分做太多的优化，匹配到的路段数与耗时比例大约为10∶1(s).

4 路径重规划

静态路径规划在行驶车辆遇到特殊情况的时候就失去了实际的引导意义，如前方道路阻断或是检测到前方道路存在禁行标志，此时就需要在线动态规划.

针对上述情况，本文提出如下在线重新规划设计流程(图10)：

5 实验验证

本文以江苏省常熟市福溪路部分道路网络为对象，通过读取任务点，得到从起点经途经点到达终点的最优路径.

其中，实验平台采用美国北极星全地形山地车作为车体底盘，经过对车体改装，实现按钮、油门、档位以及刹车的自动控制. 整个系统所包含感知设备主要有：3D激光雷达、2D激光雷达、毫米波雷达、全景摄像头、广角摄像头、长焦摄像头、编码器以及组合导航设备等. 组合导航设备采用SPAN-CPT，是一款集成GPS+INS的紧耦合组合导航定位系统.

表1所示为任务点的属性列表.

表1 任务点属性列表

其中属性1提供的属性中，0表示此点为起点，1表示此点为途经点，2表示此点为终点；属性2提供的属性中，1表示没有特殊属性，2表示此点前后一定距离内社会车辆较多，3表示此点前后一定距离内为限速区域，4表示此点前方为U-turn点，5表示此点处有交通标识.

图11所示为无人地面车辆行驶所选区域构建的道路网络.

图12所示为读取的任务点在道路网络中的位置. 图13为加入道路模型后的路径规划结果. 其中，红色路线表明前方是直行路段；绿色路线表明前方路口将进入左转；蓝色路线表明前方路口将进入右转. 图14为车辆右转和左转时的轨迹，U-turn如图9所示，可以看出，车辆在路口转弯的时候不再是直角弯，而是处理后的圆弧. 表2列举了规划出的路径中3个拐弯点的入点坐标、出点坐标和转弯半径，以及U-turn的入点和出点坐标.

属性点拐弯1拐弯2拐弯3U-turn入弯点/(°)出弯点/(°)120.77887120.7790831.5909031.59086120.78124120.7815131.5881531.58809120.78323120.7833731.5889631.58894120.77680120.7769031.5901731.59002半径/m15.33024318.5699649.504948

表3给出了每个任务点在道路网络中匹配到的道路的ID号，以及在保证不走重复路线的前提下，连续的两个任务点之间距离最短的3条可通行路线长度.

表3 匹配道路的ID号和路径长度

实验中无人地面车辆行驶的实际路线总长约2 358 m，路径规划时匹配到的路段数为53条，规划耗时约6.8 s，行驶最高时速40 km，行驶中涉及交通标识检测、交通灯识别、障碍物躲避、行人检测、侧方停车、终点停止线检测以及社会车辆跟随等任务，全程耗时约11 min，无人工干预，顺利通过所有任务点，行驶稳定平顺.

6 结 论

在给定任务点的约束条件下，本文提出方法首先将任务点的大地坐标转化为适用于路径规划的平面坐标，利用路段匹配算法获得关键点序列；基于提出的双线路口模型，结合GIS数据库提供的先验信息，设计出一条符合无人地面车辆运动特性的行驶轨迹，对车辆完成路口识别起到重要作用. 对U-turn轨迹进行特殊处理，以及对车辆进行动态重规划保障了无人地面车辆的自主行驶. 本文设计的最优路径实现方法已经应用于本实验的无人地面车辆中，并参加了国家自然基金委组织的中国智能车未来挑战赛以及总装备部组织的跨越险阻地面无人平台挑战赛.

由于实验场地和比赛环境中参杂的不稳定因素较少，如基本没有行人，社会车辆较少等，本文路径规划以路径长度为主要考虑因素，如何融合更多的影响因素，使得最终的行驶路径能够达到最短距离、最少时间、最少耗费是下一步研究内容.

[1] Wang Y， Wang S， Tan M， et al. Real-time dynamic Dubins-Helix method for 3-D trajectory smoothing[J]. IEEE Trans Control Syst Technol， 2015，23(2):730-736.

[2] Wang Y， Wang S， Tan M. Path generation of autonomous approach to a moving ship for unmanned vehicles[J]. IEEE Trans Ind Electron， 2015，23(2):730-736.

[3] 程林，王美玲，张毅.一种基于SuperMap GIS的改进Dijkstra算法[J].地球信息科学学报，2010，12(5):649-654.

Cheng Lin， Wang Meiling， Zhang Yi. An improved Dijkstra algorithm based on supermap GIS[J]. Journal of Geo-Information Science， 2010，12(5):649-654.(in Chinese)[4] 尤淑撑，严泰来.基于人工神经网络面插值的方法研究[J].测绘学报，2000，29(1):30-34.

You Shucheng，Yan Tailai. A study on artificial neural network based surface interpoliation[J]. Acta Geodaetica et Cartographica Sinica， 2000，29(1):30-34.(in Chinese)

[5] 王曦鸣.军用无人车的路径规划与仿真研究[D].北京：北京交通大学，2010.

Wang Ximing. The path planning and simulation research of military unmanned vehicle[D]. Beijing: Beijing Jiaotong University， 2010. (in Chinese)

[6] 王延亮，张玉娟.城市导航电子地图的道路模型[J].测绘与空间地理信息，2005，28(3)：62-64.

Wang Yanling， Zhang Yujuan. The road model of city navigation electronic map[J]. Geomatics and Spatial Information Technology，2005，28(3)：62-64.(in Chinese)

[7] 姜岩，赵熙俊，龚建伟，等.简单城市环境下地面无人驾驶系统的设计研究[J].机械工程学报，2012，48(20):103-112.

Jiang Yan， Zhao Xijun， Gong Jianwei， et al. System design of self-driving in simplified urban environments[J].Journal of Mechanical Engineering，2012，48(20):103-112.(in Chinese)

[8] 张浩杰，龚建伟，姜岩，等.基于变维度状态空间的增量启发式路径规划方法研究[J].自动化学报，2013，39(10):1602-1610.

Zhang Haojie， Gong Jianwei， Jiang Yan， et al.Research on incremental heuristic path planner with variable dimensional state space[J]. Acta Automatica Sinica， 2013，39(10):1602-1610. (in Chinese)

(责任编辑：李兵)

Research on Optimal Path Planning with Constraints Based on GIS

WANG Mei-ling， PAN Yun-hui

(School of Automation， Beijing Institute of Technology， Beijing 100081， China)

According to the requirements of unmanned ground vehicle(UGV) autonomous navigation， an implementation method was proposed for path optimization with given task points as constraints. Firstly， a geographic information system (GIS) database was built based on the GIS platform to provide priori information for UGV. And then a road-matching algorithm was designed based on the computational geometry. Simultaneously the static and dynamic path planning was conducted combining with A*algorithm. Secondly， a new crossroads model was proposed according to the movement characteristics of UGV and the demand in recognizing the intersection. An algorithmic design for the intersection tracks and U-turn tracks was conducted to smooth the UGV’s driving routes and to ensure the accuracy of intersection recognition. At last， a dynamic re-planning driving strategy was put forward. The validity of designed algorithm was verified by actual car experiments.

path planning; GIS; crossroads model; road-matching algorithm; dynamic re-planning

2015-04-13

国家自然科学基金资助项目(61173076)；国家自然科学基金重大研究计划培育资助项目(91120003)

王美玲(1970—)，女，教授，博士生导师，E-mail:wangml@bit.edu.cn.

潘允辉(1991—)，男，硕士生，E-mail:pyhforever@163.com.

TP 242.6; P 208

A

1001-0645(2016)08-0851-07

10.15918/j.tbit1001-0645.2016.08.014