一种改进的分层路网的路径规划算法应用

吕方兴，方昕

一种改进的分层路网的路径规划算法应用

吕方兴，方昕

为了提高路径规划效率，提出一种改进的分层路网的路径规划算法。首先，城市路网进行分层处理，以经典A*算法为核心，在高层路网上使用改进机制，评估函数做相应调整，然后，对其权值设置上下限阈值，提高算法的搜索精度及搜索效率。实验结果表明，规划的路径并非Dijkstra算法的最短，但是改进的算法使快速路段所占比例达90%以上，实际运行最优。

分层路网；路径规划；A*算法；Dijkstra算法

0 引言

交通拥挤、道路状况已经成为智能交通系统（Intelligent Transportation System，ITS）重点解决的问题，其中路径规划显得尤为重要，即给定起点和终点，求解一条符合出行者心理需求的路径。此路径需要通过路径搜索算法求得，路径搜索可分为平面搜索和分层搜索两类。平面搜索典型代表是Dijkstra最短路径算法[1]，其时间复杂度为为O(n2)，效率较低。为了提高搜索效率，减少搜索范围，后来学者提出带有启发函数的A*算法[2]等。但这些算法求解的路径有时并非人们理想的“最优”路径，例如：司机希望在较宽的主干道上行驶，而并非小道小巷。于是，路网分层的思想及算法逐渐诞生[3-7]，但这些算法不能较好兼顾效率和准确率。而本文视图设计一种实用的改进分层路径规划算法，首先建立分层路网，结合A*算法采用OPEN表排序提高搜索效率，然后改变启发函数[8-9]改进A*算法在高层路网上搜索，以当前高层搜索节点到目标节点的距离作为评估值，通过权值在某一规定区间上的变化来控制算法的搜索范围和精度，最后通过实验验证改进的路径规划算法搜索效果。

1 分层路网

根据出行者习惯可以对一个城市路网进行分层处理，一般一个城市路网具有不同道路等级，目前我国将城市道路网络分为快速路、主干路、次干路及支路等[10]，快速路和主干路路况较好，不易拥堵，符合人们出行需求，而次干路和支路易产生拥堵。所以，在进行最短路径规划时，应尽可能选择高等级道路出行。但是，城市道路等级又不易划分过多，否则数据存储不便，因此本文将某市区MapInfo格式电子地图分为两层：高层路网包括城市快速道、主干道、国道、省道、县道等且连通和低层路网包括次干道、支路、市区小道等且与高层保持连通。同时，添加道路等级，节点名称及编号等重要属性信息。每条路段都有各自编号、头尾节点编号、路段距离、节点经纬度坐标、路段所在路网（0代表低层路网，1代表高层路网）。

2 分层A*算法

A*算法是一种启发式路径搜索算法，启发式搜索主要体现在评估函数：f(n)=g(n)+h(n)，f(n)代表从起点经由扩展点n到达终点的耗费，g(n)是起点到扩展点n的实际代价，可能被更新，h(n)是扩展点n到终点的估价值，保持不变。当h(n)总小于等于从n点到终点的实际代价值时，能保证得到最优解[11]启发函数h(n)采用扩展点到终点的欧氏距离，当h(n)=0时，f(n)=g(n)即演变为Dijkstra算法。因此，h(n)的选取是算法求解关键也是高层路网节点选取的切入点，可进一步缩小搜索空间，只存储快速路段。

分层A*算法首先判断起点与终点之间的欧式距离，当距离长时采用分层计算，当距离短时采用传统A*算法计算。分层计算分为三个阶段，前两个阶段分别从起点S和终点T出发，搜索高层路网的入口与出口节点（S1和T1），计算过程采用传统A*算法；第三阶段以S1和T1为高层路网的起点终点搜索一条路径，采用改进的算法求解。这种分层算法最终可以规划得到一条“S->S1->T1->T”的路径，此路径也许不是最短距离但却是最优选择。

3 改进算法及实现

改进算法[12]主要体现在高层路段即“S1->T1”，对评估函数f(n)=g(n)+h(n)的调整，算法思想：（1）获得S1和T1经纬度坐标计算两点间直线距离D。（2）计算当前节点的一个邻接点到终点T1的直线距离D1，若D1>D，则权值w=Q，Q小于1的常数，W∈[L，H]；否则W=D1 /D，W∈[L，H]，L和H是距离长度单位为m，根据经验设定。（3）启发函数修改为：f(n)=(1-w)*g(n)+w*h(n)，选取评估函数值最小的节点作为下一个当前节点。如此循环直到当前节点为T1为止，即找到了“S1->T1”的路径。设置w可以双重保证搜索效率和搜索精度，而算法时间复杂度最坏理论值为O（n2）。但是，由于在实际的路网中关联节点并不多且高层关联节点更少，改进A*算法在对OPEN表和CLOSE表扫描时时间复杂度可认为O（Cn），明显优于Dijkstra算法。

每个阶段算法实现的具体步骤如下：

初始化的状态：起点S，终点T，g(0)=0，h(0)=D(S，T)，f(0)=g(0)+h(0)，并将起点加入开启列表，采用最小二叉堆管理开启列表，使用OPEN表和CLOSE表。OPEN表存储最小临时节点，CLOSE表存储永久节点，每次循环从OPEN表选点并将其转为永久点。

（1）加载路网，设定初始状态。

（2）判断OPEN表是否为空，如果为空则寻路失败，退出循环；否则转向（3）。

（3）获得S和T所在路网层次，判断是否采用改进的A*算法，若为高层节点则采用改进A*算法，否则转入（4）。

（4）搜索OPEN表和CLOSE表，采用经典A*算法，找到由低层到高层的节点S1和T1，求解路径“S→S1”和“T1→T”。

（5）采用改进A*算法，求解路径“S1→T1”。

（6）连接三条路径“S→S1→T1→T”为最优路径，算法结束。

4 实验结果及分析

本系统采用某市区地图数据，将此算法在Visual Studio2005.net环境下用VC++编程实现，采用MapInfo8.0，MapX5.0整理和加载数据。为了更好统计算法性能，以实际道路长度和搜索时间作为参考，分别用Dijkstra算法、分层A*算法和改进的A*算法计算两个节点的最优路径，并在地图上使用不同颜色粗线条显示，随机选取几对起止点，统计各个算法搜索结果如图1、图2和表1所示：

图1 节点1025-1110各个算法搜索结果

图2 节点2325-1121各个算法搜索结果

表1 路径长度统计对比

图中蓝色线路为Dijkstra算法结果，黄色线路为分层A*算法结果，红色线路为改进算法结果。

硬件环境：Intel(R) Core(TM)2 CPU 6320，1.0GB；

操作系统：Microsoft Windows XP；

软件环境：Visual Studio2005，MapInfo8.0，MapX5.0;

从图1和图2中可以看到，分层A*算法和改进A*算法搜索路径主要以高层主干道为主，选取路况环境相对较好的道路，这样通常符合人们出行需求。从表1中也可看到，分层A*算法和改进A*算法搜索路径长度不一定最短。这是因为在选取主干道和快速道时可能会出现绕道情况。但是，改进的A*算法搜索路径长度较为接近最短，接近程度取决于参数w值(经验值），这说明改进算法能在一定程度上提高算法搜索精度。表2中各个算法求解时间会随着路径增长而加大，Dijkstra 算法增长最快，改进A*算法次之。Dijkstra 算法虽然能够找到最短路径，但是会随着路径长度增长搜索节点大幅增加。而改进A*算法会根据评估函数找到高层节点，减小搜索范围，提高了算法搜索效率。综合上述分析，改进后的算法即在一定程度上保证了搜索精度，又提高了算法运行时间，符合人们出行需求。

本文首先对实际路网进行分层处理，采用启发式搜索算法和二叉堆队列管理搜索列表实现路径规划。同时，为了提高算法搜索精度和搜索效率，对分层A*算法进行改进，修改评估函数，增加了权值。实验表明，改进后的算法总体优于原算法，并能够应用于实际的城市路网，但算法性能稳定性有待提升。

[1] Dijkstra E W.A note on two problems in connection with graphs[J].Numerische Mathematik, 1959,1 (1):269-271.

[2] Hart P E, Nilsson N J, Raphael B.A formal basis for the heuristic determination of minimum cost paths [J].IEEE Transactions on Systems Science and Cybernetics,1968,14 (3): 100-107.

[3] 李建元,师军．基于层次空间推理模型的交通网络最优路径算法［J］．计算机工程,2006,32( 20) : 207 - 209．

[4] 李清泉,郑年波,徐敬海等．一种基于道路网络层次拓扑结构的分层路径规划算法［J］.中国图象图形学报,2007,12(7) : 1280-1285.

[5] CAR A. Hierarchical spatial reasoning: theoretical consideration and its application to modeling way finding［D］. Vienna: Technical University of Vienna,1997．

[6] CHOU Y, ROMEIJN H E,SMITH R L. Approximating shortest paths in large-scale networks with an application to intelligent transportation systems［J］. Informs Journal on Computing Spring, 1998,10( 2) : 163-179．

[7] 李建元,师军,曹菡等. 一种分层寻路算法中的阈值放弃策略［J］. 计算机应用,2007,27( 2) : 473-478.

[8] Chen Xi. A new shortest path algorithm based on heuristic strategy[C]//Proceedings of the 6th World Congress on Intelligent Control and Automation (WCICA 2006), 2006:2531-2536.

[9] Qi Minju, Sun Huaining, Gao Guangfa. Research on an improved algorithm for shortest path searching in urban traffic based on GIS[C]//Proceedings of Electrical and Control Engineering International Conference, 2011: 1184-1187.

[10] 高立兵.汽车导航系统的动态路径规划优化模型与算法研究[J].甘肃联合大学学报:自然科学版,2012,26(1):55 -58.

[11] DAI Z Q, GUAN Y, GUAN R. Dynamicadjustment A* routing algorithm［C］./ / 2010 International Conference on Innovative Computing and Communication. Washington, DC: IEEE Computer Society,2010: 316-318.

[12] 钱红昇,葛文锋,钟鸣等. 基于分层的改进A*算法在路径规划中的应用[J]计算机工程与应用,2014,50(7):225-229.

5 总结

基于硬件的交互，另一种是基于计算机视觉的交互。基于硬件的交互需要比较昂贵的电磁式或光学式等跟踪设备，而且这些设备往往比较笨重，不便于携带，使交互操作受到一定的限制。基于计算机视觉的交互包括基于智能识别技术的交互。目前，识别目标不再局限于之前的黑白marker，而是把范围扩大到普通的2D图片以及现实中的立体物体，如照片、logo、海报的识别、人体识别技术、人脸、手势等识别等。而且对识别对象的识别响应速度也得到了大大提高，解决了识别的局限性的问题，增加了增强现实类产品的实用性。

3）跟踪注册

跟踪注册是为了使用户在真实环境的运动过程中保持虚拟场景在真实环境中的存在性和一体性。随着先进的2D图片跟踪及现实3D物体跟踪技术的发展，物体跟踪技术的稳定性有了明显的提高，能够进行识别的距离和范围都有了很大的提升，能最大程度的保证虚拟物体不丢失。跟踪注册技术效果的好坏直接决定增强现实系统的成功与否。

1.2 增强现实的应用领域：

溯江而下，江面的水产养殖，一度成为生态公害。珍珠、渔业这些新兴产业给村民带来财富的同时，也付出着昂贵的生态代价。

目前，增强现实技术应用的领域越来越广泛，如在市场营销上可采用AR互动大屏的方式，使现场的人与里面的虚拟场景进行互动，这样消费者更容易接受，更有亲切感和具传播性，如图3所示：

在移动端AR的应用上，用户可以扫下优惠卷就可以看到真实的优惠商品；扫下购买后的商品可以听到一首歌、一段视频、一个游戏或是其他有趣的互动；扫下餐桌就可以出现3D菜单随意搭配自己想吃的口味，这样有趣的体验，更利用产品营销推广。还如现在的3D试衣体验和谷歌眼镜用的就是增强现实技术。另外在其他的医疗、军事、电视转播等各方面都有应用，如图4所示：

2 基于AR-Builder的增强现实应用

2.1 增强现实编辑器（AR-Builder）

增强现实编辑器（AR-Builder）是由中视典公司在虚拟现实编辑器（VRP）的基础上开发的，面向增强现实行业的编辑器。它既具有VRP的绝大部分基础功能又包括了AR的核心技术。它可以让不懂编程的用户也能用PC/移动端针对动作捕捉设备创建增强现实互动应用。

增强现实编辑器使用了先进的2D图片跟踪及现实3D物体跟踪技术，在5米之外仍然能够识别对象。即使识别对象被遮挡只剩1/32时，软件仍能保证虚拟物体不丢失。

2.2 在主题公园互动的应用

在公园互动区域内，可以通过AR互动方式可以让游客进入虚拟地社区环境中，也可选择喜欢的场景，感觉亲临现场；让游客和各种动画人物亲密接触、拍照留念，也可以让动画人物和游客互动。 下面以迪斯尼乐园案例为例，介绍下基于增强现实编辑器（AR-Builder）的AR互动的具体操作流程：

1）先安装好3dsMax软件、再安装AR-Builder和VRP-for-3dsMAX插件，安装的路径选择3dsMax的安装路径，这样会发现3dsMax工具集中会多了一个[*VRPlatform*]菜单，如图5所示：

然后通过VRP_For_Max插件中的“导出”命令保存场景至.vrp文件。

3）打开AR-Builder，导入刚刚保存的vrp文件，从“增强现实”菜单中选择“插入节点”菜单项，将在界面左侧的场景树中增加一个新的“增强现实 1”节点，如图7所示：

图3 AR互动大屏的应用

图4 增强现实应用领域

图5 VRPlatform插件

图6 创建模型

图7 添加节点

4）选择识别对象：点击选择上一步中新建好的“增强现实 1”节点，界面右侧的属性栏中将显示此节点的属性。通过在属性栏中的“从库中选择卡片”、 “选择自定义图片”、“绑定KINECT动作”3个按钮选项，可分别设置黑白卡片（Marker）、普通图像与手势动作3种识别对象。

5）添加展示的虚拟内容：展示内容是指当识别到卡片或图像时，在其上叠加的对象。通过在“增强现实 1”节点属性栏中选择“绑定视频”，或将想要添加的三维物体拖到“增强现实 1”节点之下，可添加视频与三维模型两种展示内容。

6）添加交互脚本：通过脚本事件来实现交互目的。

7）测试运行：先将摄像头连接好，再点击 “测试运行”按钮，程序将开启摄像头。将摄像头对准识别对象，在其上将显示叠加的展示内容，如图8所示：

图8 选择识别对象

8）发布：点击工具栏上的“发布EXE包”按钮和 “发布IOS工程包”按钮，可分别发布到PC端和移动端。

9）通过摄像头获取现场画面，将将现场画面与虚拟场景融合后输出。

10）捕捉现场体验者的动作，电脑主机接收到动作信号后，触发虚拟场景动作，完成交互，如图9、图10、图11所示：

图9 绑定视频

图10 识别对象

图11 体验着交互

3 总结

虽然受到一些计算机视觉算法和移动设备硬件的限制，目前增强现实技术的潜力还远远没有发挥出来。将来随着这个问题的逐渐改善，我们所能体验到的视觉空间将得到极大延展。市场发展的脚步从不会停歇，增强现实技术应用前景是很广阔的。据美国市场研究分析公司ABI research的预测：增强现实的开发商将会在增强现实这个应用上投资巨大金额，分析师还认为“AR”这个应用将会成为“更加日常化的移动设备应用的一部分”尤其在市场营销、车载系统、游戏娱乐和医学医疗等领域将得到越来越广泛的应用。增强现实技术将成为展览展示的趋势；增强现实技术将成为市场营销的卖点；凭借车速和车距计算出行车安全性，AR技术能显示出对空间的感知能力，结合增强现实技术的车载系统将成为汽车标配；增强现实让游戏娱乐拉进现实；增强现实成为医生的“助手”；增强现实让图书更立体更互动。

参考文献

[1] 吴帆,张亮.增强现实技术发展及应用综述.电脑知识和技术.2012.

[2] 王贞东,肖租秀.增强现实应用研究.玉林师范学院学报(自然科学).2012.

[3] F. Niebling,etal. Using Augmented Reality and Interactive Simulations to Realize Hybrid Prototypes. in 4th International Symposiumon Visual Computing,Las Vegas,NV, 2008.

[4] Dengzhe Ma, Jurgen Gausemeier, Michael Grafe.虚拟现实与增强现实技术及其工业应用.上海交通大学出版社,2011.

（收稿日期：2014.11.16）

Application of an Improved Layered Path Planning Algorithm on Road Network

Lv Fangxing, Fang Xin
(Department of Electronic and Information Engineering, Ankang University, Ankang725000, China)

In order to improve the efficiency of path planning, an improved hierarchical path planning algorithm is been proposed on road network. First, classical A* algorithm as the core, urban road network is layered. Using an improved mechanism for high-level road network, the evaluation function is adjusted accordingly. Its weight is set upper and lower threshold to improve search accuracy and search efficiency. Experimental results show that the path planning length is not Dijkstra shortest, but the improved algorithm enables rapid road proportion is more than 90% and the actual operation of the optimum.

Hierarchical Road Network; Path Planning; A* Algorithm; Dijkstra Algorithm

TP311

A

2014.08.29）

1007-757X(2015)1-0059-03

陕西省教育厅自然科学专项项目（NO.14JK1014）；安康学院高层次人才项目专项（NO.AYQDZR201204）；安康学院高层次人才项目专项（NO.AYQDZR201203）；安康学院教材建设基金项目（NO.Jc201307）

吕方兴（1985-），男，黄淮学院，信息工程学院，助教，硕士，研究方向：测控技术，电气工程，安康，725000

方 昕（1985-），女，安康学院，电子与信息工程系，讲师，硕士，研究方向：智能优化、数据挖掘，安康，725000