1. 引言
截止2024年6月底，我国汽车保有量超3亿辆。汽车的保有量持续增加，导致了城市道路交通压力，对汽车的停、取带来了新的难题。目前汽车在停车场内的停、取通常是以用户个人的角度，选取一条对自己最佳的路线，没有路线指引，甚至在停车位资源匮乏情况下，造成长时间寻找不到车位，导致时间与空间的资源浪费。在停车场区域内目前还缺乏较好的相关软件或系统对用户的路线进行设计与规划[1]。
本项目在此背景之下，设计为用户在停车场区域规划路线的系统。基于道路网的路径，实时提供最优的行车路线，解决用户停车乱、停车难的痛点，有效地缩短了停车场进出车辆的时间，提高停车场利用率。本研究收集城市各个停车场实时停车信息，分析整合，综合考虑停车位及路程时间的因素，提供参考的停车场以及停车场内的最短路线，用以A*算法为基础的路径规划算法设计路线，为用户提供合理的停车场选择方案。
2. 智能停车场的定位
即通过GPS、惯导、激光雷达等传感器，获取车辆的位置和航向信息。
GPS (Global Position System)是一种基于卫星的无线电导航技术，这项技术的通用名称是GNSS (Global Navigation Satellite System)，即全球导航卫星系统，它通过向地球发送数据的方式，使手机等设备能够接收到。利用这些信息和几何原理，GPS可以计算设备在参照系中的位置，精度可达米级。GPS的关键原理是三边测量，即一种利用几何原理确定物体相对位置的数学方法。当我们已知卫星位置和卫星与接收设备之间的距离时我们可以利用此原理建立数学模型，从而确定接收设备的位置。
绝对定位是指通过GPS实现，采用双天线，通过卫星获得车辆在地球上的绝对位置和航向信息。相对定位是指根据车辆的初始位置，通过惯导、里程计等传感器获得加速度和角加速度信息，即可得到相对初始位置的当前位置信息。
针对本文的研究性质，需要获得用户的绝对位置，所以需要绝对定位，而相对定位在自动驾驶领域发挥了重要作用。
目前用于停车场的主要定位技术有无线Wi-Fi技术、RFID技术、UWB技术、蓝牙定位、红外定位和可见光定位等，它们各有优势、应用广泛[2]。
城市智能停车场路径规划系统首先就是要确定用户的位置，为之后进行路径规划奠定基础。
3. 路径规划算法
3.1. 城市路径规划
现代城市规模不断扩大，人口不断增加，车辆的持有率也在不断上升，然而城市的停车场却无法提供充足的停车位，这就会导致行驶者在未知停车场是否空余的情况下，进行大量的寻找，这些不必要的路程不仅会浪费行驶者的时间，也会对城市交通以及城市环境带来不好的影响。所以我们首先要解决的是如何以最短路径到达有冗余停车位的停车场。这就是在城市中的路径规划。
路径规划给行驶者提供一条最优的行驶路径，是最优控制、网络优化、人工智能、智能交通等领域的重要组成部分。这里指的是点到点的路径规划，即为根据行驶者的定位信息规划出一条到有冗余停车场的安全可靠的最短路径[3]。
路径规划算法根据理论的不同大体上可以分为智能算法、基于图搜索的算法、基于采样的算法等。智能算法的原理是对自然现象进行仿生，用比较低的成本解决不确定的复杂问题，但是此种方法需要大规模的训练，并且计算量很大，难以精确求解。图搜索法利用可视图方法对现实环境进行建模。并在此图中进行图搜索，目前应用最为广泛，比较常用的主要是Dijkstra算法、最佳优先搜索算法(BFS)、A*算法等。基于图搜索的算法通常运行在栅格地图上的，当栅格的分辨率越大时，算法的路径就会越优。基于采样的算法是一种融合了采样和图搜索的综合查询方法，先构建线路图再采样和碰撞检测建立完整的无向图，最后通过图搜索得到可行的路径[4]。此方法需要采样和路径规划比较复杂，为了便于研究，本文重点讨论基于图搜索的算法。
Dijkstra算法：
计算从一个节点到另一个节点的最短路径，将网络中的节点分成三部分：未标记节点、已标记节点和最短路径节点。算法工作过程中，现将起点作为最短路径节点，其余的都作为未标记节点，由起始点开始向邻近节点遍历，将起始点之外的相邻节点都标记为已标记节点，权值更新后，再从所有已标记节点中取得权值最小的节点作为新的起始节点，开始下一次遍历，重复以上步骤直到所有的节点都遍历完成，算法就完成了。在实际应用中，Dijkstra算法会耗费大量的内存空间和计算时间，许多改进的Dijkstra算法计算结果也不十分尽如人意[5]。
最佳优先搜索算法(BFS)：
此算法的逻辑是深度每增加一次，队列中所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的，它的目的就是求从一个起点走到终点的最短路径。由于BFS算法需是盲目搜索，以点带面的遍历节点，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止，所以空间复杂度较高[6]。
A*算法：
是一种启发式搜索方法，是静态路网中求解最短路径最有效的方法。该算法的特点是对于已知的两个起点和终点，通过引入一个已知的全局变量，对起始节点与终点距离进行估计，这个全局变量就是衡量最优路径上可行性的判断量，最大可能性地搜索目标节点。该算法的原理是从当前节点开始，每遇到一个新的节点，全部按照估计函数
计算出它的最佳估计函数值，选择估计函数值中最小
的节点作为当前节点，之后重复以上步骤继续搜索，直到找到最优路径。
估计函数的形式如式(1-1)所示：
(1-1)
把估计函数分成两个部分，一部分是当前路程代价
，指的是从起点出发走的距离。另一部分估计函数是预估代价
，它用来表示从当前位置到终点大概的距离，它并不是一个精确的数值，也不代表一定会走此距离，但是可以用这个预估的值来指导算法去优先搜索更有希望的路径。常用到的预估代价有欧拉距离，即为两点之间的直线距离，另一种是曼哈顿距离，即为两点在竖直方向上和水平方向上的距离总和。
A*算法具体实现步骤如下：
1) 建立两个表，第一个存放已经发现但是还没有被访问节点的表OPEN，第二个存放已访问过的节点的表CLOSED。计算得出节点估计函数值并存入OPEN表中。
2) 若OPEN表不是空，则将其中估计函数值F(n)最小的节点n取出，否则直接退出。
3) 如果当前节点是目标节点，则直接退出，表示已找到到达目标节点的最优路径。否则，进行下一步。
4) 从OPEN表中取出当前节点n并删除记录，把n存入CLOSED表中。
5) 遍历当前节点的所有子节点x，并计算它们的估价函数值F(x)。如果节点在OPEN表中，且估价函数值F(x)小于OPEN表里原来节点的估价函数值，则把节点n设为节点x的父节点，同时更新OPEN表中的估价函数值。若节点x在CLOSED表中，则继续向下遍历。若节点x即不在OPEN表中也不在CLOSED表中，则把节点n设为节点x的父节点，并计算节点x的估计函数值再一起存入OPEN表中。
6) 跳回步骤(4)继续执行，直到找到目标节点后退出程序。
A*算法流程图如图1所示：
Figure 1. A* algorithm flowchart
图1. A*算法流程图
综上可知，A*算法没有进行盲目的遍历，而是根据估计函数进行有选择的探索，这大大降低了运算时间和内存空间，和前两种算法相比较性能优越，所以我们选用A*算法作为路径规划的算法。
3.2. 停车场路径规划
当顺利找到有空余车位的停车场后，就需要快速找到停车场中的车位，大型停车场错综复杂，再加上停车高峰期，如果盲目寻找车位则会花费大量的时间。
在这里，依然可以使用上述停车场路径规划所应用的算法A*算法，根据停车场信息管理系统所收集的场内车辆的信息情况，在所有空余停车位中找到最近的停车位进行停车。具体实现过程如下，首先收集空余车位的位置信息，用A*算法规划出用户所在位置到各个空余车位的最短路径，再计算出各个最短路径的距离，最后将距离进行比较，找出最近的空余车位，系统根据所计算出的最短路径给用户进行导航。
3.3. 反向寻车
因为停车场一般建在地下或者室内，光线不充足，布局也比较雷同，身处其中常常容易迷失方向，用户在之后寻找自己的车时也有一定困难，耽误宝贵时间。所以反向寻车也十分必要进行路径规划。
具体实现方法和城市路径规划以及停车场路径规划的方法类似，根据系统指引的最短路径进行寻车即可。
4. 代码编写
由上文可知，最终选择A*算法作为本研究路径规划的算法。了解了A*算法的基本原理后，用python语言进行算法的代码编写。
Figure 2. A* algorithm code1
图2. A*算法代码1
如图2所示，A*算法代码的第一部分，首先我们定义一个Astar用来求解A*算法。其中先定义一个初始化函数，初始化了五个变量，分别是w区域宽度，h区域高度，s初始点坐标，g目的点坐标，wall障碍物，它是列表。之后构建一个全零矩阵，维度是w乘以h，再把s和g设置为1，障碍物设置为2。np.zeros_like函数能创建一个新数组，其形状和类型与给定数组相同，但是所有元素都被设置为0。
Figure 3. A* algorithm code2
图3. A*算法代码2
此部分的plot的作用是绘制图像，pcolor在Python中是用于绘制二维数组的伪色彩图的一个常用函数，它可以将二维数组中的数据映射到颜色，以形成一幅有趣的图像。edgecolor则是设置格子线的颜色，这里我们设置颜色为白色，其余属性保持默认值。最后的plt.show()则是将图形画出。具体代码如上图3所示。
Figure 4. A* algorithm code3
图4. A*算法代码3
在阐述具体算法实现部分之前，先确定两个重要基础函数，为算法实现做准备。第一个是H函数，它计算了当前遍历节点到终点的横纵坐标差的绝对值的和，即计算的是预估代价，也就是前文所说的H(n)。第二个是f函数，它的值为当前遍历节点的预估代价H与当前路程代价G的和。具体代码如上图4所示。
Figure 5. A* algorithm code4
图5. A*算法代码4
另外一个重要的前提函数是find_edge函数，它的作用是找到遍历的边界节点。
若closed数组非0，则执行下列代码：
np.array的作用是把列表转化为数组，这里把closed列表转化为数组。np.vstack能将数组在竖直方向上堆叠，将closed数组和wall数组在竖直方向上堆叠。若closed数组为0，则执行下列代码：实例化wall以便后续调用。
定义一个空列表res，进入for循环。range可以生成一个整数序列，创建一个整数列表，range(−1, 2)即为[−1, 0, 1]。通过对i和j的循环，可以将当前遍历节点周围的8个邻居节点循环一遍，为后续判断此邻居节点是否符合要求做铺垫。
np.all用于测试是否数组中所有元素都满足指定条件，若都满足则输出Ture，否则输出False。np.any用于测试是否存在至少一个元素满足指定条件，若存在至少一个元素满足则输出Ture，否则输出False。axis = 1的含义是按列的方向执行操作。这部分代码的目的是求出当前遍历节点的周围8个邻居节点是否和障碍物重合，若重合则此节点不进行考虑；接着判断是否存在并且在区域范围内，若满足则将此节点添加到res列表中，若不满足则此节点也不考虑。具体代码如上图5所示。
Figure 6. A* algorithm code5
图6. A*算法代码5
来到重要的算法实现部分，首先定义边界，它的含义是从起点到终点的最短路径；定义一个空列表closed，存放已经处理完的节点；parent则是存放父节点，即当前最短路径节点的上一节点。
首先进入edge循环，定义flag是1，设置最小估计函数的初始值为w区域宽度加h区域高度。对edge里面的每一个节点进行循环。如果终点的坐标和当前遍历节点的值相等，则将该遍历节点存入边界edge集合中，接着break跳出循环；如果终点的坐标和当前遍历节点的值不相等，则表明寻找最短路径的工作还未完成，就要继续进行下一步。
将find_edge函数中筛选出来的满足条件的邻居节点赋值给child数组，并循环其中的节点。算出各邻居节点的估计函数，若小于之前存放的估计函数，则进行替换，并把此邻居节点作为最短路径上的下一个节点。如此循环往复，直到遍历到终点，找到最短路径为止。具体代码如上图6所示。
Figure 7. A* algorithm code6
图7. A*算法代码6
最后，将Astar函数中的变量设置好，这里设置区域宽度为20，区域高度为30，起始点位置(0, 0)，终点位置(5, 29)，障碍物位置在第九列，由此开始的10个长度。运行find_way这个主体函数，再将图像画出，具体代码如上图7所示，至此A*算法代码编写完成。
5. A*算法的运算模拟结果
Figure 8. Draw a pseudo color image of a two-dimensional array
图8. 绘制二维数组伪色彩图
如上图8所示，区域宽度w和高度h为30和20，在左下角设置起点s，右下角设置终点g，深蓝色部分为障碍物，黄色部分即为计算出来的最短路径，浅绿色部分为遍历计算过的节点。从图8中能清晰看出绿色部分并没有遍及整个区域，遍历的节点不是盲目的，而是有选择性的，估计函数帮助算法进行有选择的探索，这大大降低了运算时间和内存空间。
6. 总结
根据仿真实验分析结果可知，本论文所选用的A*算法能够快速准确地找到最短路径，为用户提供足够可靠的路线指引，为城市智能停车场路径规划系统提供坚实的基础，方法设计合理。
基金项目
2023年江西省大学生创新创业训练计划项目(课题编号：S202310407081)。