周云城 杨东晓 田 欢

（1. 华设设计集团股份有限公司，江苏 南京 210014；2. 江苏大学，江苏 镇江 212013；3. 清华大学苏州汽车研究院（相城），江苏 苏州 215134）

0 引言

随着智能化设备的发展，出现了各式各样的定位导航软件，定位导航技术获取方便，使用简单，为人们的出行带来了极大便利，智能化设备在大多数人的日常出行生活中已经变得不可或缺了[1]。然而当车辆驶入地下停车场等大面积的室内场所时，由于卫星信号受到建筑物的严重干扰，车辆通常难以接收到GPS/北斗信号进行定位，因此车辆已有的导航系统无法实现导航功能。尤其是当车辆位于大型的地下停车场时，由于停车场的空间较大，各区域场景相仿，标志物较少，不易分清方向，人们在寻找停车位以及寻车离场时往往会遇到一定困难。当停车场中的车流较多时，会在停车场内要安排一定的工作人员对车辆进行引导，但每个工作人员往往只负责某个固定区域，其视野有限且人员之间沟通不畅，停车场内的车流容易出现混乱的状况甚至导致拥堵，车主寻车离场基本上只能依靠自己完成，用户体验较差[2]。这样的车辆引导管理方式效率不高，停车位利用效率低，而且需要支出一定的人工费用，增加了停车场的运营成本。

1 数据处理与分析

该文对地下停车场的导航算法展开研究，与室内高精度定位技术组合在一起，可以在司机寻找车位以及寻车离场时为司机导航，减少了司机在寻车上消耗的时间，提升了车辆流通的效率，进而提高停车位的利用效率，在一定程度上可以帮助改善城市中“停车难”的状况。在利用导航算法对停车场环境进行路径规划时，首先要对停车场的平面图进行处理，对地图的障碍物部分与道路部分进行区分，可以用黑色对障碍物部分进行标识，用白色对道路进行标识，如图1、图2 所示。

图1 地下停车场平面图

图2 标识后的地下停车场地图

在完成标识后，便成功地区分了地下停车场环境中的障碍物与道路，但是由于导航算法程序并不能直接对处理后的图片进行运算处理，因此需要计算机对处理后的地图进行读取，并将其转换为可以直接进行运算的数据，由于停车场是以图片的形式进行环境输入，并且用颜色对障碍物、道路进行区分，因此可以用图片中各点的像素点灰度值作为存储形式进行存储。

程序载入地图的图片后，可以利用Python 常用的图像处理库Pillow 按照像素读取地图中该像素点的灰度值，并按顺序将其存储在1 个二维数组中，这样就成功地将地图数据以二维数组的形式存储下来，并且二维数组中某点的序号即代表该像素点的像素坐标。其中灰度值为0（黑色）的部分代表障碍物，灰度值为255（白色）的部分代表道路。

由于图片中并非任意点均满足白色部分灰度值为255、黑色部分灰度值为0 的条件，因此，灰度值可能会有细微的变动，为了明确地对障碍物、道路进行区分，可以进一步地对二维数组进行简化，对数组进行二值化处理，将数组中灰度值小于127 的部分标记为“#”，代表道路；将灰度值大于127 的部分标记为“.”，代表障碍物。

2 基于PRM 的导航算法

2.1 PRM 算法基本原理

PRM（Probabilistic Road Map）算法的基本思路是在地图中利用随机采样节点构造概率路径图[3]，在构造出的路径图中使用搜索算法进行检索，从而搜索出最短路径，PRM 算法有2 个基本阶段，即学习阶段和查询阶段。

2.1.1 学习阶段

学习阶段的主要任务在于构造出用于路径检索的概率路径图[4]。首先要对地图进行处理，用黑色对地图中的障碍物部分进行标识，用白色对道路部分进行标识。完成对地图的处理后，在地图上随机采样N个节点。完成随机采样后，由于采样的节点可能会位于障碍物内部，因此需要对各采样点进行检测，剔除其中与障碍物重叠的点。

当完成节点的碰撞检测后，用线段将剩余的节点连在一起，连线时需要保证各节点的连线不能与障碍物重叠，为了节省计算量，缩短路径检索时间，各节点只连接自己邻域范围内的点，不太远的点进行连接。当所有节点均完成连线后即成功完成了概率路径图的构造，如图3 所示。

图3 概率路径图

2.1.2 查询阶段

查询阶段的主要任务是在学习阶段完成的概率路径图中检索出从起始位置到达目标位置的最优路径[5]，其具体步骤如下：1）将起点与终点分别与其在概率路径图中与之距离最短的点进行连接，从而将2 个点添加至学习阶段构造出的路径图中。2）利用Dijkstra 搜索算法在完成连接的路径图中进行检索，选用距离作为优化指标，查询从起始位置到达目标位置的最短路径，如图4 所示。

图4 随机采样点取200 个规划出的路径

2.2 PRM 算法优化

由于在地下停车场环境中障碍物较多，因此在随机采样时大部分位于障碍物内部的采样节点都会被舍去，保留下的节点也会出现与障碍物距离过近的情况，这样可能会导致规划出的路径与障碍物距离过短，即出现“贴边”现象，并且由于各节点位置随机，各节点的连线通常与道路中心线不平行，路径规划效果较差，如果增加采样节点，则会导致运算时间大幅增长，而路径规划效果并不会出现明显提升，考虑到停车场中大部分道路结构较为简单，很少会有弯曲道路，因此可以将各路口中心点作为采样节点集，路径规划效果会有大幅提升，同时解算时间也会有所缩短。可以对优化前后的算法进行简单的对比实验，实验中将起点的像素坐标设为（305，380），终点的像素坐标设为（615，990），如图5 所示。

图5 优化PRM 算法规划出的路径

由表1 可以看出原始的PRM 算法在增加采样点数量及邻域距离后，虽然路径规划效果有所提升，但是路径解算耗费的时间大幅增长。这主要是因为增加采样点及邻域距离后，节点的连线数量会呈几何倍数增长，其中大部分为无效连线，算法检测连线是否穿越障碍物时耗费了大量资源。而采样点数量较少时，路径规划效果很差。需要进行大量实验，让采样点数量、邻域范围处于一个适中的区间，使规划效果与耗费时间之间达到一个合理的平衡。优化的PRM 算法利用检索出的节点，避免了对大量资源进行搜索的工作，在大幅节省解算时间的同时，取得了最好的路径规划效果。

表1 优化前后算法数据对比

同时考虑到地下停车场道路较为狭窄，车辆在道路上难以掉头，在初始时，车辆只能沿着车头方向向前行驶，因此需要对车辆的初始行驶方向进行限制，可以在学习阶段对路径图的生成过程进行修改，在节点集中对节点进行判断，删去与车辆位于同一道路上且处在车辆后方的节点，在构造路径图时，不会生成与车头方向相悖的路径。这样在后续的查询阶段中便不会搜索出与车头朝向相悖的路径，从而确定路径初始方向。

2.3 导航信息输出

当驾驶者利用导航软件进行导航时，软件在规划出路径的同时会结合车辆的定位对驾驶者进行导航信息提示。在实际应用中，导航信息中通常包括2 个信息：1）距离信息。车辆与下一路口间的距离。2） 方向信息。车辆在下一路口位置上应进行何种操作，例如直行、左转或是右转。

在进行坐标变换之后可以通过查询车辆定位以及下一路口位置简单算出导航信息所需要的距离，坐标变换时为了保证精度，路口中心点的坐标变换采用像素坐标与世界坐标一一对应的方式，而起点、终点的坐标则通过计算得出。方向信息的分析则略微复杂些，其本质在于折线段的拐向判断，判断的基本方法是求向量积，其基本原理如图6 所示。

在图6 所示的简单折线段中，要判断A点处的拐向，可以分别将A点两侧的线段视作向量P、Q，设P向量为（x1，y1），Q向量为（x2，y2），将P、Q的向量积记作I。

图6 简单折线段拐向判断

由向量积的性质可知，当I小于0 时，P在Q的逆时针方向，说明在A点处折线段向右拐，反之，当I大于0时，P位于Q的顺时针方向，A点处折线段拐向朝左，I等于0 时，P与Q同向，折线段变为直线段。

利用上述基本原理可对停车场地图中规划路径的方向信息进行分析，首先查询规划路径中经过的路口中心节点，将起点、路口节点以及终点按顺序连接在一起，将每条连线视作向量，并用像素坐标表示这些向量，求出任意相邻2 个向量的向量积并与0 进行比较，就可以得出路径在各路口的方向信息。

3 总结

在停车位供不应求的问题短时间内难以得到解决的大背景下，提高城市中已有停车位的利用效率是缓解“停车难”的一种有效手段，然而现有停车场的空间较大，且各区域场景相仿不易分清方向，从而在寻找停车位以及寻车离场时会存在一些困难。为此，该文在总结已有理论及技术的基础上，对面向地下停车场的路径规划问题进行研究，成功对地下停车场环境进行路径规划并给出导航信息，在提高停车位利用效率的同时，也为驾驶者在停车场中的寻找车位、寻车离场带来了便利。