2012年数学建模机器人避障问题

1机器人避障问题摘要本文主要运用直线逼近法等规律来解决机器人避障问题.对于问题一：要求最短路径运用直线逼近法证得圆弧角三角形定理，得出结论：若一大圆弧角三角形完全包括另一小圆弧角三角形，则该三角形曲线周长必大于小的三角形周长.那么可知机器人在曲线过弯时，选择最小半径可满足路径最短，即为10个单位半径，通过观察可得可能的所有曲线，通过仅考虑直线段的大致筛选选出总长较小、长度相近（之差小于100）的曲线，然后利用平面几何知识对相关切点，进而求出各直线、曲线的长度，求和可得最段路线.对于问题二：通过对机器人过弯规律21.0100e1)(vvv的分析可知，当过弯半径13时，机器人速度达最大速度为50v个单位/秒，再大就无变化了，那么可分两种情况考虑：1）当13时，过弯速度无变化，但由圆弧角三角形定理可知，此时随着的不断变大，其路线总长不断变大，这时越小OA所用时间最短；2）当13时，统计计算分别为10、11、12、13时，过弯速度v也不断变化，计算所用时间发现随不断变大，OA所用时间越短，此时当13时，时间最短.综合上述可知：当13时，时间最短.关键词：质点机器人安全范围直线逼近法圆弧角三角形定理10单位半径21问题重述在一个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在该平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）.规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径.机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位.为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位.机器人直线行走的最大速度为50v个单位/秒.机器人转弯时，最大转弯速度为2100.110()(1e)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的最短时间路径.2问题分析2.1问题一：该问题要求路径最短，即不要求速度与时间，则可认为以最小半径10的圆过弯.如图2.1所示：由圆弧角三角形定理（简单证明见模型准备5.3）可知过弯时，只有采用10单位半径过弯时，才会使得过弯路径最短，因此解决问题一的过弯拐角问题均采用10单位半径过弯路径.2.2问题二：由于O→A过程中，机器人至少要经过一3次转弯；因为转弯时的速度一般小于直线行走的最大速度，又由分析指出转弯次数越多，转弯路径越远，转弯所花费的时间也越长.所以可以确定有且只有一次转弯时才存在最短时间路径.就仅考虑只经过一次转弯的情形.3模型假设1）假设机器人可准确执行运动轨道，无任何偏差；2）假设机器人为一可运动的质点，即质点机器人不考虑其外形尺寸；3）假设机器人的行进速度可瞬时加减变化，不受条件限制；4）假设机器人可到达边界线而不会发生碰撞，即对边界线不再加10个单位.4符号说明hijD：机器人的行走路径上各切点，h表示路径目的地（A、B、C），i表示到达h机器人行走路线的第(1,2,3,)ii种方案，j表示机器人在该路线上所经过的第(1,2,3,)ii个点；hijL:机器人的行走路径上的线段长或弧长，h、i、j同上定义；ijD：机器人的行走路径上的障碍物的顶点，i、j同上定义；`hjD：机器人在OABCO环道中的各线切点h、j同上定义5模型准备5.1建立机器人运动坐标系：以O为原点，两对应坐标轴，水平方向为X轴，垂直方向为Y轴5.2建立机器人可安全运动到达的区域图：由于保持安全距离10个单位，则机器人的实际可到达到区域应由各障碍物的外延10个单位的区域组成如图所示图5.2.1实线外的空白部分.5.3圆弧角三角形定理：4定义1：平面内若两不平行直线所夹的角被一同时与这两条直线相切的圆弧段取代而形成的角，叫做圆弧角.如图5.3.2，称为凸圆弧角（本文主要讨论）；如图5.3.3，称为凹圆弧角.定义2：由有一内角为凸圆弧角的三角形为圆弧角三角形.圆弧角三角形定理：圆弧角`DHD在直线`DD及上方范围完全包含圆弧角`DGD（即圆弧角DGD’各边均在圆弧角`DHD的边与线段DD’所构成的封闭区间内，如图5.3.1所示）时，则有曲线段`DGD的长度恒小于曲线段`DHD成立.证明：如图5.3.1，过圆弧'EGE的一个端点E作该圆弧在该点的切线的垂线交曲线DH于点F，同样过圆弧'EGE的另一个端点'E也作相应的垂线交曲线'DH于点'F，两条直线的交点O显然为圆弧'EGE所在圆的圆心.（1）,EFDE90DEF；,DFDE曲线段DFDF，曲线段DFDE.（2）'''',EFDE'''90DEF；'''',DFDE曲线段''''DFDF；曲线段''''DFDE.（3）将''EFFE分成n等份（如图5.3.5），每部分（见图5.3.4）中，,(1,,)iiMNin是MN与边界的交点.令iiMN为iM，iN两点间直线长度，''iiMN为`iA,`iE两点间直线长度，则圆弧MN长度=1limniiniMN，曲线`AE长度=''1limniiniMN5又容易证明，''(1,,)iiiiMNMNin，故有''11limlimnniiiinniiMNMN.因此，圆弧MN长度曲线''MN长度.综合（1）（2）（3）的证明，得曲线段DF+曲线段''DF+曲线''MN长度DE+''DE+圆弧MN长度.结论得证.6模型建立与求解该问题要求路径最短，即不要求速度与时间，则可认为过弯半径允许以最小半径10，如图6.1所示.由圆弧角三角形定理可得：本论文问题一求路径最短可采用10单位过弯半径，即以半径为10个单位的圆弧过弯可满足两点避障过弯最短问题.6.1问题一的模型建立与求解：6.1.1：机器人从O(0,0)出发，OA的最短路径.由圆弧角三角形定理可得：采用10单位半径过弯路径最短，解决过弯避障拐角问题采用10单位半径过弯路径.已知机器人所走路线为直线或圆弧，那么通过实际规划可得如下四种避障行进方案：如图6.1.1首先对上述四条路线进行筛选：1）当机器人以一个连续圆弧过弯，即选择路线二或路线四时,其中路线二：分别过点OA，和障碍物5的切点23aD（72.74，216.88），则可得过该三点的圆的方程：225406140xyxy显然当0x时，y有不等的两个根，则该路线超出规定场地.同理路线四的圆方程：22(73.98)(226.02)56558.350xy(Matlab求解程序见程序01)当0y时，x有不等的两个根，则该路线也超出规定场地.2）当机器人以直线—圆弧—直线的方式过弯，即有以10单位半径过弯模式的线路一和三：比较线路一与线路三：显然路线一的总长1111213aaaaLLLL，线路三的总长3313233aaaaLLLL.解得13471.04498.44aaLL6则可知O→A的最短路径为路线一总长为1471.04aL，下表5.1.1为线路一的各点的详细参数，表6.1.2为各线的参数.表6.1.1表6.1.2：6.1.2机器人从O(0,0)出发，OB的最短路径由圆弧角三角形定理可得：采用10单位半径过弯路径最短：通过观察可得如下四种较短的避障行进方案，如图6.1.2：由于方案较多，可预先进行粗略筛选：如图所示：大致统计长度仅包括直线段长度如下表6.1.2表6.1.2线段编号路线号123456总长l路线一305.78162.2573.656096.95111.36810路线二224.50175.70230.5096.95111.36839路线三235.37240.05230.5096.95111.36914.22路线四235.37620.85170.301026.52则由上表可知：路线一和路线二相差不大，且路线较短，则可进一步仅考虑该两路线的精确长度：设：11bOD、1111bDD分别表示O点到点11bD，点11bD到点11D之间的向量；1111bDD为11bD、11D两点之间的向量的模；()(),hijhijxy表示切点hijD坐标；()(),ijijxy记为障碍物顶点ijD的坐标；222b11(61)(00)=()Lyyr(61)(00)（x-x）点号坐标11aD12aDx50.1451.68y301.64305.55线号长度11aL12aL13aLl224.509.05237.4972220(b12)(b11)(b12)(b11)00b12-((x-x)+(y-y))22=arccos()L22b13(61)(63)=()Lyy(61)(63)（x-x）11(11)(00)(11)(00)(,)bbbODxxyy161(61)(00)(61)(00)(,)ODxxyy1111(11)(11)(11)(11)(,)bbbDDxxyy21111110bbDDOD31111bDDr4联立方程1234解得11bD(50.14,30.64)由于点12bD，13bD分别是以点61D，61D为圆心r为半径圆的外公切线切点，所以由点到直线的距离公式得220(12)(61)(12)(61)()()bbxxyy5220(13)(63)(13)(63)()()bbxxyy6并且线段13126163bbDDDD7由于直线13126163bbDDDD平行直线由斜率相等得(13)(13)(61)(63)(13)(13)(61)(63)bbbbxxxxyyyy8联立方程5678解得点12bD的坐标(51.6795,305.547)13bD的坐标(141.68,440.55)线路一和线路二的各段路线及总长分别如下表6.1.2,6.1.3表6.1.211bL12bL13bL14bL15bL16bL17bL18bL19bL110bL111bL总长长度305.784.24162.257.7573.6515.71609.8996.956.15111.36853.73表6.1.321bL22bL3bL24bL25bL26bL27bL28bL29bL总长长224.58.37178.1212.22230.499.8996.956.15111.36878.058度由上两表可知：线路一总长最短.同理可解得各点坐标如下表6.2.4表6.1.411bD12bD13bD14bD15bD16bD17bD18bD19bD110bDx50.1451.68141.6814