发布时间 : 星期三 文章机器人路径规划演示平台设计更新完毕开始阅读7efab99de53a580217fcfe01
山东建筑大学毕业论文
要包含了超声波测距原理的研究和避障算法的研究。由于避障过程解决的不只是机器人避开障碍物，还为机器人提供了轨迹的规划走向，所以，智能避障过程又被称为机器人轨迹规划。目前常用到的路径规划方法主要有人工势场法、栅格法、神经网络等。
2.3 栅格法 2.3.1 栅格法简介
栅格法是由W.E.Howden[4]在1968年提出来的，他在进行路径规划时采用了栅格来表示地图。栅格法属于环境建模技术方面的研究，也称作是单元分解建模。已经在许多机器人系统中得到应用，是使用上较为成功的一种方法，这属于一种近似的描述建模，当然它的离散特性也有利于栅格地图的创建和维护。该方法的特点是简单和易于实现，易于扩展到三维环境。但它对工作区域的大小有一定的要求，如果区域太大，将使栅格的数量急剧增加，使搜索存在组合爆炸的问题。栅格法是后来许多方法的一个基础，而且随着激光、摄像头对三维环境重建的发展来看，这种方法也将一直不断地发展下去。
进行路径规划时我们用栅格表示地图，假设环境的最大长度为L，宽度为W，栅格的尺度可以根据需要确定值，在本论文里假设长和宽均为b，也就是假设每个栅格为一个正方形，那么栅格数就为（L/b）*（W/b），环境Map由栅格构成：
Map={mapi=0或1，i为整数}
其中mapi表示该栅格为自由区域（即此栅格机器人可安全通过），mapi表示该栅格为障碍区域（即此栅格机器人无法安全通过或者此栅格某部分机器人无法安全通过）。
栅格法将机器人规划空间分解成一系列的具有二值信息的网络单元，工作空间分解成单元后则使用启发式算法在单元中搜索安全路径。搜索过程多采用四叉树或八叉树表示工作空间。基于四叉树的环境表示方法实质上是一种层次化的表达方式，是基于环境中非相似区域的不断递归分解。本论文采用的是八叉树的方式，栅格的一致性和规范性使得栅格空间中邻接关系的简单化。赋予每个栅格一个通行因子后，路径规划问题就变成在栅格网寻求两个栅格节点间的最优路径问题。
栅格法以基本元素为最小栅格粒度，将地图进行栅格划分，基本元素位于自由区取值为0，处在障碍物区或包含障碍物区为1，这样在计算机中建立一幅可用于路径规划的地图。 用尺寸相同的栅格对机器人的二维工作空间进行划分，栅格的大小以机器人自身的尺寸为
- 8 -
山东建筑大学毕业论文
准。若某个栅格范围内不含任何障碍物，则称此栅格为自由栅格；反之，称为障碍栅格。自由空间和障碍物均可表示为栅格块的集成。
栅格法通过优化算法完成路径搜索，该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短，栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降。在密集环境下发现路径的能力减弱，栅格划分小了，环境分辨率高。在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长，可以采用改进的栅格法弥补原栅格法的不足。这些方法虽然计算的实时性很强，便于机器人的动力学优化控制和实时路径规划，但却保证不了能够寻求到全局最优的路径。栅格法是将机器人工作环境分解为一系列具有二值信息的网格单元，采用均匀的栅格覆盖整个工作空间，从而将其分成被障碍物占据的栅格和自由的栅格，障碍物栅格和非障碍物栅格具有不同的识别值，然后用启发式算法在栅格中搜索一条无碰撞路径，即要求路经的栅格都必须是自由的。该方法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。
2.3.2 栅格法算法原理简介
移动机器人在二维平面上的有限运动区域（环境地图）上运动，其内部分布着有限多个静态障碍区，障碍物的坐标位置有栅格的编码表示。为了简单起见将移动机器人的模型可以转换为点状机器人，这样机器人就可以忽略不计，可以将静态障碍物的尺寸以障碍物的边缘分别向外扩展到机器人本体长、宽方向上最大尺寸的一半，经过这样的处理之后，可以使得障碍物的边缘为安全区域，并且各障碍物之间及障碍物与区域边界不想交。
环境信息的描述要考虑三个重要的因素：(1) 如何将环境信息存储与计算机当中；(2)要求环境信息方便使用；(3) 问题的求解要求有实时性和高效率性。才用栅格法表示环境，每个栅格中都有一个概率，概率为1表示这个栅格中存在障碍物或部分被障碍物占有，概率为0表示此栅格为自由区域，移动机器人可以自由通过。栅格大小的选取直接影响到算法的性能，栅格选的小，环境分辨率高，但抗干扰能力弱，环境信息存储量小，决策速度快，但分辨率下降，在密集障碍物环境中发现路径的能力减弱。在一般情况下，栅格的大小与机器人的移动步长相适应，即机器人的移动就可以转化为从一个完全可行栅格移动到另外一个完全可行栅格。
- 9 -
山东建筑大学毕业论文
则路径规划问题的一般表述如下：设起始点的位置即为机器人的位置（假设用A表示），在整个栅格环境中运动，机器人的位置可以用起始位置的编号来表示。整个网络环境假设用map表示，即把map划分为一个个大小相同的6*6的方格，整个运动环境中的静止障碍物栅格区用Bi（i=1,2,3，…，n）表示，Bi表示第i个障碍物区在整个环境为位置map中所占的区域的号码编号。依照不同的环境情况，障碍区域的信息可能已知，也可能未知。在机器人运动的每个时刻，将障碍物区Bi映射入位置环境map，则在位置环境map中的避障空间表示为mapB={q?map,A(q)?Bi=?},其中q为位置空间的某一个栅格位置，A(q)表示机器人处于q点。路径规划就是寻找从A的初始位置到目标位置（假设用B表示）的避障路径。运动空间中的每个栅格表示一个自由区域或者障碍区域，这些区域用如下函数来描述：map（i）=1表示i为障碍物区域，map（i）=0表示i是自由区域。因此，整个运动环境转换为一个二进制方阵，即等价成一个二维数组，记为mapB，这样障碍区域在mapB中被划分为一个map（i）=1的区域。
根据栅格位置的不同，可以将栅分为中间栅格和边界栅格。面对中间栅格，下一步可有八个方位进行搜索，即：东、南、西、北、东北、东南、西北、西南；面对边界栅格，则要去掉不可行的方位，顶角栅格只有三个方向可用，图2.1显示栅格为左下角栅格时，只有北，东北和东三个方向的栅格。
北 东北 东 图2.1 左下角栅格
若栅格为边界栅格时则有五个方向，如图2.2所示，在栅格为最左边界栅格时，则存在北，东北，东，东南，南，五个方向的栅格。
- 10 -
山东建筑大学毕业论文
北 东北 东 南 东南 图2.2 最左边界栅格
2.3.3 路径选择概率
设在第i条路径的搜索中,当前的位置位于栅格u处,设与u相邻的完全可行方位的集合为V,v是V中的任一完全可行方位,在这里u和v均表示它们在环境地图中的栅格序号,那么集合V中任一完全可行方位被选择的概率公式为:
?0??puv???(iv)??(iv)???(ik)??(ik)???k?V栅格u，v之间完全不可行栅格u，v之间完全可行 （2.1）
puv越大,也就表明第i条路径从u到v的几率也就越大。
2.3.4 栅格法优缺点分析
优点：简单、易于实现，易于扩展到三维环境。
缺点：对工作区域的大小有一定的要求，如果区域太大，将使栅格的数量急剧增加，使搜索存在组合爆炸的问题。 2.4 人工势场法 2.4.1 人工势场法原理
人工势场法是由Khatib于1985年提出的一种虚拟力法，实现了机械臂的实时避障，其基本思想是将机器人在环境中的运动视为一种虚拟的人工受力场中的运动，障碍物对机器
- 11 -