基于矢量地图数据的路径规划算法研究

分析了矢量地图数据格式的特点,在进行路网拓扑信息提取和“分层分块”存储的基础上,比较了几种常用路径搜索算法;给出一种基于多级比例尺地图模型的多比例尺启发式最优路径规划算法,并对如何提高路径规划的实效性进行了探讨。     

基于最优路径存储的游戏寻径算法

研究了应用于游戏中的多个路径搜寻算法, 以及游戏路径搜寻的一些特点, 提出了基于最优路径存储的寻径算法. 主要是通过最优路径矩阵存储部分的最优路径, 减少大量路径的重复计算, 提高游戏中的路径计算效率. 针对游戏场景角色的移动引起路径点通行状态的变化导致当前的最优路径失效, 提出了路径更新算法, 更新最优路径矩阵当中的最优路径. 另外, 针对地图路径点规模增大的情况, 提出了地图路径点分块处理的策略, 然后对每一子块分别使用最优路径矩阵进行路径存储.     

基于 A* 算法与自适应分片的大规模最优路径规划

路径规划引擎是在线地图系统中一个至关重要的部分,静态路径规划算法是重中之重。现有的对A*算法的改进主要是通过预处理算法,对路网数据进行静态分层预处理,其效率过低。文章提出了一种自适应分层的思想,同时对A*算法的启发式函数进行改进,引入了方向引导函数,使得A*算法在日常路网上的可用性有了较大的提高。实际的路网实验表明,提出的算法的搜索效率、效果均优于同类算法,与标准层次A*算法相比,文章算法的搜索空间降低为原来的42%,搜索时间仅为原来的13%。     

基于电势场法的移动机器人全局路径规划算法

针对传统路径规划算法计算量大、电路映射地图建模复杂等问题,提出了一种基于电势场法的路径规划新方法.首先,为降低环境建模的复杂度,对Zhang细化算法进行了改进,获得能够细致描绘地图连通关系的骨干图;在此基础上,提出了一种基于电势场理论的模型建立方法,此后通过对模型电流通路的快速搜索获取初始路线,大大降低了路径规划算法的运算量;然后,基于内接圆角方法对路径进行平滑处理,解决了路径离散问题,得到适合服务机器人行走的最优路径.大量对比实验表明,该改进Zhang细化算法有效降低了建模及求解复杂度,提出的基于电势场法的全局路径规划算法很好地解决了传统算法搜索效率低的问题.     

基于出租车轨迹数据的最优路径规划方法

针对传统的路径规划算法并不一定能计算得到现实中最优路径的问题,提出一种融合了出租车驾驶经验并以时间为度量的路径规划算法。该算法的实现是将路径规划这个以计算为中心的技术变为以数据为中心的数据驱动挖掘技术。首先,从大量的出租车轨迹数据中提取真实的载人轨迹数据,并将载人轨迹数据匹配到路网数据中;然后,根据地图匹配结果计算路段的访问频次,选取前Top-k个路段作为热点路段;其次,计算热点路段间行车轨迹的相似度,对轨迹进行聚类分析,在路网的基础上构建该k个路段的热点路段图;最后,使用一种改进的A^*算法实现路径规划。实验结果表明,与传统的最短路径规划算法和基于驾驶经验路网分层的路径规划算法相比,所提出的基于热点路段图的路径规划方法有效地缩短规划路径的长度及路径行驶时间,提高路径规划的用时效率。     

用于热门路径查询的动态热度路网的构建方法

基于位置的服务在蓬勃发展的同时,产生出大量的用户位置轨迹数据,同时基于轨迹数据的热门路径问题也越来越受到人们的重视。对于求解点到点热门路径的问题,一张带有动态热度信息的热度路网是非常必要的。首先,提出了一个高效的交叉口生成算法,用于构建静态的热度路网,并在此基础上提出一种新的时间段分割算法来使得路网中对应热度边动态化。采用希腊雅典的一部分卡车的GPS轨迹数据集,通过大量充分的实验,印证了算法的合理性和高效性。     

基于分层路网的路径规划算法

为了提高路径规划的效率,提出了一种基于分层路网的二叉堆管理开启列表启发搜索算法。首先根据路网分级特点的存在,建立分层地图数据库,然后以启发式A*算法为主搜索方式,结合优先队列二叉堆来管理开启列表,完成路径规划。通过实验对比不同路径规划算法的平均耗时显示：启发式A*算法的效率是盲目式Dijkstra算法的4倍左右,同时在算法中引入二叉堆至少节省5%的规划时间。分层策略使快速路段所占比例达到90%以上,且将路径规划耗时控制在3s以内。实现结果表明,所提算法具有很高的运行效率,同时能满足驾驶者多走快速路段的行车心理。     

一种基于概率的路径预测与查询算法

研究了路网空间内的路径预测与查询技术,设计了基于统计信息和概率论的最优路径预测算法。实际应用中,路网错综复杂。提出可能路径集合的概念,并设计算法来提取当前路径预测涉及到的路网子网,减小路网规模和路径预测的复杂度。在空间网络环境下,现有移动对象位置预测技术主要针对短期预测,不能预测下一路口的交通情况。为了弥补这一缺陷,降低用户端的位置更新率,设计了路网移动模型来简洁描述提取自大量历史移动路径的移动统计特征,捕捉路口处转向模式。基于移动模型,提出了具有较高精度的交通预测模型来预测对象的运动路径。     

基于免疫遗传优化的实时交通路径诱导方法

传统交通路径规划方法忽略了对路径评估、选择的反复择优,导致路径的规划质量不高,路网通行效率无法有效提升.于是提出基于免疫遗传优化的实时交通路径诱导方法.根据出行者期望行驶速度,设定出行预期速率临界值,利用路网节点间的动态连通性优化路网架构,构建实时交通局部路网模型;计算局部路网中最短路径,在免疫遗传优化算法中加入单点交...     

基于物联网的智能交通系统车辆路径规划算法优化研究

本文提出了适用于智能交通系统的基于双向搜索的改进算法。典型的最短路径算法被认为是Dijkstra算法,其时间复杂度是O(n2)。但一个城市的路网地图有很多节点,该算法的时间复杂度高和解决速度慢。为了改变这种情况,我们从算法的设计方面进行了讨论,提出了改进的双向搜索算法。实践证明,改进后的算法能够提高了搜索速度,适用于智能交通系统。     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

A Hierarchical Path View Model for Path Finding in Intelligent Transportation Systems

Effective path finding has been identified as an important requirement for dynamic route guidance in Intelligent Transportation Systems (ITS). Path finding is most efficient if the all-pair (shortest) paths are precomputed because path search requires only simple lookups of the precomputed path views. Such an approach however incurs path view maintenance (computation and update) and storage costs which can be unrealistically high for large ITS networks. To lower these costs, we propose a Hierarchical Path View Model (HPVM) that partitions an ITS road map, and then creates a hierarchical structure based on the road type classification. HPVM includes a map partition algorithm for creating the hierarchy, path view maintenance algorithms, and a heuristic hierarchical path finding algorithm that searches paths by traversing the hierarchy. HPVM captures the dynamicity of traffic change patterns better than the ITS path finding systems that use the hierarchicalA * approach because: (1) during path search, HPVM traverses the hierarchy by dynamically selecting the connection points between two levels based on up-to-date traffic, and (2) HPVM can reroute the high-speed road traffic through local streets if needed. In this paper, we also present experimental results used to benchmark HPVM and to compare HPVM with alternative ITS path finding approaches, using both synthetic and real ITS maps that include a large Detroit map (> 28,000 nodes). The results show that the HPVM incurs much lower costs in path view maintenance and storage than the non-hierarchical path precomputation approach, and is more efficient in path search than the traditional ITS path finding using A* or hierarchical A* algorithms.     

基于数据库的城市道路中最短路径搜索

根据城市交通路网建设的实际 ,研究了描述城市交通网络图的城市道路数据库的组织结构 ,在此数据结构的基础上依靠 GIS技术的支持 ,采集了大量具体道路信息 ,采用 Dijkstra算法实现了快速最短路径搜索。根据城市的交通状况对交通网络图的边值赋予不同的权值可实现最优路径搜寻 ,给出了一个搜索实例——一个包含 6 1个交通路口的最短路径搜索结果的搜索时间约为 1.1s     

基于改进A*算法的移动机器人路径规划研究

A*算法广泛应用于移动机器人路径规划中，而传统A*算法在寻路时，普遍存在搜索时间较长、效率低下等问题，因此，采用双向搜索的方式，对传统A*算法加以改进，该算法在路径规划过程中，可同时进行正反向路径搜索，同时采用正反向搜索交替机制，保证了最终目标节点搜索在连线中点区域内相遇，从而缩短了寻路计算时间。在MATLAB平台上，针对改进后的A*算法进行仿真实验，结果证明，双向A*算法减少了规划时间，且可生成最优路径。最后，将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上，进行现场实验，实验结果表明，双向A*算法减少了寻路计算时间，从而使得路径搜索效率得到显著提升，且规划路径合理，满足路径规划要求。     

路网中基于地理位置和区域封闭性的最短路径的查询算法

针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。     

基于分层网络拓扑结构的最优路径算法

由于Dijkstra算法的基础是平面网络拓扑模型，因此当计算网络的节点数目较大时，计算的时间将急剧膨胀。为了快速地搜索到最优路径，基于分层网络拓扑结构（HiTopo），提出了双向分层搜索最优路径算法（BHWA）；该算法对现有分层路径算法进行了以下两点改进：（1）将分级网络的局部连通性作为划分子图的指标；（2）在路径计算过程中，使用弧段作为搜索目标，并采取了双向搜索策略。通过北京道路数据的实验表明：该算法在保持分层路径算法高效性的基础上，还提高了路径搜索结果的准确性；通过进一步研究表明，如果使用启发式搜索来对算法进行优化，则可以使算法的速度有更大的提升。     

一种适合于移动定位的路径搜索算法

随着3G时代的来临,在快速发展LBS业务中,一个重要功能是获得手机与手机之间或手机到地图上指定位置的最短路径.通过将路网划分成主干网与支路网,并且使用二级R*树来索引路网边,给出了一种获取手机周边道路与计算最短路径的算法.分析了该算法的复杂度,在适当划分主干网与支路网后,该算法可以缩小搜索空间,提高搜索性能.     

基于双向搜索的改进蚁群路径规划算法

针对移动机器人在复杂地图环境中移动耗时长、易陷入局部最优等问题,设计了一种基于双向搜索的改进蚁群路径规划算法。基于K-means算法对地图预处理,量化地图的局部复杂度程度,并将局部环境信息融合到状态转移概率函数,使机器人优先选择在复杂程度小的区域进行寻优,减少路径拐点。设定双向搜索规则,改进启发函数,提高算法的局部方向搜索精度和全局搜索效率。针对蚁群算法中蚂蚁遇到U障碍物陷入死锁的问题,提出死锁判断系数,增加了有效蚂蚁的数量,进一步提高了算法性能。仿真结果表明所设计的算法在复杂地图环境中相较于传统蚁群算法移动机器人的路径搜索效率更高。