68 Agriculture Mechanization Research》 农机化研究 2020 年 9 月上 无人驾驶汽车路径规划仿真分析 原 静 陕西铁路工程职业技术学院 （ 陕西 渭南 ， 714099） 摘 要：本文介绍了应用于无人驾驶汽车路径规划中全局路径规划的 A* 算法，从规划结果出发 ，分析传统 A* 的缺陷， 并提出 16 邻域改进算法。 为提高规划效率，减少路径规划时间提出双向 16 邻域改进算法。 并与 24 邻域及 48 邻域算法 进行比较，模拟仿真实验显示，改进后的双向 16 邻域算法在规划空间和搜索效率均为最优 ，双向搜索 16 邻域算法规划 的路径转角少，平顺性好，规划时间短，规划效率高。 关键词：全局路径规划；A* 算法；双向搜索 中图分类号：U463.6；TP301.6 文章编号：1672-3872（2020）17-0068-02 文献标志码：A Abstract:This paper first introduces the applied to the unmanned vehicle path planning in the global path planning of A* al鄄 gorithm. According to the planning results, analysis the defects of traditional A*, and put forward 16 neighborhood improve鄄 ment algorithm to improve the efficiency of planning, path planning time bidirectional 16 neighborhood improvement algorithm and neighborhood 24 and 48 neighborhood algorithm, simulation experiments showed that the improved bidirectional 16 neigh鄄 borhood algorithm in planning space and search efficiency is optimal, two-way 16 neighborhood search algorithm for planning the path to the corner, good comfort, planning time is short, the planning of high efficiency Keywords:global path planning;A* algorithm;bidirectional search 0 引言 ， ， ， 、 ， ， 。 比如 疲劳驾驶 汽车出行在人们生活中的重要性越来越高 醉酒驾车 开车人的自身原因 、 及情绪身体问题等原因也引发了许多交通事故[1]。 人驾驶汽车的路径规划研究迫在眉睫 目前 车的路径规划可以分为全局性和局部性 [2]， 于是否已知路径的所有情况 起点到终点的所有环境信息 定的 但是由于 ， 接听电话 无 无人驾驶汽 两者的区别在 全局路径规划是指已知从 因此此时的最优路径是确 因此 。 另一种是局部路径规划 通过各类传感器测量车辆与障碍物之间的距离 此时未知或者部分已知从 有部分信息是需要实时采集或 障 局部路径规划具有很强的 难度也 比较大 对规划结果的影响因素繁多 起点到终点的环境信息 收集 碍物的大小及方向位置信息 实时性 环境变化多 甚至有时候会出现局部规划达到最优 规划不能够到达终点的问题 规划局部最优路径的算法复杂 复杂程度高 ， 但是整体的路径 。 。 ， ， ， ， ， ， ， ， ， ， 、 、 ： 。 栅格法 蚁群算法 可视图法 神经网络算法 、 无人驾驶汽车路径规划中 目前无人驾驶汽车的全局路径规划算法主要有下面 自 可以将规划的 首先选择合适的算法模型将出发点 在这些小空间 ， 也就是将全局的 然后应用合适的算法对路径进行 几种类型 由空间算法等 过程分为以下步骤 至目标点之间的运动空间划分为小空间 内对是否存在障碍物进行设定和标定 障碍物信息标示出来 规划 得到最优路径 、 ， ： ， ， 。 ， 本文选择栅格法对空间进行分割 。 栅格法是基于地图 也就是用大小相等的栅格将无人驾驶 。 信息建模的方法 ， 作 者 简 介 ：原 静 （1992—），女 ， 陕 西 渭 南 人 ， 硕 士 ， 助 教 ， 研 究 方 向：交通运输规划与管理。 ， ， ， ： ， ， 。 。 Dijkstra 划分栅格 再根据栅格的位置对障碍物进行定位 用不同的方式表征小区域内是否存 因此 ， 对栅格内是 这样就可以通过 。 同时标示障碍物的 汽车的运动区域分开 在障碍物 栅格法进行路径规划的步骤如下 否存在障碍物进行编码 进行路径规划 不同的编码形式区分是否存在障碍物 大小和位置 1 A* 算法概述 直到到达目标点 算法是单源性质的最优化算法 将还未考察的点放入点集当中 应用该算法 该 从出发点向四周延伸和搜 这个算法需要对周围的每个点进行 最后得到的 可以获得任意一个节点到另外节点之间的最短距离 算法是将起始点作为出发点 索 查询和搜索 点集输出成为最优路径 最佳优先搜索算法 法 它与上述算法有一些相似之处 ， 法优先考虑路径规划中的时间代价 发点附近开始搜索 算法能够优化路径搜索的速度 算法规划出的有时候并不是最优路径 是另一种常用的路径搜索算 但是最佳优先搜索算 因此算法并非从出 该 而是首先考虑目标点附近的位置 。 但是 BFS 提升规划效率 。 （BFS） 。 。 。 。 ， ， ， ， ， ， ， ， ， ， A* Dijkstra 算法[3]。 A* 此算法鲁棒性好 算法是目前最常用的全局路径搜索算法 它的优点 是结合了最优搜索算法和 算法可以用 在 算法 于各类不同路况的路径规划 中初始点与当前栅格以及目标栅格三者的估价函数是由 初始点与其中一个栅格的真实代价和当前栅格与目标栅 可以使得该 格的预估代价二者共同决定[4]。 因此 提升 算法偏向于最优搜索算法或者是 ， 了找到最优路径的可能性且缩短了搜索路径所需时间 2 传统 A* 算法路径规划流程及缺陷 算法在栅格地图上进行路径规划 调整代价函数 ， 算法 需创建 Dijkstra 应用 A* 。 。 ， 。 A* ， 

2020 年 9 月上 农机化研究 》 Agriculture Mechanization Research 69 现提出改进的 从而使得前进方向不再受制于 算法 A* 即将相邻的 。 邻域算法需要逐个检查待考察栅格点的 算法的明显缺点为当临近的 个 规划的路径便被一定程度上限 8 邻域扩展为 π/4 。 16 8 的整数倍 16 改进 个临 首先需判断 。 16 个邻域栅格其中是否存在障碍 如果不 需要判 表中 OPEN 如果已存在 邻域算法如下 ， ： ， 再判断是否已存在于 ， 则添加至 表中 ， 针对上述分析 ， 表中 ， 16 ，A* 栅格中不存在障碍物时 制[6]， 邻域 后的 近点可否加入 OPEN 待考察栅格点周围的 栅格 在 断该栅格的价值大小 其次需要判断第 碍栅格 始点到目标点中途径障碍栅格 评价函数值 表中 如果存在 表中 就选择直接舍弃 OPEN OPEN 1～8 对 ， ， ， ， 。 OPEN CIOES 。 改进后的 邻域 16 A* 如有需要则对前向指针进行更新 ， 层栅格是否是障碍栅格 9～16 。 如果不是障碍栅格 。 如果有障 但是从起 计算临接点的 将其移至 ， 。 栅格 f ， 仍需舍弃 ， 表中最小代价的 表 和 传统的 表中 ， ， 选择 A* ， CLOSE 个栅格点纳入 OPEN 8 值 OPEN 将考察完的点从 重复迭代直至抵达预定目标点 即为最短路径的集合[5]。 编程仿真结果可得 OPEN 上述 OPEN 表中评价函数最小的点作为当前节点 S 算法是将起始点 的周围 计算各个节点的评价函数 并 ， 不停 表中 表中所有点 CLOSE OPEN ， 。 表中删除移至 此时 ， 邻域 8 A* 算法所规划出的 ， ， ， 8 线路平顺性差 路径不光滑 ， 所规划的路径过于靠近障碍 这主要是由于当前点周 算法中待考察栅格的 整数倍所 使得规划的路径安全性降低 个点中不存在障碍物时 最短路径存在较多转折点 并且在存在障碍物的地方 物 ， 围的 自由栅格与当前栅格的行进角度被限制为 造成的 3 改进双向 16 邻域 A* 算法 3.1 改进 16 邻域 A* 算法 。 ，A* π/4 。 算法增加了搜索的范围 最多可在 邻域 ， 此时 ， 个邻 16 的整数 π/4 因此规划的角度不再局限于 选取的最优节点将不再局限于 域中进行选择 倍 而是显著的增加了可能的方向 改进后的 邻域 8 ， 。 。 16 规划的路径距离减少 A* 算法规划的线路平顺性得到显 可以提高无人驾驶汽车行 搜索时间也显 ， 由于搜索范围的增加 但是 ， 。 ， ， 著提高 车的安全性 著增加了 。 ， ， 48 48 24 16 将 及 A* 个点 邻域 邻域及 ， 邻域 为了获得最优搜索算法 规划路径平顺性没有明显变化 ， 这是由于 围的 、24 法的最终规划的路径结果进行对比 的路径长度有所减少 是搜索时间显著增加 邻域及 了最优节点在未被考察前就删除的风险 [7]， 算法 均优于传统 。 使得需要搜索的点大大增多 的地图时 延误增加 。 时间及成本 都更优 将搜索的范围分别扩展到周 算 仿真结果表明规划 但 邻域均规避 48 因此规划结果 但是由于扩展的邻域太多 ， 尤其是如果处在比较复杂 搜索成本增加也使得 平顺度及搜索 ， 邻域 邻域及 搜索的时间会成倍增加 因此 综合考虑搜索路径长度 ， 邻域改进 算法较之 邻域 ，16 A* A* 24 24 48 8 ， ， ， ， 。 。 。 。 。 ， ， ， 8 16 16 A* A* 算法 邻域 ， 邻域 邻域的缺点 路径的平顺性高 3.2 双向搜索 16 邻域 A* 算法 算法规划路径短 ， 层层推进直到到达目标节点 直到获得同一个最优节点时 双向 但是 这主要是由于 存在着规划搜索时间长于 采用单向搜索的方式 也就是每一步都计算评价函数从而 因此提出 获得最优栅格点 从反向和正向同时推进开 双向改进的 实验结 始搜索 但是 果表明 A* 也存在下述缺点 规划所得路径存在明 ：1） 会出现搜 当搜索不到共同的最优节点时 显转折点[8]。 2） 索失败或者是算法陷入死循环的问题 [9]。 双向搜索 因此 ， 结束搜索进 算法的难点在于如何找到同一个最优节点 [10]， 程 当正 反搜索的同一个最优节点出现在起始栅格和目标栅格的 中间区域时 。 算法有效缩短了路径规划的时间 对算法的运行机制进行优化 为达到这个目的 搜索的时间最短 较之单向搜索 搜索停止 ， ， ， ， ， ， 。 。 ， 。 算法流程如下 ： 改进后的双向 表和 A* 先将两端点信息分 如 并将子节 ， 。 。 。 ， ， ， ， ， ， 表 即从 结束 即从 表中 CLOSE OPEN2 CLOSE2 如果找到 判断是否找到路径 同时更新正向当前点 表中 将其存入 表中 计算正向评价函数 别存入 OPEN2 OPEN1 果没有 则正向扩展子节点 ， ， 点存入 OPEN1 表中弹出表头 ， 判断是否找到路径 ， 算反向评价函数值 更新反向当前点 表中 ， 。 其存入 在 和 CLOES1 双向搜索 向前指针找到最优路径 。 留了 邻域算法的优点 同时大大缩短了路径搜索时间 4 结语 OPEN2 并将 表中根据各自 算法依然保 OPEN1 反向扩展子节点 ， 则需要计 并将子节点按一定顺序存入 CLOSE2 邻域 16 。 如果没有 表中弹出表头 算法缺陷的原因 算法是目前常用的全局性的路径规划算法 本文探索传统 为了提高搜索效率 但因 因此规划的路径并不能很好的应用于实 并据此扩大搜索 能够有效改 其存在着缺陷 际 。 节点 进传统的 A* 参考文献： [1] 彭晓燕 ，谢浩 ，黄晶.无人驾驶汽车局部路径规划 算 法 研 究 [J]. 算法路径规划结果 提出双向搜索算法 A* A* A* 16 ， ， ， ， ， ， ， ， 。 。 汽车工程，2020，42(1)：1-10. [2] 曾 鹏 ，万 华 森 ，王 一 霖.基 于 Vanet 的 无 人 驾 驶 动 态 路 径 规 划 算法研究[J].计算机工程与科学，2019，41(11)：2055-2062. [3] 李永丹，马天力，陈超波，等.无人驾驶车辆路径规划算法综述 [J].国外电子测量技术，2019，38(6)：72-79. [4] 郭蓬 ，吴学易 ，戎辉等.基 于 代 价 函 数 的 无 人 驾 驶 汽 车 局 部 路 径规划算法[J].中国公路学报，2019，32(6)：79-85. [5] 袁 师 召 ，李 军.无 人 驾 驶 汽 车 路 径 规 划 研 究 综 述[J].汽 车 工 程 [6] 高奇.无人驾驶 自 主 代 客 泊 车 路 径 规 划 与 跟 踪 控 制 策 略 研 究 师，2019(5)：11-13+25. [D].西安：长安大学，2019. [7] 刘春晓，马政，谢思锐，等.基于深度学习的无人驾驶路径规划 和控制[J].人工智能，2017(6)：72-79. [8] 杜星星.复杂环境下无人车局部路 径 规 划 问 题 研 究 [D].长 沙 ： 国防科学技术大学，2016. [9] 关泉珍，鲍泓，史志坚.基于 A* 算法的驾驶地图路径规划实现 [J].北京联合大学学报(自然科学版)，2016，30(2)：31-39. [10] 耿 以 才.基 于 动 态 人 工 势 场 法 无 人 驾 驶 汽 车 路 径 规 划 研 究 [D].上海：上海工程技术大学，2016.