| 标题 | 增维启发式搜索路径规划算法 |
| 范文 | 吴宏 摘要：在智能无人车路径规划研究中，路径规划算法的效率一直是重要的研究问题。搜索状态空间过大、时间复杂度过高以及低效率一直是路径规划算法的瓶颈。本论文提出一种增维启发式搜索算法来解决的这一问题。该方法通过多阶段增加搜索空间维度，降低了搜索算法的状态空间从而提高算法效率。仿真实验结果显示，与一般的高维启发式搜索算法相比，该方法减少了87%的搜索状态，执行效率提高了近10倍。实验结果表明，该算法在算法效率与生成轨迹质量两方面取得一个非常好的平衡。 关键词： 增维启发式搜索； 智能车； 路径规划； 高效率； 平衡 中图分类号： TP311 文献标识码：A 文章编号：1009-3044（2016）36-0188-04 Increment-dimensional Heuristic Search Motion Planning Algorithm WU Hong （Department of Computer Science and Technology， Tongji University， Shanghai 201804， China） Abstract： For intelligent vehicle motion planning， effective enough is always an important issue. The huge statue-space， high time complexity of the high dimensional search approach is always the bottle-neck of the algorithm. To solve this problem， this paper proposes a new method， increment-dimensional heuristic search algorithm. This method is a stepped-up heuristic search to reduce the searching status and improve the search algorithm execution efficiency. In experiment， the result shows that this algorithm reduces 87% of searching status and executes time is nearly 1/10 of that of the traditional heuristic search method. It is a very good trade-off between execution efficiency and trajectory quality. Key words： increment-dimensional heuristic search； intelligent vehicle； motion planning； effective； trade-off 1 引言 在智能无人车领域，智能车无人车的行驶安全以及驾驶舒适度一直是一个非常重要的研究问题。而智能无人车的路径规划是这一问题的核心。智能无人车路径规划算法需要在有限的时间内，输出高质量高精度的路径，传输给智能无人车的控制模块、执行模块加以执行。一般的移动机器人路劲规划算法研究的是在高维度的空间里探索出一条路径，相比之下，智能无人车的路径规划则需要考虑车辆动力学模型约束，通常我们需要考虑四维状态。二维状态（x， y），表示车辆的地理坐标，车辆的航向角θ，以及行驶速度v。在四维状态空间里搜素出一条可行路径，是一个计算密集型的任务。与此同时，智能无人车的行驶速度可能很高，因此要求规划算法能够在一个非常有限的时间里给出搜索的结果。 为了解决这一问题，本文给出一种增维启发式路径规划搜索算法。该算法采取一种分阶段，逐步增加搜索维度的方法来生成路径。在每一个阶段，增维搜索算算法选择离车辆当前位置附近的一个区域，增加状态空间维度，进行启发式搜索。因此该算法的输出轨迹是多精度的轨迹。在车辆附近位置，输出轨迹为高维度高精度，充分考虑车辆动力学模型，驾驶舒适度，能耗以及可靠性。而在远处，低维度低精度的轨迹依然可以引导智能无人车的行驶方向正确，充分考虑的地图信息，障碍物信息。从人类正常的驾驶习惯上来说，驾驶员总是对近处的驾驶精度较高，而远处相对较低。该算法充分利用了这一点原理，牺牲了远处的轨迹精度，极大地提高了算法的运行效率。在频繁联系的反复规划中，车辆会一直执行高精度部分轨迹。因此，该算法在运行效率以及输出轨迹质量方面，取得一个非常好的均衡。 为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一个停车场，需要在目标停车位泊车。实验结果表明，相比传统的高维度启发式搜索算法，该算法减少了超过87%的搜索状态，运行性能提高了近10倍。 2 研究现状及文献综述 从20世纪70年代开始，欧美的西方国家开始无人驾驶汽车方面的研究工作，并在智能无人车的控制和商用化方面取得一定进展。在汽车工业非常发达的德国，各大汽车公司都资助或者联合高等院校以开发可在普通道路上行驶的智能无人车。目前，欧盟已启动一个名叫CyberCars的智能无人车项目，以推动智能无人车的研究和各国间智能无人车技术的信息共享。 在20世纪的80年代，我国部分大学开始智能无人车的研究工作，虽然起步较晚也取得一定成果。目前，从事这方面研究工作的 主要是国防科技大学、军事交通学院及清华大学等科研机构。[1-6] 在智能无人车决策模块的相关研究中，最核心的部分是路径规划算法的研究。文献[7]提出一种快速扩展随机树生成算法—RRT （Rapid-Exploring Random Tree）算法。RRT是一种多维空间中有效的路径规划算法。它以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或者进入目标区域，便可以在当前随机树中找到一条从初始点到目标点的路径。文献[8]在RRT算法在自动驾驶汽车以及宇宙空间探测器路径规划上的应用。文獻[9]对RRT算法提出优化方法并通过实验，解决了基本RRT算法存在的动态环境中规划路径不稳定的问题，同时提出双向RRT生成算法以及动态步长等优化方法，提高了RRT算法生成初始点到目标点路径生成的速度。然而RRT算法在规划路径的过程中产生的是可行解，而非最优解。文献[10]提出了RRT*算法，RRT算法进行了改进，保证了RRT算法生成解是渐进最优解。然而RRT*算法在时间复杂度上远高于朴素的RRT算法。文献[11]提出了一种RRT*算法加速的方法，通过使用预生成RRT随机树，在使用RRT*_S算法优化当前随机树，构造出与RRT*算法生成随机树本质相同的RRT*_S随机树，从而实现RRT*算法的加速。文献[12]为麻省理工学院将RRT*算法运用于叉车移动路径规划的一次应用实践，并对RRT算法与RRT*算法在实际应用中的结果给出对比分析。 文献[13][14][15][16]给出了2007年美国DARPA智能无人车比赛麻省理工学院（MIT）参赛智能无人车的整体架构，MIT智能无人车的轨迹生成算法，主要是用RRT算法生成可行路径，并对该路径进行平滑，以此为基础生成智能无人车运动轨迹。 文献[17][18][19][20][21][22]主要阐述了状态空间搜索算法，通过估价函数进行启发式搜索以及状态空间搜索剪枝。文献[23]提出了ARA*（Anytime A*）算法，对短时间间隔内连续反复用A*搜素算法进行空间状态搜索这一类状态空间搜索应用场景进行优化。 3 增维启发式搜索算法 增维启发式搜索是一种两阶段的启发式搜索算法。在算法的第一阶段，搜索出一条从车辆当前位置到目标位置的几何最短路的轨迹。在第一阶段的搜索，我们只考虑二维的搜索状态空间（x， y），即车辆的地理坐标。第二阶段，选取第一阶段的路径中的一个点作为本阶段目标点，搜索状态加入车辆的航向角θ，以及行驶速度v，总体状态空间提升到四维，并且考虑车辆动力学模型，在此状态空间下，搜索出一条高精度可执行的车辆行驶轨迹。 3.1 第一阶段搜索 在这一阶段，因为我们只考虑二维状态空间（x， y），即车辆的地理坐标。如果将状态空间离散化，这一搜索问题会退化成一个图论的最短路问题。虽然图论的最短路问题有很多经典成熟的算法。但是在这里还是有一些值得讨论的问题。 3.1.1 栅格随机化 一般地，在执行最短路算法之前，会把状态空间离散化成栅格，然后对栅格做4联通或者8联通处理，但是这种离散化方法会使最短路失去最优解，如图1a、1c所示。 图1 a. 离散化使得几何最短路失解；b. 随机化18联通栅格法；c. 8联通栅格法几何最短路（黑），随机化18联通栅格法几何最短路（红）。 为了解决这一问题。如图1b所示，算法使用一种随机化18联通的栅格法来离散化空间。即在栅格之间连边的时候，每个栅格除了相邻向相邻8个栅格联通，同时随机向其他10个栅格联通。选取的10个栅格满足与该栅格曼哈顿距离小于7，满足条件的格子约为100个，足以随机化，同时连边长度小于两个栅格长度，也方便计算是否与障碍物碰撞。 3.1.2 最短路算法 在离散化为栅格之后，采用单源最短路算法来计算车辆当前位置到其他位置的几何最短路，虽然单源最短路算法非常的经典成熟，但依旧有值得讨论的地方。 最短路的经典算法是堆优化的Dijkstra算法，该算法时间复杂度为 [O（eloge）]，其中[e]代表离散化后边的数量，然而在稀疏图中，SPFA算法的实际时间复杂度约为[O（e）]，在18随机联通结构的图中效率比价高，因而在本阶段中，我们采用SPFA算法计算单源最短路。 3.2 第二阶段搜索 在第二阶段的搜索中，我们选取第一阶段结果，几何最短路上的一个点来作为目标点，在搜索状态加入车辆的航向角θ，以及行驶速度v，在搜索中充分考虑车辆动力学模型，搜索出一条高精度可执行的车辆行驶轨迹。 3.2.1 启发函数 在启发式搜索过程中，一个强力有效的启发式函数对搜索效率来说至关重要。启发式函数不仅为搜索的实际代价提供了一个下界，同时也是实际代价的一个良好估算，可以引导搜索往正确的方向扩展，并且实现搜索剪枝，在第二阶段的搜索中，使用以下启发式函数。 动力学约束无障碍启发函数，[hnh（x，y，θ，v）]，该函数忽略障碍物信息，考虑车辆动力学模型，在此条件下求出最优的路径。这一启发式函数因为忽略了障碍物信息，只考虑动力学模型，所以可以离线计算、存储，在真实路径规划的过程中查询，计算速度极快。该函数极大的消除接近目标点航向角错误的搜索分支。 地图信息非动力学模型启发函数，[hh（x，y）]，该启发函数是上一启发函数的对偶函数，忽略车辆动力学模型，以几何最短路作为启发函数。该启发函数充分考虑的地理信息，消除了错误行驶方向的搜索分支。 结合二者，选取启发函数[h（x， y，θ，v）] = max（[hnhx，y，θ，v， hh（x，y））]， fxyv） = g（x， y， ，v） + h（x， y， ，v） （1） fxyv） Fxyv） （2） f 为状态[（x， y， θ， v）]的估价函数， g为当前搜索状态[（x， y， θ， v）]的实际代价， [F]为实际搜索代价。 在该启发函数的引导下，第二阶段启发式搜索可以高效地计算出四维高精度路径。 4 仿真实验以及实验结果 为了展示该算法的性能，本文进行了仿真实验。在实验中，智能无人车刚刚进入一個停车场，需要在目标停车位泊车。实验环境为Ubuntu 12.04 Linux系统，Intel i5处理器， 8GB内存。停车场大小为长80米宽50米，栅格离散化精度为10厘米，车辆采用72个不同的航向角，同时采用两个速度，最大的前向速度以及最大的后向速度。 图2 a朴素四维启发式搜索；b增维启发式搜索；c朴素四维启发式搜索输出路径；d增维启发式搜索输出路径 a
b c d 表1 算法性能比較 [ 阶段 朴素四维启发式搜索 增维启发式搜索 搜索状态数量 第一阶段 400000 第二阶段 10808634 408773 共计 10808634 808773 算法运行时间 （毫秒） 第一阶段 142 第二阶段 2844 141 共计 2844 283 ] 如图1b，对于每一次路径规划，增维启发式搜索算法可以有效地减少搜索状态的数量，因为高维度高精度部分的搜索集中在离车辆较近的区域，而从全局的角度，二维的几何最短路依旧引导着轨迹往正确的方向。相比之下朴素的四维启发式搜索搜索量极大（图2b）。从输出轨迹上看，两者的输出轨迹质量几乎相同（图2c、2d）。 5 结论 本文展示了增维启发式搜索路径规划算法。该算法分为两阶段。第一阶段在全局考虑二维的搜索状态空间，得出起始点到目标位置的几何最短路。在第一阶段几何最短路基础上选取一个目标点作为第二阶段目标状态空间，进而得到考虑了车辆动力学模型、四维的高精度可执行轨迹。仿真实验结果表明，在现实场景下，该算法极大地减少了搜索状态数量，提高了算法执行效率，同时输出高质量的智能无人车行驶轨迹。 参考文献： [1] 杨明.无人驾驶车辆研究综述与展望[J]..哈尔滨工业大学学报，2006，38（增刊）：1259-1262. [2] 孙振平.自主驾驶汽车智能控制系统[D].国防科技大学，2004. [3] 杨森森.基于GPS/INS/激光雷达的无人车组合导航[D].上海交通大学硕士学位论文，2013. [4] 钱钧，杨汝清，王晨，等，基于路标的智能车辆定位[J].上海交通大学学报，2007，41（6）：894-898. [5] 王曦鸣.军用无人车的路径规划与仿真研究[D].北京交通大学硕士学位论文，2010. [6] 曹玉芬，张国斌.美国无人地面车辆计划[J].国外坦克，2004（5）：25-27. [7] Rapidly-exploring random trees： A new tool for path planning. S. M. LaValle. TR 98-11， Computer Science Dept.， Iowa State University， October 1998 [8] RRT-based trajectory design for autonomous automobiles and spacecraft. P. Cheng， Z. Shen， and S. M. LaValle. Archives of Control Sciences， 11（3-4）：167--194， 2001. [9] Rapidly-exploring random trees： Progress and prospects. S. M. LaValle and J. J. Kuffner. In Proceedings Workshop on the Algorithmic Foundations of Robotics， 2000. [10] S. Karaman and E. Frazzoli， Sampling-based algorithms for optimal motion planning，I. Robotic Res.， vol. 30， no. 7， pp. 846C894， 2011. [11] Yun-xiao Shan Bi-jun Li Jian-Zhou Yue-Zhang，An Approach to Speed Up RRT* ，2014 IEEE Inteligent Vehicles Symposium （IV） June 8-11 [12] Karaman S， Walter M R， Perez A， et al. Anytime motion planning using the RRT*[C]//Robotics and Automation （ICRA）， 2011 IEEE International Conference on. IEEE， 2011： 1478-1483. [13] Leonard J， How J， Teller S， et al. A perception-driven autonomous urban vehicle[J]. Journal of Field Robotics， 2008， 25（10）： 727-774. [14] Kuwata Y， Fiore G， Teo J， et al. Motion planning for urban driving using RRT[C]//Intelligent Robots and Systems， 2008. IROS 2008. IEEE/RSJ International Conference on. IEEE， 2008： 1681-1686. [15] Leonard J， Barrett D， How J， et al. Team MIT urban challenge technical report[J]. 2007. [16] Kuwata Y， Karaman S， Teo J， et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology， IEEE Transactions on， 2009， 17（5）： 1105-1118.
[17] Barbehenn， M. and Hutchinson， S. （1995）. Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest path trees. IEEE Transactions on Robotics and Automation， 11（2）： 198–214. [18] Gaschnig， J. G. （1979）. Performance measurement and analsis of certain search algorithms. Ph.D. Dissertation， Carnegie Mellon University. [19] Stentz， A. （1995）. The Focussed D* Algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence （IJCAI）， pp. 1652–1659. [20] Pearl， J. （1984）. Heuristics： Intelligent Search Strategies for Computer Problem Solving. Boston， MA： Addison-Wesley [21] Hart， P. E.， Nilsson， N. J. and Raphael， B. （1968）. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics， 4（2）： 100–107. [22] Hart， P. E.， Nilsson， N. J. and Raphael， B. （1972）. Correction to “A formal basis for the heuristic determination of minimum cost paths”. ACM SIGART Bulletin， 37： 28–29. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。