EN中文

地球信息科学学报 >

2018 , Vol. 20 >Issue 6: 753 - 761

DOI: https://doi.org/10.12082/dqxxkx.2018.180019

2017年中国地理信息科学理论与方法学术年会优秀论文专辑

SA*：一种多线程路径规划算法

  • 孙经纬 , 1 ,
  • 孙广中 1 ,
  • 詹石岩 1 ,
  • 毛睿 2 ,
  • 周英华 , 1, *
展开
  • 1. 中国科学技术大学计算机科学与技术学院,合肥 230026
  • 2. 深圳大学计算机与软件学院,深圳 518060
*通讯作者：周英华(1978-),女,博士,高级工程师,主要从事算法优化与数据分析研究。E-mail:

作者简介：孙经纬(1992-),男,博士生,主要从事高性能计算与算法优化研究。E-mail:

收稿日期: 2018-01-02

  要求修回日期: 2018-03-10

  网络出版日期: 2018-06-20

基金资助

国家自然科学基金项目（61432016、61303047）

广东省普通高校国家级重大培育项目(2014GKXM054)

广东省普及型高性能计算机重点实验室（2017B030314073）

收起

SA*: A Multi-thread Path Routing Algorithm

  • SUN Jingwei , 1 ,
  • SUN Guangzhong 1 ,
  • ZHAN Shiyan 1 ,
  • MAO Rui 2 ,
  • ZHOU Yinghua , *, 1
Expand
  • 1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China
  • 2. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China
*Corresponding author: ZHOU Yinghua, E-mail:

Received date: 2018-01-02

  Request revised date: 2018-03-10

  Online published: 2018-06-20

Supported by

National Natural Science Foundation of China, No.61432016, 61303047

Guangdong Pre-national project, No.2014GKXM054

Guangdong Province Key Laboratory of Popular High Performance Computers, No.2017B030314073

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。

关键词： 多线程; 并行计算; 路径规划; 启发式搜索

本文引用格式

孙经纬 , 孙广中 , 詹石岩 , 毛睿 , 周英华 . SA*：一种多线程路径规划算法[J]. 地球信息科学学报, 2018 , 20(6) : 753 -761 . DOI: 10.12082/dqxxkx.2018.180019

Abstract

Path routing problem is a fundamental problem in many applications on road networks. The A* algorithm is an efficient method to find the point-to-point path. Road networks with Cartesian coordinates can provide Euclidean distance as a heuristic function to guide the search direction of A*, then A* can simply and intuitively outperforms the classic Dijkstra's algorithm. However, Euclidean distance is a fairly relaxed lower bound of the real distance. It limits the potential of pruning more search space of A* on road networks. Higher performance is needed to fit the real-time requirement in the application on large-scale networks. Parallel computing is an effective approach to accelerate many algorithms. However, there are strong data dependencies between iterations of A*, and each iteration has little potential parallelism because of the low-dimensional property of road network. Thus, it is difficult to efficiently exploit the availability of multiple cores with the standard A* algorithm. In this paper, we propose Segmented A* (SA*) algorithm, which is more adaptable to modern multi-core CPU platform than A*. It selects some waypoints that split the required shortest path into several segments, then it searches on each segment separately and concatenates these segments as an approximate result. SA* performs better than A* on account of two factors. One is that sequential SA* can prune more search space than A*. The other is that the searches of SA* on segments can be parallelized, so SA* can make better use of multi-core CPU. The selection of waypoints has a key impact on both calculation performance and the accuracy of path. To exploit the benefit from segmented search and meanwhile reduce the performance overhead from this selection, we consider using some low-cost heuristic strategies to select the waypoints before handling each path routing sub-problem. At first, we rapidly calculate a rough path as a guidance, then select the nodes in this rough path that uniformly split the path to several segments. We can easily guarantee that each segment has the same number of nodes. This split has more possibility to lead to a balanced search space in parallel calculating each segment. In our experiments, using 16 cores, SA* can be 30 times faster than A* on a large-scale real-world road network with a loss of path accuracy less than 10%.

Key words： multi-thread; parallel computing; path routing; heuristic search; road network

1 引言

路径规划问题是路网交通应用中的一个基础问题。通常情况下,路网可近似抽象为一个有向、强连通、稀疏、低分支、结点带有平面直角坐标的 图G=（V,E）,其中V为结点集,不妨令|V|=n,E为边集,|E|=O（n）。结点通常代表道路交叉口或者其他有特定意义的地点,而边则代表结点之间的道路 链接。每个结点具有笛卡尔坐标,而每条边e具有非负的权值w（e）,表示该边所代表的路段的长度或者通行时间。两点间的最短路径即连接给定的2个结点且权值和最小的一个边集合。本文主要讨论寻找路网上的点到点最短路径的方法。对于其他和路网有类似特征的场景,例如人工智能领域中的智能体规划、视频游戏等,本文的方法也同样适用。
最经典的路径规划算法为Dijkstra算法[1]和Bellman-Ford算法[2]。在使用了高效的优先级队列时[3],Dijkstra算法性能比Bellman-Ford更高效。 Dijkstra算法是针对一般化的图上的单源点最短路径问题的算法,不能充分利用路网的信息,同时对于求解点到点的路径而言产生了过多的不必要搜索操作,因此它在大规模的路网上实用性不高。
A*算法[4]是一个目标导向的启发式搜索算法。借助一个估值函数来估计当前结点到目标结点的代价的下界。A*算法可以剪去一些搜索分支,从而减少搜索空间,并且估值的准确性越高,搜索空间也越小。对于路网而言,两点间的欧几里得距离是一个相当简单直观的估值函数,可以使A*算法获得明显优于Dijkstra算法的性能。然而,欧几里得距离通常和2个结点之间的最短距离仍然存在差距,这使得A*算法的剪枝效果受到了限制。
双向A*[5,6]是对A*算法的改进。双向A*在原图上进行正向搜索,同时在反向图上进行反向搜索,在2个方向的搜索满足一定条件后得到最终的路径结果。2个方向的搜索空间之和通常小于原始A*的搜索空间,因此可以减少一定量的搜索空间。同时,2个方向的搜索可以一定程度地并行执行,因此相对原始的A*有一定性能提高,但并行规模只有2个线程。
双向A*搜索给进一步提升A*的性能带来一些启发：将搜索划分成多段,可以同时从2个方面提升性能,即减少搜索空间和产生可并行性。PRS（Parallel Ripple Search ）算法[7,8]体现出了这方面的思路。该算法通过在高级图（high level graph）上估计一些导航点（waypoints）,将其连接作为所求的路径。高级图是通过Girvan-Newman分层聚类产生的原图的一个缩略骨架。导航点则是高级图上的可能被待求最短路径经过的结点。PRS算法进一步强化了分段搜索的技巧,但其相应的代价为非常高的预处理时间复杂度。该方法需要至少O(n^3)的时间来产生高级图,其中n为图的结点数。
本文提出一种基于分段搜索（segmented search）的A*算法,称之为SA*,用于寻找大规模路网上的两点间近似最短路径。该算法首先快速计算出一条从给定的起点到终点的粗略路径,选择该路径的k等分点作为导航点,然后并行执行k个A*搜索求得一条精度较高的路径。求得的路径长度相对于实际的最短路径长度的相对误差有一个松弛的理论上界。实验结果表明,在实际运行中产生的误差远远小于该上界。
本文的主要贡献有：
（1）本文提出SA*算法可用于寻找大规模路网上的近似最短路径。原始A*算法由于具有天然的串行性而难以充分利用现代处理器的多核架构。SA*通过一些技巧使得A*的搜索空间减少,同时又可以比较合理地并行执行。
（2）SA*作为一个算法框架,可以在各个组成部分上选择不同的实现方法,从而在路径的精度、求解速度、实现复杂程度等方面做出权衡。本文使用了基于简单的欧几里得距离和二叉堆实现的A*算法作为每段的搜索方法,主要关注点为分段方法所带来的并行性。在每段的搜索上应用更复杂的搜索策略,可以进一步提高SA*的性能。
（3）SA*算法无需对图进行预处理,因此该算法可以更加灵活地处理图的动态变化,也更适用于图是基于临时目的生成（如紧急情况导航、视频游戏中的随机地图场景等）,没有大量的路径查询请求来分摊预处理的开销情况。

2 启发式搜索

Dijkstra算法是一个无目标导向的搜索算法。该算法按照从源结点到当前结点的距离递增的顺序依次扩展当前搜索空间的边界,直到扩展到目标结点。无目标导向的搜索空间在路网上则表现为以源结点为中心的近似圆形,并且当目标结点较远时,搜索空间几乎覆盖整个图,如图1（a）所示。
Fig.1 Comparison of search space of different algorithms

图1 不同算法的搜索空间比较

针对Dijkstra无目标导向搜索的缺点,A*算法加入了启发式函数用于估计当前结点到目标结点的距离,即所谓的启发式搜索。A*算法在搜索时,更加倾向于先扩展离目标结点更近的结点,因此搜索空间在路网上表现为由源结点指向目标结点的叶形,如图1（b）所示。算法1给出了A*算法的步骤。通常,启发函数的估值越接近真实值,则减少的搜索空间越多。A*算法实际上是Dijkstra算法的一般化情况,当启发函数h的值恒为0时,即退化为Dijkstra算法。
算法1 A*算法
输入: 图G,结点s, t
输出: 从s到t的最短路径path
1. f[]初始化为无穷大inf
2. 初始化优先级队列queue
3. S为空集
4. s入队列,f[s]=g[s]=0,u=s
5. while u!=t&&!queue.empty（） do
6. u=queue.pop（）;
7. S=S∪{u};
8. for each u的邻居v do
9. h[v]=v到t的估计距离
10. if （g[u]+d（u, v）+h[v]<f[v]）
11. g[v]=g[u]+d（u, v）;
12. f[v]=g[v]+h[v];
13. path[v]=u;
14. return path;
当启发函数为可满足（admissible）和一致（consistent）时[4],A*算法可以返回最优解,即给定两点间的最短路径。可满足是指启发函数所估计的距离始终不会超过真实的最短距离。一致是指任意3个结点间启发函数的估计值满足三角不等式。使用欧氏距离是一个简单直观的可满足且一致的启发函数。然而,路网上2个点的欧式距离通常和实际距离有差距。在美国路网上随机抽取1000点对之后计算每对点之间欧式距离和实际距离的比值,其分布情况如图2所示。该路网数据来自9th DIMACS比赛的数据集[10-11]中的USA地图,其中距离使用的是抽象单位,不对应任何实际单位（m、km等）。
Fig. 2 The estimation accuracy using Euclidean distance

图2 使用欧氏距离进行估计的精度

路网上可以有更精确的估值作为启发函数,从而提升A*算法的性能,但这通常需要一定时间的预处理来获得。在一些实际应用场景中,图的边权值和拓扑结构往往处于动态变化中,使得离线处理得到的辅助信息部分或者完全失效。无离线处理的算法则可以更好地适用于动态的场景。
双向A*搜索提供了从另外一个方向来提高A*性能的思路。该算法通过将搜索分成正向和反向 2个搜索,减少了总搜索空间,同时产生了一定的可并行性。图1（c）展示了双向搜索的搜索空间。然而双向A*只有至多2线程的并行规模,因此仍然难以完全利用目前常见CPU中的4核甚至8核的计算资源。

3 SA*分段搜索

本文提出Segmented A*（SA*）算法,尝试通过划分更多的搜索分段使A*算法获得更好的加速效果。SA*算法的整体框架如算法2所示。当给定源结点s和目标结点t之后,SA*从图中选择k+1个结点作为导航点,其中的m0和m0分别指代源节点和目标结点。所选择的k+1个导航点将搜索分成了k段,每一段执行常规的基于欧氏距离的A*算法,最终拼接成一条路径作为结果输出。由于每一段的搜索相互之间不存在依赖关系,因此可以很直接地实现并行化。在共享内存并行系统上实现的SA*算法,每一段的搜索结果直接写入到Path的对应位置即可,拼接路径段的过程实际上并不需要做任何实际操作。
导航点的选择对算法的性能和结果的精度都有直接的影响。下文将详细讨论导航点的不同选择策略。
算法2 SA*算法
输入：图G,结点s和t,分段数k
输出：从s到t的近似最短路径
1. 产生导航点m0, m1 ,…, mk,其中m0=s,mk=t
2. parallel-do
3. 使用A*求解mi到mi+1的最短路径,0≤i<k
4. 将k段路径拼接并作为结果返回

3.1 按直线选择导航点

对于2个点间的最短路径,一个常见的假设最短路径上的结点通常不会偏离直线s-t太远,尤其是当路网结点在平面上分布比较密集且均匀,且s到t的距离较长时,因此可以考虑选择线段s-t附近的结点作为导航点。选择k等分点附近的结点可以获得相对较为均匀的段划分。令（xs,ys）和（xt,yt）分别表示源节点和目标结点的坐标。则s-t线段上的第i个k等分点的坐标为：
x i = x s + i × ( x t - x s ) / k y i = y s + i × ( y t - y s ) / k （1）
为了快速查找到s-t线段上k等分点附近的结点,需要记录其邻域内的结点。网格划分可以简单方便地确定一个结点的邻域。由于网格划分可以在载入图数据的同时完成,因此可以认为其开销忽略不计。确定网格边长L后,可以很容易通过结点（x, y）找到对应的网格（row, col）。令图数据的坐标下界为xmin和ymin,则有：
row = ( y - y min ) / L col = ( x - x min ) / L （2）
因此,按直线选择导航点的方法如下：当源节点和目标结点给定后,借助式（1）求出s-t线段的k等分点;用式（2）由每个等分点的坐标求得该等分点所在的网格,然后随机选择网格内的某个结点作为导航点。确定导航点之后,即可使用常规的A*算法在2个相继的导航点之间进行搜索。图3显示了k=2和k=4时的搜索示例,与图1（b）相比搜索空间明显减少。
Fig. 3 The search space of SA*

图3 SA*的搜索空间示意图

3.2 按路径选择导航点

按直线选择导航点的思路非常简单直观,但其仍然存在一些问题,产生的结果误差难以估计。“最短路径通常在线段s-t附近”这一假设并非总是成立,尤其是当s和t相距较近的情况下,可能会产生较大的误差。由于导航点选择没有基于更丰富的地图语义,可能导致路径的经由地点不符合常识和情理。另外,尽管选择s-t线段的k等分点有助于获得较为均匀的划分,但每一段的实际搜索开销与图的结构关系比较复杂,简单地按s-t线段等分并不能有足够好的均匀划分。
另一个选择导航点的思路：首先快速计算出一条从s到t的粗略路径,即一条误差较大的路径,然后选择该路径上的k等分结点作为导航点。作为引导,粗略路径相对于线段来说更具有合理性,可期望获得更均匀的路段划分。
计算粗略路径的方法至关重要。首先其本身的计算开销需要尽可能小,若选择导航点的开销过大,则之后的分段A*搜索就失去了意义。另外,需要控制其误差。本文选择了一种A*算法的变体[9]来计算粗略路径。在算法1中,可以给估值函数h乘以系数e。常规的A*算法可以视作e=1.0,从而保证估值函数是可满足的。若令e>1.0,A*算法可以更快速地搜索到目标结点,然而无法保证计算出的路径是最短的,因为2个结点之间的欧氏距离乘以大于1的系数之后可能会大于结点间实际距离的长度。文献[9]证明了相对误差的上界是e-1。

4 实验验证与分析

4.1 实验设置

本节将通过实验来验证SA*算法。使用的机器配置为双路Intel Xeon E5-2680 v3 2.5GHz 12核,64GB DDR4 2133MHz ECC REG主存。实验程序使用C++编写,ICC 13.1.0编译,在CentOS 6.5上运行,使用OpenMP进行并行化。
实验数据选取了若干大规模真实路网数据。数据来自于9th DIMACS比赛的数据集[10,11]。表1列出了本文所使用的数据集的信息。在该数据集中,边权值的单位为抽象单位,不对应任何实际使用的距离单位（如m、km等）。
Tab. 1 Basic information of dataset used in experiment

表1 数据集的基本信息

数据名 结点数 边数
USA 23 947 347 58 333 344
W 6 262 104 15 248 146
E 3 598 623 8 778 114
CAL 1 890 815 4 657 742
NE 1 524 453 3 897 636
NW 1 207 945 2 840 208

4.2 实验结果与分析

实验比较了A*和不同参数下的SA*的性能。对于每个实验数据集,随机选择2000对源结点和目标结点,寻找路径,记录其时间开销。表2列出了不同方法的平均时间开销,其中SA*包含了导航点选择的耗时。A*算法使用欧氏距离作为估值函数,使用二叉堆作为优先级队列。在SA*中,每一段的搜索分配一个线程,因此实验中k段搜索使用k个核并行执行。表3列出了SA*在不同参数下的相对误差,即求得的路径长度与实际长度间的差值与实际长度的比值。
Tab. 2 Comparison of average calculation time cost （in milliseconds） using different methods

表2 不同方法的平均计算时间（ms）

方法 分段 NW NE CAL E W USA
A* N/A 105 129 178 318 423 1524
SA*(line) k=2 44 50 79 131 146 513
k=4 22 35 39 64 64 200
k=8 14 32 20 42 34 99
k=16 11 33 13 39 24 72
SA*(path) k=2 38 50 68 116 137 465
k=4 15 22 27 46 52 169
k=8 8 14 12 23 24 75
k=16 5 11 6 15 14 47
Tab. 3 Comparison of average relative error using different methods

表3 不同方法的平均相对误差（%）

方法 分段 NW NE CAL E W USA
SA*(line) k=2 6.5 6.4 6.5 4.5 5.1 1.9
k=4 17.0 13.3 17.0 12.2 13.4 5.5
k=8 36.5 26.2 36.5 23.1 30.1 12.5
k=16 66.8 49.1 66.7 45.5 61.2 33.1
SA*(path) k=2 3.2 1.4 3.1 1.7 2.5 1.8
k=4 5.8 3.3 5.8 3.6 4.7 3.4
k=8 7.7 5.2 8.2 5.5 6.9 5.3
k=16 9.4 7.1 10.1 7.4 8.8 7.1
表2、3表明SA*在性能上明显优于A*。分段数越多,则性能提升越多,同时误差也有一定增长。在2种不同的导航点选择方法下,SA*的性能表现出较大的差异。随着分段数的增长,按直线选择导航点的方法产生了较大的结果误差,而按粗略路径选择导航点则保持了较小的误差,同时性能也稍有优势。结果表明3.2节的分析是正确的。直线是对最短路径的一个较差的近似,而使用粗略路径则可以更精确地选择导航点。
两点间路径规划的计算过程和两点的距离也有密切关系。实验以USA图为例,考察了在不同的距离范围内的2个结点之间进行路径规划的平均耗时和平均相对误差。实验结果如图4、5所示。所有方法的时间消耗都随着两点间距离增长而增长,而A*算法的增长速率更快。分段数越高,则SA*的时间增长越缓慢。在各个距离范围上,实验所测试的方法的性能表现规律都是一致的。相对误差则随距离增长呈现出了缓慢下降的趋势。
Fig. 4 The trend of time cost with the increase of real distance

图4 各种方法的计算时间随结点的距离增长的变化趋势

Fig. 5 The trend of related error with the increase of real distance

图5 各种方法的相对误差随结点的距离增长的变化趋势

SA*的性能提升来自2个方面：① 分段导致搜索空间减少;① 并行带来的加速。表2的结果为这2个方面因素共同作用的结果。为了单独考察并行带来的加速效果,实验以USA图为例,测试了当 k=16时使用不同线程数下的运行时间。实验结果如图6所示。线程数为1时,性能提升完全来自于分段搜索所减少的搜索空间。16线程时,加速比约为3.2,从加速的效率上来说并不算高。相对于难以并行化的A*算法来说,SA*算法对现代CPU多核架构的利用率仍然有所提高。
Fig. 6 The time cost of SA*（k=16） in different parallel scale

图6 SA*（k=16）在不同线程下的计算时间

影响并行加速比的因素有2个方面：① 导航点选择的开销作为程序的串行部分开销,影响了整体的加速比;② 即使在粗略路径上选择划分结点,也仍然难以保证最终每一段的搜索量均衡。图7反应了串行开销对加速比的影响。可以看到,导航点的开销对加速比提升有一定的负面影响。
Fig. 7 Speedup ratios of SA*（k=16) with and without navigation point selection overhead

图7 SA*（k=16）的实际加速比和忽略导航点选择开销加速比

实验的结果表明了分段数k对算法结果的重要影响。k的取值需要从算法耗时和算法误差2方面来进0行考虑。随着k的增长,算法的耗时减少,同时误差增大。在某些情况下,如针对大规模路网、资源受限的嵌入式硬件环境或大量用户并发访问的网络环境中,此时若需要较快的系统响应速度,可以考虑选择较大的k取值。而在比较重视误差的应用中,则可以考虑选择较小的k值。另外,图4、5的结果表明,若起点和终点的距离较长（可以先用直线距离估计）,则应选择较高的k值,因为此时较高的k带来的加速效果比短距离规划更加明显,而误差也更低。

5 相关工作

Dijkstra[1]提出了最经典的最短路径算法,用于求给定源结点到图上其他所有结点的最短路径树。关于Dijkstra算法的优化有大量的研究工作,主要集中在优化该算法所使用的优先级队列。高效的优先级队列实现可以在路网上达到接近宽度优先搜索的性能。然而,针对点到点的最短路径问题,Dijkstra算法由于较多的冗余搜索而性能较低。
Hart等[4]首先提出了A*算法用于有信息的图搜索。该算法使用启发函数将搜索引导至目标。启发函数通过利用图上的信息,估计当前状态到目标状态的代价的下界。路网上点到点路径规划问题可以作为有信息的图搜索问题处理,因此可以使用A*算法解决。通过路网结点的坐标可以计算欧几里得距离作为启发函数。Phol[5]提出了双向A*算法。Ikeda等[6]则在其基础上设计了一个新的启发函数用以提升双向A*的性能。这些算法在原图上从源结点执行一个正向搜索,同时在反向图上从目标结点执行一个反向搜索,因此称为双向搜索。Joint算法[12]和LPA*算法[12]是A*算法的变体,通过结果近似来获得一定的加速效果。Korf[13]提出的IDA*是一个深度优先的启发式搜索,可以获得较好的空间复杂度,但是由于会产生许多重复搜索而耗时较多。Bjornsson等[14]提出的Fringe Search算法通过复用搜索树来提高IDA*的性能。
Brand在文献[7]中提出PHS(Parallel Hierarchies Search)算法,可以利用多核CPU并行地进行路径搜索。在文献[8]中,Brand进一步提出改进算法PRS（Parallel Ripple Search）。PRS借助导航点将搜索划分为多个阶段,然后并行求解。导航点从预先生成的高级图上选择,然而高级图的生成需要较多的预处理时间,因此对于大规模图具有一定局限性。
一些算法通过较长时间的预处理,获得了非常高的在线性能。Goldberg等[15,16]通过预先选择地标结点,计算地标结点到其他结点的距离,在线计算时使用A*算法,利用三角不等式构造的启发函数,可以极大地减少搜索空间。Geisberger等[17]提出Contraction Hierarchies算法,算法不仅本身是较高效的路径规划算法,同时还可以作为有效的预处理手段进一步提高在线计算性能。目前性能最好的使用预处理的算法几乎都用到了Contraction Hierarchies算法,如Transit Node Routing[18], PHAST[19]以及Hub-based labeling[20]等。还有一些算法[21,22,23,24]采取了极端的预处理手段,通过预先计算出所有的最短路径并压缩存储,在线计算时直接查询返回所需的结果,从而获得很高的在线性能。
层次化路网信息[25,26,27,28]可以有效加速路径规划的搜索。陆锋等[25]、李清泉等[26]利用了道路设计等级对路网进行分层。高松等[27]按照道路平均通行速度将道路分级,并将分级作为启发式搜索的代价评估因素。刘康等[28]认为道路设计等级与驾驶者对路网的层次认知并不一致,因此利用拓扑结构地位代替道路设计等级来表达道路的层次性特征。在分层的路径规划中,搜索仍然会规约为若干次同层次网络上的搜索过程,此时每次搜索仍然可以使用本文提出的SA*算法进行进一步的加速。
大部分最短路径算法都由于内在的迭代依赖关系而难以进行并行化。Meyer等[29]提出Δ-stepping是一个比较好地进行并行化的单源点最短路径算法。在Δ-stepping中,每次迭代被限制在长度不超过Δ的范围内,然后在迭代内部进行并行计算。然而,在Madduri[30]的实验中,Δ-stepping在大规模路网上难以获得很高的加速比。

6 结论

本文主要讨论了大规模路网上点到点路径规划问题的求解方案。通过分析A*的并行化困难,以及考虑到在无预处理路网上难以设计优于欧氏距离的启发函数,本文提出了改进的SA*算法,通过分段的搜索方式,在合理的误差范围内减少了搜索空间,同时获得了一定的并行性,能充分利用现代处理器的多核架构。SA*算法包括导航点的选取和分段搜索2个部分。本文通过简单实现分段搜索部分展现了SA*算法策略的有效性。具体的搜索算法仍然可以进一步改进,如使用更复杂的A*算法变体等。下一步的工作可关注每段搜索上的算法改进;同时,在导航点的选取上,可以尝试通过结合更丰富的地图语义,以便更快速地选择出更自然合理、更均匀划分任务的导航点,从而获得更好的并行效率。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Dijkstra E W.A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959,1(1):269-271.

DOI

[2]
Bellman R.On a routing problem[J]. Quarterly of applied mathematics, 1958:87-90.

[3]
Cherkassky B V, Goldberg A V, Radzik T.Shortest paths algorithms: Theory and experimental evaluation[J]. Mathematical programming, 1996,73(2):129-174.We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research.

DOI

[4]
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,4(2):100-107.

DOI

[5]
Pohl I.Bi-directional and heuristic search in path problems[D]. Stanford: Stanford University, 1969.

[6]
Ikeda T, Hsu M Y, Imai H, et al.A fast algorithm for finding better routes by AI search techniques[C]. Vehicle Navigation and Information Systems Conference, 1994:291-296.

[7]
Brand S.Efficient obstacle avoidance using autonomously generated navigation meshes[D]. TU Delft, Delft University of Technology, 2009.

[8]
Brand S, Bidarra R.Parallel ripple search-scalable and efficient pathfinding for multi-core architectures[C]. International Conference on Motion in Games. Springer Berlin Heidelberg, 2011:290-303.

[9]
Pearl J.Heuristics: Intelligent search strategies for computer problem solving[M]. Boston: Addison-Wesley Longman Publishing Company, 1984.

[10]
Demetrescu C, Goldberg A V, Johnson D S.The shortest path problem: Ninth DIMACS implementation challenge[M]. American Mathematical Soc, 2009.

[11]
Camil D, Andrew G, David J. 9th dimacs implementation challenge - shortest paths[EB/OL]. , 2009-10-21

[12]
Ratner D, Pohl I.Joint and LPA*: combination of approximation and search[C]. Proceedings of the Fifth AAAI National Conference on Artificial Intelligence. AAAI Press, 1986:173-177.

[13]
Korf R E.Depth-first iterative-deepening: An optimal admissible tree search[J]. Artificial intelligence, 1985,27(1):97-109.

DOI

[14]
Björnsson Y, Enzenberger M, Holte R C, et al.Fringe Search: Beating A* at Pathfinding on Game Maps[J]. CIG, 2005,5:125-132.ABSTRACT The A* algorithm is the de facto standard used for pathfinding search. IDA* is a space-efficient version of A*, but it suffers from cycles in the search space (the price for using no storage), repeated visits to states (the overhead of iterative deepening), and a simplistic left- to-right traversal of the search tree. In this paper, the Fringe Search algorithm is introduced, a new algorithm inspired by the problem of eliminating the inefficiencies with IDA*. At one extreme, the Fringe Search algo- rithm expands frontier nodes in the exact same order as IDA*. At the other extreme, it can be made to ex- pand them in the exact same order as A*. Experimental results show that Fringe Search runs roughly 10-40% faster than highly-optimized A* in our application do- main of pathfinding on a grid.

[15]
Goldberg A V, Harrelson C.Computing the shortest path: A search meets graph theory[C]. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005:156-165.

[16]
Andrew G, Renato W.Computing Point-to-Point Shortest Paths from External Memory[C]. Proceedings of the seventh International Workshop on Algorithm Engineering and Experiments, 2005. SIAM, 2005:26-40.

[17]
Geisberger R, Sanders P, Schultes D, et al.Contraction hierarchies: Faster and simpler hierarchical routing in road networks[C]. International Workshop on Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2008:319-333.

[18]
Arz J, Luxen D, Sanders P.Transit node routing reconsidered[C]. International Symposium on Experimental Algorithms. Springer Berlin Heidelberg, 2013:55-66.

[19]
Delling D, Goldberg A V, Nowatzyk A, et al.Phast: Hardware-accelerated shortest path trees[J]. Journal of Parallel and Distributed Computing, 2013,73(7):940-952.78 Novel single-source shortest path algorithm. 78 Takes advantage of features of modern CPU architectures (SSE and multiple cores). 78 Additional speedup when implemented on a GPU. 78 Up to three orders of magnitude faster than Dijkstra’s algorithm. 78 Makes applications based on all-pairs shortest-paths practical.

DOI

[20]
Abraham I, Delling D, Goldberg A V, et al.A hub-based labeling algorithm for shortest paths in road networks[C]. International Symposium on Experimental Algorithms. Springer Berlin Heidelberg, 2011:230-241.

[21]
Botea A, Baier J A, Harabor D, et al.Moving target search with compressed path databases[C]. Proceedings of the Twenty-Third International Conference on International Conference on Automated Planning and Scheduling. AAAI Press, 2013:288-292.

[22]
Sankaranarayanan J, Alborzi H, Samet H.Efficient query processing on spatial networks[C]. Proceedings of the 13th annual ACM international workshop on Geographic information systems. ACM, 2005:200-209.

[23]
Sankaranarayanan J, Samet H, Alborzi H.Path oracles for spatial networks[J]. Proceedings of the VLDB Endowment, 2009,2(1):1210-1221.Abstract One embodiment of the invention is directed to a method including constructing a path-distance oracle that provides both an intermediate vertex of a shortest path between two vertices in a spatial network and an approximate distance between the two vertices. The constructing comprises decomposing the spatial network into a set of path-coherent pairs (PCPs) that satisfy at least one predefined property.

DOI

[24]
Sun J, Sun G.SPLZ: An efficient algorithm for single source shortest path problem using compression method[J]. GeoInformatica, 2016,20(1):1-18.Abstract: Efficient solution of the single source shortest path (SSSP) problem on road networks is an important requirement for numerous real-world applications. This paper introduces an algorithm for the SSSP problem using compression method. Owning to precomputing and storing all-pairs shortest path (APSP), the process of solving SSSP problem is a simple lookup of a little data from precomputed APSP and decompression. APSP without compression needs at least 1TB memory for a road network with one million vertices. Our algorithm can compress such an APSP into several GB, and ensure a good performance of decompression. In our experiment on a dataset about Northwest USA (with 1.2 millions vertices), our method can achieve about three orders of magnitude faster than Dijkstra algorithm based on binary heap.

DOI

[25]
陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3):226-232.

DOI

[ Lu F, Zhou C H, Wan Q.An optimum vehicular path algorithm for traffic network base on hierarchical spatial reasoning[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000,25(3):226-232.

[26]
李清泉,郑年波,徐敬海,等.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报,2007,12(7):1280-1285.鉴于平面最短路径算法应用于大规模网络规划中的效率不高，而分层算法引入“分而治之”策略，则能有效解决此难题。为了利用分层算法进行路径规划，首先研究了分层算法的数据基础――道路网络层次拓扑结构，其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型；接着提出了一种适用于LBS（基于位置的服务）的分层路径规划算法。该算法先通过距离值判断是否切换到上一层；然后利用启发式A^＊算法搜索入口和出口；最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明。该算法能从本质上提高大规模网络中路径规划的效率。

DOI

[ Li Q Q, Zheng N B, Xu J H, et al.A hierarchical route planning algorithm based on multi-level topological structure of road network[J]. Journal of Image and Graphics, 2007,12(7):1280-1285. ]

[27]
高松,陆锋.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报,2009,11(2):151-156.本文提出了一种基于路网等级启发式策略的路径搜索算法。通过引入考虑路网等级因素的代价评估函数,有目的地引导搜索过程考虑路网道路等级特征,限制路径搜索规模,在精度可控的前提下,大幅度提高时间最短路径算法的效率,并使得搜索路径结果更符合心理认知过程。其与经典的层次空间推理算法相比,本文提出的算法实现过程简单,效率和精度相似。理论分析和实验过程验证了本文所提出算法的有效性。

[ Gao S, Lu F.A path finding heuristic algorithm for a road network hierarchy[J]. Journal of Geo-information Science, 2009,11(2):151-156. ]

[28]
刘康,段滢滢,张恒才.基于路网拓扑层次性表达的驾车路径规划方法[J].地球信息科学学报,2015,17(9):1039-1046.人对所处客观世界的认识具有显著的空间层次特征，可指导出行路径规划过程。常用的层次空间推理的分层路径计算方法，虽顾及了路网的层次性特征，但道路规划等级与人对路网的层次性认知往往并不一致。而道路网络自身的拓扑结构可客观反映道路重要程度，以及出行者对道路的层次性认知经验。本文以拓扑结构指标表达道路的层次性特征，以此规划驾车出行路径，并通过与出租车行驶路径的匹配度及距离最短路径耗时比评价路径规划结果的合理性。研究结果表明，基于路网拓扑层次性表达的规划路径优于距离最短路径、动态时间最短路径、基于道路等级的静态时间最短路径及基于动态中介中心性分层的距离最短路径，与基于出租车经验建模的路径规划结果相当。但本文所提出的方法不需出租车经验建模所依赖的浮动车系统支持，更利于部署应用。

DOI

[ Liu K, Duan Y Y, Zhang He C.A driving route planning method based on road network topological hierarchy expression[J]. Journal of Geo-information Science, 2015,17(9):1039-1046. ]

[29]
Meyer U, Sanders P.Δ-stepping: a parallelizable shortest path algorithm[J]. Journal of Algorithms, 2003,49(1):114-152.The single source shortest path problem for arbitrary directed graphs with nodes, edges and nonnegative edge weights can sequentially be solved using , sequential -stepping needs denotes the maximum shortest path weight from the source node to any node reachable from . For example, this means linear time on directed graphs with constant maximum degree. Our best parallel version for a PRAM takes work on average can be achieved. We also discuss how the algorithm can be adapted to work with nonrandom edge weights and how it can be implemented on distributed memory machines. Experiments indicate that already a simple implementation of the algorithm achieves significant speedup on real machines.

DOI

[30]
Madduri K, Bader D A, Berry J W, et al.Parallel Shortest Path Algorithms for Solving Large-Scale Instances[R]. Georgia Institute of Technology, 2006.

Options
文章导航

/

〈 〉