数事技术每点用
算法分析
动态路径规划算法在车辆导航领域中的应用
岳双
(电子科技大学四川成都611731)
摘要：在车辆导航系统中，实时露况、交通管制以及其它一费影响交通状况的实时信息，是路径规划的一个重要参考因素，同时电是实现动态导航系统的至关重要的因素。本文研究了广泛应用于机器人据选的D*算法，结合实时路况信息和道路网络的一些特点，采增量启发式技索算法，并对D+算法进行了速当的调整和改进，将其应用予车辆路径规划，在初始环境信息基确上规划出一条从起点到目样点的最优路径，实现动态露径规则的更高效运行
关键调：智能交通系统动态路径规划实时路况信息动态导航
文章编号：1007-9416(2012)03-0095-02
文献标识码：A
中图分类号：TP18
1、引言
随着社会经济的高速发展，由于机动车增长迅速，再加上我国交通路网结构先天不足，道路交通承载的压力也越来越大，随之面来的是一大堆的交通问题：交通拥堵加剧，交通事故频发，交通污染严重这些问题严重阻碍了社会经济的发展和人民对舒适安逸生活的追求。面对诸多严峻问题，交通部门在从各个角度寻求解决方案，最直接的方式是通过修建道路，建设数量更多、等级更高的道路来实现，但是在一定的社会经济条件基础下，这并不是最根本的解决方法。因此实现对现有的道路交通基础设施进行有效利用，是我们在进行路径规划的时候必须要考患的间题。
路径规划系统是智能交通的研究的重要内容之一，它的核心任务是如何找出一条考虑了出行者路径选择行为的"最优路径”，以便于出行者利用该系统可以方便地在交通路网中顺利地从起始地到达目的地。路径规划系统中关键的间题是最短路径间慧，也是路径规划间题的核心。Dijkstra算法是经典的计算最优路径的算法之
生设计的，以几何距离、道路质量为路阻进行计算的最短路径和静态路径，这些都属于静态型最优路径。
但是传统的路径规划算法(如Dijkstra、A*算法等)大多仅应用于静态网络，也就是说，道路路径是在出行者出发前规划好的，路网中道路的权值是静态的、确定不变的。出来的结果是一条固定唯一的道路，一般是以行驶距离最短或行驶时间最短作为目的，然而实际的道路交通网络权值并不是固定不变的，而是随时间的变化在不断变化的，是动态变化的，也是随机的，因此传统的路径规划方法在现实生活中的应用没有多大的意义。如何结合当前现有的信息和我们对当时路网动态信息，利用合理的算法规划出一条满足实时最优
的动态路径是我们的研究方向。 2、动态路径规划算法的研究
常见的路径规划算法有Dijkstra算法，A*算法以及D+算法(动态A+)。Dijkstra算法是经典的最短路径算法，简单地说：A+算法基于Dijkstra算法的基础，给两个结点之间加上了估价值。而D+算法
D*算法即动态A+算法(DynamicAStar)，由卡内及梅降机器人中心的AnthonyStentz提出，D+算法最初用于机器人导路；当机器人在行进过程中，检测到前方环境发生变化，此时就需要机器人快速地重新计算出一条到达目标点路径。比较简单的方法就是在行进过程中以当前结点作为新的起始结点，计算到目标结点的最知路径，但是这样做算法的效率比较低下，Stentz提出的动态A*算法有效地解决了这个问题，提高了算法的执行效率，
D+算法将两个结点之间的路线看来一张带权值的有向图，这与很多最短路径算法相似，从起始结点出发，沿着有向弧的方向计算出一条到目标结点的路径，确保这条路径上的权值累加值最小，
即为两结点之间的最短路径。万方数据
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：表示从X到Y的返回指针：也就是说Y是X到G路径中的第个状态。
D+算法是一种DynamicA+算法，因此在某些方面还是有很多相似之处，与A+算法相似的是，D*算法也包含了用来存放扩展节点状态信息的OPEN列表。但是这些节点包含两种状态信息：Raise和 Lower状态。Raise状态用于表示由于弧段权值增加，致使路径传输成本的增加，Lower状态表示成本代价的降低或重新计算新的最优路径，节点的Raise状态和lower状态的改变，都会导致state在open 表中的迁人或迁出，同时需要将改变的相邻节点更新到open表中。在D+算法中需要有三种状态的表：new，open和closod状态。New状态表情是一个没有估计值h的状态，open状态表示是存在估计值，但是需要被传播到其他状态。而closed表表示存在估计是，且已经被传播。假设在计算的过程中，我们采用state(x)来标记每个节点的状态信息，则假如节点尚未被放人open表，则该节点state(x)为new状态；如果现已经是open表中的节点，则state(x)为open状态；否则 state(x)为closed状态。
在Open表中，K(G,X)是搜索过程的关键函数。由于h(G,X)在修改之前，并且X在Open列表中，则K(G，X)的所有值由h(G,X)来决定。在其传播过程中，假如K(G,X)=当前h(G,X),则在扩展过程中传播将会降低到后代及其它节点上，我们称这种状态为低位状态，如果K(G,X)<当前h(G,X),则传播将会提升到后代节点上或其他的节点上，同时也会尝试去寻找其他的更短路径。
在进行D+算法第一次搜索时，接照传统Dijkstra算法进行授索，但是搜索过程采用从目标节点到源点进行反向搜索，构造一条搜索路径，在搜索的过程中假如发现周围的运动环境发生了变化，例如障碍物的出现等，便会引起代价c(X，Y)发生了变化，如果X披标记为closed状态，这时需要更新h(x)，同时标记X为open状态，并用新的关键函数进行排队，然后再队列中运行process_state，直到当前的路径显示为最优或者open列表的队列为空。
D+算法虽然可以实现动态环境下路径规划和重新规划，但是，若要把用于机器人寻径的D+算法迁移到车辆路径规划或车辆导航领域，还是需要对算法进行一些调整。将D+算法应用于车辆路径规划中，我们需要利用任意时间算法和增量搜索思想将其与D+结合，
使改进后的算法能够更好地满足实时更新的动态要求， 3、增量式D*算法流程改进
经典的D*路径规划算法在遇到环境发生变化的情况下，会重