汽车技术

算法	搜索时间/s	节点数量/个	路径长度/m
普通混合A*算法	0.583	163	16.3
改进混合A*算法	0.286	154	15.4

算法	搜索时间/s	节点数量/个	路径长度/m
普通混合A*算法	0.583	163	16.3
改进混合A*算法	0.286	154	15.4

算法	搜索时间/s	节点数/个	路径长度/m
普通混合A*算法	0.259	174	17.4
改进混合A*算法	0.068	100	10.0

算法	搜索时间/s	节点数/个	路径长度/m
普通混合A*算法	0.259	174	17.4
改进混合A*算法	0.068	100	10.0

基于改进混合A*算法的自动泊车系统路径搜索方法

PDF下载

曹彦博 ¹ , 颜京才 ² , 李旭升 ² , 曹立波 ¹

汽车技术 | 第二十五届汽车安全技术国际学术会议专题 2023,(6): 37-41

收起

汽车技术 | 第二十五届汽车安全技术国际学术会议专题 2023, (6): 37-41

基于改进混合A*算法的自动泊车系统路径搜索方法

全屏

曹彦博¹, 颜京才², 李旭升², 曹立波¹

作者信息

¹ 湖南大学，汽车车身先进设计制造国家重点实验室，长沙 410082

² 毫末智行科技有限公司保定分公司，保定 071000

A Method of Path Search for Automatic Parking System Based on Improved Hybrid A* Algorithm

Yanbo Cao¹, Jingcai Yan², Xusheng Li², Libo Cao¹

Affiliations

¹ State Key Laboratory of Advanced Design and Manufacturing of Automobile Body, Hunan University, Changsha 410082

² Baoding Branch of HAOMO.AI Technology Co., Ltd., Baoding 071000

出版时间: 2023-06-24 doi: 10.19620/j.cnki.1000-3703.20230268

文章导航

摘要

收起

针对混合A*算法在短距离泊车场景下由于终点附近环境复杂，难以用无碰撞的RS曲线加速搜索的情况，提出一种改进混合A*算法，从目标位姿开始反向搜索路径，结合通过A*算法计算得到的代价地图查表获得启发值，通过判断车身轮廓线与简化后的障碍物线是否相交进行碰撞检测以节省搜索时间，并通过设置合适的车辆转向角度分辨率增加节点扩展方向的数量，保证路径的平滑性。最后使用MATLAB对改进算法与原始算法进行仿真对比分析，结果表明，在平行和垂直车位泊车场景下，该改进混合A*算法均可有效缩短路径搜索时间，获得的路径更短、更平滑。

关键词

自动泊车 / 混合A*算法 / 路径搜索

Abstract

收起

For the situation that the hybrid A* algorithm is difficult to accelerate the search using collision-free Reeds-Shepp (RS) curves due to the complex environment near the destination in short distance parking scenarios, this paper proposed an improved hybrid A* algorithm that reversely searched the path from the target posture, combined with the cost map look up calculated by A* algorithm to obtain heuristic values. Collision detection was performed by judging whether the car body contour line intersecting with the simplified obstacle to save search time, and by setting suitable vehicle steering angle resolution to increase number of the node expansion direction to ensure the smoothness of the path. Finally, MATLAB was used to simulate and compare the improved algorithm with the original algorithm. The results showed the improved hybrid A * algorithm effectively shortened the path search time both in parallel and vertical parking scenario, resulting in shorter and smoother paths.

Key words

Automatic parking / Hybrid A* / Path searching

引用本文

曹彦博, 颜京才, 李旭升, 曹立波. 基于改进混合A*算法的自动泊车系统路径搜索方法. 汽车技术, 2023 , (6) : 37 -41 . DOI: 10.19620/j.cnki.1000-3703.20230268

Yanbo Cao, Jingcai Yan, Xusheng Li, Libo Cao. A Method of Path Search for Automatic Parking System Based on Improved Hybrid A* Algorithm[J]. Automobile Technology, 2023 , (6) : 37 -41 . DOI: 10.19620/j.cnki.1000-3703.20230268

正文

收起

1 前言

收起

路径规划作为自动泊车系统的重要组成部分，是保障行驶安全、泊车效率和乘员舒适性的关键。路径搜索是路径规划的重要步骤，路径搜索算法一般可分为图搜索算法、树搜索算法和智能优化算法^[1]。图搜索算法^[2-3]的原理是将车辆附近的环境信息转换为离散图，然后通过一定的搜索算法得到基础路径，如A*算法^[4]、D*算法^[5]、混合A*算法^[6]等；树搜索算法在高维空间可行，可以得到安全无碰撞的路径，但由于采样具有随机性，导致前、后规划的路径有可能不一致，路径曲率连续性差；智能优化算法^[7]将路径规划视为集安全、边界和最短距离的约束，包括蚁群算法、遗传算法和细菌觅食法等。

传统的路径搜索算法得到的路径普遍存在一些缺点，如路径不够平滑、难以跟踪控制、搜索效率不高等。针对这些问题，本文基于较随机采样更加稳定的图搜索算法，提出一种改进的混合A*算法对短距离的自动泊车进行路径搜索：针对障碍物较多、避障更复杂的车位内的终点和周围相对较宽敞的起点，采用反向搜索的方法结合适用于该场景的线碰撞检测方法获得路径；利用A*算法获得代价地图，在进行路径搜索时通过查表得到启发值，大幅缩短搜索时间；通过设置可变的车辆转角分辨率在节点扩展时增加其扩展方向数量，提高路径的平滑度，使其更易于被优化和跟踪控制。

2 自动泊车路径搜索

收起

2.1 碰撞检测

在自动驾驶研究中描述车辆周围环境信息的方法一般包括栅格地图、拓扑地图和几何地图等方法^[8]，而考虑到自动泊车在非结构化道路复杂环境下进行，并且本文所研究的混合A*算法基于栅格进行搜索，因此选用栅格地图来描述环境信息，即在感知系统获得真实世界坐标后通过设置合适的分辨率将其转变为栅格地图，利用栅格存储相应的节点信息进行节点扩展和路径回溯。

基于栅格地图的碰撞检测通常用包围盒来描述车身轮廓，然后通过逐一判断障碍物占据的栅格与车身的距离进行碰撞检测。常用的包围盒包括轴对齐包围盒（Axis-Aligned Bounding Box，AABB）、有向包围盒（Oriented Bounding Box，OBB）和球包围盒。其中，AABB使用与栅格平行的直线包围车身，OBB采用有向的边界框，能更好地描述物体的原形状，球包围盒则用若干个圆包裹车辆，各包围盒具体形式如图1所示。这种栅格占据的碰撞检测方式可以较好地描述车身轮廓并通过判断与障碍物的距离进行碰撞检测，但需要对所有障碍物占据的栅格进行判断，增加了搜索时间，并且将障碍物离散化为栅格容易出现误差，同时较小的分辨率会增加时间成本，较大的分辨率则会导致对障碍物的描述不准确。

本文重点研究车辆已在车位附近的短距离自动泊车场景下的路径搜索，此场景下车辆起点周围环境简单，通常不会有复杂的障碍物，只需考虑停入车位过程中的避障即可。因此，为了简化碰撞检测的计算，本文将车位边框设置为障碍物线，只保留泊车的入口，如图2所示。然后通过向量叉积法判断车身轮廓线与障碍物线是否相交进行碰撞检测，即在已经设定好的泊车场景中，利用车身参数和当前所处位置计算出车身4个顶点的坐标，如D点坐标(x_D,y_D)：

（1）

x D = x r - l r c o s θ + W 2 ⋅ s i n θ y D = y r - l r s i n θ - W 2 ⋅ c o s θ

式中，(x_r，y_r)为车辆后轴中心坐标；l_r为车辆后轴到车身后端的距离；W为车身宽度；θ为车辆轴线与水平方向的夹角。

得到4个顶点的坐标即可获得描述车身轮廓的4条线段，然后通过判断其与障碍物线是否相交进行碰撞检测。这种碰撞检测方法计算简单，可以节省混合A*算法搜索路径的时间，并且这一过程在世界坐标下进行，无需进行障碍物占据栅格转化，误差较小。

2.2 基于混合A*算法的反向搜索

A*算法采用贪心策略，通过设计启发函数选择代价估计值小的点进行搜索，相较于广度优先搜索和深度优先搜索有着更高的搜索效率^[9]。传统A*算法搜索出的路径是折线，显然不符合车辆的运动学条件。与传统A*算法相比，混合A*算法改变了连通图结构，额外考虑车辆位姿，引入θ这一状态量，优化了节点拓展方式，并以车辆的最小转弯半径作为约束条件，使得搜索出的路径满足车辆的运动特性，从而易被跟踪执行，2种算法的节点扩展方式如图3所示。

与A*算法相同，混合A*算法也使用评价函数选择更优的节点：

（2）f(n)=g(n)+h(n)

式中，f(n)为从初始状态经由状态n到目标状态的成本估计量；g(n)为在状态空间中从初始状态到状态n的实际成本；h(n)为从状态n到目标状态的最佳路径的成本估计。

但混合A*算法的内涵与普通A*算法存在较大差别。g函数除原有意义外，还应针对不理想因素施加惩罚，如对反复前进倒退、频繁变化转角等情况进行惩罚来体现当前节点的竞争力^[10]。启发值h的计算方法一般为：

（3）h=max{h_{c_av},h_{k_c}}

式中，h_{c_av}为考虑避障因素但不考虑运动学可行性时的路径长度；h_{k_c}为考虑车辆运动学约束但忽略碰撞时的路径长度。

式（3）的含义为：如果当前节点与终点距离较近，生成路径的难度在于保证运动可行性，此时h_{k_c}更能反映路径长度；反之，路径生成难度在于避障，需要h_{c_av}作为启发值。通常用RS（Reeds-Shepp）曲线估算h_{k_c}，用经典A*算法确定h_{c_av}的取值。

一般情况下，混合A*算法从起始位姿开始，朝着目标位姿扩展节点，同时尝试使用无碰的RS曲线连接当前节点和目标点以加快搜索速度。但在车位较小或终点附近环境复杂时，连接终点的RS曲线无法满足避障要求，导致节点扩展过多，最终出现搜索不到路径或耗时较久的情况。

在本文所研究的泊车场景中，车辆的起点处环境简单，根据2.1节的分析，仅考虑车位附近的避障，即车位线，因此目标点（车位内）避障要求较高。针对此情景，本文提出一种基于混合A*算法从目标位姿向起始位姿反向搜索的搜索策略，将泊车路径分为2段，如图4所示。第1段从空间狭窄的车位中的目标点开始向起点不断进行节点扩展（E-O段），第2段尝试在满足避障要求的条件下用RS曲线从当前节点连接起点（O-S段），最终将所有点逆序输出即可得到搜索出的泊车路径，而由于起点附近空间较大，RS曲线会较早实现无碰连接起始位姿来加速搜索。同时，终点附近狭窄的车位也由扩展节点结合碰撞检测保证路径的最优性。

此外，传统的混合A*算法在节点扩展时仅有6个方向，即直行的前进、后退以及转向盘向左、向右最大转角状态下的前进和后退，导致车轮的转向角较大，难以实现车辆的控制并且影响乘员的乘坐体验。本文通过设置车轮转向角的分辨率增加搜索过程中的节点扩展方向，其扩展方式如图5所示，同时考虑了转向角的代价值，使得搜索出的路径更加平滑，避免车辆转向角过大导致各段路径之间连接处曲率不连续，使路径易于被优化和跟踪。在代价函数方面，除为使路径更加平滑设置的转向角度代价外，还加入了车辆前进/后退挡位切换代价、转向代价等，并将其加权放入函数g中，共同保证了路径的平滑和泊车过程中乘员的舒适性。

2.3 基于A*算法的代价地图

由于式（3）中h_{c_av}指使用A*算法得到的当前节点到目标点的启发值，因此通常在搜索过程中需要不断使用A*算法计算当前栅格到终点栅格的h，耗费大量时间。

本文使用一种代价地图来获得启发值h，在混合A*算法开始路径搜索前先将地图栅格化，接着利用A*算法计算每个栅格到终点栅格的代价值，将该值与栅格对应存储即得到代价地图，如图6所示，图中数值为A*算法计算得到的栅格代价值，Inf表示该栅格代价值为无穷大，为车辆不可到达的区域。因此，在后续路径搜索过程中无需再逐一进行计算，可以直接从代价地图中通过查表方式获取启发值，可大幅节省时间，提高路径规划效率。且本文设计的搜索算法从终点向起点反向搜索路径，再使用A*算法计算代价地图时的目标点即为泊车起点，即可得到所有栅格到起点的代价值，相当于同时得到了多个车位到起点的启发值。多车位下全自动的泊车路径规划同样具有重要意义，在本文研究的自动泊车系统中具体表现为：自动泊车系统启动后，系统首先自动计算代价地图，用户选择想要泊入的车位后泊车系统进行路径搜索，在搜索过程中省略了使用A*算法计算启发值的步骤，直接从代价地图中查表获得，极大节省了搜索时间。

2.4 路径搜索算法框架

综上，本文提出的路径搜索算法流程如图7所示。通过传感器等得到环境信息和起止点后首先通过A*算法得到整体的代价地图，再使用改进混合A*算法从目标位姿反向搜索路径，其间不断尝试用RS曲线连接当前节点与起点并进行碰撞检测，直到成功利用无碰撞的RS曲线连接或直接扩展到起点时结束搜索，最后逆序输出所有节点即可获得有效泊车路径。在搜索过程中通过open和close 2个集合对节点进行管理，open集存放待扩展节点，将已经扩展过的节点存入close集。

3 仿真分析

收起

城市中常见的车位类型有水平式和垂直式，因此本文使用MATLAB分别设计针对这2种常见车位的泊车场景，对改进的混合A*算法和原始算法进行对比仿真分析，以验证其合理性和有效性。

3.1 水平车位

在水平车位泊车场景下分别使用普通混合A*算法和本文提出的改进混合A*算法进行泊车路径搜索，结果如图8所示。普通混合A*算法的节点扩展方向只有6种，因此本文在进行时间比较时将改进混合A*算法的节点扩展方向设置为与其相等，以验证本文设计的反向搜索结合代价地图查表的混合A*算法的实时性。2种算法的仿真结果数据如表1所示。

结合图8和表1可以看出，改进混合A*算法用时更短，得到的路径也更短、更加平滑，提高了泊车效率，易于后续对车辆的控制，从而实现较好的轨迹跟踪。

3.2 垂直车位

垂直车位泊车场景下仿真条件设置与水平车位场景相同。图9所示为普通混合A*算法和改进混合A*算法的路径搜索结果，其仿真结果数据对比如表2所示。

从图9中可以看出，改进算法得到的路径更优，且由表2可知，改进算法比原始算法节省了2/3以上的时间，极大提高了规划效率。

综合2种车位泊车场景下的仿真结果，本文提出的改进混合A*算法在水平车位泊车场景和垂直车位泊车场景下均比传统混合A*算法用时更短，说明在短距离泊车、车位附近环境复杂的场景下，反向搜索结合代价地图的使用可以有效提高路径搜索效率。并且结合仿真数据和得到的路径可以看出，改进的算法获得的路径更短、更平滑，验证了变分辨率节点扩展的优越性。

4 结束语

收起

本文基于混合A*算法，针对短距离自动泊车提出一种反向搜索的路径搜索算法，结合适合此泊车情景的较简单的线碰撞检测方法，使其从终点开始扩展，同时尝试用RS曲线连接起点，通过设置转向角分辨率增加路径搜索过程中的节点扩展方向，并结合使用A*算法得到的代价地图，使其能够适用于有多个可选车位的泊车场景，然后使用MATLAB分别设计了平行和垂直车位泊车场景，对提出的算法进行仿真分析，并与普通混合A*算法进行对比。结果显示，2种场景下改进的混合A*算法均有效提高了搜索效率，且得到的路径更短、更平滑。

完整的自动泊车路径规划系统应包括搜索、优化，并对速度进行规划得到完整的泊车轨迹，本文只开展了路径规划中的搜索工作，未对搜索到的路径进行优化，这也是本文后续需要研究的内容。

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

高健博. 无人驾驶汽车运动规划方法研究综述[J]. 汽车工业研究, 2018(8): 37-42.

GAO

J B

. An Overview of Research on Motion Planning Methods for Autonomous Vehicle[J]. Auto Industry Research, 2018(8): 37-42.

[2]

KIADI

, GARCIA

, VILLAR

J R

, et al. A*-Based Co-Evolutionary Approach for Multi-Robot Path Planning with Collision Avoidance[J]. Cybernetics and Systems, 2023, 54(3).

[3]

SEDIGHI

, NGUYEN

D V

, KUHNERT

K D

. Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications[C]// 2019 5th International Conference on Control, Automation and Robotics (ICCAR). Beijing, China: IEEE, 2019.

[4]

张辉, 张瑞亮, 许小庆, 等. 基于关键节点的改进A*无人车路径规划算法[J]. 汽车技术, 2023(3): 10-18.

ZHANG

, ZHANG

R L

, XU

X Q

, et al. Key Nodes-Based Improved A* Algorithm for Path Planning of Unmanned Vehicle[J]. Automobile Technology, 2023(3): 10-18.

[5]

MAUROVIC

, SEDER

, LENAC

, et al. Path Planning for Active SLAM Based on the D* Algorithm with Negative Edge Weights[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 48(8).

[6]

ESPOSTO

, GOOS

, TEERHUIS

, et al. Hybrid Path Planning for Non-Holonomic Autonomous Vehicles: An Experimental Evaluation[C]// IEEE International Conference on Models & Technologies for Intelligent Transportation Systems. Naples, Italy: IEEE, 2017.

[7]

, ACARMAN

, ZHANG

Y M

, et al. Tractor-Trailer Vehicle Trajectory Planning in Narrow Environments with a Progressively Constrained Optimal Control Approach[J]. IEEE Transactions on Intelligent Vehicles, 2020, 5(3): 414-425.

[8]

林明德. 基于改进混合A*算法的非结构化道路路径规划[J]. 机电技术, 2022(1): 38-41+74.

LIN

M D

. Unstructured Road Path Planning Based on Improved Hybrid A* Algorithm[J]. Mechanical & Electrical Technology, 2022(1): 38-41+74.

[9]

任秉韬, 王淅淅, 邓伟文, 等. 基于混合A*和可变半径RS曲线的自动泊车路径优化方法[J]. 中国公路学报, 2022, 35(7): 317-327.

REN

B T

, WANG

X X

, DENG

W W

, et al. Path Optimization Algorithm for Automatic Parking Based on Hybrid A* and Reeds-Shepp Curve with Variable Radius[J]. China Journal of Highway and Transport, 2022, 35(7): 317-327.

[10]

李柏, 张友民, 彭晓燕, 等. 自动驾驶决策规划技术理论与实践[M]. 北京: 中国铁道出版社有限公司, 2021.

, ZHANG

Y M

, PENG

X Y

, et al. Autonomous Driving Theory and Practice of Decision-Making and Planning Technologies[M]. Beijing: China Railway Publishing House Co., Ltd., 2021.

2023年第卷第6期

PDF下载

241

101

引用本文

BibTeX

文章信息

doi: 10.19620/j.cnki.1000-3703.20230268

首发时间：2025-12-07
出版时间：2023-06-24

补充材料

相关文章

文章信息

作者

出版历史

修回日期：2023-04-04

基金

作者信息

¹ 湖南大学，汽车车身先进设计制造国家重点实验室，长沙 410082

² 毫末智行科技有限公司保定分公司，保定 071000

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/qcjs/CN/10.19620/j.cnki.1000-3703.20230268

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT