一种车辆导航系统的最佳路径计算方法

摘要

本发明涉及一种车辆导航系统的最佳路径计算方法。本发明是一种车辆导航系统的最佳路径算法在执行的过程中只对栅格地图中的转折点进行识别和选取，从一个转折点到其相邻的下一个转折点的中间节点可以被忽略，进而大量地减少了需要处理的节点数量。本发明提出的算法简单，不需要对栅格地图进行任何的预处理和额外的计算机存储空间开销，可以高效率的搜索出最佳路径，提高车辆导航的效率，并可以很好的在复杂地图环境下进行对车辆路径的规划，迅速为车辆寻找最佳路径。

说明书

技术领域

本发明涉及一种车辆导航系统的最佳路径算法，特别涉及一种基于TPA*算法的复杂地图环境下车辆导航系统的最佳路径寻找方法。

背景技术

车辆导航系统中最主要的部分是确定最佳路径的算法，用来确定车辆在道路交通网中从当前位置到目的地的最佳路径。对于大多数车辆导航系统来说，起始点和终点之间的最佳路径通常定义为预计行进时间最短的路径。确定车辆导航系统中最佳路径的主要思路是：用最短路径算法计算出车辆当前位置到目的地的完整路径，使得其预计旅行时间最短，最后把计算出的路径提供给车辆驾驶员参考。

最佳路径是寻找网络中节点对直接最短路径的一类问题，通常是采用图论和数学规划的方法进行对路径的搜索。目前，最佳路径问题已经在计算机科学、运筹学、地理信息科学等众多领域广泛应用。在具体应用上包括智能交通系统、地理信息系统、路径规划问题、计算机网络通信等。

自上世纪50年代开始，各领域的学者对最佳路径问题进行了深入的研究。基于Bellman优化原理，求解节点网络中一个节点到所有其他节点最佳路径的Dijkstra算法，求解节点网络里任意对节点之间最短路径的Floyd算法，以及智能搜索A*算法等为代表的经典算法奠定了节点网络最佳路径算法的基础。

在众多的最佳路径算法中，A*算法是目前比较流行的一种最佳路径的搜索算法，同Dijkstra等算法相比，A*算法采用了启发式的搜索策略，在搜索的过程中对每一个搜索的节点进行估计和计算，避免了路径搜索的盲目性，可以很大程度上减少搜索过程中遍历的节点，从而提高算法的执行速度。

通过对目前最佳路径算法性能的比较可以发现，当应用在大型复杂的节点网络中的时候，即使性能比较优越的A*算法也存在着遍历节点数量多、运算速度慢等问题，在应用于复杂地图环境下的车辆导航系统中时，也不能很好地满足车辆导航系统对实时性的要求，因此实有必要提出改进的算法来解决复杂地图环境下车辆导航的问题。

发明内容

本发明提出一种车辆导航系统的最佳路径计算方法，以解决复杂地图环境下车辆导航的问题，通过识别和减少以最佳的路径到达终点所需要遍历的节点来提高算法的速度，具有算法实现简单，不占用计算机额外的存储空间，不需要对地图的预处理等优点，能快速地在复杂地图环境下寻找到最佳路径，对车辆进行导航。

本发明采取的技术方案是，包括以下步骤：

步骤一：建立二维无方向、权重相同的网络节点栅格地图，其中，每个网络节点n的邻域节点集合neighbors(n)中都包含有8个节点，根据车辆行驶地图不同地理特征，每个节点有可通行和不可通行两种状态，一个节点通过直线移动和斜线移动两种方式到达另外一个相邻的节点，相邻节点间的距离默认为1；

步骤二：对节点n的邻接节点集合neighbors(n)进行删减，目的是要确定出同到达目标的最佳路径不相关的节点x，根据父节点p(n)到节点n的方向不同而需要考虑两种情况，分别是直线移动和斜线移动；另外，如果节点n是起点，因为其父节点为空，故而无法进行邻接节点的删减；

（1）、直线移动

在这种情况下，对满足公式（1）中约束条件的任何节点x（x∈neighbors(n)）进行删减：

len(<p(n),…,x> )≤len(<p(n),n,x>)    (1)

（2）、斜线移动

同上述直线删减规则相似，但是在斜线移动的情况下，对节点x的删减限制条件更加的严格，需要满足公式（2）中的约束条件：

len(<p(n),…,x> )<len(<p(n),n,x>)    (2)

在上述的两种情况中，neighbors(n)中都没有包含障碍节点，将此时经过删减之后得到的节点称为节点n的普通邻接节点（NormalNeighbor）；而当neighbors(n)中含有障碍节点时，会出现不能完全对非普通邻接节点进行删减的情况，这时称这些未被删减掉的节点为特殊节点（Special Neighbor）；如果一个节点x（x∈neighbors(n)）是特殊节点，那么它应该满足：节点x不是节点n的普通节点，并且满足公式（3）中的约束条件。

len(<p(n),n,x>)<len(<p(n),…,x> )    (3)

步骤三：进行对路径转折点的搜索工作，节点n到节点x∈neighbor(n)的移动方向是一个关键因素，对转折点的定义如下：

节点m是节点n的后继节点，n到m的方向为如果n在此方向上经过最少k次单位移动后到达m，即并且满足下列约束条件之一，则称节点m是节点n的转折点；

1）.节点m是终点；

2）.节点m的邻接节点中至少有一个是特殊节点；

3）.是斜线方向时，存在一个节点在方向上距离m节点k_i个单位距离，并且节点p是满足上述条件1或条件2的一个转折点；

步骤四：将按照步骤三中定义得到的、属于节点n的转折点存放到数组ProcessList中，任意节点x∈ProcessList是待处理的节点，在每一次向ProcessList中插入节点的时候，都需要保持ProcessList的有序性，即ProcessList中的第一个节点的路径开销值：即从起点到此节点的行进距离最小，最后一个节点的路径开销值最大，在下一次算法循环的时候，取出ProcessList中的第一个节点进行处理；

步骤五：循环执行上述步骤二至步骤四，当终点n_goal被插入到ProcessList中时，完成对最佳路径的搜索，结束；从终点n_goal开始，依次将其前继节点即父节点添加到路径数组PathList中，直到将起点n_start添加到PathList中，路径数组PathList中保存的即为寻找到的最佳路径上的所有路径节点，车辆导航系统可以按照此最佳路径对行驶在地图上的车辆进行实时的导航工作。

与现有的算法相比，本发明一种车辆导航系统的最佳路径算法在执行的过程中只对栅格地图中的转折点进行识别和选取，从一个转折点到其相邻的下一个转折点的中间节点可以被忽略，进而大量地减少了需要处理的节点数量。本发明提出的算法简单，不需要对栅格地图进行任何的预处理和额外的计算机存储空间开销，可以高效率的搜索出最佳路径，提高车辆导航的效率。采用本发明，可以很好的在复杂地图环境下进行对车辆路径的规划，迅速为车辆寻找最佳路径。

附图说明

图1是本发明算法中涉及到的等长路径的示意图；

图2是本发明算法中在不同情况下对邻域节点进行删减的示意图；

图3是本发明算法中对转折点的搜索示意图。

具体实施方式：

以下通过特定的具体实例并结合附图说明本发明的实施方式，本领域技术人员可由本说明书所揭示的内容轻易地了解本发明的其它优点与功效。本发明亦可通过其它不同的具体实例加以施行或应用，本说明书中的各项细节亦可基于不同观点与应用，在不背离本发明的精神下进行各种修饰与变更。

在具体介绍本发明之前，先说明下本发明一种车辆导航系统的最佳路径算法的主要中心思想：通过对A*算法分析可以发现，A*算法在搜索最佳路径的过程中存在着大量的等长路径。本发明中对等长路径的定义是：如果两条路径具有相同的起点和终点，而且可以通过对其中一条路径的组成子路径进行置换重组而得到另一条路径，那么称这两条路径为等长路径。图1中所示的几条路径互为等长路径，通过观察可以得到，每一条路径都是由9个竖直方向和9个水平方向的子路径组成的。

为了减少A*算法中对等长路径的不必要的搜索和遍历，进一步提高算法的效率和运行速度，本发明提出了一种TPA*（Turning Point）算法。TPA*算法的中心思想是删减任何可以从当前节点的父节点以最佳的方式到达的邻接节点，通过这种方式可以避免大量的等长路径。另外，在TPA*算法中，所有待处理的节点都是那些在路径前进方向上可能发生方向转折的节点，在两个转折节点之间的部分节点并不进行处理，这就意味着需要遍历的节点数量同A*算法相比会大幅度的减少。

下面结合附图，对本发明的具体实施方式作详细的描述。

步骤一：为了寻找车辆导航系统的最佳路径，首先需要建立本发明算法的具体实施环境。本发明一种车辆导航系统的最佳算法的实施是在二维无方向权重相同的网络节点栅格地图中进行的。其中，每个网络节点n的邻域节点集合neighbors(n)都含有8个节点，根据车辆行驶地图不同地理特征，每个节点可以有可通行和障碍两种状态。一个节点可以通过直线移动和斜线移动两种方式到达另一个节点，相邻节点间的距离默认为1。

步骤二：对节点n的邻接节点集合neighbors(n)进行删减，目的是要确定出同到达目标的最佳路径不相关的节点x。为了达到上述要求，需要对两类路径的长度进行比较：π，该路径从节点n的父节点p(n)开始，经由节点n并到达节点x；π'，该路径同样是从节点n的父节点p(n)开始，但是不经过节点n而到达节点x。需要注意的是，上述两条路径中所包含的节点都包含在集合neighbors(n)中。根据父节点p(n)到节点n的方向不同而需要考虑两种情况，分别是直线移动和斜线移动。另外，如果节点n是起点，因为其父节点为空，故而无法进行邻接节点的删减。

1、直线移动

在这种情况下，对满足公式（1）中约束条件的任何节点x（x∈neighbors(n)）进行删减：

len(<p(n),…,x> )≤len(<p(n),n,x>)    (1)

如图2（a）中所示的情况，p(n)=7，除了节点x=2之外的所有节点都将被删减。

2、斜线移动

同上述直线删减规则相似，但是在斜线移动的情况下，对节点x的删减限制条件更加的严格，需要满足公式（2）中的约束条件：

len(<p(n),…,x> )<len(<p(n),n,x>)    (2)

如图2（c）中所示的情况，p(n)=1，除了节点x=5，x=7，x=8之外的所有节点都将被删减。

本发明中涉及的算法在上述的两种情况中，neighbors(n)中都没有包含障碍节点，将此时经过删减之后得到的节点称为节点n的普通邻接节点（Normal Neighbor）。而当neighbors(n)中含有障碍节点时，会出现不能完全对非普通邻接节点进行删减的情况，这时称这些节点为特殊节点（Special Neighbor）。如果一个节点x（x∈neighbors(n)）是特殊节点，那么应该满足：节点x不是节点n的普通节点，并且满足公式（3）中的约束条件。

len(<p(n),n,x>)<len(<p(n),…,x> )    (3)

图2（b）中的x=1节点和图2（d）中的x=3节点都是满足上述条件的特殊节点。

本发明所涉及的算法在完成了对节点n周围的8邻域节点的删减工作之后会得到一个节点n的邻域节点集合neighbor(n)。考虑在最恶劣的情况下，即节点n是路径的起点n_start时，集合neighbor(n)中的节点数目是8。考虑一般情况，并且在节点n的邻域中没有特殊邻接节点（SpecialNeighbor）的情况下，集合neighbor(n)中的最大节点数量在直线移动时是1，而在斜线移动时是3；在存在特殊节点的情况下，集合neighbor(n)中的最大节点数量在直线移动时是3，在斜线移动时是5。经过删减之后的邻域节点数量有了显著的下降。

步骤三：在本发明算法的后续工作中，并不直接将步骤二中得到的邻域节点作为下一步待处理的节点，而是进行对路径转折点的搜索工作。在此步骤的搜索中，节点n到节点x∈neighbor(n)的移动方向是一个需要考虑的关键因素。本发明所涉及的算法对转折点的定义及搜索示例如下：

节点m是节点n的后继节点，n到m的方向为如果n在此方向上经过最少k次单位移动后到达m，即并且满足下列约束条件之一，则称节点m是节点n的转折点。

1.节点m是终点。

2.节点m的邻接节点中至少有一个是特殊节点。

3.是斜线方向时，存在一个节点在方向上距离m节点k_i个单位距离，并且节点p是满足上述条件1或条件2的一个转折点。

图3（a）中的节点m是节点n的一个转折点，满足上述条件2。图3（b）中所示的节点m是满足条件3的转折点。从节点n开始沿斜线方向移动，直到遇到节点m，从m开始经过k_i=2次水平移动到达节点p，而p点是m点的一个转折点（满足条件2），因此，节点m是节点n的一个转折点。

步骤四：将按照步骤三中定义得到的，属于节点n的转折点存放到数组ProcessList中，任意节点x∈ProcessList是待处理的节点。在每一次向ProcessList中插入节点的时候，都需要保持ProcessList的有序性，即ProcessList中的第一个节点的路径开销值（从起点到此节点的行进距离）最小，最后一个节点的路径开销值最大。在下一次算法循环的时候，取出ProcessList中的第一个节点进行处理。

步骤五：循环执行上述步骤二至步骤四，当终点n_goal被插入到ProcessList中时，完成对最佳路径的搜索，算法结束。从终点n_goal开始，依次将其前继节点即父节点添加到路径数组PathList中，直到将起点n_start添加到PathList中。路径数组PathList中保存的即为寻找到的最佳路径上的所有路径节点。车辆导航系统可以按照此最佳路径对行驶在地图上的车辆进行实时的导航工作。

综上所述，本发明一种车辆导航系统的最佳路径算法在执行的过程中只对地图中的路径转折点进行识别和选取，从一个转折点到其相邻的下一个转折点的中间节点可以被忽略，进而大量地减少了需要处理的节点数量。本发明提出的算法简单，不需要对地图进行任何的预处理和额外的计算机存储空间开销，可以高效率的搜索出最佳路径，提高车辆导航的效率。采用本发明，可以很好的在复杂地图环境下进行对车辆路径的规划，迅速为车辆寻找最佳路径。

以上所述仅为本发明的优选实施方式，本发明的保护范围并不仅限于上述实施方式，凡是属于本发明的原理的技术方案均属于本方面的保护范围，对于本领域的技术人员而言，在不脱离本发明的前提下进行的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。