环境模型建立方法主要有可视图法、栅格法、自由空间法和拓扑法等。 ⒈可视图法。 在C空间( Configuration Space,位姿空间)中,运动物体缩小为一点,障碍物边界相应地向外扩展为C空间障碍。在二维的情况下,扩展的障碍物边界可由多个多边形表示,用直线将物体运动的起点S和所有C空间障碍物的顶点以及目标点c连接,并保证这些直线段不与C空间障碍物相交,就形成一张图,称为可视图。由于任意两直线的顶点都是可见的,因此,从起点S沿着这些直线到达目标点的所有路径均是运动物体的无碰路径。对图搜索就可以找到最短无碰撞安全运动路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。 可视图法的优点是概念直观,实现简单;缺点是缺乏灵活性,一旦车辆的起始点和目标点发生改变,就要重新构造可视图,而且算法的复杂性和障碍物的数量成正比,且不是任何时候都可以获得最优路径。 2.栅格法。 栅格法是用栅格单元表示整个的工作环境,将自主车辆的连续工作环境离散化分解成一系列的网格单元,一般情况下,栅格大小与自主车辆的尺寸相同,尽量把自主车辆的工作环境划分为尺寸大小相同的栅格,但是也有尺寸大小不同的情况,主要还是根据自己的实际情况来定。自主车辆的整个工作环境划分后的栅格分为两种,即自由栅格和障碍栅格。自由栅格指的是某一栅格范围内不含有任何障碍物:障碍栅格指的是这个栅格范围内存在障碍物,有的时候可能整个栅格内都布满障碍物,有的时候可能只有栅格的一部分是障碍物,但是只要有障碍物的存在就称为障碍栅格。 栅格的标识方法有两种,即直角坐标法和序号法。直角坐标法以栅格左上角
第一个栅格为坐标原点,水平向右为x轴正方向,竖直向下为y轴正方向,每一个栅格区间对应于坐标轴上一个单位长度:序号法就是从栅格阵左上第一个栅格开始,按照先从左至右、从上至下的顺序给每一个栅格一个编号。
均匀分解法中栅格大小均匀分布,占据栅格用数值表示。均匀分解法能够快速直观地融合传感器信息,但是,它采用相同大小栅格会导致存储空间巨大,大规模环境下路径规划计算复杂度增高。
为了克服均匀分解法中存储空间巨大的问题,递阶分解法把环境空间分解为大小不同的矩形区域,从而减少环境模型所占空间。递阶分解法的典型代表为四叉树分解法和八叉树分解法。八叉树分解法是2D四叉树结构在3D空间的扩展用层次式的3D空间子区域划分来代替大小相等、规则排列的3D栅格,能够较好地表示三维空间。
栅格法对环境空间的划分方法和操作都比较简单,有一致的规则,较容易实现。但由于连续的工作空间被划分为离散的栅格空间,没有考虑环境本身固有的些特点,这就使得栅格属性代表的信息具有片面性,并且栅格法对栅格大小的划分有很大的依赖性,当栅格划分较小且环境很复杂时,搜索空间会急剧增大,算法的效率就会相当低。
自由空间法是采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,然后通过搜索连通图来进行路径规划。
自由空间法比较灵活,起始点和目标点的改变不会造成连通图的重构,但算法的复杂程度与障碍物的多少成正比,且不是任何情况下都能获得最短路径。
4.拓扑法。
拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。将规划空间分割成具有拓扑特征一致的子空间,根据彼此连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径拓扑法中自主车辆所处的环境用图形来表示,不同的地点用点来表示,不同点的相邻可达性用弧来表示。拓扑法的优点是不管环境多么复杂,都能找到无碰撞路径:缺点是建立拓扑网络的过程相当复杂,其计算量十分庞大。在障碍物数量增多或障碍物位置改变的时候,修改原来的拓扑网络是很棘手的问题。
总之,环境模型建立方法很多,可以根据具体情况选择,也可以把几种方法结合起来。
