机器人避障-论文正文

1机器人避障问题摘要本文从机器人避障问题的基本算法：福德法出发，先假设机器人行走过程中可以折线转弯，以及机器人行走过程中可以和障碍物发生零距离接触，对第一问也就是普遍机器人寻找最优路径的情况进行求解。问题一中，在建模过程中运用福德法求解最优路径时要涉及到次要障碍物产生干扰，为此我们人为进行简要选择最有可能发生阻扰机器人经过最优路径到达终点的障碍物进行福德法建模，求解最优路径，这样就避免了那些不必要的障碍物的考虑。运用这种想法，我们就可以对第一问中的最优路径进行逐一求解。当把机器人从起点到终点的路径的最优路径确定之后，我们再对此基础模型的路径进行细化，把机器人转弯过程中的最小圆半径为10和与障碍物距离最大为10的约束条件进行补充，考虑到转弯过程中，机器人转弯发生的所有情况，我们分别对所发生的情况逐一进行研究，并加以证明，选择出最佳转弯情况并进而给出每种情况所对应的最短路径图。问题二中，我们利用对问题一中O-A的最短路径方案进行进一步的最短时间路径研究，初步判断导致从0-A最短路程路径与0-A最短时间路径不同的原因是：机器人转弯过程中发生的转弯半径、圆心位置的不同，而机器人转弯路径的不同间接导致到机器人走过的路径长度不同，以及转弯过程中的速度不同，这样就造成了最短时间路径选择与最短路程路径的不同的结果的产生。我们通过分析得出最短时间路径的最高点，即此路径相对于直线OA的最远距离应该尽可能小。为此我们得出一个结论，最短时间路径总得圆弧段必然与障碍物5的最高点相切，也就是说此圆弧所对应的圆心在障碍物5的对角线上。此时引入此圆弧所对应的半径r作为变量，通过一系列几何分析，最后得出了通过此路径的总时间T与半径r的关系式，并通过MATLAB进行仿真得出了O到A的最短时间路径图，并可知此通过此路径的时间为T(总)min=94.223秒，且路径总长度为L(总)=471.10。关键词：福德法、局部分析、最优路径、避障路径、拓扑研究2一、问题重述图1是一个800×800的平面场景图，在原点O(0,0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号障碍物名称左下顶点坐标其它特性描述1正方形(300,400)边长2002圆形圆心坐标(550,450)，半径703平行四边形(360,240)底边长140，左上顶点坐标(400,330)4三角形(280,100)上顶点坐标(345,210)，右下顶点坐标(410,100)5正方形(80,60)边长1506三角形(60,300)上顶点坐标(150,435)，右下顶点坐标(235,300)7长方形(0,470)长220，宽608平行四边形(150,600)底边长90，左上顶点坐标(180,680)9长方形(370,680)长60，宽12010正方形(540,600)边长13011正方形(640,520)边长8012长方形(500,140)长300，宽60在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆3弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为50v个单位/秒。机器人转弯时，最大转弯速度为21.0100e1)(vvv；其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)，具体计算：(1)机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。(2)机器人从O(0,0)出发，到达A的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。4二、问题分析问题一：问题一要求寻找出机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径，我们可以先不要考虑机器人转弯过程中的最小半径为10个单位、机器人行走时与障碍物的距离不得少于10个单位约束条件，对要进行求解的行走路径途径的始点与终点的障碍物进行局部优化，只对影响到机器人从始点到终点最优路径选择的障碍物进行考虑，在此基础山运用福德法分别求解出机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最优路径。在求出最优路径的基础上，我们分别对约束到机器人行走的两个因素：1、机器人转弯过程中的最小半径为10个单位；2、机器人行走时与障碍物的距离不得少于10个单位加以补充，再运用几何分析的方法对机器人在转弯节点所发生的情况分别研究，给出相关转弯情况的解决方案，最后我们就可以结合由福德法确定的最优路径以及转弯过程所发生的情况的解决方案，对问题提问到的：机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径，分别给出具体结果，进而问题一得到解决。问题二：我们利用对问题一中O-A的最短路径方案进行进一步的最短时间路径研究，初步判断导致从0-A最短路程路径与0-A最短时间路径不同的原因是：机器人转弯过程中发生的转弯半径、圆心位置的不同，而机器人转弯路径的不同间接导致到机器人走过的路径长度不同，以及转弯过程中的速度不同，这样就造成了最短时间路径选择与最短路程路径的不同的结果的产生。我们通过分析得出最短时间路径的最高点，即此路径相对于直线OA的最远距离应该尽可能小。为此我们得出一个结论，最短时间路径总得圆弧段必然与障碍物5的最高点相切，也就是说此圆弧所对应的圆心在障碍物5的对角线上。此时引入此圆弧所对应的半径r作为变量，来分析总时间T与半径r的关系。三、模型假设（1）假设机器人在行走过程中自能前进不能后退；（2）假设机器人行走的地面不出现凹凸现象，地面是平坦的；（3）机器人行走过程中始终与障碍物保持10个单位的安全距离；（4）机器人从直线前进进入到到转弯曲线进行时的状态瞬间完成；5四、符号说明L1：机器人从OA的路径；L2；机器人从OB的路径；L3：机器人从OC的路径；L4；机器人从OABC的路径；V1……Vn表示机器人前进拓扑图总的分叉节点；:为机器人转弯时对应的圆弧的半径；T(总)：为机器人从O到A之间的路径所花费的时间；五、模型建立、求解与数据分析一）、建模准备：1：在建模前，我们先看一个福德法在求解机器人寻找最短路径的实现的例子：例：首先对移动机器人及工作环境作以下假设：1)工作环境是在一个面积大小为64的正方形区域；2)移动机器人形状大小为1×1的正方形；3)障碍物形状不作限定，所占面积为1~n，n取值范围[1,64]；将移动机器人的工作环境以栅格地图的形式进行分块，每个栅格形状大小为1×1，并对每个栅格进行编号，从坐标原点开始，沿X轴编号，编号形式如图1所示，图1中蓝色部分为障碍物位置。图16假定移动机器人所在位置为点(xs,ys)，移动机器人的移动方向有8个，方向表示如图2所示，移动一个单元格后机器人的位置分别为(xs+1,ys+1)、(xs,ys+1)、(xs–1,ys+1)、(xs–1,ys)、(xs–1,ys–1)、(x,ys–1)、(xs+1,ys–1)、(xs+1,ys)，需要移动的距离分别是。1：Floyd算法是建立在已知节点的权值及方向的基础上的，因此移动机器人的最短路径规划从算法节点选择、节点的带权有向图入手进行研究。:2：节点的选择垂线法是指在指定连线上作垂线，通过垂线与障碍物边沿的交点，确定Floyd算法中的节点的方法，通过垂线法能有效的将环境中最短路径上节点选择出来，垂线法选择节点的流程为：1）连接始点v0、终点vt，找出连线上所经过的障碍物Oi，图中障碍物为O1；2）在障碍物O1、O2上，以v0vt的连线（简称为t）作垂线m，垂线m与t的交点为Qi，垂线m与障碍物边沿的交点为Ui；3）分别选择t两边UiQi距离最大的点vi，纳入节点集合S中，图1中障碍物O1选择的节点为v1、v2；因此，根据垂线法得到集合S中的节点为：S={V0、V1、V2、Vt}所在位置计算出节点间的权值大小。w01指节点v0、v1间的权值，权值大小由两节点间的移动距离得到，为方便观察，将vt用v3代表。如果两点连线间有障碍物，7这两点间的权值为∞，路径的走向是沿着连线t的方向，也就是连线t同一边节点间的方向，与确定它的Qi点间的方向是相同的，在t不同边的点直接不限制相互间的方向。所以只存在有v0到v1、v0到v2的方向，而没有v1到v0、v2到v0的指向。如果两点连线间有障碍，权值仍为∞。因此，根据节点位置、障碍物位置和连线的t方向，得到环境路径的有向带权图，如图所示：以及有向图的邻接矩阵，如图所示：移动机器人寻找最短路径的实现步骤如下：1）写出vi到vj初始无中间节点权值矩阵A0，如式(1)所示，从权值矩阵看出，v0、v1、v2、v3相互间的权值关系和方向关系。2）计算vi到vj间有1个中间节点情况下的最短权值矩阵。设vj经过一个中间点vr到达vj，则vi到vj的最短距离为：，最短权值矩为：。即移动机器人中间经过1个节点到达终点的权值矩阵为：8注：当机器人经过的障碍物大于一时，我们可以计算vi到vj间有k个中间节点情况下的最短权值矩阵。设vj经过中间点vr到达vj，vi经过r个中间节点到达点vr的最短距离为，vr经过k–r个中间节点达到点vj的最短距离为，则vi经过k个中间点到达vj的最短距离为，最短权值矩阵为：。2：在对实际问题中给出的路径进行求解时，我们可能会面临不可以运用福德法求解的情况，这时我们为了能够顺利运用到福德法进行对路径的求解可以对要求解的路径进行分析，找出导致这种现象产生的原因，从而找出机器人从起点到终点时必将通过的节点，然后我们以节点为分界点，对整个路径进行局部分解，例如题目给出的从原点O-B时，我们为了能够顺利运用福德法求解从O到达B点的最优路径，我们可以对O-B，进行分段处理，选择机器人从O到B过程中必定通过的节点进行分解求解，例如机器人从0—B中必将通过节点T，此时我们就可以将机器人从O-B的整个过程分解为O-T和T-B，然后我们分别运用福德法对O-T和T-B的最优路径进行分别求解，确定OT，TB的最优路径，进而得出O-B的路径。3、为了能够快速利用福德法求出机器人行走的最优路径，我们对于机器人从始点开始到终点的过程中，只把影响到机器人从始点到终点过程中经过可能成为最优路径（其中最优路径必然包含在这些可能的路径中）的只要障碍加以研究，对于机器人行走过程中没有涉及到到障碍物忽略不计。二）建模过程：分析一：91)、由于在求解机器人行走的最短路径时，机器人受到的两个约束因素：1、机器人转弯过程中的最小半径为10个单位；2、机器人行走时与障碍物的距离不得少于10个单位，不影响其最优路径的总体确定，而只对具体路径确定之后的细节部分影响，所以我们先不考虑这两个约束条件，对路径进行逐步求解：在机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径的求解的过程中，我们利用上面所述思想分别对题目所要求求解的路径进行逐一求解：（1）机器人从原点O开始到达终点的A的情况：根据1）所述，机器人从始点OA到终点A的优化结果如图2所示：图2根据上述方法我们可以很容易的得到机器人从O-A的有向带权图，如下：以及有向带圈矩阵如下：10机器人中间经过1个节点到达终点的权值矩阵如下：经过分析机器人从O点出发到达终点B，途径节点V2的路程最短，即O-A的最短路径为O-V2-A；（2）机器人从原点O开始到达终点的