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

摘要

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