【《移动机器人路径规划算法综述》5500字】

绪论II移动机器人路径规划算法综述目录TOC\o"1-3"\h\u27931移动机器人路径规划算法综述 156241.1地图表示方法 1117831.1.1栅格地图 1299691.1.2其他地图表示方法 4237401.2全局路径规划A*算法 4286901.1.1Dijkstra和BFS算法 553711.1.2A*算法 540131.1.3A*算法在Matlab中编程实现 842891.3局部路径规划 11291111.3.1VFH算法的改进 11151541.3.2VFH演示结果与分析 12对于移动机器人能够自主导航的关键是路径规划算法，他的好坏直接影响移动机器人是否按照预期从起点运动到目标点。本部分将从全局路径规划和局部路径规划两方面，着重分析基于A*算法的全局路径规划和基于VFH算法的局部路径规划算法。1.1地图表示方法任何路径规划算法都是基于环境地图模型而发展出来的。在路径规划算法领域，研究和采用的主流的地图模型是几何特征、栅格和拓扑。1.1.1栅格地图所谓栅格法，是将移动机器人工作空间的障碍物信息分割成同等规格的方形小格，工作环境转换成二维的平面栅格空间。此方法是W.E.Howden提出的[33]。其表示障碍物信息是使用栅格的占用值实现的，通过环境以某一高度水平面截取得到截面图，环境中的障碍物截面面积大小来表征栅格的占用情况。也就是所谓的占用栅格地图，设定某一个障碍物阈值，投影面积大于阈值的栅格确定为障碍物格栅并赋值为1，反之为自由空间赋值为0，对所有的栅格做了处理之后就得到了二值占用地图。在栅格地图模型上对每个栅格进行有序的编号，用于描述其相对位置。如果不做处理，障碍物的位置和体积将不再变化。图2-1显示了一般栅格化过程。本文使用的A*算法就是基于栅格地图而来的。图1.1栅格地图转换过程（1）不规则障碍物膨胀处理移动机器人实际的工作环境是随机多变的，尽管算法上理想的障碍物是具有规则的几何形状，但是仍有概率存在不规则物体，在一般栅格地图下，对于一个栅格来说，占用状态用1表示有障碍物，自由状态(Free)用0来表示，那么只有部分被占据的情况怎么表示？不规则障碍物膨胀处理可以使用占据栅格地图表示方法、通常采用二值膨胀的图像处理法，将障碍物占据的栅格截面面积扩大到几倍栅格尺寸[34]。处理效果如下：图2-2不规则障碍物二值膨胀处理（2）栅格尺寸栅格法将机器人的工作环境简化为一个二维平面模型，在和轴方向建立笛卡尔二维直角坐标系，最大范围到和。栅格中的障碍物信息是离散化的，由于栅格大小，或者分辨率造成栅格地图与实际的障碍物形状位置存在一定的差别。因此，栅格地图分辨率的选取至关重要，通常来说，栅格尺寸作为评判地图质量的标准，当在一个确定大小的平面范围内，栅格尺寸越小或者说分辨率提高，地图精度就越高，与实际环境信息的差别就会减小。但是，当工作环境的范围增大时，越高的分辨率带来的是栅格数量的大幅增加，占用过多的内存空间。反之，当栅格尺寸过小，将导致栅格地图的分辨率偏小，影响地图精度和后续的规划路径的准确性。由于在栅格地图上，各种路径规划算法都将机器人视为质点并且运动后只停留在栅格中心，在使用栅格地图进行路径规划时，为了保证每个栅格都有余量的空间大小使得机器人运动不受阻。通常情况下是以机器人本身最大直径作为最小尺寸基准。建立的栅格地图。计算公式见下两式：(1.1)(1.2)（3）栅格的标识方法应用栅格地图模型描述了环境占用信息，那么在计算机中运行路劲规划算法程序时，怎样得知栅格的环境信息和还原路径的位置呢？栅格的标识就是必不可少的一个步骤。常用的有序号法和直角坐标系法[35]，本文采用后者方法。①直角坐标系法:对于任意二维工作环境，将左下角点设为坐标原点，沿横向和纵向建立直角坐标系的和轴。其中的小栅格边长设置成固定值1，对于不同分辨率下的栅格地图，栅格的实际边长在和轴上按比例伸缩，所以可以用每个栅格的右上角点的坐标标识栅格的位置。如图2-3所示，序号为15的栅格其坐标是(5,3)；序号为81的栅格其坐标为(1,9)。图2-3栅格地图直角坐标系法标识②编号法:根据建立的栅格地图中的所有栅格按照从左下角开始，一般情况下是从左到右、从上到下的顺序从1到进行编号。通常计算机将栅格地图信息数据存储为矩阵形式，因此编号也称为线性索引(index)，具体的编号顺序要结合使用的编程软件合理选择。栅格编号号与坐标之间有对应关系，如编号为12的栅格坐标为（2,2）、97号栅格坐标为（7,10），它们之间的关系：(1.3)(1.4)上两式中，表示对应序号栅格的直角坐标。1.1.2其他地图表示方法(1)几何特征地图本地图是使用一种或多种探测装置感知并收集工作环境的障碍物信息，然后以相同特性为提取原则，得到基本的几何元素特征来建立地图模型[36]。移动机器人工作环境中的物体特征描述成点线面角等基本几何量，用这些基本几何量来表示的地图简洁而紧凑，有利于计算机存储和快速处理，机器人能够迅速且准确的知道障碍物的几何特征和自我定位。但是该地图模型在高维、复杂的大空间场景中，难以对所有物体完成精确的特征抓取，抽象过程复杂；其次，该地图上的数据相关性不大，对传感器精度和稳定性要求比较高。拓扑地图拓扑地图是由点和线构成的，跟几何特征地图相反的是它十分强调地图上重要节点之间的关联度的地图模型。对于移动机器人的规划地图来说，它将工作环境中所有可行的特定局部范围浓缩为一个节点，而点前面的连线上标识的权重数字表示两个局部范围之间的运动代价[37]。这种拓扑地图比几何特征地图模型更简洁，数据结构简便易于计算机存储和处理。但没有考察了机器人自身运动限制及周围环境的具体状态，对智能移动机器人的精确定位和自主导航产生较大影响。特别适用在大范围环境下，忽略运动本身制约的场景中，应用典型的如各种手机导航软件算法。1.2全局路径规划A*算法1.1.1Dijkstra和BFS算法Dijkstra算法是一种贪心算法，以起始点为原点逐层向外扩散迭代，直至遍历到所有节点的最短路径[38]。Dijkstra能够保证找到最短路径，图2-4(a)中所示：红色为起点，绿色为目标点，灰色的栅格表示算法考察过的节点。最佳搜索算法（BFS）与Dijkstra方法类似，关键差异是一个称为启发式的估计函数，即当前节点到目标节点的预估代价，侧重选择检查最接近目标点的的节点，该方法不一定能够找到短路径，但是它舍弃了很多没有必要检查的节点，算法运行效率得到明显提高。使用了启发式函数可以非常快速的朝着目标搜索，图2-4(b)为BFS算法得到的路径图。aDijkstra规划路径bBFS规划路径图2-4Dijkstra算法与BFS算法路径规划比较图通过上两图比较可以发现，Dijkstra算法遍历的节点较多，运行速度较慢，但是一定能找到一条最短路线。BFS算法虽然减少了不必要检查的节点数目，提升了算法的效率，但是规划出的路径并不是全局最优的，我们分析其原因：BFS算法中的估计函数是以离目标最近的点计算的，因此算法只看重目标，对之前付出的移动代价并不考虑在内，导致最终的路径长度不够理想。很显然，将两者算法的思想结合起来，理论上能够既保证规划路径全局最优，又保持了BFS高效率的特点。1968年，斯坦福研究院的P.E.Hart、N.J.Nilsson等人共同发表了A*算法，它建立在启发式函数之上，能够保证算法高效率并且找到一条最短路径。1.1.2A*算法A*算法是一种在静态环境地图上求解最短路径问题的方法,这种算法具备超群的场景适应能力和较高的改进的灵活度，在智能移动机器人的路径规划领域广泛应用，最大的优势是容易与其他优化算法融合。其算法核心是代价函数[39]：(1.5)其中：：总代价估计，从起始点经过中间点到目标点的移动代价；：起始点到达当前中间节点的实际移动代价；：中间点到目标点的估计代价,作为A*算法的启发式函数,预测当前节点到目标点的代价,选择最接近目标点的子节点作为搜素节点，有目的性的快速导向目标节点,。启发式函数是该算法的核心，影响A*算法的行为。设中间节点到目标点的实际代价，理论上：（1）如果，则A*算法能够找到最短路径，并且随着越小，A*算法搜索节点扩大，速度越来越慢。极端情况，那么该算法只有起作用，会转变为Dijktrsa算法，但还能保证找到最短路径的任务。（2）如果，则A*算法能够保证最快速的找到最短路径，并且永远也不会扩大搜寻节点范围，此时算法的效率最高，实际应用中要尽可能接近实际代价。（3）如果，则A*算法不能保证找到最短的路径，但能较快的找到搜索路径，效率较高；一种极端情况下：，那么该算法衰退为BFS算法。在栅格地图中，若起点A,终点B，传统的A*算法主要有以下三种表征启发式函数的方法：①曼哈顿距离X、Y轴方向上距离之和，其计算式：（1.6）②切比雪夫距离指坐标系中两点之间横纵坐标差值的最大绝对值。其计算式：（1.7）③欧几里得距离指两点之间的直线距离，使用其计算式：（1.8）假设从一个位置移动到相邻位置的最小距离为L，有以下结论：采用曼哈顿距离表征启发函数，在格栅地图中的启发式函数就是曼哈顿距离L的倍数，由于只能前后左右四个方向移动，方向受限，并不是最优的启发式函数。采用切比雪夫距离表征启发函数，它的搜索代价为与初始节点距离相等的所有节点，即每次搜索代价为8*L，并且随着地图增大而剧增，不适合作为启发式函数。采用欧几里得距离表征启发式函数，更能够贴合实际情况：移动小车能够沿着任意方向移动。由于欧氏距离比上面两种距离都短，我们能够得到较优的路径，但运行效率较低。。改变计算的方法，可以控制算法的速度和精度，这是A*算法一个比较灵活的地方，也是A*算法值得改进的空间，可以决定A*算法的最终规划的路径效果，要根据实际应用场景，设计与之相应启发函数。鉴于本文研究地图环境，移动机器人转向能力，选择欧式距离作为启发式函数更加符合要求。A*算法过程中需要至少两个数据表：创建待考察的开放点集合OpenList；已考察且综合代价最低的点集合CloseList。算法输出规划路径点数据表CloseList_Path。传统的8邻域A*算法的过程描述：起点开始，将起点作为父节点放入CloseList；将起点周围的8个子节点放入待考察集合Openlist，若父节点是终点则算法结束，否则循环下两步：（1）计算Openlist中点的g,h,f，将代价f最小的节点放入CloseList，CloseList_Path，（2）将代价最小的子节点视为父节点，找到不包括已在Closelist中的子节点，还需要判断这些节点是否有已存在于OpenList:①若存在：重新计算相同节点的成本，比较前后成本大小，若小于，则Openlist中相应的节点更新为较小成本，否则，不做变化；②若不存在：所有有效子节点追加放入OpenList。图2-5常规A*算法流程图1.1.3A*算法在Matlab中编程实现本小节使用Matlab2020B软件编写常规A*算法脚本程序，分别绘制栅格地图、确定起始点，在计算机程序上实现A*路径规划算法，展示该算法的搜索路径的效果。（1）栅格地图绘制为n*m的二维平面，按分辨率1建立二值占用栅格这个平面，得到二值占用地图矩阵保存在计算机中，如5*7格栅地图，下图2-6所示：图2-6二值占用栅格地图栅格地图上绘制不同的颜色以区分各个格栅块的占用信息情况：绿色起点，红色终点，黑色块为障碍物不可通过。A*算法启发式函数本论文设计使用欧式距离计算：（1.9）设置起点直角坐标（1,4）；终点(7,3)；障碍物（4,2）、(4,3)、（4,4）绘制得到栅格地图，图2-7(a)所示。A*程序运行后输出规划路线并窗口显示，图2-7(b)中折线即为规划的运动路径。a创建的栅格地图b规划的路径图1.7A*算法效果图演示我们继续扩大地图范围到10*10，增加地图上位置随机的障碍物数量，提高环境的障碍物密度。考察A*算法在高占用密度地图上的路劲规划能力。运行结果如图2-8所示。图2-810*10地图规划路径继续拓展栅格地图至50*50，传统A*算法规划路径见图2-9。图2-950*50地图规划路径从图2-9可以看到，在格栅化的大范围地图上，使用欧式距离作为启发式函数传统A*算法规划出的路径就会出现路径不平滑、比较曲折的问题，很多地方是是贴着障碍物边沿行走，在以质点为研究对象的A*算法演示程序中能够正常通过，但是在实际机器人应用上，存在着机器人几何尺寸、速度和障碍物形状等物理特性，在建立栅格模型时就要考虑了机器人尺寸的因数，但仍有可能会导致机器人在循迹的过程中可能会与障碍物发生碰撞，因此还需要增强机器人的实时避障子系统的局部路径规划。1.3局部路径规划全局路径规划依赖于拓扑级地图信息[40]，属于静态规划或者事前规划，规划的精度取决于地图信息是否完全表征了环境信息，然而实际应用场景中，环境信息是动态变化的，基于静态的地图模型而规划的全局路径必然不能实际应用。在智能移动机器人上必须装载距离传感器实时采集实际的环境信息，进行局部的避障的动作。1.3.1VFH算法的改进随着VFH避障方法在路径规划领域的广泛应用，其不足之处逐渐显露出来，越来越限制了它的实际运用效果。因此其改进算法称为VFH+算法。主要作了以下优化[42]：考虑了机器人本身的物理尺寸和必要的安全距离，将栅格地图上的不规则障碍物栅格膨胀化，并适当提高分辨率；（2）考虑机器人运动学约束条件，将实际的车辆最小转向半径考虑在算法程序中；（3）采用双阈值，将极直方图上密度大于高密阈值的方向视为障碍物，低于低密阈值的方向视为候选区域，使算法给出的方向一定是能够通过的，这