基于多目标点A*算法的停车场车位路径引导系统设计

肖 玮，张 磊，邱泽华，钟 勇，张铁楠

(1.陆军勤务学院军事物流系，重庆 401311； 2.92356部队，天津 300450； 3.四川省通信产业服务有限公司雅安市分公司,四川 雅安 625000； 4.海军大连舰艇学院服务保障中心社会化保障室，辽宁 大连 116001)

0 引 言

目前我国成为了世界第三大汽车生产国和第二大汽车消费国。据公安部交通管理局统计，截至2019年3月底，全国机动车保有量达3.3亿辆，总量及增量均居世界第一。随之产生的停车难问题已成为城市交通管理亟需解决的一个主要问题[1-2]。目前，以场外引导为主的智能交通系统ITS[3-4]能够为用户显示停车场的位置、价格等，但因缺乏车位引导，难以准确掌握停车场内车位空闲状态，更不能快速帮助用户精准寻找到空闲车位。用户停车时往往只凭直觉与经验在停车场里瞎转，靠肉眼左顾右盼人工观察寻找车位，不仅费力费时，还存在一定安全隐患。据物联网公司Inrix2017年报告，寻找停车位给美国、英国和德国的司机带来了巨大的经济负担，估计这些国家每年的成本分别为727亿美元、233亿英镑和404亿欧元。以纽约、伦敦、法兰克福为例，这些地方的司机平均每年花费107 h(纽约)、67 h(伦敦)和65 h(法兰克福)的时间来搜索停车位[5]。为此，场内停车引导(辅助)系统应运而生[5-17]。文献[5-17]介绍的智能停车引导系统，依托物联网、云平台等虽然能准确实现停车场场内停车引导，但由于需要对现有停车场加装感应线圈、超声波、地磁、红外线、RFID、视觉文献[18-20]等传感器来监测车位空余情况，需要租用(云)服务器来储存、处理信息，存在系统复杂、成本高、工程量大等现实问题。因此，场内停车引导系统基本停留在理论研究阶段，较少实际应用，用户找停车位难的问题仍广泛存在。为此，本文设计一种基于现有停车场基础设施，能够以低成本、小工程量实现停车场车位引导，利于推广应用。

1 系统总体设计

1.1 系统总体框架

依据经济适用原则，本文设计的停车场车位引导系统由出入口控制模块、车位状态监控模块、路径引导模块和信息处理中心这4个部分构成，系统结构如图1所示。出入口控制模块、车位状态监控模块与信息处理中心基于停车场现有硬件基础设施，通过有线方式通信；为减小系统施工量，路径引导模块与信息处理中心通过无线方式通信。

图1 系统结构框图

1.2 模块功能设计

出入口控制模块的功能是拍摄车牌、显示车牌识别结果、场内剩余车位数、道闸升降。可依托现有停车场出入口的控制设施实现，如摄像机、电子显示屏、语言播报器、道闸等。

车位状态监控模块的功能是车位空闲情况监测与传输。可借助停车场已有的摄像机及其信息传输线路，利用图像处理及模式识别技术[18-19,21]实现。

路径引导模块的功能是完成用户从停车场入口到目标车位的路径引导。为便于工程实现，硬件设施由安装在场内各路口的若干无线通信装置、电子指示牌和语音播报器组成。无线通信器可根据停车场大小，选用对应的无线通信方式(如Wifi、Zigbee、WLAN、NB-IoT、LoRa等方式)接收信息处理中心发来的路径引导信息；电子指示牌和语音播报器则将接收到的路径引导信息通过文字和语音发布给用户，引导用户达到目标停车位。对有条件接入互联网或移动通信网络的新建停车场，可利用手机APP等方式进行联网信息播报。

信息处理中心是本系统的信息枢纽，负责整个系统的信息处理，主要包括以下功能：

1)停车场信息数字化。停车场信息数字化的目的是用一个二维数组表示、储存整个停车场，为后续车位引导奠定基础。具体方式是基于停车场内道路和车位设计特点，把停车场按平面划分为若干车位大小的像素，每个车位为一个独立像素，并按一定顺序编号。像素中如包括交叉路口、障碍物、拐弯点，通过设置不同的权重来区分。

2)车位状态信息数字化。将车位状态监控模块监测到的车位状态信息在停车场二维数组的对应车位中标识出来。本系统中，空闲车位标识符设置为0，占用车位标识符设置为1。

3)车牌识别及费用计算。对出入口控制模块拍摄到的车牌图像进行识别，按需控制升降道闸，依据车牌识别结果记录停车时长和计算、收取停车费。

4)车位路径规划。利用后文设计的多目标点A*车位算法完成从入口到目标车位的路径规划。本系统主要设置3种常用模式：最近车位路径规划、步行最少路径规划、连续空余车位路径规划。默认情况是最近车位路径规划。并将车位路径规划信息无线传输给路径引导模块。

信息处理中心除需加装无线通信装置外，基本可以依托现有多数停车场的硬件设施，仅需对其相关软件进行升级。

由于本系统基于现有停车场的硬件基础设施，因此本系统具有成本低、易于安装、维护费用低等特点。

假设停车场内有空余车位的情况下，图2给出了系统完成一次车位路径引导的工作流程。

2 多目标点A*路径规划算法

路径规划是停车场引导系统的核心功能，即引导用户到达目标空余车位的最优路径规划。A*算法是一种在静态路网求唯一起点和目标点之间最短路径的搜索方法，具有速度快、占用资源少、稳定性强的特点[21-22]。当停车场内存在唯一空余车位时，可直接选用A*算法进行车位路径规划。但更多的实际情况是停车场内存在多个随机分布的空余车位，为此本文设计了一种多目标点的A*路径规划算法。

图2 车位路径引导工作流程

2.1 算法原理

多目标点A*路径规划算法的基本思想是：首先设计规则进行目标唯一化处理，从多个随机分布的目标点中遴选出一个最优目标点，然后利用A*算法进行最优目标点和起点间的最短路径规划。具体到本系统即是从多个随机分布的空余车位中，选取距离起点最近的空余车位为最优目标点，再利用A*算法进行最短路径规划。多目标点的A*车位路径规划算法由信息处理中心通过软件实现，具体方法如下：

针对停车场内随机分布的空余车位，按式(1)进行目标唯一化处理，找到距离起点最近的最优目标点。鉴于停车场的行车规则，此处的“距离”指的是“曼哈顿距离”[23-24]。起点根据需要可设置为停车场入口或出口。当系统处于最近车位路径规划和连续空余车位路径规划模式时，起点设置为停车场入口。当系统处于步行最少路径规划模式时，起点设置为停车场出口。

Si=xi·Wxi+yi·Wyi

(1)

其中，Si表示第i个车位距离起点的曼哈顿距离；xi和yi分别表示第i个车位的横纵坐标，经初始停车场信息数字化处理后，均为整数；Wx和Wy分别表示x和y这2个方向的道路权重，一般设置为1。在实际应用中，可根据停车场内实际路况，如拥堵、工程施工进行灵活设置。

目标唯一化处理的示意图如图3所示。车位i、车位j、…、车位z是停车场内随机分布的n(n≥2)个空余车位。按式(1)计算这n个空余车位的曼哈顿距离，令So=min (Si,Sj,…,Sz)，So对应的空余车位o即是距离起点最近的最优目标点。

当停车场内仅存在唯一空闲车位时，可跳过此步，直接进入最短路径规划。

图3 目标唯一化处理示意图

2.2 最短路径规划

Step1按目标唯一化处理所述步骤确定车位路径规划的起点A和最优目标点O。

Step2建立Open和Close这2个列表。Open列表用于记录所有被考虑来寻找最短路径的像素块；Close列表用于记录不会再被考虑的像素块。

Step3首先在Close列表中添加起点A。然后，再把起点A的所有相邻像素块添加到Open列表中。

Step4根据公式(2)计算起点A的所有相邻像素的路径增量F。其中G表示从起点A到当前像素需要移动的像素总数；G会随着距离起点A远近线性变化。H表示从当前像素到最优目标点O需要移动的水平和垂直的像素总数，是略去了障碍物的数量。基于停车场的行车规则，G和H表示的均是曼哈顿距离，不考虑对角线移动的情况。所以，从起点A到其相邻像素块需要移动的像素总数均为1。

F=G+H

(2)

Step5选择F值最小的像素块，把它添加到Close列表中，然后再按公式(2)计算它的相邻像素的F值。

Step6重复Step4，直到把最优目标点O添加到Close列表中。

Step7从最优目标点O开始，一步步返回到起点A即构成起点A和最优目标点O的最短路径。至此，路径规划完毕。

3 系统验证

为验证系统的有效性，以某小区停车场为例，基于C#语言，利用Microsoft Visual Studio 2015平台对基于多目标点A*算法的车位路径引导系统进行模拟仿真。在停车场信息数字化后，为贴近停车场实际情况，每个车位权重设置为1，交叉路口像素、拐弯像素的权重设置为1.5。主要验证：最近车位路径规划、步行最少路径规划和连续空余车位路径规划这3种常用模式。为验证多目标点A*路径规划算法的性能，还将其与Dijkstra算法[25]和Floyd算法[26]进行了对比验证。模拟系统界面如图4～图6所示。图中每个长方格表示一个车位，格内的数字表示车位号。空余车位由随机算法生成，用灰色方格表示。起点即停车场的出口或入口，目标车位用点状方格表示。

3.1 最近车位路径规划模式

最近车位规划即完成从停车场入口到最近空余车位的路径规划。模拟系统界面如图4所示，通过点击右侧“最近车位”按键进入“最近车位规划”模式。为体现普适性，生成了多个随机分布的空余车位。按键后，系统后台运用前文设计的多目标点A*路径规划算法进行目标唯一化处理，首先在众多空余车位中确定最优目标点。由于选择的是最近车位规划模式，所以系统选取的最优目标点是距离入口最近的空余车位，本示例是车位165号。然后，运用路径规划算法为用户规划从起点到最优目标点的最短路径，即行车路线。模拟系统中用箭头指示。

由图4所示的运行效果可知，在最近车位规划模式下，本系统能够在众多空余车位中为用户寻找到距离入口最近的车位，并准确规划入口到最优目标点的最短行车路线。

图4 最近车位路径规划模式示意图

Dijkstra算法的特点是以起点为中心向外层层扩展，直到扩展到终点为止。当目标车位距离起点越远时，算法执行效率越低。Floyd算法的核心思想是如果任意2点a和b经过m1，m2,…,mN共N(N≥1)个点中转后，当L(a,m1)+…+L(mN-1,mN)+L(mN,b)

3.2 步行最少路径规划模式

当停车场出入口相同时，该模式同最近车位路径规划模式。当出入口不同时，步行最少导航模式意味着距离停车场出口最近，多目标点A*路径规划算法中的起点应设置为出口。该模式模拟系统界面如图5所示，通过点击右侧“步行最少”按键进入“步行最少路径规划”模式。系统首先初始化路径规划起点为出口，然后运用前文设计的多目标点A*路径规划算法进行目标唯一化处理，在随机生成的8个空余车位中遴选距离出口最近的177号车位为最优目标车位。然后，多目标点A*路径规划算法为用户规划从停车场出口到最优目标车位的最短路径，图中用箭头标识，即车辆从入口驶入停车场后，直接右转直行，经路径引导模块提示左转后，直行即到177号车位将车辆停入，而后步行离开停车场。

由图5所示运行效果可知，在步行最少路径规划模式下，本系统能够在众多空余车位中快速为用户寻找到距离出口最近的车位，并准确规划出口到最优目标点的最短行车路线。在步行最少路径规划模式下，即将最近车位路径规划模式中的起点由停车场入口替换成出口。因此，Dijkstra算法和Floyd算法仍存在算法复杂度大、实时性较差的问题。

3.3 连续空余车位路径规划模式

连续空余车位路径规划模式是针对泊车技术欠佳的用户设置的，为了让用户有足够的空间泊车，因此连续空余车位路径规划模式选取最优目标点的原则是，距离入口最近且相邻车位均是空余车位的空余车位。连续空余车位路径规划模式的系统界面如图6所示，随机生成50个空余车位。其中，连续空余车位共有7处：连续4车空余1处、连续3车空余1处、连续2车空余5处。通过点击右侧“连续空车位”按键进入“连续空余车位路径规划”模式。系统首先初始化路径规划起点为入口，然后运用前文设计的多目标点A*路径规划算法进行目标唯一化处理。按先前设置的规划原则，本示例选择有连续4个空余车位中的158号为最优目标点；然后，运用多目标点A*路径规划算法为用户规划从停车场入口到最优目标车位的最短路径，图中用白色箭头标识。

图5 步行最少路径规划示意图

图6 连续空余车位路径规划示意图

由图6所示运行效果可知，连续空余车位路径规划模式下，本系统能够在众多空余车位中为用户寻找到最宽的泊车空间，并准确规划出口到最优目标点的最短行车路线。面对多个空余车位时，Dijkstra算法或Floyd算法只能逐一计算停车场入口到每个空余车位的距离，但并无机制确保找到连续空余车位。因此，基于Dijkstra算法或Floyd算法不能完成连续空余车位路径规划模块的路径规划任务。

4 结束语

本文设计了一种基于多目标点A*算法的停车场车位路径引导系统。该系统由出入口控制模块、车位状态监控模块、路径引导模块和信息处理中心4个部分构成，能最大程度地基于现有停车场基础设施进行扩展，具有工程量小、成本低的特点。设计的多目标点A*车位路径规划算法能够根据用户的不同需求，在多个潜在目标点中遴选出一个最优目标点，并完成最优路径规划。最后，以某小区停车场为例，利用Microsoft Visual Studio 2015平台和C#语言对本系统的可行性和有效性进行了模拟仿真，重点模拟运行了最近车位路径规划、步行最少路径规划、连续空余车位路径规划这3种常见模式。为验证多目标点A*路径规划算法的性能，还将其与Dijkstra算法、Floyd算法等常用路径引导算法进行了对比验证。理论分析与运行结果表明，本文设计的基于多目标点A*算法的停车场车位路径引导系统能够快速按照用户的需求为用户规划到最适合的车位位置，极大地降低了停放车辆时的盲目和费时费力问题，保证了停车效率，降低了危险性，具有工程可行性。基于Dijkstra算法、Floyd算法的路径规划虽然在最近车位路径规划模式和步行最少路径规划模式下能完成规划任务，但算法复杂度大于多目标点A*算法。同时，上述2种方法并不能完成连续空余车位路径规划模式下的路径规划。