1.环境建模
车辆依据自身的惯性定位传感器及其相机、毫米波雷达、激光雷达等传感器组成的系统获取车辆当前的位置信息及其环境信息，构建对应的环境地图。环境地图可分为二维环境地图和三维环境地图两大类，二维环境地图考虑到了车辆的尺寸信息、障碍物分布信息及尺寸信息及不可行区域信息，但并未考虑到地形的高度、坡度等三维信息，反之，三维环境地图具有上述特点。
1.1二维环境建模
二维地图建模的方法可分为栅格法、可视图法、Voronoi（沃罗诺伊）图法、拓扑法、四叉树等。下面依次对各种方法进行简单阐述。[i]
1.1.1栅格法
栅格地图是将机器人的工作环境空间分解为多个简单的区域（栅格），并由这些栅格构成一个连通图。其数据类型主要是用 0 和 1 表示（1 代表该栅格包含障碍物，0 代表该栅格不包含障碍物）。栅格法建立地图不仅简单有效，而且对于障碍物的适应能力强，并可以降低建模的复杂性以及便于计算机储存和处理。但是栅格法建模也存在一些缺点，例如栅格划分越小，其精度则越高从而也大大增加计算机数据存储量以及算法计算的复杂度。而栅格划分越大，地图的精度却往往达不到要求。栅格地图如下图3所示，黄色栅格为起点，深色栅格为目标点。
1.1.2可视图法
可视图是将工作环境中移动机器人视为一点，障碍物的轮廓用凸多边形表示，然后用线段将机器人所在点（起点）、凸边形障碍物的顶点、目标点进行连接，但要求连线不能穿越障碍物，这样形成一张机器人的工作环境地图，称为可视图。采用路径规划算法在可视图上进行路径搜索，车辆沿着环境中规划出的路径序列行驶。若可视图比较复杂时，可以运用相应优化算法剔除可视图中一些不必要的连线，进而简化可视图从而缩短路径搜索时间。可视化法进行地图建模，不仅比栅格法消耗计算机数据存储量小，而且在可视图中进行路径规划时直观，容易求得最短路径。但当机器人的起点和目标点发生改变，则需要重新构造新的可视图，即其局部规划能力会变差。
1.1.3voronoi（沃罗诺伊）图法
沃罗诺伊图考虑了安全等因素（如机器人路径规划中对机器人碰撞的安全性考虑），要求规划路径与障碍物之间有一定的距离。中，沃罗诺伊图由直线组成，而直线由距两个障碍物或多个障碍物等距离的所有点构成。初始点 和目标点 的配置被映射到沃罗诺伊图的 和 ，各由画直线得到，沿着该直线到障碍物边界的距离增加最快。在沃罗诺伊图上也可选择运动方向，使之距边界的距离增加最快。沃罗诺伊图上的点表示从直线段（两直线间的最小距离）到抛物线段（直线和点之间的最小距离）的过渡。当配置空间障碍物都是多边形时，沃罗诺伊图由直线和抛物线段组成。该方法的优点是计算速度快，寻得的路径较安全，离障碍物较远，且路径较平滑，合理性较好；缺点是路径常常不是最优路径。而将沃罗诺伊图法用于机器人自建图中的二次建模，提高建图的效率。
1.1.4拓扑图
拓扑图法是将机器人的工作环境表示为带节点和相关连接线（无向边）的拓扑结构图。在拓扑地图中，用节点来表示机器人工作环境中特定的位置点，例如工作站点、拐点、交叉路口等。边用来表示节点之间的连接，例如走廊等。其中拓扑地图中边为可行路径，AGV 可以沿着边行走。拓扑法建立电子地图简单紧凑，不仅可以表示节点的信息，而且可以表示节点与节点的长度信息、路径与路径之间角度信息。但是在拓扑法建立模型上，AGV 的运动会受到一定的限制，并且由于信息的抽象性使得 小车难以实现精确可靠地进行自定位，需要人工设定路标进行精确定位。图 2-3 为拓扑图，0-9 标识为节点，0 表示机器人的起点，1、4、7表示交叉路口，2、3、5、6、8、9 表示工作站点（任务点）。拓扑地图模型如图所示：
1.1.5四叉树法
四叉树法是将图像表示成一棵树，树根就是原图像本身，定义为除边沿节点外，树中每个节点均有个子节点，分别对应于原图像或图像块象限的子块。这一算法通过不停地把要查找的记录分成部分来进行匹配查找直到仅剩下一条记录为止。根据划分方式不同，可以分为矩形四叉树法和三角形四叉树法，如图所示：
1.2三维环境建模
对比二维地图，三维地图多了地形高度和坡度信息，下面针对地形高度及其坡度信息进行阐述[i]。
1.2.1地图坡度定义
由于在复杂野外环境中，倾斜坡是属于比较特殊的地形，此类地形的通过性与坡度和车体的位姿以及无人车的性能有关。坡度地形就其坡度变化不同而分为多种类型的地形。如下表所示。
地形图中，坡度变大的，则形成陡坡、悬崖，峭坡等垂直障碍；障碍边缘地面起伏过快，则形成凸障碍；而对于坡度变化较为缓慢的坡度地形，如微斜坡、缓斜坡、斜坡地形无人车有可能通过的，坡度越大无人车通过此处的安全性越低。为了方便对坡度的表示，将野外环境地形的实际地形曲面的拟合平面画出来，拟合平面的平面法向量与 z 轴平行线之间的夹角则为此实际地形的坡度。坡度示意图如下：
1.2.2地图高度定义
为了更好的计算路径的坡度，对地图进行等高线提取，在跌宕起伏的野外环境的地形中，将高程相等的各个点连接起来，形成海拔高度相同的闭合的曲线，投影到二维的水平面上形成地形的等高线。在等高线的地图中，等高距相同的情况下，等高线越密集，则表示地形的坡度越陡，等高线越稀疏，则代表了此处的地形越平缓，将野外地形提取等高线的示意图如图所示：
2.路径规划算法
2.1基于图搜索的路径规划算法
基于搜索的算法有Dijkstra、A*算法及其衍生的变种算法D*算法、LPA*算法、D* Lite算法等，下面着重讲解Dijkstra与A*算法。
2.1.1迪杰斯特拉(Dijkstra)
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个节点遍历其余各节点的最短路径算法，解决的是有权图中最短路径问题。
算法思想：
1.设是一个带权有向图，把图中节点集合分成两组，第一组为已求出最短路径的节点集合(用表示，初始时中只有一个源点，以后每求得一条最短路径,将该节点加入到集合中 ，直到全部节点都加入到中，算法结束。
2.第二组为其余未确定最短路径的节点集合(用表示),按最短路径长度的递增次序依次把第二组的节点加入中。在加入的过程中，总保持从源点v到中各节点的最短路径长度不大于从源点v到中任何节点的最短路径长度。
3.此外，每个节点对应一个距离，节点的距离就是从v此节点的最短路径长度，中的节点的距离，是从v到此节只包括中的节点为中间节点的当前最短路径长度。
算法步骤：
（1）初始时只包含起点；包含除 外的其他节点，且中节点的距离为“起点 到该节点的距离”[例如，中节点v的距离为的长度，然后 和 v不相邻,则v的距离为∞]。
（2）从中选出“距离最短的节点k”并将节点 k加入到 中；同时，从 中移除节节点 k 。
（3）更新中各个节点到起点。之所以更新中节点的距离，是由于上一步中确定了k是求出最短路径的节点,从而可以利用k来更新其它节点的距离；例如，的距离可能大于+.
2.1.2 A*(A-Star)算法
A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法，被广泛应用于室内机器人路径搜索。优点：使用广泛，运行速度快，效率高，使用与很多地形，可以找到较优的路径。缺点：并不能找到最优的路径，在局部路径时容易出现很多曲折，而且评估函数并未考虑到车辆的转角和转向次数.表中会含有不需要的点等问题.
A*(A-Star)算法结合了贪心算法（深度优先）和Dijkstra算法（广度优先），是一种启发式搜索算法。路径优劣评价公式为：
其中f(n)是从初始状态n由状态到目标状态的代价估计，g(n)是在状态空间中从初始状态到n的实际代价。h(n)是从状态n 到目标状态的最佳路径的估计代价。路径优劣判断依据是移动代价，单步移动代价采取Manhattan 计算方式，即把横向和纵向移动一个节点的代价定义为1.斜向移动代价参考等腰三角形计算斜边的方式。
使用了两个状态表，分别称和。表由待考察的节点组成，表由已经考察过的节点组成。
算法步骤：以图为列：
1.首先考察g,由于从A到该格子是斜向移动，单步移动距离为,故g为。
2.再考察估计代价h，估计的含义是指忽略剩下的路径是否包含有障碍物（不可走），完全按照Manhattan计算方式，计算只做横向或纵向移动的累积代价：横向向右移动3步，纵向向上移动1步，总共4步，故为4 。
3.因此从A节点移动至I节点的总移动代价为：f=+1。 以此类推，分别计算当前中余下的7个子节点的移动代价，挑选最小代价节点F,移到,现在,.
4.从中选择 值最小的 (方格) 节点I,放到,并把它作为新的父节点。检查所有与它相邻的子节点，忽略障碍物不可走节点、忽略已经存在于的节点,如果方格不在中,则把它们加入到 中，即把加入.
5.如果某个相邻的节点已经在,则检查这条路径是否更优，更新计算移动单价估计值，也就是说经由当前节点( 我们选中的节点)到达那个节点是否具有更小的g值。如果没有，不做任何操作。
6.依次类推，不断重复。一旦搜索到目标节点,完成路径搜索，结束算法。
2.2基于采样的路径规划算法
2.2.1RRT算法
RRT 算法最早由 La Valle 在 1998 年提出，是一种基于随机采样的路径规划算法，其可以直接应用于非完整约束的系统的路径规划，且在多维复杂环境中具有极高的搜索效率，相比于如A*算法之类的其他算法，其搜索效率不会随着环境维度的上升而出现明显的下降，在其提出之后的 10 多年中，RRT 算法无论在应用上还是在理论上都经历了突飞猛进的发展，并且衍生出了许多种行驶，比如双树RRT_Connect算法、Informed RRT*算法、RRT*算法，下面对RRT算法进行原理介绍。
(1)确定起始点和目标点，并以 为起点产生随机树，即作为根节点。
(2)在空间中选定一随机点。由于初始时，只有起点，直接选取起点为最近点。以最近点和随机点的连线为生长方向（随机点仅起确定生长方向的作用）如果随机点最近点与随机点发生障碍物碰撞，重新开始步骤（2），直至不发生碰撞，确定。
(3)在随机树的所有节点中选择与重新生成的随机点最近的一点 作为邻近点，随机树从邻近点为起点向方向以算法的步长为长度生成一个新的节 节点,为父节点。如果邻近点向新节点 向新节点 方向扩展过程中不与障碍物发生碰撞，则将新节点放入随机树中，若发生碰撞，重新采样随机点。
(4)直到新产生的节点与目标点的距离小于算法的步长时，算法停止。算法流程图如图所示。
算法缺陷：
1.由于其随机采样的性质，RRT 算法只能保证搜索得到一个可行解，并非最优解，这意味着即使在求解同一个路径规划问题时，RRT 算法前后两次得到的结果可能截然不同。
2.同样是由于随机采样的问题，RRT 算法并没有一个指向目标位置的导向，因此算法的收敛速度可能较慢。
3.由于传统的 RRT 算法与 A*算法一样都是一种全局搜索算法，因此一般应用于静态环境的路径规划，较难应用于动态环境的路径规划之中。
[i] 黄小芹.复杂野外环境无人车极限驾驶辅助规划系统设计与实现
[i] 张志文. AGV路径规划与避障算法的研究[D]. 电子科技大学, 2018.
https://space.bilibili.com/477041559?spm_id_from=333.999.0.0
相关文章
您阅读本篇文章共花了：
发表评论