手机贤集

工业平台

返回贤集网

无人驾驶汽车的路径规划方法、技术特点及优化

孤独到底 2021-06-15 16:48:18

摘要:路径规划作为无人驾驶汽车发展研究的关键技术之一,一直以来受到广泛的研究和关注。针对目前无人驾驶汽车在路径规划过程中存在的由于环境复杂度高、多约束、随机性强等情况而导致的无法规划获得最优路径这一问题,考虑无人驾驶汽车的实际应用以及研究现状,从局部路径规划和全局路径规划2个方面对无人驾驶汽车的路径规划方法进行综述,对各类路径规划思路、方法进行归纳与分析,总结了各种传统算法、类智能算法等路径规划技术的特点,为无人驾驶汽车最优路径求解这一问题的深入研究提供参考。

无人驾驶汽车的路径规划方法、技术特点及优化

如今人工智能技术得到了不断发展和应用,其中无人驾驶作为汽车逐渐智能化的一个方面备受关注。无人驾驶技术不仅可以减少由于驾驶员疲劳或操作不当等造成的交通事故以及拥堵现象的发生,而且可以提高能源的利用率,是未来汽车重要的技术发展趋势之一。路径规划作为无人驾驶汽车运行的关键环节,具有重大的研究意义。文章从全局和局部路径规划2个方面综述当前无人驾驶汽车路径规划中的各种算法,分别从算法的搜索收敛能力、算法的实时性以及算法的复杂程度等方面进行阐述,并分析比较各算法的优缺点,为今后的深入研究提供参考。


1无人驾驶汽车的路径规划


作为无人驾驶汽车顺利运行的重要环节,路径规划是指无人驾驶汽车在具有障碍物的环境中,能够规划出一条从起始位置状态到目标位置状态无碰撞的最优路径或次优路径,并满足所有约束条件,是实现汽车智能化的关键技术之一。根据路径规划的目标范围,可以将其分为全局路径规划和局部路径规划2种[1]。全局路径规划主要是对局部路径规划起到导向和约束作用,使车辆沿着导航系统提供的一系列期望局部目标点行驶。全局路径规划不算复杂,前提是有拓扑级地图,而局部路径规划是在车辆沿期望路径行驶时,通过车载传感器感知周围环境及交通信息,从而实现车道保持、动态避障等功能,又可以称作避障规划。局部规划要求算法具有较高的实时性,以应对实时变化的环境信息,这对传感器、算法的效率和处理器的运算能力都是极大的挑战,避障规划不仅考虑空间还考虑时间序列。目前,对于已知环境的路径规划,已存在很多成熟算法,可实现车辆无碰撞地到达目标地点,但在未知环境下,如何根据无人驾驶汽车的传感器实时探测到的局部环境信息进行路径规划,仍处于试验研究阶段。


1.1全局路径规划


全局路径规划是在已知的环境信息下,在事先已建好的环境模型中,去获得一条从初始地到目标地中符合一定性能的可行或最优的路径,其优点是保证了规划路径的最优性和可达性[2]。


全局路径规划在搜寻最优路径的算法上,根据搜索算法可分为图搜索类算法、随机采样类算法、智能算法等。图搜索类算法[3]主要包括Dijkstra算法[4]、A*算法[5-6]、D*算法等。与Dijkstra算法相比,A*算法增加了启发式估计,并减少了搜索量,提高了效率,同时保证了路径的最优性,但在环境复杂、规模较大时,效率仍较低。文献[7]采用仿真和试验相结合的方法,对AGV路径规划的A*算法和D*Lite算法进行了比较研究,比较的重点是生成轨迹的计算时间和生成轨迹的距离。结果表明,D*Lite能够以比A*更快的计算速度规划出更短的路径。然而,在某些情况下,D*Lite不如A*有效。这就表明选择哪种算法合适应该根据系统的需求。针对A*算法的不足,文献[8]将跳点搜索算法与原有的A*算法相结合,提出在生成最终路径的过程中,通过筛选跳点进行扩展,并且在扩展过程中,将A*算法中可能被添加到OpenList和ClosedList中的大量不必要的节点用跳点来替代以改进A*算法,减少了计算量。


文献[9]提出了一种优化路径的方法,即拓展Moore型元胞邻居结构,使得路径较原D*算法进一步优化。对于D*算法的改进,主要发生在路径长度和运算时间上。就D*算法的路径长度问题,提出了拓展Moore型元胞结构,将原D*算法的路径进一步缩短;与此同时,采用跳点搜索算法对原D*算法的运算速度进行一定幅度的提高。跳点搜索算法可以大量地节约内存,有效地提高运算效率,具有更快的速度、更高的空间复杂度。随机采样类算法主要包括概率路标算法、快速随机树算法,在复杂环境中得到了大量应用,如存在动态障碍物、高维状态空间和存在运动学、动力学等约束条件下的环境中,但这类算法存在耗费代价较大、实时性较差、可能规划得到非最优路径的问题[10]。智能仿生算法是一种模拟生物进化和仿生自然界动物昆虫觅食筑巢等行为的智能化算法,主要有遗传算法[11-12]、蚁群算法[13]、粒子群算法[14-15]等。遗传算法、蚁群算法适用于复杂问题的求解和优化,具有潜在的并行性的特点,但存在运算速度慢、解早熟的现象;与遗传算法和蚁群算法相比较而言,粒子群算法的优点主要在于收敛速度快。文献[16]提出了一种改进蚁群算法,应用在移动机器人路径规划中,对复杂环境下的机器人建立栅格模型,将指向上一节点的数组引入传统转移规则中,使算法逃逸能力得到了增强;在信息素更新中去掉最差蚂蚁释放的信息量,以利于种群的进化,使得在复杂环境中的路径搜索能力优于传统算法。


文献[17]提出的优化的蚁群算法改进了信息素的更新方式和状态转移概率、设置了信息素浓度的阀值,并引入了死锁处理策略,避免求解过程中的早熟现象,增加解的多样性,从而使蚂蚁搜索最优路径的范围缩小,能够降低搜索过程中的迭代次数以加快运算速度、提高搜索效率,从而使全局最优路径可以高效、快速地获得。文献[18]提出的基于滚动窗口优化的智能汽车轨迹规划方法,能够同时满足行驶安全和全局最优的要求,把路径曲线描述为6次多项式,并将路径规划问题转化为求解a6k的过程。该方法引入滚动窗口优化策略,用以解决智能汽车在多约束条件下、未知环境中生成全局最优轨迹的问题。

无人驾驶汽车的路径规划方法、技术特点及优化

1.2局部路径规划


局部路径规划是指无人驾驶汽车根据自身传感器获取到的周围环境信息,能够在未知或部分未知的周围环境中,自主规划出一条无碰撞的最优路径。用于局部路径规划的传统算法有人工势场法[19]、模拟退火法[20]、模糊逻辑法[21-22]、神经网络法[23]、动态窗口法、强化学习法[24]及基于行为的路径规划方法。人工势场法的优点是结构简单、计算量较小,但存在容易产生局部最小值的问题。文献[25]建立了改进的无人驾驶汽车人工势场模型,该改进模型通过利用高斯组合隶属函数在建立引力的目标点函数中,将障碍物约束和车辆约束考虑进去,并引入调节因子,解决了传统人工势场法容易陷入局部极小、目标不可达的问题。文献[26]把传统斥力势场中的实际距离利用椭圆化距离代替,并在传统人工势场法中引入道路边界斥力场模型,综合考虑了车道引力势能场、障碍物斥力势能场和道路边界势能场三者对汽车的影响,从而能够在较小车道空间内获得合适的汽车避撞局部路径。文献[27]结合车辆的实际运行情况,通过一种用正弦避障换道的方式,以最小安全距离作为对称距离的障碍点模型构建方法,使局部目标点处于对称轴线上,解决目标不可达和局部最小值的局部路径规划问题。


智能水滴算法模拟水流与泥沙相互作用而形成水道的机制,是一种新型的群落智能算法,在计算科学领域中,当求解的问题比较复杂时,可以应用该算法进行求解。但是对于路径规划问题,智能水滴算法在求解时,存在启发性不足的缺陷,会导致所规划的路径不理想。文献[28]针对原智能水滴算法的以上缺陷,通过变量更换、改进概率选择策略和更新机制,使得该改进算法的求解能力较原算法明显提高。模糊逻辑法是根据模糊的环境信息,依照对应表格规划出的信息,实现局部路径规划,优点在于容易计算,能够实时跟踪规划。文献[29]提出一种基于模糊控制的移动机器人避障方法,但模糊规则根据经验设定,存在经验不完备等问题,因此该算法灵活性差、存在未知短板。


可见,无论哪一种算法均存在各自的不足,因此,为了解决和弥补单一算法存在的问题和不足,可采用2种算法相结合的方法。文献[30]在研究移动机器人路径规划问题中,采用了双层路径规划思想,将改进遗传算法和改进人工势场法相结合,首先采用改进的遗传算法进行全局路径规划,解决最优个体丢失的问题;然后利用改进的人工势场法,对已规划好的全局路径进行局部动态避障,解决了局部极小点问题。文献[31]在蚁群算法搜索过程中加入人工势场局部搜索寻优算法,用局部扩散信息素代替人工势场法中的力因素,使蚁群在搜索过程中更倾向于朝着具有高适应值的子空间搜索,提高了蚁群的预避障能力。文献[32]将修正APF算法与模糊逻辑算法相结合,既解决了人工势场法规划中存在的局部极小值问题,又提高了算法在复杂环境中的有效性,并使用粒子群优化算法对模糊逻辑算法的隶属度函数进行了优化,使得在静态和动态的环境中能够快速作出响应并规划出合适的路径。


2结论


文章从无人驾驶汽车全局路径规划和局部路径规划两方面对目前文献中常见的规划算法进行了概括和分析。对传统经典算法,如人工势场法及其改进算法和智能算法,做出了分析,初步得出不管是哪一种算法都有其自身局限性和缺点,如人工势场法尽管具有算法简单、实时性好、规划的路径轨迹圆滑的优点,但是存在容易进入局部最小点、目标不可达的问题和不足;遗传算法、蚁群算法的不足在于存在容易陷入局部最优的问题;神经网络算法的不足则是需要大量样本。面对复杂多变的路径规划问题,采用单一的规划方法往往已不能取得很好的效果,因此趋向于将多种研究方法相结合,如将局部路径规划与全局路径规划相结合,如将在局部环境已知条件下可实现的局部路径规划通过滚动窗口优化原理进行前后衔接,可实现全局路径规划;传统规划方法与新的智能方法相结合。如将蚁群算法与强化学习算法相结合,全局或局部路径规划与动态环境路径规划相结合等,可得到更加完美的、用于无人驾驶汽车的路径规划算法,这些是今后研究的重点与难点。

无人驾驶汽车的路径规划方法、技术特点及优化

参考文献


[1]张旭,程传奇,郝向阳.一种兼顾全局与局部特性的机器人动态路径规划算法[J].测绘科学技术学报,2018,35(3):315-320.


[2]王春颖,刘平,秦洪政.移动机器人的智能路径规划算法综述[J].传感器与微系统,2018,37(8):5-8.


[3]SUN X,YEOH W,KOENING S.Moving target D*lite[C]//9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010:Volume 1 of 2.Toronto,Ontario,Canada:International Foundation for Autonomous Agents and Multiagent Systems,2010:67-74.


[4]康文雄,许耀钊.节点约束型最短路径的分层Dijkstra算法[J].华南理工大学学报(自然科学版),2017,45(1):66-73.


[5]FRANTISEK D,ANSREJ B,MARTIN K,et al.Path planning with modified A*algorithm for a mobile roboT[J].Procedia Engineering,2014,96(96):59-69.


[6]PERSSON S M,SHARF I.Sampling-based A*algorithm for robot path-planning[J].International Journal of Robotics Research,2014,33(13):1683-1708.


[7]SETIAWAN Y D,PRATAMA P S,JEONG S K,et al.Experimental comparison of A*and D*lite path planning algorithm for differential drive automated guided vehicle[J].Lecture Notes in Electrical Engineering,2013,282:555-564.


[8]赵晓,王铮,黄程侃.基于改进A*算法的移动机器人路径规划[J].机器人,2018,40(6):903-910.


[9]张希闻,肖本贤.改进D~*算法的移动机器人路径规划[J].传感器与微系统,2018,37(12):52-54.


[10]王全.基于RRT的全局路径规划方法及其应用研究[D].长沙:国防科学技术大学,2014:1-10.


[11]TIAN L F,COLLINS C.An effective robot trajectory planning method using a genetic algorithm[J].Mechatronics,2004,14(5):455-470.


[12]TSAI C C,HUANG H C,CHAN C K.Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J].IEEE Transactions on Industrial Electronics,2011,58(10):4813-4821.


[13]LISSOVOI A,WITT C.Runtime analysis of ant colony optimization on dynamic shortest path problems[J].Theoretical Computer Science,2015,561:73-85.


[14]DUAN H,LI P,SHI Y,et al.Interactive learning environment for bio-inspired optimization algorithms for UAV path planning[J].IEEE Transactions on Education,2015,58(4):276-281.


[15]EBERHART R,KENNEDY J.A newoptimizer using particle swarm theory[C]//International Symposium on MICRO Machine and Human Science.[S.l.]:IEEE,2002:39-43.


[16]刘锴,游晓明,刘升.复杂环境移动机器人路径规划的改进蚁群算法[J].计算机工程与应用,2016,52(13):60-63.


[17]左大利,聂清彬,张莉萍.移动机器人路径规划中的蚁群优化算法研究[J].现代制造工程,2017(5):44-48.


[18]张琳,章新杰,郭孔辉.未知环境下智能汽车轨迹规划滚动窗口优化[J].吉林大学学报(工学版),2018,48(3):652-660.


[19]RASEKHIPOUR Y,KHAJEPOUR A,CHEN S K,et al.A potential field-based model predictive path-planning controller for autonomous road vehicles[J].IEEE Transactions on Intelligent Transportation Systems,2017,18(5):1255-1267.


[20]KIRKPATRICH S,VECCHI P.Optimization by simulated-annealing[J].Science,1983(220):671-680.


[21]MAAREF H,BARRET C.Sensor-based fuzzy navigation of an autonomous mobile robot in an indoor environment[J].Control Engineering Practice,2000(8):757-768.


[22]WANG M,LIU J N K.Fuzzy logic-based real-time robot navigation in unkown environment with dead ends[J].Robotics and Autonomous Systems,2008,56(7):625-643.


[23]ER MJ,GAO Y.Robust adaptive control of robot manipulators using generalized fuzzy neural networks[J].IEEE Transactions on Industrial Electronics,2003,50(3):620-628.


[24]CHEN Y F,LIU M,EVERETT M,et al.Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning[C]//2017 IEEE International Conference on Robotics and Automation.Singapore:ICRA,2017:285-292.


[25]修彩靖,陈慧.基于改进人工势场法的无人驾驶车辆局部路径规划的研究[J].汽车工程,2013,35(9):808-811.


[26]唐志荣,冀杰,吴明阳.基于改进人工势场法的车辆路径规划与跟踪[J].西南大学学报(自然科学版),2018,40(6):174-182.


[27]安林芳,陈涛,成艾国.基于人工势场算法的智能车辆路径规划仿真[J].汽车工程,2017,39(12):1451-1456.


[28]宋晓琳,潘鲁彬,曹昊天.基于改进智能水滴算法的汽车避障局部路径规划[J].汽车工程,2016,38(2):185-191.


[29]杨小菊,张伟,高宏伟.基于模糊控制的移动机器人避障研究[J].传感器与微系统,2017,36(3):51-54.


[30]陈尔奎,吴梅花.基于改进遗传算法和改进人工势场法的复杂环境下移动机器人路径规划[J].科学技术与工程,2018,18(33):79-85.


[31]刘建华,杨建国,刘华平.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报,2015,46(9):18-27.


[32]ABDALLA T Y,ABED A A,AHMED A A,et al.Mobile robot navigation using PSO-optimized fuzzy artificial potential field with fuzzy control[J].Journal of Intelligent&Fuzzy Systems,2017,32(6):3893-3908.


来源:无人机公众号 重庆交通大学机电与车辆工程学院袁师召李军

注:文章内的所有配图皆为网络转载图片,侵权即删!

免责声明

最新回答

还没有人评论哦,抢沙发吧~

为您推荐