计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1763-1766.DOI: 10.3724/SP.J.1087.2013.01763

• 典型应用 • 上一篇    下一篇

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

罗亚男,付永庆   

  1. 哈尔滨工程大学 信息与通信工程学院,哈尔滨 150001
  • 收稿日期:2012-12-20 修回日期:2013-01-23 出版日期:2013-06-01 发布日期:2013-06-05
  • 通讯作者: 罗亚男
  • 作者简介:罗亚男(1986-),女,河北唐山人,硕士研究生,主要研究方向:车载导航系统;付永庆(1956-),男,黑龙江哈尔滨人,教授,主要研究方向:微弱信号检测、混沌通信、信号处理。

Path planning algorithm based on hierarchical road network

LUO Ya’nan,FU Yongqing   

  1. College of Information and Communication Engineering, Harbin Engineering University, Harbin Heilongjiang 150001,China
  • Received:2012-12-20 Revised:2013-01-23 Online:2013-06-05 Published:2013-06-01
  • Contact: LUO Ya’nan

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

关键词: 分层路网, 拓扑结构提取, 路径规划, A*算法, 二叉堆

Abstract: In order to improve the efficiency of path planning, a heuristic search algorithm was presented, which was based on the hierarchical road network and used binary heap to manage the open list. According to the characteristics of the network classification, the hierarchical map database was established. This article made the heuristic A* algorithm as the main search mode, and used the binary heap to manage the open list, thus realizing path planning. The statistical results of average time consumption of different algorithms show that: The efficiency of A* algorithm is improved about four times than Dijkstra algorithm. The use of binary heap makes time consumption reduced 5%. Last, the stratified strategy makes the proportion of fast sections reach 90% or more, and path planning is completed in 3 seconds. The results of experiments prove that this algorithm has high efficiency, and it also can meet the drivers’ psychological needs.

Key words: hierarchical road network, topology extraction, road planning, A* algorithm, binary heap

中图分类号: