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

Path planning algorithm based on hierarchical road network

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

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.