路径规划的经典算法主要有 Dijkstra算法、A‘算法、D算法等。 1. Dijkstra算法。 Dijkstra算法是最经典的路径搜索算法,寻找解的质量稳定,计算速度快Dijkstra算法使用全局搜索,不但能够保证在一个区域当中找到两个坐标之间的最短路径,而且能够找到区域中某一点到其他点中的最短路径。 Dijkstra算法的根本思想:若每个点都设有一个坐标(d,P),其中d是原点O到某一点j的一条长度是最短的路径,P则是d的前一个点,求解从原点O到某一点j的路径中最短的一条路径,其算法应该如下。 ①判断路径规划的可行性(就是说起始点和终点的选择是否可行和存储结点的容器是否正确),将存放节点的容器初始化,然后把所有结点粘贴到临时缓存。 ②首先查找离第一个节点最近的相关节点和两者之间的道路信息,并把它们都存储起来,然后通过查找与之距离最短的一个节点是不是终点,假如是终点那么将节点存储起来,返回:若不是,则从暂时缓存中删除第一个节点,执行下步操作。 ③寻找离目前中间点最近的一个节点,将此节点存储起来。 ④再次判断目前节点是不是线路规划的终点,假如是则返回节点,若不是则可以删除临时缓存中的已分析节点,重新回到步骤。③Dijkstra算法的核心方法就是对当前网络中存在的所有节点开始查找,找到第个节点到任意一个节点的最短线路,这种方法并没有考虑到任何节点是否存在方向性,因此 Dijkstra算法具有比较好的计算可靠性、稳定性;但同时也存在着缺点,在范围较大的路径规划中, Dijkstra算法计算效果不是很好。 2.A*算法。 在静态路径下的规划算法中常用的算法为A算法。它是一种启发式搜索策略,能根据求解问题的具体特征,控制搜索往最可能达到目的地方向前进。这种搜索策略针对问题本身特点进行,因而比完全搜索的方案效率要高很多,它往往只需要搜索一部分状态空间就可以达到目的地。 A算法是目前最为流行的最短路径启发式搜索算法,它充分运用问题域状态空间的启发信息,对问题求解选取比较适宣的估价函数,再利用估价函数的反馈结果,对它的搜索战略进行动态的调节,最终得到问题的最优解。A算法给出的估价函数为
算法步骤如下。
①赋给初始值,初始化所有节点、临时缓存和关联容器。
②计算初始节点和各个相关节点的权值f(,然后保存起来,从中获得权值最小的节点,并保存该节点,最后把它从节点存储器中去掉。
③计算该节点是不是终点,假如是终点就返回节点,若不是终点就接着计算下一步。
④获得所有的中间节点与相关节点的权值f(),然后开始判断,假如这个节点没有保存,那么把这个节点存储起来;假如这个节点已经保存,比较这个节点的权值和已保存节点的权值大小,如果不大于已保存权值,则开始更新替换。
⑤查找中间点的关联节点中权值最小的一个节点,将该节点保存,然后将其从节点缓存中去掉,并转到步骤③。
A*算法的独特之处在于使用估价模型函数,这种算法会自动地使运算结果趋向于目的地,因此,它查找的节点越少,存储空间被占用得越少。与其他算法相比,如果它们的时间复杂度是一样的,A*算法在实际应用中效果会更优越。
3.D*算法。
A*算法主要是在静态的环境下进行最短路径规划,但在实际环境下,可能由于交通环境复杂,路面的行人、路障、非机动车辆、机动车辆以及其他各种动态障碍物都会影响车辆的行进,所以有必要进行路径的动态规划。典型的动态规划算法为D*算法。它的基本思想如下:
①利用A算法对地图上给定的起始点和目标点进行路径规划,建立OPEN表和 CLOSED表,存储规划路径上的每一路点到目标路点的最短路径信息。
②在车辆对规划出的路径进行跟踪时,当下一个路点没有障碍能够通行时则对上面规划出的路径从起始路点向后追溯到目标路点,直至车辆到达目的地。
当在跟踪到某一路点Y时,检测到在下一路点处有障碍发生时,则在当前路点处重新建立对后续路点的规划,保存障碍物之前的路点在OPEN表和 CLOSED表里的信息和指针,删除障碍物之后路点在OPEN表和 CLOSED表里的信息和后继
指针。
③利用A算法从当前路点Y开始向目标路点进行规划,重新规划得到最短路径。回到步骤②
