动态路径规划算法在车辆导航领域中的应用.pdfVIP

算法分析 术一用 动态路径规划算法在车辆导航领域中的应用 岳双 f电子科技大学 四川成都 611731) 摘要：在车辆导航系统中，实时路况、交通管制 以及其它一些影响交通状况的实时信息，是路径规划的一个重要参考因素，同时也是实现 动态导航系统的至关重要的因素。本文研究了广泛应用于机器人循迹的D★算法，结合实时路况信息和道路网络的一些特点，采用增量启发式搜 索算法，并对D 算法进行 了适当的调整和改进 ，将其应用于车辆路径规划，在初始环境信息基础上规划出一条从起点到 目标点的最优路径，实 现动态路径规划的更高效运行。 关键词：智能交通系统 动态路径规划 实时路况信息 动态导航 中图分类号：TP18 文献标识码 ：A 文章编号：1007—9416(2012)03．0095—02 1、引言 D 算法规定 ： 随着社会经济的高速发展，由于机动车增长迅速，再加上我国 c(X，Y)为从Y到x的代价，如果运动是不允许的，则c(X，Y)是 交通路网结构先天不足，道路交通承载的压力也越来越大，随之而 未定义的； 来的是一大堆的交通 问题：交通拥堵加剧，交通事故频发，交通污染 Nerghbors(X)：如果c(X，Y)或c(Y，X)被定义了，则任何的Y就 严重……这些问题严重阻碍了社会经济的发展和人民对舒适安逸 是Nerghbors(X)； 生活的追求。面对诸多严峻问题，交通部门在从各个角度寻求解决 o(G，X)：从X 到 目标点G的真正最优路径代价； 方案。最直接的方式是通过修建道路，建设数量更多、等级更高的道 h(G，X)：从x到 目标点G的最优路径代价的估计 ； 路来实现，但是在一定的社会经济条件基础下，这并不是最根本的 p(x)=Y：表示从xNY的返回指针；也就是说Y是X~IIG路径中 解决方法。因此实现对现有的道路交通基础设施进行有效利用，是 的第一个状态。 我们在进行路径规划的时候必须要考虑的问题。 D 算法是一种DynamicA{算法，因此在某些方面还是有很多 路径规划系统是智能交通的研究的重要内容之一，它的核心任 相似之处，与A 算法相似的是，D 算法也包含了用来存放扩展节点 务是如何找出一条考虑了出行者路径选择行为的“最优路径”，以便 状态信息的0PENCli表。但是这些节点包含两种状态信息：Raise和 于出行者利用该系统可以方便地在交通路网中顺利地从起始地到 Lower状态。Raise~态用于表示 由于弧段权值增加，致使路径传输 达 目的地。路径规划系统中关键的问题是最短路径问题，也是路径 成本的增加，Lower状态表示成本代价的降低或重新计算新的最优 规划问题的核心。Dijkstra算法是经典的计算最优路径的算法之一， 路径。节点的Raies状态和lower状态的改变，都会导致state在open 几乎 目前所有的路径算法方法都是在Dijkstm算法的基础上进行衍 表中的迁入或迁出，同时需要将改变的相邻节点更新~1]open表中。 生设计的，以几何距离、道路质量为路阻进行计算的最短路径和静 在D 算法中需要有三种状态的表 ：new。open和closed状态。New状 态路径，这些都属于静态型最优路径。 态表情是一个没有估计值h的状态，open状态表示是存在估计值 ， 但是传统的路径规划算法 (~Dijkstra、A算法等)大多仅应用 但是需要被传播到其他状态。而closed~表示存在估计是，且已经被 于静态网络，也就是说，道路路径是在出行者出发前规划好的，路网 传播。假设在计算的过程中，我们采用state(x)来标记每个节点的状 中道路的权值是静态的、确定不变的。出来的结果是一条固定唯一 态信息，则假如节点尚未被放入open表，则该节~state(x)为new状 的道路，一般是以行驶距离最短或行驶时间最短作为 目的，然而实 态；如果现已经是o