汽车导航中的路径规划是指在一定环境模型基础上,给定汽车起始点和目标点后,按照性能指标规划出一条无碰撞、能安全达到目标点的有效路径。路径规划主要包含两个步骤:建立环境模型,将现实的环境进行抽象后建立的相关模型:路径搜索,即寻找符合条件的最优路径。不同的环境模型对路径搜索方法具有非常显著的影响。 一、环境模型建立方法。 环境模型建立方法主要有可视图法、栅格法、自由空间法和拓扑法等。 1.可视图法。 在C空间( Configuration Space,位姿空间)中,运动物体缩小为一点,障碍物边界相应地向外扩展为C空间障碍。在二维的情况下,扩展的障碍物边界可由多个多边形表示,用直线将物体运动的起点S和所有C空间障碍物的顶点以及目标点C连接,并保证这些直线段不与C空间障碍物相交,就形成一张图,称之为可视图。由于任意两直线的顶点都是可见的,因此,从起点S沿着这些直线到达目标点的所有路径均是运动物体的无碰路径。对图搜索就可以找到最短的无碰安全运动路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。 可视图法的优点是概念直观,实现简单;缺点是缺乏灵活性,一旦车辆的起始点和目标点发生改变,就要重新构造可视图,而且算法的复杂性和障碍物的数量成正比,且不是任何时候都可以获得最优路径。 2.栅格法。 栅格法是用栅格单元表示整个的工作环境,将自主车辆的连续工作环境离散化分解成一系列的网格单元,一般情况下,栅格大小与自主车辆的尺寸相同,尽量把自主车辆的工作环境划分为尺寸大小相同的栅格,但是也有尺寸大小不同的情况,主要还是根据实际情况来定。自主车辆的整个工作环境划分后的栅格分为两种,即自由棚格和障碍栅格。自由栅格指的是某一栅格范围内不含有任何障碍物;障碍栅格指的是这个棚格范围内存在障碍物,有的时候可能整个栅格内都布满障碍物,有的时候可能只有栅格的一部分是障碍物,但是只要有障碍物的存在就被称为障碍栅格。
栅格的标识方法有直角坐标法和序号法两种。直角坐标法以栅格左上角第一个栅格为坐标原点,水平向右为x轴正方向,竖直向下为y轴正方向,每一个栅格区间对应于坐标轴上一个单位长度。序号法就是从栅格阵左上第一个栅格开始,按照先从左至右,从上至下的顺序给每一个栅格一个编号。
均匀分解法中栅格大小均匀分布,占据栅格用数值表示。均匀分解法能够快速直观地融合传感器信息,但是,它采用相同大小栅格会导致存储空间巨大,大规模环境下路径规划计算复杂度增高。
为了克服均匀分解法中存储空间巨大的问题,递阶分解法把环境空间分解为大小不同的矩形区域,从而减少环境模型所占空间。递阶分解法的典型代表为四叉树分解法和八叉树分解法。八叉树分解法是2D四叉树结构在3D空间的扩展，用层次式的3D空间子区域划分来代替大小相等、规则排列的3D栅格,能够较好地表示三维空间。
栅格法对环境空间的划分方法和操作都比较简单,有一致的规则,较容易实现。但由于连续的工作空间被划分为离散的栅格空间,没有考虑环境本身固有的些特点,这就使得栅格属性代表的信息具有片面性,并且栅格法对栅格大小的划分有很大的依赖性,当栅格划分较小且当环境很复杂时,搜索空间会急剧增大,算法的效率就会相当低。
3.自由空间法。
自由空间法是采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,然后通过搜索连通图来进行路径规划。
自由空间法比较灵活,起始点和目标点的改变不会造成连通图的重构,但算法的复杂程度与障碍物的多少成正比,且不是任何情况下都能获得最短路径。
4.拓扑法。
拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。将规划空间分割成具有拓扑特征一致的子空间，根据彼此连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。
拓扑法中自主车辆所处的环境用图形来表示,不同的地点用点来表示,不同点的相邻可达性用弧来表示。拓扑法的优点是不管环境多么复杂,都能找到无碰路径;缺点是建立拓扑网络的过程相当复杂,其计算量十分庞大。在障碍物数量增多或障碍物位置改变的时候,修改原来的拓扑网络是很棘手的问题。
总之,环境模型建立方法很多,可以根据具体情况选择,也可以把几种方法结合起来。
二、路径规划的经典算法。
路径规划的经典算法主要有 Dijkstra算法、A*算法、D*算法等。
1. Dijkstra算法。
Dijkstra算法是最经典的路径搜索算法,寻找解的质量稳定,计算速度快。
Dijkstra算法使用全局搜索,不但能够保证在一个区域当中找到两个坐标之间的最短路径,而且能够找到区域中某一点到其他点中的最短路径。
Dijkstra算法的基本思想:若每个点设都有一个坐标(dj,pj),其中dj是原点O到某一点j的一条长度最短的路径;p则是d,的前一个点。求解从原点O到某一点j的路径中最短的一条路径,其算法步骤如下。
①判断路径规划的可行性,即起始点和终点的选择是否可行和存储结点的容器是否正确,将存放节点的容器初始化,然后把所有结点粘贴到临时缓存。
②首先查找离第一个节点最近的相关节点和两者之间的道路信息,并把它们都存储起来,然后查找与之距离最短的一个节点是不是终点,假如是终点,那么将节点存储起来,返回;若不是,则从暂时缓存中删除第一个节点,执行下一步操作。
③寻找离目前中间点最近的一个节点,将此节点存储起来。
④再次判断目前节点是不是线路规划的终点,假如是则返回节点,若不是则可以删除临时缓存中的已分析节点,重新回到步骤③。
Dijkstra算法的核心方法就是对当前网络中存在的所有节点开始查找,找到第一个节点到任意一个节点的最短线路。这种方法并没有考虑到任何节点是否存在方向性,因此 Dijkstra算法具有比较好的计算可靠性、稳定性,但同时也存在着缺点,在范围较大的路径规划中, Dijkstra算法计算效果不是很好。
2.A*算法。
在静态路径下的规划算法中常用的算法为A*算法。它是一种启发式搜索策略,能根据求解问题的具体特征,控制搜索往最可能达到目的地方向前进。这种搜索策略针对问题本身特点进行,因而比完全搜索的方法效率要高很多,它往往只需要搜索一部分状态空间就可以达到目的地。
A*算法是目前最为流行的最短路径启发式搜索算法,它充分运用问题域状态空间的启发信息,对问题求解选取比较适宜的估价函数,再利用估价函数的反馈结果,对它的搜索战略进行动态的调节,最终得到问题的最优解。A*算法给出的估价函数为：
式中,f(j)为估价函数;g(j)为从原点到当前节点j的代价:h(j)为从当前节点j到目标节点之间的最小代价的估计函数。
当h(j)=0时,即h(j)没有用到任何启发式信息,此种情况下,A*算法会演变衰退为一般的 Dijkstra算法。因此,在一般情况下,h(j)到底为何种样式应该按照待求问题的实际情况而定,但是它务必需要使估价函数中的h(j)项小于等于点到目标节点的实际最小代价,根据这样的搜索策略,就肯定可以找到最优解。
在最短路径问题中,h(j)可选择为当前顶点到目标顶点的直线距离d(j)，而g(j)则选择为原点到当前节点的实际距离d(j),则估价函数为：
A*算法步骤如下。
①赋给初始值,初始化所有节点、临时缓存和关联容器。
②计算初始节点和各个相关节点的权值f(j),然后保存起来,从中获得权值最小的节点,并保存该节点,最后把它从节点存储器中去掉。
③计算该节点是不是终点,假如是终点就返回节点,若不是终点就接着计算下一步。
④获得所有的中间节点与相关节点的权值f(j),然后开始判断,假如这个节点没有保存,那么把这个节点存储起来:假如这个节点已经保存,比较这个节点的权值和已保存节点的权值大小,如果不大于已保存权值,则开始更新替换。
⑤查找中间点的关联节点中权值最小的一个节点,将该节点保存,然后将其从节点缓存中去掉,并转到步骤③。
A*算法的独特之处在于使用估价模型函数,这种算法会自动的使运算结果趋向于目的地,因此,它查找的节点越少,存储空间被占用的越少。与其他算法相比,如果它们的时间复杂度是一样的,A*算法在实际应用中效果会更优越。
3.D*算法。
A*算法主要是在静态的环境下进行最短路径规划,但在实际环境下,可能由于交通环境复杂,路面的行人、路障、非机动车辆、机动车辆以及其他各种动态障碍物都会影响车辆的行进,所以有必要进行路径的动态规划。典型的动态规划算法为D*算法。
D*算法步骤如下。
①利用A*算法对地图上给定的起始点和目标点进行路径规划,建立OPEN表和 CLOSED表,存储规划路径上的每一路点到目标路点的最短路径信息。
②在车辆对规划出的路径进行跟踪时,当下一个路点没有障碍能够通行时，则对上面规划出的路径从起始路点向后追溯到目标路点,直至车辆到达目的地。当在跟踪到某一路点Y时,检测到在下一路点处有障碍发生时,则在当前路点处重新建立对后续路点的规划,保存障碍物之前的路点在OPEN表和 CLOSED表里的信息和指针,删除障碍物之后路点在OPEN表和 CLOSED表里的信息和后继指针。
③利用A*算法从当前路点Y开始向目标路点进行规划,重新规划得到最短路径。回到步骤②。
三、路径规划的智能算法。
路径规划的智能算法主要有遗传算法、模拟退火算法、蚁群算法等。
通过蚁群算法求解某些比较复杂的优化问题时,则将体现出该算法的优越性,同时蚁群算法自身也具有不少缺陷。蚁群算法具有以下优点。
①蚁群算法在优化问题领域具有很强的搜索较优解的能力,因为它能够把一些常用的分布式计算、贪婪式搜索等特点综合起来,并且是一种正反馈机制的算法。想要快速地发现较优解,可利用正反馈机制得到;而过早收敛现象可由分布式计算来排除;这样在查找过程的前期,就会找到可实施的方法,同样,若要减少查找过程消耗的时间,可通过贪婪式搜索来实现。
②蚁群算法具有很强的并行性。
③蚁群中蚂蚁之间通过信息素展开协同合作,则系统会有比较好的可扩展性。
蚁群算法也具有以下缺陷。
①蚁群算法需要消耗比较多的时间来查找。尤其是在群体规模较大时,由于蚁群中的蚂蚁活动是任意的,即使利用信息交换都可以找到最优路径,但在不是很长的时间里,很难发现一条比较好的线路。由于在刚开始寻找路径时,各线路上的信息浓度大小几乎是相同的,这样就存在一定困难。虽然利用正反馈方法反馈信息,能够让好线路上的信息量越来越多,但是需要消耗很长的时间间隔,才能使较多的信息量出现在较好的路径上,伴随正反馈的不断进行,会产生明显的差别,从而得到最好的路径。这一过程需要较长时间。
②当查找过程进行到一定阶段时,蚁群中蚂蚁查找到的解相同,很难能够在深层次去查找得到更好的解,使算法出现停滞现象。
除了上述算法之外,还有其他很多算法,如基于广度优先搜索、深度优先搜索、最小生成树、神经网络、层次空间推理等。
