A*算法在自动驾驶车辆路径规划中的应用

冯凯 吉星 杨昕

摘 要：路径规划是自动驾驶系统研究的重要内容之一，A*算法是一种启发式的搜索算法，可以大幅度减少搜索过程中的扩展节点，从而可以快速找到一条从起点到终点的最优路径。结合高精度地图在自动驾驶系统中的应用，文章将A*算法用于自动驾驶车辆在高精度地图中的全局路径规划，通过在自动驾驶车辆平台上实验测试表明该算法能够快速准确地规划出一条最短路径。

关键词：路径规划;A*算法;无人驾驶;高精度地图

中图分类号：U469.7  文献标志码：A  文章编号：1671-7988（2020）22-25-04

Abstract： Path planning is one of the important contents of automated driving system research. A* algorithm is a heuristic search algorithm， which can significantly reduce the extended nodes in the search process， so as to quickly find an optimal path from the starting point to the end point. Combined with the application of high-precision map in the automated driving system， this paper applies the A* algorithm to the global path planning of the autonomous vehicle in the high-precision map. The experimental test on the platform of the autonomous vehicle shows that the algorithm can quickly and accurately plan a shortest path.

Keywords： Path planning; A* algorithm; Automated driving; High precision map

CLC NO.： U469.7  Document Code： A  Article ID： 1671-7988（2020）22-25-04

引言

无人驾驶车辆也称无人车、自动驾驶汽车，是指搭载有先进的车载传感器、控制器、执行器等装置，具备复杂环境感知、智能决策和控制等功能，能根据自身对周围环境条件的感知、理解，自动进行合理的车辆运动控制，且能够达到人类驾驶员驾驶水平的车辆[1][2]。路径规划是无人驾驶车辆系统最基本的环节之一，它是指在真实的道路环境中，无人驾驶系统按照设定的性能指标（如无碰撞、距离最短、时间最短等）寻找一条从开始位置到目标位置的最优路径[3][4]。根据对周围环境信息的知道程度不同，可以将路径规划分为全局路径规划和局部路径规划[5]。全局路径规划是指在已知的地图数据中规划出从起点到目标点的最优路径;局部路径规划是指依靠感知数据、局部地图数据和车辆位姿信息规划出一条无碰撞、满足约束条件的可行驶轨迹。

目前常用的全局路径规划算法有Dijkstra算法、A*算法、蚁群算法和粒子群算法等[6][7]，其中由尼尔森提出的A*算法在路径规划领域广泛应用。本文在基于无人驾驶高精度地图的基础上，通过A*算法进行了全局路径规划的设计与实现，将算法在无人车平台上进行了真实环境下的测试与验证，结果表明A*算法能够更加快速的找到一条最短路径。

1 A*算法描述

A*算法是在Dijkstra算法的基础上提出的，它引入了启发式函数和预估代价，是在一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。算法的核心部分在于估价函数的设计[8]，其估价函数如式1所示：

其中，f（n）是从初始状态经由状态n到目标状态的代价估计，g（n）是从初始状态到状态n的实际代价，h（n）是从状态n到目标状态的最佳路径的估计代价。

在A*算法中由于g（n）表示实际距离，而h（n）表示估计距离，所以在A*算法估价函数中h（n）的选择具有关键性的作用，决定了A*算法的效率，其中常用的估价函数有曼哈顿距离、对角线距离和欧几里德距离等。在估价函数中，如果h（n）等于0，那么f（n）= h（n），则A*算法就演变成为了Dijkstra算法，能够找到从起点到终点的最短路径，但是扩展节点会增多，效率变差。如果h（n）比从节点n移动到目标节点的真实代价小，此时A*也能保证找到一条最短路径;但是h（n）越小，A*的扩展节点越多，耗费资源越大，运行效率降低。如果h（n）精确的等于从节点n到目标节点的真实代价，则A*将会快速的寻找到最佳的路径并且不会进行额外的搜索扩展，此时算法运行效率最高。如果h（n）比从节点n移动到目标节点的真实代价大，那么A*不能够保证找到最短的路径，但是此时算法的运行速度快。另一种极端的情况为h（n）远远大于g（n），那么此时f（n）≈ h（n），则A*算法演变为BFS算法。

2 高精度地图的有向图建模

高精度地图是无人驾驶的基础，它包含了车道模型、道路部件、道路属性和其它的图层信息。在无人驾驶领域高精度地图必须要满足车道级的自动驾驶导航，为了能为自动驾驶车辆进行精准的转向、制动等，地图中除了需要包含车道线、车道中心线、车道属性变化等道路细节信息，还需要包含道路的曲率、坡度、航向、横坡等参数，此外还应包含交通标志牌、路面標志等道路部件等，这些综合信息数据一起构成了无人驾驶高精度地图。

目前高精度地图的主流形式有Opendrive和NDS两种。本文中无人驾驶车辆所用的高精度地图采用OpenDrive格式进行存储，由于地图数据元素众多，而全局路径规划关注的是地图路网的连接关系，所以必须先对其进行解析然后进行路网数据提取。我们需要从地图数据中提取表示一条路段的必要元素：id号、起点、终点和长度以及连接关系，因为地图数据中的路网连接关系是有方向的，为了将路网数据抽象为有向图的形式进行表达，所以可将每条路段抽象为一个节点并将路段A的长度作为路段A到其相邻路段权重，并最终采用邻接表进行路网数据的表示，如图1所示为从采集的高精度地图中提取的路网数据（左图中标红的路线）。

3 基于A*算法的路径规划设计与实现

3.1 估值函数选择

在真实道路环境中一条路段的起点至终点的距离长度一定大于等于两点之间的直线距离，结合A*算法中估计函数h（n）的选取原则，本文中选取欧几里德距离作为A*算法的估计函数，例如地图中存在点A和点B，并且在地图数据中的坐标分别表示为（A.x，A.y）和（B.x，B.y），则AB之间的估值计算如式2所示。

采用欧几里德距离作为估计函数时，因为h（n）一定小于等于道路的真实距离，所以此时A*算法一定能够规划出最短路径且运行效率高。

3.2 A*算法数据接口设计与实现

根据对真实路网数据的有向图表达形式结合A*算法对数据结构的需求，对路网数据结构进行接口设计。其中，路网中一条Section路段表示为结构体SectionInfo。

3.3 A*算法流程设计

A*算法在进行路径规划时，需要建立两个列表用来进行辅助规划搜索。一个是用来存放已经被检测过的节点列表Close_List，另一个是用来存放待检测节点的列表Open_List。本文设计实现的A*算法具体步骤如下所示。

4 算法测试与验证

4.1 实验平台

本文中所实现的路径规划算法的实验是在陕汽汽车工程研究院智能服务研究所无人驾驶车辆平台上进行的，如图4所示为实验所用的无人车驾驶车辆，无人车上装配有激光雷达、相机和组合导航等传感器。

4.2 实验结果

实验所用的无人驾驶车辆平台中所使用的地图均为同向单车道且道中间为实线，无人车在行驶过程中禁止变道。测试验证时无人车的姿态朝向为西向（图中朝左方向），路径规划的测试结果如图5所示，其中绿色路段为规划出的路径。

5 结语

本文将A*算法应用于从高精度地图数据中提取的路网上，可以高效准确地规划出最短路径。实验结果表明采用A*算法能够满足封闭园区无人驾驶车辆对路径規划的需求，本文实现的路径规划模块已经部署在自动驾驶车辆平台上并且可以很好的运行。

参考文献

[1] 宋飞扬.无人驾驶汽车及其发展[J].中国高新科技，2019（05）：24-27.

[2] 袁师召，李军.无人驾驶汽车路径规划研究综述[J].汽车工程师， 2019（05）：11-13+25.

[3] ZAMIRIAN M，KAMYAD A V，FARAHI M H. A novel algorithm for solving optimal path planning problems based on parametrizationmethod and fuzzy aggregation[J]. Physics Letters A， 2009.373（38）.

[4] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策， 2010.25（7）：961-967.

[5] 黄金豪，吴建悍.基于改进A*算法的室内服务机器人路径规划[J].技术与市场，2020，27（03）：62-63.

[6] 赵晓，王铮，黄程侃，等.基于改进A*算法的移动机器人路径规划[J].机器人，2018，40（06）：903-910.

[7] 张广林，胡小梅，柴剑飞，等.路径规划算法及其应用综述[J].现代机械，2011（5）：85-90.

[8] 武雅杰，杨晶东.基于A*算法的机器人路径规划[J].电子科技，2017， 30（06）：124-127.