地球信息科学学报 ›› 2018, Vol. 20 ›› Issue (6): 753-761.doi: 10.12082/dqxxkx.2018.180019

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

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

孙经纬1(), 孙广中1, 詹石岩1, 毛睿2, 周英华1,*()   

  1. 1. 中国科学技术大学计算机科学与技术学院,合肥 230026
    2. 深圳大学计算机与软件学院,深圳 518060
  • 收稿日期:2018-01-02 修回日期:2018-03-10 出版日期:2018-06-20 发布日期:2018-06-20
  • 通讯作者: 周英华 E-mail:sunjw@mail.ustc.edu.cn;yinghua@ustc.edu.cn
  • 作者简介:

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

  • 基金资助:
    国家自然科学基金项目(61432016、61303047);广东省普通高校国家级重大培育项目(2014GKXM054);广东省普及型高性能计算机重点实验室(2017B030314073)

SA*: A Multi-thread Path Routing Algorithm

SUN Jingwei1(), SUN Guangzhong1, ZHAN Shiyan1, MAO Rui2, ZHOU Yinghua1()   

  1. 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
  • Received:2018-01-02 Revised:2018-03-10 Online:2018-06-20 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

摘要:

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

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

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