无人驾驶汽车规划A算法研究毕业论文

2020-02-13 15:01:41

摘要

本文在无人驾驶的背景下，基于matlab平台对A*规划算法展开了系统而完整的研究，详细介绍了A*算法的发展由来和进化路线，并对路径搜索算法也展开了介绍，并指出了A*算法存在的启发性不足导致路线冗余，鲁棒性不强，复杂地图处理能力弱这三大问题，同时介绍了生物智能算法在路径搜索问题上的应用，并详细研究了蚁群与路径搜寻的关系，最终融合了蚁群算法与A*算法提出了自己的算法流程，并运用自己的改进方法修正了本文所分析出的问题。

研究结果表明本文借助蚁群算法对于路线的局部优化能力较有效的改正了A*算法的路线冗余问题和鲁棒性弱的缺点，同时A*算法的全局性强的特性又弥补了蚁群的收敛缺点，两个算法互相弥补得到了较好的融合。

本文的特色在于创意性的将A*与生物智能算法相融合，同时把改进方向放在了冗余路线优化上，与现有的研究方向相区分又紧密联系。

关键词：A*算法；蚁群算法；冗余路线优化

Abstract

In the background of unmanned driving, this paper systematically and commylxetely studies the A* mylxanning algorithm based on matlab mylxatform, introduces the development origin and evolutionary luxian of A* algorithm in dqfjzil, and introduces the path search algorithm, and points out The insufficiency of A* algorithm leads to three major problems: luxian redundancy, weak robustness and weak commylxex map processing ability. At the same time, the apmylxication of bio-intelligence algorithm in path search problem is introduced, and ant colony is studied in dqfjzil. The relationship with the path search finally combines the ant colony algorithm and the A* algorithm to propose its own algorithm flow, and uses its own improved method to correct the problems analyzed in this paper.

The research results show that the ant colony algorithm can effectively correct the luxian redundancy problem and the weak robustness of the A* algorithm by means of the local optimization ability of the luxian. At the same time, the global strong feature of the A* algorithm makes up for the ant colony. The shortcomings of convergence, the two algorithms commylxement each other and get a better fusion.

The characteristic of this paper is the creative integration of A* and bio-intelligence algorithms, and the improvement direction is mylxaced on the optimization of redundant luxians, which is closely related to the existing research directions.

Key Words：A* algorithm; ant colony algorithm; redundant luxian optimization

第1章绪论.....................................................................................................................1

第2章文献回顾.............................................................................................................4

第3章算法改进.............................................................................................................6

3.1 地图的栅格化........................................................................................................6

3.1.1 地图概况.........................................................................................................6

3.1.2 地图表示方法.................................................................................................7

3.1.3 地图识别.........................................................................................................8

3.2 启发函数改进.......................................................................................................10

3.1.1 启发函数介绍................................................................................................10

3.1.2 传统改进函数................................................................................................11

3.1.3 启发改进函数................................................................................................12

3.3 路线冗余改进.......................................................................................................15

3.1.1 蚁群算法介绍................................................................................................15

3.1.2 蚁群算法融合................................................................................................16

第4章算法结果与分析................................................................................................22

4.1 地图结果...............................................................................................................22

4.2 A*算法处理结果...................................................................................................23

4.3 蚁群算法处理结果...............................................................................................24

第5章算法评价............................................................................................................31

第6章算法落地平台及展望.........................................................................................33

参考文献

致谢

第1章绪论

最短路径问题一直是图论，计算科学，运筹学等学科研究的一个热点，区别于路径规划问题，最短路径问题本身还存在一个搜寻的过程。最短路径问题希望能够找到图中两结点之间的最短路径。其中问题具体包括四个形式：已知起始节点和终点的最短路径，已知起始节点未知终点的最短路径，已知终点未知起始节点的最短路径，未知点求整张图上的所有最短路径。

A*算法作为一个状态空间启发式算法，主要解决的已知起始节点和终点之间的最短路径，同时由于我在大学期间学习的车辆工程专业，我将对于A*算法的研究设定在无人驾驶的背景之下，也就是在已知地图和起始点终点的情况下，最快，最优的找到一条无障碍的路线。算法参考

1.广度优先搜索：是连通图的一种遍历算法，它并不考虑最短路线的可能性位置，而只是彻底的搜索整张图，系统的对全局的点都展开并进行搜索。其基本的过程是，从开始的根节点开始，沿着每一个节点所有的邻点进行遍历，若所有的节点均被遍历过，则算法终止。

2.Dijkstra算法：通过已求出的最短路径的顶点到出发点的距离来考虑最短路线的可能性位置，是众多的启发性算法的原型。其引进两个集合S和U。S代表的是已求出最短路径的顶点(以及与之对应的最短路径长度)，而U代表的是还未求出的最短路径的顶点(以及目前该节点到起点s的距离)。基本的操作步骤：(1) 开始时，S只包含出发点s；U包含除出发点外的所有顶点，且U中节点的距离为'起点s到该节点的距离'[例如，U中节点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为infin;]。(2) 从U中选出'距离最短的节点k'，并将节点k加入到S中；同时，从U中移除节点k。(3) 更新U中各个节点到起点s的距离。之所以更新U中节点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它节点的距离；例如，(s,v)的距离可能大于(s,k) (k,v)的距离。(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

3.A*算法：在求取最短路径时引入启发信息，对状态空间的每一点是否是最短路线的可能性进行评估，从而省略一些无效的搜索，提高了效率。

4.IDA*算法：IDA*算法综合吸取了迭代加深算法和A*算法的优点，并将其互相融合互相补充。迭代加深算法的改进之处在于对于任意搜索的当前的节点的搜索深度，采用里递归搜索函数去判断其余预设的最大搜索深度，若大于成立，即关闭当前层的搜索，反之若不成立，则维持原搜索不变。因此遵循这样的搜索逻辑后得到的结果必然是最小值。与之相应的在A*算法中，通过对启发信息的合理运用，然后在可选择的节点里选择最小代价值的节点，以此得到搜索解的优化。但A*算法的缺陷在于始终要维持禁忌表和选择表，以及在状态检测和选择节点这些过程中，占据里电脑较大的内存。

而IDA*算法吸取里迭代算法占据内存较少的特性与A*算法的启发性的优点，产生里如下的思路：先设定搜索的最大深度H值为maxH，然后迭代进行深度优先搜索，并在选择下一步节点时忽略所有大于H的节点；若在此过程中，所有的待搜索节点的值都大于H，则逐步增大maxH，重复上述搜索过程，直到得到解。在这样的逻辑下，通过启发式信息得到的搜索节点若满足H,则可以保证得到的是最优解。并且在编程上，IDA*的难度也易于A*，因为其搜索节点不必保存，也不用判断是否已搜索，内存消耗较小。不过需要注意的是启发式信息在IDA*算法中也是通过估价函数的方式展现。

5.跳点搜索算法：JPS算法在保留A*算法的框架的同时，进一步优化了A*算法寻找后继节点的操作。JPS与A*算法主要区别在后继节点拓展策略上，不同于A*算法中直接获取当前节点所有非关闭的可达邻居节点来进行拓展的策略，JPS根据当前结点current的方向、并基于跳点的策略来扩展后继节点，遵循“两个定义、三个规则”（见表二，两个定义确定强迫邻居、跳点，三个规则确定节点的拓展原则）。jps算法判断状态空间的部分节点而非全部，是目前已知的最好最快的路径搜寻算法。

定义一，强迫邻居：如果点n是x的邻居，并且点n的邻居有阻挡（不可行走的格子），并且从parent(x)、x、n的路径长度比其他任何从parent(x)到n且不经过x的路径短，其中parent(x)为路径中x的前一个点，则n为x的强迫邻居，x为n的跳点）

定义二，跳点：（1）如果点y是起点或目标点，则y是跳点（2）如果y有邻居且是强迫邻居则y是跳点，（3）如果parent(y)到y是对角线移动，并且y经过水平或垂直方向移动可以到达跳点，则y是跳点。

规则一，JPS搜索跳点的过程中，如果直线方向（为了和对角线区分，直线方向代表水平方向、垂直方向，下文所说的直线均为水平方向和垂直方向）、对角线方向都可以移动，则首先在直线方向搜索跳点，再在对角线方向搜索跳点。

规则二，（1）如果从parent(x)到x是直线移动，n是x的邻居，若有从parent(x)到n的路径不经过x且路径长度小于或等于从parent(x)经过x到n的路径，则走到x后下一个点不会走到n；（2）如果从parent(x)到x是对角线移动，n是x的邻居，若有从parent(x)到n的路径不经过x且路径长度小于从parent(x)经过x到n的路径，则走到x后下一个点不会走到n（相关证明见论文）。

规则三，只有跳点才会加入openset，因为跳点会改变行走方向，而非跳点不会改变行走方向，最后寻找出来的路径点也只会是跳点集合的子集。

6遗传算法：依照生物进化论的思想进行创建的算法，与上述算法都不同的是，遗传算法是一种随机算法，但同时又具备了较强的方向性，因此它比一般的随机搜索类的算法的效率要高出很多。它的操作过程是对参数集进行编码操作，并用一个评价函数来评价该编码，在本文的背景下，可以将路线直接作为编码进行使用。遗传算法包括复制和交叉重组两个步骤进行，复制即对于问题的所有可行解，按照其评价值的高低按概率复制，复制的目的是为了改进做准备，就如同我们备份一份文件在新的文件上进行修改，而交叉重组，就是模仿人类的基因进化过程，将可行解的编码进行一部分互换，从而改变了解的性能。为了加快和全面进化的速度，遗传算法还存在变异和移民，变异即是对可行解的编码进行人为改动，移民是人为加入新的可行解，这些都是为了产生新的可行解，只有产生新的可行解才能为进化提供基础，才能找到最优解，在本文的背景下，遗传算法还有一个特别的概念，名为远亲交配，即将相差较多的两个可行解的交叉概率适当增大，这样在实际操作过程中，可以较有效的避免路径重复。

7蚁群算法：模拟蚂蚁觅食的生物习性而设计的一种仿生算法，蚂蚁会习惯找到最短的路。然后在用蚂蚁算法求解路径搜索问题时，首先将路径搜索优化的问题表达成与信息素相关的模式，然后在根据蚂蚁的前进方式，凭借局部信息素的含量，进行决策构造，并根据评价函数，对每一个解进行优劣评判，从而进行全局信息素的更新，这样的过程不断迭代，即可求出路径搜索问题的优解。

8元胞自动机算法：将现实的路线图抽象为一个无向图，并在此基础上，定义一个元胞集合为无向图的所有顶点，定义一个元胞的邻居集合为与该元胞相通的所有顶点，则元胞的状态就归为几种离散状态：未被寻路，已被寻路及其他，依据预先设定的变化规则，其邻居元胞的状态会因为根据规则而翻转，并且根据并行的规则，在不同的时刻元胞会向各自的节点演化，记录元胞的的变化信息，以此类推，必然有一个时刻终点也被元胞吞噬，即被寻路，则率先到达目标节点的元胞演化记录就是路径搜寻的最优路径。其中演化规则可设定为：假设t时刻，中心元胞，记为，起始元胞到中心元胞的最短距离为r(),则有以下四点演化规则：

（1）若为S_M状态，意味着当前的搜索点已经被搜寻过，状态保持不变。

（2）若状态，意味着搜索点刚好被搜寻，状态翻转为S_M。

（3）若为S_G状态，意味着搜寻点正在被搜寻，检验邻居：若邻居存在S_B状态且，则r()=,若-min()=0,则继续翻转状态空间为S_B，相反则状态不变。

（4）若为S_N状态，则继续考察其周边邻居，若存在S_B状态，则翻转为S_G，且。

以上为元胞自动机的基本思路，是模仿生命系统的自复制功能，一种空间时间均为离散，并且被时间因果关系和空间的相互作用所影响的局部网格动力学模型，将其与路径搜索相互联系，也是路径搜索生物智能算法里较主流的方法。

根据以上的算法介绍，我们可以得到如下结论：

（1）路径搜寻算法的改进思路基本可以总结为，更少的评估状态空间内的路线点，更准确的评估路线点的可能性距离。

（2）从算法的规划效果，时间复杂度和空间复杂度上来说：跳点搜索算法gt;IDA*算法gt;A*算法gt;Dijkstra算法gt;广度优先搜索。

（3）其中IDA*算法对于选择的临界阈值非常敏感，但在算法流程上它大大缩小了空间复杂度，而对于跳点搜索算法来讲，本质上它是将A*算法的估价函数细化，并且通过理论研究得到了很多先决条件，在这个方面空间和时间将不会再成为路径搜索方法的制约。

根据以上的算法介绍，我们可以发现在时间复杂度和空间复杂度方面，A*算法已经不是最优的算法，但它仍然是大多数算法的基础，但以上的算法解决的大多数都是如何快速，高效的得到最短路径，而并未将重点放在最短路径的再次优化上，因此本文希望解决的问题是，在牺牲一定的空间和时间的前提下，进一步的优化规划后的路线。

第2章文献回顾

A*作为一种状态空间启发式算法，最主要的区别在于它引入了启发信息的概念，对状态空间的每一个可能性的点都做出相应的评估，在判断出最优的位置，再从这个位置继续评估，直到搜索到终点。

在搜索的过程中，我们设置一个估价函数f(x)，对于任何一个待评估的点，估价函数的评估值为从出发点到评估点的最小路径的代价值g(n)与从评估点到终点的预计最短路径的代价值h(n)的加权值，而该种评价方式的得到的最短路径，我们称为A算法，而预计最短路径的代价值h(n)，正是启发式信息的由来。

对于任何一个h(n)lt;h*(n)的下界，表示的估值趋于保守，而采用该种下界作为启发式函数的A算法，我们定义为A*算法。

其中g*(n)是出发点到评估点的代价值，h*(n)是评估点到终点的预计代价值。

图一

图一显示了A*算范的逻辑思路，根据上述的逻辑思路，可以节省大量的无效搜寻。A*作为路径搜索的经典算法，在各个场景都有很强的实用性，并且针对不同的搜索情况都具有良好的适应性和扩展性。针对这个问题的研究者们对不同的搜索条件都做对算法做了不同的改进，王殿军对传统的A*算法存在的规划路径有过多冗余路径的问题提出了改进，并提出了路线转折处的最小转折角度，确定了路线的转向；辛煜等解决了运动方向被设定为/4的整数倍问题，通过无限领域的A*算法思想，但同时该思想增大了算法的计算复杂度，使搜索时间变长；顾尘在牺牲了一定的安全性的条件下，利用优先级的子节点生成方法避开路径穿过障碍物内；王红卫设计了一种平滑式的A*算法，当进行规划的两点之间无遮挡物时，将中间的节点删除，实质上是jps算法的一部分；周献中改进了启发因子，得到了直线性的优化，但消耗时间过多需要的约束条件过多；Botea发明了Hpa*算法，尽管该算法可以减少搜索空间，但不能总是得到最优的路径；Goldberg改进了启发函数以提高预计的准确度，但同样也造成了搜索缓慢的问题；高东明使用了一种双向搜索的A*算法来寻找最佳路径，并在计算距离时采取了多近邻的计算方案，提高了搜索的效率，但这种方法无法使用在较复杂的大型地图上。在对于A*算法的逻辑改进之外，还有针对于不同的场景改进，比如在红绿灯情况下的，不同交通状况下的多区域多层次规划，根据以上对于A*算法改进的介绍，我们可以发现，A*算法有以下几个问题尚待解决：对规划后的路线的冗余进行处理，对启发函数的多方向改进，移动路线的安全问题，对大型地图的搜索效率提升。为了继续研究A*算法，我将研究重点放在路线的冗余问题和启发函数的改进上。

第3章算法改进

3.1 地图栅格化

3.1.1 地图概况

无人驾驶作为代替人类手动驾驶的新课题，同人类的驾驶过程相似，存在着同样的行为逻辑：分别是：环境感知，高精度定位，行为决策，决策控制实施这四大步骤，对于人类来说，环境的感知依靠的是我们的生理构造，我们的眼睛与耳朵等信息感知构造，而对于无人驾驶来说，它需要的是摄像头，激光雷达，惯导系统，毫米波雷达等一系列的传感器以达到同样的信息接收的效果，并且转化为数字数据进行决策使用；对于高精度定位的环境，人们会将肉眼和耳朵等环境反馈的信息与大脑中的生理记忆进行对比，并且通过一系列比对过程后判断出自己在自己大脑空间感中的位置和方向，而对于自动驾驶来说，这一过程可以简化为将传感器所收集到的信息与本身存储在反应器中的地图数据，以此判断位置和方向，在这一环节内无人驾驶比人类有优势，因为相对于人的记忆系统，无人驾驶的芯片系统更有高效率和低误差的特点；在人进行高精度地图定位这一环节后，人类驾驶员会依照汽车知识和目的地等记忆规划将汽车开向目的地，而对于这一过程，自动驾驶需要完成的环节将变得多得多，自动驾驶为了模仿人类的决策系统，需要先对行驶路线做出规划，并且做出对于发动机，刹车，横拉杆等控制器的命令组合，最后才能完成行车的整体规划。由此可以发现，在无人驾驶的整体流程里，高精度地图是极为重要的，承担着坐标系的基地角色，并起到了高精度定位，规划辅助决策，环境感知等功能。

但无人驾驶所使用高精度地图与现在使用的车载导航地图有较大的不同，这些不同在于使用导航地图的使用者是人类，科普和认知是其重点，而高精度地图主要被提供给计算机，功能也与人类大大不同，在设施上，导航地图作为车载的休闲娱乐辅助系统，通常为了使用方便而配备显示屏等交互式工具，但高精度地图的划分领域属于车载安全系统，通常不需要显示屏，而在包含的数据上，导航地图仅仅包含科普类信息，例如主要建筑物，主要道路线条，而高精度地图则是一个详细的地图模型，包含道路及车道等局部模型，道路属性等多种与事实高度符合的信息。

高精度地图通常由静态高精度和动态高精度这两个层次组成。其中静态地图中包含了不变的道路车道部件等定位信息，还有道路细节例如车道数量车道宽度中心属性等数据，以及行驶规则例如那些区域可以变道，好让车辆可以准确的制动变道转向爬坡。而动态地图就跟贴近实时信息，例如前方是否拥堵，道路是否维修，有无交通事故，乃至天气状况都将纳入动态地图的考虑范围内，由于路网的变化是无法预知的，各种原先在静态地图上的标识点都看发生磨损与变化，这些变化需要及时体现在高精度地图上，不然就会在无人驾驶的规划路线中出现意外。

高精度地图的主要来源与传统地图是不同的，由于高精度地图需要实时更新，这使得传统地图的由自企业的采集方式变得不可行，而转变成为了多级采集体系，即变得自由化，行业化，社会化这三化方式来完成。

自由专业采集体系是由自己的高精度采集车在路边采集，与传统地图收集方法类似，即使用运输车，专业目的车如出租车的gps，摄像头等方式即时的传送道路信息，也是现在导航地图采集交通动态信息的方法之一。

但真正让高精度地图的采集与传统地图行业区分开来的，是众包模式，尤其是其中的UGC模式的重要性正在不断提升，新一代的高精度地图的来源将是每辆车上的摄像头，激光雷达，被采集的数据在云上进行处理，处理的方式包括但不限于深度学习技术，激光点云识别技术，大数据处理，最终将实现自动化验证和人机交互式体验。

图二

目前主流的高精度地图主要由以下两类公司提供。

首先是以Mobileye为代表的众包模式厂商，与之相似的有丰田，特斯拉，ABB HERE公司，其中Mobileye的重点在于路上的导流标识，信号灯，方向标识等路标，这些微观因素的收集可以改善由整到零的传统方式带来高成本低效率的缺点。丰田则采用车载摄像头结合Gps的方式最后在云端处理生成地图，特斯拉的方式更依靠自己生产的车的自身摄像头，绘制高精度地图并基于三维稀疏一维稠密的策略。ABB HERE的手段采用更多，Liar，GPS，摄像头都是他们的手机数据的工具。

而集中制图的公司主要有高德，百度，TOMTOM。高德采用了HAD级别的高精度采集车采集地图数据，以激光雷达和摄像头来进行三维模型搭建。百度也同样自研了数据采集车，其摄像头和高精度雷达可以精确识别交通标志，地面标志，车道线等标志物。较为不同的TOMTOM公司，其公司的测绘车的激光雷达设备的功能名为“深度地图”，该系统能够长时间观测路边场景的变化形状和距离，用这种方式去取代识别出每个具体的物体，并计算汽车自身的传感器的数据，分析整段道路，最终得到车辆的位置。

高精度地图作为无人驾驶领域的关键一环，在整个领域中处在核心和关键资源的地位，但高精度地图的准入资质和发展都还处在初级阶段，本文的介绍的目的是因为本文的重点算法规划需要在精度地图的基础上进行实施。

3.1.2 地图表示方法

对于我们目前使用的二维地图，应用于智能驾驶问题的环境建模方法主要有三种方法：栅格地图，直线地图，拓扑地图。

栅格地图：将整张地图表示为由边长相等的栅格组成，其中空白栅格表示可移动存在的区域，黑色栅格表示存在障碍物，不能被选取为路线点。其中在程序中，黑色栅格表示为1，空白栅格被表示为0。图3中我们给出直观表示。