【《四轮移动小车A星算法和遗传算法两种小车全局路径规划算法分析》4000字（论文）】

四轮移动小车A星算法和遗传算法两种小车全局路径规划算法分析目录TOC\o"1-3"\h\u15169四轮移动小车A星算法和遗传算法两种小车全局路径规划算法分析 1115391.1全局路径规划研究 1138421.1.1Dijkstra算法与A*算法 1324821.1.2基于遗传算法的小车全局路径规划 4152261.2局部路径规划研究 8146691.3路径规划算法试验 10小车路径路线规划主要是根据最短行驶距离，寻找规划出一条从起始点到目标点之间的无碰撞行驶路径。基于上一章移动小车系统的整体设计，结合二维激光雷达和栅格地图的相关知识，很容易实现小车的路径规划。本章重点研究了A*算法和遗传算法两种小车全局路径规划算法，DWA动态窗口规划算法用以完成局部路径规划。1.1全局路径规划研究1.1.1Dijkstra算法与A*算法Dijkstra算法是用于计算一个节点到另一个节点的最短路径的典型算法。对于单源最短路径，首先指定图中的一个顶点为起点，以起点为中心向外扩展，记录下从起点到各个点的距离。然后在剩余顶点中找出与源点距离最近的一个可行顶点作为第二个点向外扩展，依此类推，直到所有的点都被选完。每个被选定的点组成一条可行路径，该算法为贪心算法的策略。如图1.1所示，这是模拟Dijkstra算法的路径规划。绿色网格是起点，黄色网格是终点，红色网格是基于源点的可行范围，黑色网格是障碍物，蓝色表示区域边界。这种遍历搜索方式的优点是能以最短路径找到最优解，但没有考虑到搜索时间、搜索效率等问题。图1.1Dijkstra算法路径规划A*算法结合了最佳优先级搜索策略，在Dijkstra算法的基础上添加了启发式搜索算法，如图1.2中的算法路径搜索。使用以下函数f(n)来计算每个节点的优先级： (1.1)图1.2A*算法路径搜索f(n)是节点的综合优先级。f(n)由g(n)和h(n)组成，优先级越高，f(n)越小；其中g(n)是当前节点从起点的开销，h(n)是当前节点从终点的开销；每次从优先级队列中选择f(n)值最小的节点作为下一个要遍历的节点。正如栅格地图模型，下列距离模型可用于h(n)：图1.3A*算法流程图曼哈顿距离：，如果图形中只允许四个运动方向，则可以使用此方法表示当前位置的距离。对角距离：，如果每个节点都是正方形，且允许向相邻节点倾斜运动，那么函数可以对角测量。欧几里得距离：QUOTEhn=xn-x0采用的汽车四轮运动底盘，基本上可以实现任意方向的运动，所以选用曼哈顿距离。1.1.2基于遗传算法的小车全局路径规划遗传算法通过全局搜索空间区域，自适应地调整搜索方向直接对结构对象进行操作。路径优化过程如图1.4所示：图1.4路径规划遗传算法流程图提出了一种基于栅格地图构建的移动车辆路径规划方法。单个网格的区域需要综合考虑环境地图的障碍物信息，每个网格都按照建立的坐标系进行编号，其中白网格为可行区域，黑网格为障碍物。对于填充初始化步骤，主要目的是生成多条可达路径。首先在每一行按顺序取出一个无障碍网格，然后用公式1.2判断网格是否连续：（1.2）abs函数是绝对值函数。当且仅当D=1时，这两个网格可以判断为连续的，而其他网格则是不连续的，网格不连续时取中间网格：QUOTExnew=int(xi+1+xi新网格的坐标由公式(1.3)获得，初始化路径流程如图1.5所示。图1.5初始化路径流程图通过初始化路径过程，可以得到无数条连续的路径，最优路径由适应度函数确定。为了实际考虑，我们考虑了两个部分。首先，我们需要实现最短路径。其次，对于研究的四轮移动小车而言，道路的转弯与其他运动方式相比会导致一个巨大的定位误差，因此对路径规划的平滑度要求很高。路径长度计算如下：QUOTEd总=i=1end-1xi遗传算法首先需要经过选择操作，而轮盘赌中的选择方法比基于订单的选择方法更为简单，易于实现。轮盘赌的过程就是选择高概率而放弃低概率。因此，基于轮盘赌选择法，随机选取适应度值较大的第一部分的概率较高，适应度函数的第一部分为：（1.5）对于移动小车路径的平滑度考虑，此时考虑邻近三点间的距离：（1.6）小车的行走方式：直角、钝角、锐角和直角。路径规划的最佳方法是直线，其次是钝角和直角，最不利的方法是锐角。此时，汽车转弯过多，很容易导致汽车姿态的巨大误差。而且，在考虑相邻三点时，直线距离最大，平滑度最高，因此，在路径规划中给惩罚函数剩下的路一个较低的分数。此时，适应度函数的第二部分是：（1.7）完整的适应度函数如下：（1.8）此时，我们需要给适应度函数的第一部分和适应度函数的第二部分赋值，因为有些路径是最短的，但不能考虑平滑度，所以我们需要给a和b赋值，其和为1。在轮盘赌算法的基础上，每个个体出现的概率为：（1.9）在选择过程完成之后，即在个体的数目通过连续复制达到预定数目之后，执行交叉操作。交叉运算符的值设置为0.8以生成0到1的值。当小于0.8时，执行交叉操作，并且确定两条路径中的同一点作为插入操作的交点。完成交叉操作后，判断随机值的大小和交叉算子的0.06，如果小于0.06，则完成变异操作。为了避免突变点的值出现在操作区域之外，必须定义一个新的标记点来替换先前的突变点，并过滤掉不相关的点。MATLAB用于模拟分析。首先，建立了包含400个障碍物单元的栅格地图。起点是左下角的网格，终点是右上角，如图1.6（a）所示。此时，只考虑汽车的最短距离。从图1.6（b）可以看出，算法经过约10次迭代后收敛，网格图的单位长度为1，规划路径中有许多直角和锐角，车辆行走困难。对于图1.6（c），考虑到车辆的路径长度和平滑度，并赋予平滑度更大的权重，规划路径更平滑，两种情况下的路径长度相等。图1.6基于遗传算法的路径规划仿真通过考虑路径的平滑度和最短距离，增加了迭代次数，使路径更为平滑，适合汽车行走。在a=1的情况下，汽车只考虑最短路径。此时，虽然得到了一条较好的路径，但没有考虑汽车的运动学模型。直角或锐角的巨大转角容易导致车辆的定位偏差，因此需要综合考虑车辆路径的平顺性。1.2局部路径规划研究在地图已知的条件下，车辆可以得到全局路径规划，但不能避免遇到临时障碍物。此时需要进行局部路径规划操作并做出避障反应。在完成局部路径规划以避开障碍物后，它可以按照系统规划的一个全局路径进行移动。目前对于局部窗口路径规划主要方法有动态窗口势场法和静态人工窗口势场法。在静态人工势场法中，目的地是引力源。通过虚拟化，目标点将吸引汽车在环境中的位置，环境中的障碍物将击退汽车。因此，可以同时计算汽车在环境中的位置和姿态。人工势场法通过设置相应的参数，可以有效地避开障碍物，具有良好的实时性。然而，不完全的局部信息可能导致错误的路径规划。因此，结合汽车运动学模型，采用动态窗口法进行局部路径规划。动态窗口算法对不同速度空间条件中的多组不同数据速度进行自动采样，并在这些不同速度下自动模拟汽车在特定行驶时间和速度空间条件中的行驶轨迹。动态窗口的主要意义是根据汽车的运动学模型，通过控制增减运动速度，在可行的范围内可以获得有限的速度空间的采样。四轮移动汽车只能向前移动和旋转，轨道是直线或圆弧，所以在短时间内，车速可以看作是一个常数。车辆限速：（1.10）四轮小车的运动是由电机驱动的，电机的转矩是有限的，所以小车的加速度也是有限的，所以单位时间内小车速度的变化也是有限的：（1.11）在式(1.10)中，计算小车的最大加速度和减速度。如果环境中有障碍物，则需要在障碍物前方一定距离处停车。考虑到车辆的加速度，速度范围为：（1.12）式中，表示在采样空间中，当前采样值下距障碍物最近的距离。这种情况需要模拟汽车的运动轨迹。当观察到障碍物时，只有当前的采样速度才能允许车辆停在障碍物前面，此速度将被接受。小车速度的空间范围如式(1.12)所示：（1.13）确定最优轨道是必要的：(1.14)在公式(1.14)中，指的是方位角评价函数，用来评价四轮移动小车以当前速度到达模拟轨道末端时方向与目标之间的角度误差。是指到评价函数的距离，并计算出与障碍物之间的距离。如果此时道路上没有障碍物，这是一个常数。指的是评价函数的速度，在局部导航的过程中，小车不仅能避开障碍物，还能以更高的速度到达目标点。为了使评估过程顺利进行，有必要在添加前对这三个部分进行规范化。(1.15)规范化方程（1.13）中的三个评估函数，其中n是轨迹总数，i是当前轨迹。通过将三个索引标准化，然后将它们相加，可以平滑评价函数，并避免某个索引过大。为了反映汽车的局部规划能力，采用了MATLAB仿真分析方法。首先，将起点坐标定义为坐标轴的原点，终点为坐标系中的（10，10）。图1.8显示了汽车的本地路径规划和导航。地图上的障碍物信息用图中的红色圆圈表示，汽车在地图上不断规划路径，通过在评价函数在地图上选择正确的路径运动，达到避障和合理规划的目的。 （a） (b) (c) (d)图1.7动态窗口算法导航从图1.7可以看出，这辆车不断规划着穿过DWA的路线。该车通过绿色终端规划得出的每组速度矢量估计其运动轨迹，并通过评价函数得到最优路径，实现避障。DWA算法还可以实现从起点到终点的路径规划。但由于速度矢量计算量大，计算速度受到很大影响，导致计算时间长。1.3路径规划算法试验在研究基于地图的路径规划之前要构建好小车所在环境的地图。通过鼠标构建好地图后，首先进行小车定位初始化，将小车摆放在地图的任意位置，通过2DPose校正小车位置，使小车停放位置与构建地图时小车的起始位置一致，这样就可以让小车位置与地图位置更好的匹配。通过ROS操作系统中multi_goals启动已经构建好的多点导航地图并且启动激光雷达，激光雷达根据默认的转速高速转动。运行rviz操作系统后，就可以看见小车处于已构建好的地图中,如图1.8（a）。然后设定目标点位姿，在文件中选择文件名2DNavGall，在目的地的位置长按鼠标左键，使绿色箭头的方向与起始点到目标点的方向一致，如图1.8（b）。(a)小车定位初始化