基于强化学习思想的地下车库车位排布研究

王潇霆 张易诚 沈炜

摘  要： 在地下车库排布车位，往往受到车库轮廓、障碍物和连通性等条件约束，本文设计并实现了一种基于探索策略和区域划分的车位排布方案。探索策略借鉴了强化学习的思想，通过设置奖励机制使智能体在地下车库环境中进行主路的铺设；区域划分算法可以在保证不堵塞车道情况下得到尽可能多的车位数量。本文算法能够在短时间内获得车位排布结果，帮助设计师减轻工作量，提高項目收益。

关键词： 地下车库； 车位排布； 奖励机制； 探索策略； 区域划分

中图分类号：TU248.3          文献标识码：A     文章编号：1006-8228（2023）09-54-05

Research on parking arrangement algorithm for underground

garage based on reinforcement learning

Wang Xiaoting， Zhang Yicheng， Shen Wei

（School of Computer Science and Technology （School of Artificial Intelligence）， Zhejiang Sci-Tech University， Hangzhou， Zhejiang 310018， China）

Abstract： In underground garages， parking spaces are often constrained by garage contours， obstacles， connectivity and other conditions. In this paper， a parking arrangement scheme based on exploration strategy and regional division is designed and implemented. The exploration strategy draws on the idea of reinforcement learning， and makes the agent lay the main road in the underground garage environment by setting up a reward mechanism. The regional division algorithm can get as many parking spaces as possible without blocking the lanes. The proposed algorithm can obtain the results of parking arrangement in a short time， which can help designers reduce workload and improve project income.

Key words： underground garage; parking space arrangement; reward mechanism; exploration strategy; regional division

0 引言

随着城市化的进程不断加快，城市的土地资源紧缺问题日益严重[1]。怎样才能充分利用停车资源、增加经济效应[2]成为了城市发展的一个重要问题。目前已有许多专家学者对如何在地下车库中获得更多的车位问题进行了深入探究[3]。对于车库轮廓为不规则形状的停车场，徐涵喆等[4]提出了一种基于遗传算法的外圈车位排布启发式算法解决外圈车位排布问题；黄逸彬等[5]提出了基于图形分割的城市地下车库车位排布优化方法处理复杂轮廓内部整排车位的排车角度问题；对于主楼空隙内的车位排布方案，冯嘉宇等[6]提出了一种基于分离障碍物的地下车库车位排布算法。但是目前这些研究在障碍物数量多、分布不规律情况下，想要始终保证车道之间的连通性会非常困难。

因此，为了在诸多约束条件下最大程度地利用地下停车场资源，使车位数量最大化，本文提出一种基于探索策略和区域划分算法的模型。该模型参考了强化学习的思想[7-9]，通过设置的奖励机制使智能体在地下车库环境中进行主路的铺设，接着运用区域划分算法划分区域并排布车位。本文模型能适用于任意复杂的地下车库图，并且能有效地处理车道连通性问题，降低无效车位存在的概率。算法最终能够得出所有车位的坐标并可视化呈现，辅助人工设计。

1 模型建立

1.1 车库环境网格化处理

为了清晰地描述并记录车库中每个位置的状态，本文对车库环境进行了网格化处理。该方法使用网格记录位置状态，这样状态的更新操作就变得十分容易。网格化处理步骤如下：首先求出地下车库外轮廓最小矩形闭包，之后对闭包进行切割，根据切割精度确定状态矩阵[Sstate]的行和列。当网格处于有障碍物时，其值设为-1；当处于边界外时，其值设为-2；当处于空旷区域，其值设为0；当网格已被铺设为过道时，其值设为1。环境网格化处理初始结果如图1所示。

1.2 基于奖励机制的探索策略

1.2.1 奖励机制

为了引导智能体在环境中进行有效的探索，奖励的设置会非常关键，合理的奖励机制能使智能体在探索中获得的奖励最大化。地下车库中有许多约束条件会影响最终的车位排列结果，把这些条件进行网格化处理后得到集合[Zw]，记[Zw=A，B，c，d，E]，其中[A]为车库边界的网格集合，记[A=a1，a2，…，an]，[B]为车库环境内障碍物最小闭包的网格集合，记[B=b1，b2，…，bn]，[c]为车位宽度所占网格数量，[d]为车位长度所占网格数量，[E]为车库环境内相交道路的网格集合，记[E=e1，e2，…，en]。约束条件之间关系简单描述为：①[B]和[E]必须存在于[A]的内部；②[B]和[E]在车库环境内始终不存在交集。

当智能体进行过道铺设时，在[Sstate]中的位置记为[Sn]，考虑到[Zw]和排列过程中的车位数量问题，最理想的情况为过道两侧都排上车位，所以[Sn]距离[A]和[B]为[d]时最佳。因此奖励的设置如下：

⑴ 如果当前位置已被探索过，奖励设为0。

⑵ 当智能体选择某一方向进行移动时，[Sn]的其中一侧与障碍物或边界距离为一个车位长度，即中间刚好能排竖向车位，得到+200奖励。

⑶ 当[Sn]与[A]、[B]处于图2（a）情况时，由于继续前进能到达⑵中的理想位置，所以在此位置关系下设置+50奖励来鼓励走直线。

⑷ 由于基于奖励机制的探索策略主要实现的是在地下车库中沿着障碍物或边界进行主路铺设，所以当智能体的当前位置离障碍物或边界的距离过远时，智能体就脱离了主路铺设的路线，可能会导致过多的车库面积未被利用，这种情况下设置-50奖励作为惩罚。

⑸ 当两条平行车道的位置关系处于图2（b）时，过道之间距离过窄，至多只能排横向车位。这种情况会造成大量面积浪费，所以给予-50奖励。

在车库环境中获得的累计奖励[Rs]公式如下（其中[T]为智能体在环境中所行进最大步数，[rk]为智能体第[k]步所获奖励大小。）：

[Rs=k=1Trk]  ⑴

1.2.2 探索策略

本文通过基于奖励机制的探索策略来实现地下车库的主路划分，并初步解决区域间存在的车道连通性问题。智能体根据上文所设的奖励在环境中进行探索，要使得到的奖励最大化，策略至关重要。因此策略设置如下：

⑴ 设置多起点的探索策略。设定每个起点的探索步数，解决探索不全面的问题。

⑵ 计算[Sn]向前后左右四个方向行进能获得的奖励[ru]，[rd]，[rl]，[rr]。

⑶ 选择奖励最大的方向为[Sn]行进方向，当奖励相同时优先级关系为[ru>rl=rr>rd]。

把策略函数记为[Qs'n，a]，其表示执行动作[a]后从状态[Sn]转移到[S’n]获得的奖励大小，所以下一步的动作选择如公式⑵所示。

[a'=GargmaxQs'n，a]  ⑵

[argmaxQs'n，a]为下一个状态[S’n]中所有可执行动作[a]对应的最大奖励值。[G]函数实现了奖励与对应动作之间的转换。得到的探索结果如图3所示。

1.3 区域划分算法及其车位排布策略

1.3.1 区域划分算法

[Sn]在对主路进行铺设的过程中，状态矩阵[Sstate]中空地位置不断地在进行[0→1]的更新，主路铺设完毕后得到了最终的[Sstate]矩阵，其中值为0的位置为空地，表示可以排布车位。本小节讨论如何对空地进行区域的划分，使得区域内排布的车位达到尽可能最优的情况。

区域划分问题实际上也可转换为在状态矩阵中求最大矩形问题，矩形划分越大，内部排列的车位也就更多。算法简单描述为首先遍历[Sstate]中所有的位置，开始找连续值为0的区域，即最大矩形区域，随后给符合条件的区域相应位置更新为-3，表示已经遍历过。以此类推，重复上述步骤，直到新的区域已不满足条件后停止遍历，最后得到了区域集合[Arec=A1，A2，A3，…，An]，区域划分结果如图4所示。

1.3.2 车位排布策略

区域集合[Arec]包括了边界区域[Abor]（图4黑色区域）和非边界区域[Ain]（图4白色区域）。对于[Ain]区域，可以把它分为车位模块集合[P]（种类：①竖车位模块集合[P1]，记[P1=P（1）1，P（2）1，…，P（n）1]；②横车位模块集合[P2]，记[P2=P（1）2，P（2）2，…，P（n）2]。）和过道模块集合[R]，记[R=R1，R2，…，Rn]。模块之间关系满足：

[P⊆Ain，R⊆Ain，P1∈P，P2∈P] ⑶

[P（n）1∈P1，P（n）2∈P2，Rn∈R] ⑷

[∀P（n）1∩∀Rn=∅，∀P（n）2∩∀Rn=∅，∀P（n）1∩∀P（n）2=∅] ⑸

车位的排布策略如下：

⑴ 沿着区域的短边开始扫描划分[P]和[R]，得到的[P]模块能够排放更多的车位。

⑵ 遵循区域内每划分两条[P]，划一条[R]的规则，使在保证连通性的情况下[P]模块数量尽可能多。

⑶ 车位模块选择优先级为[P1]>[P2]，当[P2]模块无法放置时则划分结束。

⑷ 得到划分后所有的[P]模块集合，根据每条[P]模块的顶点坐标从左至右开始排布车位。

[Ain]区域划分及车位排列如图5所示。

由于经过区域划分得到的矩形与真实的地下车库轮廓间存在空隙，这会导致过多的面积被浪费。所以对于边界区域的处理，参考了徐涵喆等[4]提出的外圈车位排布启发式算法，该文章对边界区域的车位模块定义了水平式和垂直式两种类型。为了增加边界车位的数量，本文又提出了一种基于水平式与垂直式的组合类型模块排列方法来解决外圈车位排布问题。该方法实际步骤如下。①对外圈每条边使用垂直式模块。②在垂直式模块内排布两种类型的车位（a.水平式车位，b.垂直式车位）。③如图6（c）所示，两种车位类型排布优先级为b>a，当出现b与障碍物发生碰撞或道路堵塞情况时，即道路R1与障碍物有重叠，会进行b[→]a的替换。④每条边遍历完毕后，得到外圈所有车位坐标。

2 實验验证

实验使用了七张不同的标准CAD工程图纸对本文模型进行验证和分析，图纸包括了用地红线、主楼、坡道等约束条件。车位的长度设置为6米，宽度2.5米，道路宽度设置为6米，承重柱宽度为0.5米，地下车库网格化的分割精度设为0.5米。实验环境采用4核、3.40GHZ处理器、内存为16GB的计算机，基于Python3.8编程环境，通过Pyautocad库连接Autocad软件并读取其中的CAD图纸属性，最后使用Matplotlib库对图纸属性和算法结果进行可视化分析。

为验证算法的有效性，对比了冯嘉宇等[6]提出的基于分离障碍物的地下车库车位排布算法（记A算法）和人工排布的车位数量。结果如表1所示。

编号1～7使用了和A算法相同的CAD图纸，从实验结果看，本文算法的车位数量和运行时间都有明显提升。结合表1、图7和图8可发现：①本文算法外圈使用了组合车位模块后，车位数量明显增多。②遗传算法具有不稳定性，会陷入局部最优解，有收敛速度慢等问题，而本文算法效率比较高且稳定，算法花费的时间大幅度降低。③通过实验发现对于复杂的车库结构如图纸6，使用A算法中的像素切割方法划分车位模块，会存在较严重的连通性问题，部分车位会因为道路堵塞而被定义为无效车位。而本文算法为了尽可能的减少无效车位的个数，首先会使用探索策略划分出了主路，初步解决了车道间的连通性问题。而后使用区域划分算法，判断区域模块之间是否相邻，如果为相邻模块，则再细分车道。如图9所示，本文算法对于处理复杂的车库结构也会得到比较理想的效果。（注：处理闭包内的主楼障碍物空隙间的车位排布问题，主要参考了冯嘉宇等[6]提出的基于分离障碍物的地下车库车位排布算法文章。）

3 结束语

本文对地下车库的车位排布问题建立如下算法模型：使用基于奖励机制的探索策略和区域划分算法对地下车库进行车位模块的划分，随后根据车位排布策略在车位模块内排布车位，得到最终车位排布结果。在CAD工程图纸的约束条件下使用该算法，利用Matplotlib库对算法结果进行了可视化，得出了如下结论：①经过本文模型的处理，可以保证因连通性问题而导致的无效车位尽可能少。②对外圈模块使用本文提出的组合类型车位模块，在车位数量上会优于徐涵喆等[4]提出的水平式或者垂直式车位模块，从而进一步提高了项目的收益。③冯嘉宇等[6]提出观点中，由于遗传算法具有不稳定性、收敛速度慢等问题，所以在时间上开销比较大，但使用本文模型可以解决该类问题，在使用相同图纸情况下，所用时间能减少1/2左右。

参考文献（References）：

[1] 王欣.地下车库设计的合理性及经济性分析[J].中国建筑装饰装修，2022（17）：147-149.

[2] 刘帅，牛家兴，曾丽雯，等.地下车库柱网及结构选型综合经济技术分析[J].工程建设与设计，2021（12）：4-6.

[3] 谷锦彪.基于驾驶人行为特性的停车位规划方法研究[D].安徽：合肥工业大学，2017.

[4] 徐涵喆，黄逸彬，杨赫，等.基于规则的城市地下车库外圈车位排布启发式算法[J].北京邮电大学学报，2019，42（4）：102-108.

[5] 黄逸彬，杨赫，周钟秉，等.基于图形分割的城市地下车库车位排布优化方法[J].北京邮电大学学报，2020，43（4）：7-14.

[6] 冯嘉宇，王潇霆，沈炜.基于分离障碍物的地下车库车位排布算法[J].智能计算机与应用，2023，13（1）：25-30.

[7] 杨羊.基于强化学习的持续集成测试用例优先排序奖励机制研究[D].北京：北京化工大學，2022.

[8] 何柳柳，杨羊，李征，等.面向持续集成测试优化的强化学习奖励机制[J].软件学报，2019，30（5）：1438-1449.

[9] 余光鑫.基于强化学习的地下车库生成式设计研究[D].广东：华南理工大学，2020.