一种基于改进A*算法的限制搜索区域的路径规划方法

摘要：本文根据已有A*算法，给出了一种改进的最优路径规划算法 ,此算法在根据道路的实际情况对路网进行分层的同时，根据实际路网的拓扑特性对搜索区域进行合理的限制，实验证明此算法在进行路径规划时节省了时间。

关键词：路径规划；搜索区域；A*算法

中图分类号：TP306文献标识码：A文章编号：1009-3044(2008)21-30523-02

An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach

XU Zhan-peng, LIN Kai

(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)

Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time

Key words: Path planning; Search region; A* algorithm

1 引言

路径规划是在车辆行驶前或行驶过程中寻找车辆从起始点到达目的地的最佳行车路线的过程[1], 它属于智能交通

系统中的最短路径问题的一个具体应用。

最短路径规划产生的路径分为两种：距离最短的路径和时间最短路径,其中前者相对比较易于实现，但是它容易忽略路径的具体情况和行车实际环境以及人为因素。因为在实际车辆行驶中要求不但在此路径上行车距离尽可能短，而且路径的行车环境尽可能好，即尽量走道路较宽、路面质量较好、红绿灯较少、红绿灯设置间隔较大、车流量较小的路径，避免走行车环境太差的路径。作者针对最短路径规划存在的不足之处 ,根据已有A*算法，给出了一种改进的最优路径规划算法，此算法在根据道路的实际情况对路网进行分层的同时，根据实际路网的拓扑特性对搜索区域进行合理的限制。

2 A*算法

A*算法是人工智能中一种典型的启发式搜索算法．也是路径规划算法中的常用算法，它通过选择合适的估计函数，指导搜索朝着最有希望的方向前进．以期求得最优解限制搜索区域的多层最优路径规划算法，A*算法评价函数的定义为[2]：

f(n)=g(n)+h(n) （1）

f(n)是从初始点通过节点n 到达目标点的估价函数；

g(n)是在状态空间中从初始节点到n节点的实际代价；

h(n)是从节点n到目标节点最佳路径的估计代价。它决定了搜索的效率和可采纳性。对于几何路网来说，可以取两点间欧氏距离（直线距离）作为估价值，即

其中，(xd,yd)、(xn,yn)分别为节点n 和目标节点在数字地图中的坐标。由于估价值h(n)≤n 到目标节点的距离实际值，算法具有可采纳性，能得到最优解。[3]

3 改进的A*算法球最短路径

本文在三个方面对传统的A*算法进行了更改：1)A*算法提到的权值会根据用户的不同查询条件来调用相对应的计算权值的公式；2) 添加了一个判断过程。当查询下一个临近边的时候首先查询交通控制策略，判断是否有管制信息并将相映的点从v中删除；3) 减少路径搜索的范围，以出发点与目的地点连线的中间点为圆心，以两点之间直线距离的二分之一再加上几公里为半径画圆，在圆范围内的路径参加搜索，在圆范围之外的路径不参加搜索。

具体实现如下：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点，设各个点的权值（也称为费用值）为g。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,计算X的估价值[4]。

1)初始的OPEN表仅包含原节点．其费用值g为0，令CLOSED为空表，设其他节点的费用为∞ 。

2)若OPEN表为空．则宣告失败：否则，选取OPEN表中所有的节点移至CLOSED表，将此CLOSED表作为新的OPEN表。重复第二步，直到深度达到4。

3)对第二步在深度4时形成的OPEN表进行操作，若OPEN表为空．则宣告失败：否则，选取OPEN表中具有最小权值的节点，并叫做最佳节点NEXT．把NEXT从OPEN表移至CLOSED表．判断此NEXT是否是一目标节点。若NEXT为目标节点．转步骤3，若NEXT不是目标节点。则根据地图数据库包含的联接路段属性扩展并生成NEXT的后继节点。对于每一个后继节点n，进行下列过程：

①计算节点n的费用：g(n)= NEXT费用+从NEXT到n的费用

②如果n与OPEN表上的任一节点相同．判断n是否具有最小的g值。若是最低的g值，用n的费用代替OPEN表中相同的节点费用。且建立匹配节点的后向指针指向NEXT

③如果n在CLOSED表中与一节点相匹配。检查节点n是否具有最小的g值，如果n具有最小的g值，则用节点n的费用代替匹配节点的费用。并把匹配节点的后向指针指向NEXT。并把该匹配节点移到OPEN表

④如果n不在OPEN表。也不在CLOSED表上，则把n的后向指针指向NEXT。井把n放入OPEN表中。计算节点n的估价函数：f(n)=g(n)+h(n)

例如图1，为带权的有向图。

根据步骤三，针对图1，算法的具体实现如图2。

4)重复第三步：

若在深度为7的搜索中找到目标结点且仅有一条路径，则该路径为最终路径，返回；

若在若在深度为7的搜索中找到目标结点并且有多条路径则回朔，比较找到的路径费用，取权值最小的作为最终路径；

若在在深度为7的搜索中未找到任何目标点则跳转到第五步。

5)从深度为7的搜索中的所有的NEXT节点回朔，即从NEXT的后向指针一直到原节点遍历节点，最后报告若干条路径，比较个路径费用，取费用最小的前100条路径继续重复第三步、第四步。由于h函数在满足h下限得条件下，愈趋近于h效率愈高，因此实际应用中，我们取的是节点到目的点的直线距离保证满足下限的情况下，尽可能的趋近h。

4 结语

实践表明基于改进A*算法的限制搜索区域的路径规划方法不仅在进行路径规划时节省了时间，而且规划后的路径大部分道路位于高层路网上，路径长度与最短路径长度之比小于1.1,可以被人接受，是行车意义上的最优路径。

参考文献：

[1] 付梦印.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报,2004(10).

[2] 赵亦林.车辆定位与导航系统[M].北京:电子工业出版社,1999:1-7.

[3] 王亚文.智能交通系统中路径规划算法研究与系统设计[D].陕西师范大学,2007.

[4] 杨雁莹.路径规划算法在车辆导航中的应用[J].福建电脑,2006(12).

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”