A算法在停车场寻车路径规划中的应用研究

吕博 都美晔 李璐君

摘 要 由于A*算法在进行启发式搜索时具有较高的算法效率，并且可以基于评估函数找到最优路径，本文针对在大型停车场中寻车困难的问题提出采用A*算法进行路线规划。文章阐述了A*算法的原理及实现过程，并对停车场进行建模，通过仿真实验验证了算法应用于停车场寻车路径规划的可行性。

关键词 A*算法；路径规划；停车场

引言

随着经济的发展，中国汽车保有量及市场规模逐年增长。为满足人们停车的需求，住宅区及大型商场的停车场面积增大、层数增加，提供大量车位的同时对用户寻车也造成了一定困难。仅靠车位编号寻找车辆的方法效率较低，因此建立停车场寻车系统帮助用户寻找车辆位置，规划寻车路线十分重要。最短路径算法是计算机科学、人工智能科学等研究的热点问题[1]。两点间的所有路径中，一定有一条最佳的路径使时间和效率均为最优，这时就需要使用限制搜索区域内的最短路径算法[2]。其中，A*算法由于其性能和准确性被广泛使用[3]。

1 A*算法原理与实现

A*算法的原理是借助于开启列表（OpenList）和关闭列表（ClosedList）两个列表，通过估值函数来引导整个路径搜索的过程，快速寻找到一条最短的路径。其中，开启列表和关闭列表是 A*算法在寻路搜索的过程中必须维护的两张表。开启列表中存放着即将被访问但未被访问的节点，同时这些节点所对应着的估值值也被存放在该表中；而关闭列表中则存放着已经访问完成的节点。估值函数用来引导寻路，其数学表达式为：

F（n）=G（n） +H（n） （1）

其中F（n）为估值函数；G（n）是已经计算出的从起始点到当前路点的实际路径长度；H（n）是估测从当前点到目标点路径长度的曼哈顿距离。

使用标准 A*算法进行寻找路径的流程见图1。

A*算法需要设置起始节点S和目标节点E，并建立两个空的List：OpenList 和ClosedList。如图1所示，在第一次循环时，将起始节点S和相邻节点放入 OpenList 中。从第二次循环开始，每次选取OpenList中估值最小的节点a作为路径选取的点，把a设置为父节点，放入CloseList中并把a的相邻点加入OpenList中。直到OPenList为空，或a没有不在CloseList里的相邻点，或a为目标节点E时，循环结束。当a就是目标节点E时，路径规划成功，按照父节点回溯即可得到最短路径。

2 停车场寻车应用

在停车场寻车场景下，使用A*算法进行路径规划，在人员和车辆之间规划一条最短路径，首先需要建立停车场模型，如图2所示。其中B表示停车场的边界，O表示停车位，*表示停车场中的道路，S表示起始点即人员所在的位置，E表示终点即车辆所在位置。

使用A*算法寻找从S点到E点的最短路径，并将最终的路径用P表示。最终结果如图3所示。

3 結束语

本文介绍了A*算法并将其应用在停车场寻车路径规划中，能够帮助停车场为车主提供更便捷的服务。

参考文献

[1] 陆锋.最短路径算法：分类体系与研究进展[J].测绘学报，2001，30（3）：269-275.

[2] 付梦印，李杰，邓志红.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报，2004，24（10）：881-884.

[3] 郝振国，王玉玫.双向A*算法在军事路径规划中的应用[J].计算机工程与应用，2011，47（29）：246-248.