机器人避障的最优路径探索论文.doc

机器人避障的最优路径探索摘要本文研究了机器人避障最短路径的问题基于定积分理论，我们提出并建 立了一种选择最短路径的模型，即用起始点与FI标点的连线将障碍物分割，并通 过连接顶点的方式创建儿何图形并比较分割线两边的包含障碍物在内的新创建 的儿何图形的面积通过比较创建的儿何图形面积来选择最短路径的方向即从 面积较小的新创建的儿何图形一侧绕过障碍物抵达冃标点所走的路径最短同时我们研究了在一个区域中存在多个障碍物，由岀发点经过障碍物到达冃 标点所需最短路径的问题我们通过证明具有闘形限定区域的最短路径是由两部 分组成的：一部分是平面上的自然最短路径（即頁线段），另一部分是限定区域 的部分边界，这两部分是相切的，互相连接的依据•这个结果，我们可以认为最 短路径一定是由线和圆弧做组成，因此我们建立了线圆结构，这样无论路径多么 复杂，我们都可以将路径划分为若干个这种线圆结构来求解对于途中经过节点 再到达冃标点的状况，我们采用了两种方案，一种是在拐点和节点都采用最小转 弯半径的形式，另一种是适当扩大拐点处的转弯半径，使得机器人能够沿平滑曲 线通过途中的冃标点然后建立了模型对两种方案分别进行求解问题重述1、 基本内容：题冃给定一个800X800的封闭平面环境中点0(0,0)存在一机器人。

平而中有12个不同形状的图形为机器人不能与之碰撞的障 碍物并且在障碍物外有指定三点，耍求机器人以最短路径到达 指定点2、 约朿条件：(1)图中指定三点 A (300, 300) , B (100,700) , C (700,640)并给出平面中图形顶点坐标若干；(2) 机器人运动轨迹必须以直线段和圆弧组成，圆弧最小半径 为10个单位机器人不得走折线且必须与障碍物保持10个单 位以上的距离；(3) 机器人运动时，直线行走最大距离为Vo =5个单位/秒jfu在转弯时的速度为v = v(/7)=―加〒，其中P是转弯半径, |+el0-0.1p-且不得超速3、 问题冃标：(1)找出并计算O到各指定点以及OO的最短路径距离;(2)机器人从O (0, 0)出发，到达A的最短时间路径二、问题分析问题一：1、 问题一中耍求从定点0 (0, 0)按照一定的行走规则绕过障碍物到达冃标的最短路径2、 因为障碍物的关系，机器人运动的路径不可能是直线，而且耍求机器人要 是终与障碍物保持10单位以上的距离3、 因此，我们先可以用包络线画岀机器人行走的危险区域，这样的话，拐角 处就是一个半径为10的四分Z —圆弧，然后采用拉绳子的方法寻找可能的 最短路径。

问题二：1、 问题二中耍求定点0 (0, 0)经过中间的5号障碍物到达冃标点A所需的最短时间路径2、 这时我们考虑的就不仅仅是经过障碍物拐点的问题，也应该考虑机器人沿 路径运动速度的问题3、 我们在拐点及途中冃标点处都采用最小转弯半径的形式，也可以适当的改 变拐点处的拐弯半径，使机器人能够以更接近直线运动速度的轨迹通过途 中的障碍物而到达冃标点三、模型假设1、 假设机器人始终以最大速度运动2、 假设机器人变速可在瞬间完成，这样我们不必考虑机器人加速度的问题3、 假设机器人能够抽象成点来处理U!符号符号说明L a - r路径的总长度 第i段切线的长度 第丿•段圆弧的长度 转弯半径k障碍物上的任意点与行走路径之间的最短距离V机器人运动时的速度五、模型的建立1、 路径的选择模型1）模型一：将起始点与目标点用一条直线连接起来，则两点间的障碍物被直线分割成两部分由起始点和目标点分别连接被分割图形顶点，所 构成图形面积越大，则绕过该部分所需运动路径距离越大当被分割图形 有两个或两个以上顶点时，若顶点在三角形内则连接同一顶点距离最短；若 顶点在三角形外则分别连接最近顶点距离最短）Or L (AOa)当 SzXAOaVS/XAObMIN (L) = JL (AOb)当 SAAOa>SAAob图5・1边长血积比较示意图证明：将a与b分别与0, A相连，得到AOdA与AObA。

由于两点Z间直线最短，所以如果耍从0经过矩形障碍物至A ,则最短路径为0-a-A或0-b-A解：0a2 +aA2 =Ae2 +0e2 +2ae2Ob2 +Ab2 =0d2 +Ad2 +2bd2设Oe为X则Ae为OA-X则有 Oe2 +Ae2=2X2 +0A2 -20AX可知当Oe二Ae时C^+Ae?取得最大值同理Od二Ad时取得最大值当 0e=Ae=0d=Ad 时Oa2 +Aa2 - (Ob2+Ab2) =2ae2-2bd2I丸为ae

然后相邻矩形间的高度差与矩形的宽可以与连线构成一个小型三角形 △aba因为图形的而积越大，则矩形间的高度差吐b越大，且因为矩形的宽 是固定的，所以被矩形顶点截出的连接线段ab会随着高度差的增加而增加从 而证明连接线会随着面积的增大而增大如图5-2所示：图5-2多顶点图形证明示意图2•根据模型一的分析我们可以把全部有顶点的直边图形连接成三角形或多边 形接下来我们分析当被分割图形不存在顶点且边不为直线时的情况我们过起 始点与戸标点做关于被分割曲线图形的切线，于是我们创建的新图形是一个由直 线段与曲线组合成的图形我们可以将具分解为两个部分，即由直线段包含的部 分以及由曲线包含的部分关于直线段的部分我们可以参照Z前的方式证明，在 此我们着重探讨曲线部分的而积与边长的关系我们如果将图放大，如果填充的矩形足够细密的话，则相邻矩形顶点所截曲 线段802可近似的看做直线段，于是我们可以将曲线图形转化为直边的多边形来 对待因此，对于没有顶点的曲线图形也适用与模型一的证明范围a a320图5-3 曲边图形证明示意图除此Z外，我们还注意到WI形图的存在因为我们是将被分割图形的顶点与 起始点和冃标点相连，因此创建的新的图形总不会是凹形图。

因而无论凹形图还 是凸形图都适用于此方法2、路径的计算模型1) 模型二：具有圆形限定区域的最短路径是由两部分组成的：一部分是平 面上的自然最短路径(即直线段)，另一部分是限定区域的部分边界，这两部分 是相切的，互相连接的即问题分析中的拉绳子拉到最紧时的状况)证明：如图5-4所示，假设在平面中有A (a, 0)和B (-a, 0)两点，中间有一个半圆形的障碍物，证明从A到B的最路径为AEFBoC(0, y)A fO) g(a, 0)图5-4 最短路径计算示意图平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于 障碍物相交，所以设法尝试折线路径在y轴上取一点C (0, y),若y适当大, 则折线ACB与障碍物不相交，折线ACB的长度为：\ACB 1= 2ja?+y2显然IACBI随着y的减小而减小，减小y得y T比，即C — G，使得AC；与C/与障碍物相切，切点分别为E和F,显然AC}B是这种折线路径中最短的由于满足 0<^<|的角满足a

下而在考察一条不穿过障碍物的任何一条路径，设其分别于0E和OF的延长 线交与P、Q两点，记A和PZ间的路径长度为瓦P,显然AP>|AP|, 乂由AE丄E0,所以| AP| >AE,从而AP>AE,同理可得BQ>BFo再来比较PQ Z间路径长度蓟和圆弧EF的长度的大小若PQ Z间的路径可有极坐标方程P = P（0）,则有P > 1,可得：PQ=J Jp2 + p： d9>fd0_ -EF3亦即路径APQB的长度超过路径AEFB的长度以上证明足以说明了 AEFB 是满足条件A到B的最短路径2）模型二的推广根据模型二中的定理，我们就可以这样认为，起点到冃标点无论中间障碍物 有多少，最短路径都应该是若干个线圆结构所组成在木题中存在障碍物的状况, 且障碍物在拐点处的危险区域是一个半径为io的圆弧，，我们易知，求两点Z间 的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优图5-5线圆结构图3、路径模型根据模型二的分析，在有若干个障碍物的区域中，我们把按照线圆结构画出 从出发点到冃标点的路径图依抑模型二中的想法转换成以下图示（仅以示意）， 图中的0和A点就是添加的源点和终点，其它节点均是岀发点和冃标点到圆弧的 切线和圆弧与圆弧Z间的切线转化而成。

CDEF6Ab2c3D3图5-6对于最短路径的求解，有以下步骤：1）我们画出出发点和H标点和各个圆弧的切线，以及圆弧与圆弧Z间的切线, 但是切线有可能经过障碍物的内部或危险区域，也可能出现切线重复的状况，既 有很多不合法的切线于是我们对模型做了以下修正：1. 检验切线两个端点是否在障碍物内部2. 检验切线是否障碍物的对角线相交3. 检验圆弧所对应的圆心，即障碍物的顶点到切线的距离是否小于10如果以上三种情况满足其一，我们规定对应这段切线的顶点为M （M为无 穷大）另外还有如下图所示的一种特殊情况：两个大小相同在同一水平或者竖直位置上，不考虑切线满足1、2、3的 状况它们由2条内公切线，8条外公切线，但是有6条外公切线是重复的因 此我们作如下规定：如果某条切线与某段圆弧相切，且切点不在切线的端点上,则该切线为不合法权值矩阵中表示它的顶点也为MoB C D2） 然后把合。