专利名称：基于分层双向启发式路线规划方法的导航装置的制作方法
技术领域：
本发明属于导航装置用路线规划算法，特别是涉及一种结合多种算法的路线规划方法。
背景技术：
目前，导航系统所采用的硬件性能有限，其使用的导航数据的数据量巨大(道路记录数 超过100万条)，而在硬件性能有限而且数据量巨大的情况还需要保证导航系统路线规划的实 时性，这给导航系统路线规划算法提出了很高的要求。现有的算法有Dijkstra算法、启发式 算法、分层算法、双向搜索算法，任何一种算法单独使用都无法很好的满足导航系统对路线 规划实时性的要求。

发明内容
本发明所要解决的技术问题是提供一种基于分层双向启发式路线规划方法的导航装置， 该导航装置使用了一种结合启发式算法、双向算法、分层算法的路线规划算法。这种分层双 向启发式算法能够在硬件性能有限而且数据量巨大的情况下，保证导航系统路线规划实时性 要求。
本发明所采取的技术方案是基于分层双向启发式路线规划方法的导航装置，其路线规 划方法包括分层和启发式方法，还使用了双向搜索方法，具体包括以下步骤
1) 输入现在地和终点，计算二者的球面距离，在己分层的地图上确定最后进行路线规划的 高层层数和向上层切换的条件，设该高层层数为正整数i;
2) 判断最底层是否为第i层，如果为"是"，转至步骤5)，否则转至步骤3);
3) 在最底层通过双向启发式搜索方法进行路线规划，进行一次路线规划之后，如果满足 向上层切换的条件，就转至步骤4)，如果不满足向上层切换的条件，继续在最底层进行路线 规划，直到满足向上层切换的条件为止，然后转至步骤4);
4) 向上一层进行切换，切换后的层数加l，如果切换后的层数是第i层，转至步骤5)，
否则转至步骤6);
5) 在第i层通过双向启发式搜索方法进行路线规划，进行一次路线规划之后，判断是否 满足终止条件，如果为"是"，转至步骤7)，否则继续进行路线规划，直至满足终止条件，
然后转至步骤7);
6) 在当前层通过双向启发式搜索方法进行路线规划，进行一次路线规划之后，如果满足 向上层切换的条件，就转至步骤4)，如果不满足向上层切换的条件，继续在该层进行路线规
划，直到满足向上层切换的条件为止，然后转至步骤4);
7) 输出搜索结果。
本发明的有益效果是可以在硬件性能有限且数据量巨大的情况，满足导航系统路线规
划实时性的要求，算法流程清晰。


图1是双向启发式算法的流程图。
图2是分层双向启发式算法的流程图。
图3是地图数据上下层对应关系。
图4是单向Dijkstra算法、双向Di jkstra算法、双向启发式算法的搜索空间图。 图5是实施例分层后详细层(第0层)的节点拓扑图。 图6是实施例分层后粗略层(第l层)的节点拓扑图。 图7表示的是地图中详细层的地图信息示意图。 图8表示的是地图中粗略层的地图信息示意图。
具体实施例方式
如图2所示，基于分层双向启发式路线规划方法的导航装置，其路线规划方法包括分层
和启发式方法，其路线规划方法还使用了双向搜索方法，具体包括以下步骤
1) 输入现在地和终点，计算二者的球面距离，在已分层的地图上确定最后进行路线规划的 高层层数和向上层切换的条件，设该高层层数为正整数i;
2) 判断最底层(第0层)是否为第i层，如果为"是"，转至步骤5)，否则转至步骤3);
3) 在最底层通过双向、启发式搜索方法进行路线规划，进行一次路线规划之后，如果满 足向上层切换的条件，就转至歩骤4)，如果不满足向上层切换的条件，继续在最底层进行路 线规划，直到满足向上层切换的条件为止，然后转至步骤4);
4) 向上一层进行切换，如果切换后是第i层，转至步骤5)，否则转至步骤6);
5) 在第i层通过双向、启发式搜索方法进行路线规划，进行一次路线规划之后，判断是 否满足终止条件，如果为"是"，转至步骤7)，否则继续进行路线规划，直至满足终止条件， 然后转至步骤7);
6) 在当前层通过双向、启发式搜索方法进行路线规划，进行一次路线规划之后，如果满 足向上层切换的条件，就转至步骤4)，如果不满足向上层切换的条件，继续在该层进行路线 规划，直到满足向上层切换的条件为止，然后转至步骤4);
7) 输出搜索结果。
如图l所示，上述路线规划方法中的双向搜索方法具体包括以下步骤
1) 输入现在地和终点；
2) 根据步骤1)的数据，判断是否满足切换条件，若为"是"，进行一次后向启发式搜索，
否则进行一次前向启发式搜索，搜索完后均转至步骤3);
3) 判断是否满足终止条件，若为"是"，则输出搜索结果，否则转至步骤2)。
图3说明了高层和底层的层间关系，从上往下即为从高层到低层。在高层计算会使用较 为主要的道路网，道路网的密集程度较底层道路网要低得多，这样在高层进行搜索时就能够 使用较少的迭代次数搜索出结果。
图4说明了单向Dijkstra算法、双向Dijkstra算法、双向启发式算法的搜索空间图， 其中大圆为单向Dijkstra算法的搜索空间图；两个小圆为双向Dijkstra算法的搜索空间两个椭圆为双向启发式算法的搜索空间图。可以看出来在这几个算法中双向启发式算法的搜 索空间最小，说明了双向启发式算法会使用最少的迭代次数搜索出结果， 一般来说，这个发 明涉及的算法其计算量只是其他算法计算量的四分之一。 实施例
将整个地图分为两层，图6是图5的粗略图，图5是第0层，图6是第1层。如图5所 示，第0层的地图上有a z共26个节点，每相邻两点间的边长为1，节点a和节点z之间 的球面距离为9。如图6所示，第1层每相邻两点间的边长为3。现在需要计算出地图节点a 到节点z的最短路径，最后路线规划的高层为第1层。
我们设
V:边的集合；
O[n]:起始点到节点n的最短路径的距离费用；
G[n]:节点n到终点的欧氏距离；
D[n]:节点n到终点的最短路径的距离费用；
H[n]:节点n到终点的欧氏距离；
C[p，q]:节点p到节点q的距离费用；
wo:起点方向(到起点的最短路径)中已经找到最短路径节点的集合； wd:终点方向(到终点的最短路径)中已经找到最短路径节点的集合。 向上层切换的条件是详细层(第0层)的wo、 wd两个集合，每个都有两个或两个以上 的节点在粗略层(第l层)。
通过分层双向启发搜索算法按以下步骤顺序操作
(1) 设0[&]=0，另外将所有除节点a外的节点0[n]值设为①；设D[z卜0，另外将所 有除节点z外的节点D[n]值设为吣；两点之间的欧氏距离通过两点的坐标进行计算；
(2) 在详细层(第0层)，从起点方向进行一次前向搜索，将0
+ G[n]值最小的节点 a添加到集合wo中(a点到z点的G[n]为9)，此时wo = {a};通过0[v] = min (0[v], 0[w] +c [w， v])
(w表示在wo集合中所有节点，v为所有和w相连接的点，min为取最小值)改写所有节点 的费用信息，0[c]=l;
(3) wo集合中有子集(al在粗略层中，wd集合中没有点在粗略层中，不满足详细层中wo， wd两个集合中都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(4) wo集合和wd集合中没有相同的节点，变换搜索方向；
(5) 在终点方向进行一次后向搜索，将0[^+ H[n]值最小的节点z添加到集合wd中， 此时wd二lzh通过D[v]: min(D[v]， D[w]+c[w,v]) (w表示在wd集合中所有节点，v为所 有和w相连接的点)改写所有节点的费用信息，D[x] = l;
(6) wo集合中有子集(a }在粗略层中，wd集合中有子集(z)在粗略层中，不满足详细层 wo、 wd两个集合中每个都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(7) wo集合和wd集合中没有相同的节点，变换搜索方向；
(8) 在起点方向进行一次前向搜索，将0[!1]+ G[n]值最小的节点c添加到集合wo中，
此时wo—a， c};通过0[v]min(0[v]， 0[w]+c[w，v]) (w表示在wo集合中所有节点，v为 所有和w相连接的点)改写所有节点的费用信息，0[b]=2， 0[d]=2， 0[f]=2;
(9) wo集合中有子集"}在粗略层中，wd集合中有子集{2}在粗略层中，不满足详细层 wo、 wd两个集合中每个都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(10) WO集合和wd集合中没有相同的节点，变换搜索方向；
(11) 在终点方向进行一次后向搜索，将0[!!]+ H[n]值最小的节点x添加到集合wd中， 此时wcMz， x};通过D[v]: min(D[v], D[w]+c[w，v]) (w表示在wd集合中所有节点，v为 所有和w相连接的点)改写所有节点的费用信息，D[w]=2， D[y]=2， D[u]=2;
(12) wo集合中有子集(al在粗略层中，wd集合中有子集合(zl在粗略层中，不满足详细 层wo、 wd两个集合中每个都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(13) WO集合和wd集合中没有相同的节点，变换搜索方向；
(14) 在起点方向进行一次前向搜索，将0[11]+ G[n]值最小的节点f添加到集合wo中， 此时wo ={a， c, fl;通过0[v]: min(0[v]， O[w]十c[w,v]) (w表示在wo集合中所有节点， v为所有和w相连接的点)改写所有节点的费用信息，0[b]=2， 0[d]=2, 0[e]=3, 0[g]=3， 0[i]=3;
(15) wo集合中有子集(a)在粗略层中，wd集合中有子集lz)在粗略层中，不满足详细层 wo、 wd两个集合中每个都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(16) wo集合和wd集合中没有相同的节点，变换搜索方向；
(17) 在终点方向进行一次后向搜索，将0[11]+ H[n]值最小的节点u添加到集合wd中， 此时wd ={z， x， u};通过D[v]二 min(D[v]， D[w]化[w'v]) (w表示在wd集合中所有节点， v为所有和w相连接的点)改写所有节点的费用信息，D[w]=2， D[y]=2， D[t]=3， D[v]=3， D[r]=3;
(18) wo集合中有子集(ea在粗略层中，wd集合中有子集(z!在粗略层中，不满足详细层 wo、 wd两个集合中每个都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(19) wo集合和wd集合中没有相同的节点，变换搜索方向；
(20) 在起点方向进行一次前向搜索，将0[^+ G[n]值最小的节点i添加到集合wo中， 此时wo二(a， c， f， i};通过0[v]= min(O[v], 0[w]+c[w，v]) (w表示在wo集合中所有节 点，v为所有和w相连接的点)改写所有节点的费用信息，0[b]=2， 0[d]=2, 0[e]=3， 0[g>3， 0[h]=4, 0[j]=4， 0[1]=4;
(21) wo集合中有子集(a， il在粗略层中，wd集合中有子集{2}在粗略层中，不满足详 细层wo、 wd两个集合中每个都有两个或两个以上的节点在粗略层的条件，不向粗略层切换；
(22) wo集合和wd集合中没有相同的节点，变换搜索方向；
(23) 在终点方向进行一次后向搜索，将0[11]+ H[n]值最小的节点r添加到集合wd中， 此时wd^z， x， u， r};通过D[v]= min(D[v]， D[w]+c[w，v]) (w表示在wd集合中所有节 点，v为所有和w相连接的点)改写所有节点的费用信息，D[w]=2， D[y]=2， D[t]=3， D[v]二3， D[q]二4， D[s]=4， D[o]=4;
(24) wo集合中有子集b,"在粗略层中，wd集合中有子集(z， r》在粗略层中，满足详 细层中wo、 wd两个集合每个都有两个或两个以上的节点在粗略层的条件，向粗略层切换；
(25) 在粗略层对起点方向搜索进行处理，通过0[v]= min(0[v]， O[w]十c[w'v]) (w表 示在wo集合中所有节点，v为所有和w相连接的点)改写所有节点的费用信息，0[r]=6;
(26) 在粗略层对终点方向搜索进行处理，通过D[v]= min(D[v]， D[w]+c[w,v]) (w表 示在wd集合中所有节点，v为所有和w相连接的点)改写所有节点的费用信息，D[i]=6;
(27) 在粗略层起点方向进行一次前向搜索，将0[1!]+ G[n]值最小的节点r添加到集合 wo中，此日寸wo二ia， c， f， i， r};通过[v]二 min(0[v]' 0[w]+c[w，v]) (w表示在wo集合 中所有节点，v为所有和w相连接的点)改写所有节点的费用信息，0[z]=9;
(28) wo集合和wd集合中有相同的节点r，同时由上下层对应关系知道i-r对应i-l_o-r， 此时搜索到一条最短路径a-c-f-i-1-o-r-u-x-z，搜索结束。
地图层次示例
如图7、图8，两个图分别表示的是同一地区不同层次的地图信息，图7中表示的是详细 层的地图信息，图8中表示的是粗略层的地图信息，两个层次的地图信息在数据上有一定的 关联，可以判断出在图7中的节点在图8中是否有节点对应，按上述双向搜索算法中在图7 中进行搜索，统计当目前搜索结果中的节点在图8中有对应节点的个数，当这个个数达到一 定的数量，就向图8进行切换，可以从图中清晰的看出，图8的节点的数目远少于图7中节 点的数目，这就意味着在图8中搜索道路可以进行更少次数的搜索从而找到最短路径。
权利要求
1.基于分层双向启发式路线规划方法的导航装置，其路线规划方法包括分层和启发式方法，其特征是其路线规划方法还使用了双向搜索方法，具体包括以下步骤1)输入现在地和终点，计算二者的球面距离，在已分层的地图上确定最后进行路线规划的高层层数和向上层切换的条件，设该高层层数为正整数i；2)判断最底层是否为第i层，如果为“是”，转至步骤5)，否则转至步骤3)；3)在最底层通过双向启发式搜索方法进行路线规划，进行一次路线规划之后，如果满足向上层切换的条件，就转至步骤4)，如果不满足向上层切换的条件，继续在最底层进行路线规划，直到满足向上层切换的条件为止，然后转至步骤4)；4)向上一层进行切换，切换后的层数加1，如果切换后的层数是第i层，转至步骤5)，否则转至步骤6)；5)在第i层通过双向启发式搜索方法进行路线规划，进行一次路线规划之后，判断是否满足终止条件，如果为“是”，转至步骤7)，否则继续进行路线规划，直至满足终止条件，然后转至步骤7)；6)在当前层通过双向启发式搜索方法进行路线规划，进行一次路线规划之后，如果满足向上层切换的条件，就转至步骤4)，如果不满足向上层切换的条件，继续在该层进行路线规划，直到满足向上层切换的条件为止，然后转至步骤4)；7)输出搜索结果。
2. 如权利要求l所述的基于分层双向启发式路线规划方法的导航装置，其特征是其路线 规划方法中的双向启发式搜索方法包括以下步骤1) 输入现在地和终点；2) 根据步骤1)的数据，判断是否满足切换条件，若为"是"，进行一次后向启发式搜索， 否则进行一次前向启发式搜索，搜索完后均转至步骤3);3) 判断是否满足终止条件，若为"是"，则输出搜索结果，否则转至步骤2)。
全文摘要
本发明提供了一种基于分层双向启发式路线规划方法的导航装置。该装置的使用方法结合了分层算法、双向搜索算法和启发式算法。首先确定需要规划的高层层数和提层条件，然后在最底层进行双向启发式路线规划直至满足提层条件为止。接着往上切换一层，并判断切换后的高层是否为最终规划的高层如果为是就在该层进行双向启发式路线规划直至找到最终路线；如果为否就在该层和底层一样进行双向启发式路线规划直至满足提层条件为止，接着重复前述提层和最终路线的确认过程。本发明可以在硬件性能有限且数据量巨大的情况，满足导航系统路线规划实时性的要求，算法流程清晰。
文档编号G01C21/34GK101358855SQ20081019704
公开日2009年2月4日 申请日期2008年9月23日 优先权日2008年9月23日
发明者张宗敏, 飞 谢, 滨 邓, 杨 陆 申请人:光庭导航数据(武汉)有限公司