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

1、机器人避障问题摘要本文主要运用直线逼近法等规律来解决机器人避障问题.对于问题一：要求最短路径运用直线逼近法证得圆弧角三角形定理，得出结论：若一大圆弧角三角形完全包括另一小圆弧角三角形，则该三角形曲线周长必大于小的三角形周长.那么可知机器人在曲线过弯时，选择最小半径可满足路径最短，即为10个单位半径，通过观察可得可能的所有曲线，通过仅考虑直线段的大致筛选选出总长较小、长度相近（之差小于100）的曲线，然后利用平面几何知识对相关切点，进而求出各直线、曲线的长度，求和可得最段路线.对于问题二：通过对机器人过弯规律的分析可知，当过弯半径时，机器人速度达最大速度为个单位/秒，再大就无变化了，那么可分两种

2、情况考虑：1）当时，过弯速度无变化，但由圆弧角三角形定理可知，此时随着的不断变大，其路线总长不断变大，这时越小所用时间最短；2）当时，统计计算分别为10、11、12、13时，过弯速度也不断变化，计算所用时间发现随不断变大，所用时间越短，此时当时，时间最短.综合上述可知：当时，时间最短.关键词：质点机器人 安全范围 直线逼近法 圆弧角三角形定理 单位半径1 问题重述在一个800800的平面场景中，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动，其中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号障碍物名称左下顶点坐标其它特性描述1正方形(3

3、00, 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)边长8

4、012长方形(500, 140)长300，宽60在该平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）.规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径.机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位.为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位.机器人直线行走的最大速度为个单位/秒.机器人转弯时，最大转弯速度为，其中是转弯半径.如果超过该速度，机器人将发生侧翻，无法完成行走.下面建立机器人从区域中一点到达另一点的避

5、障最短路径和最短时间路径的数学模型.对场景图中4个点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具体计算：(1) 机器人从O(0, 0)出发，OA、OB、OC和OABCO的最短路径.(2) 机器人从O (0, 0)出发，到达A的最短时间路径.2 问题分析2.1问题一：该问题要求路径最短，即不要求速度与时间，则可认为以最小半径的圆过弯.如图2.1所示：由圆弧角三角形定理（简单证明见模型准备5.3）可知过弯时，只有采用单位半径过弯时，才会使得过弯路径最短，因此解决问题一的过弯拐角问题均采用单位半径过弯路径.2.2问题二：由于OA过程中，机器人至少要经过一

6、次转弯；因为转弯时的速度一般小于直线行走的最大速度，又由分析指出转弯次数越多，转弯路径越远，转弯所花费的时间也越长.所以可以确定有且只有一次转弯时才存在最短时间路径.就仅考虑只经过一次转弯的情形.3 模型假设1）假设机器人可准确执行运动轨道，无任何偏差；2）假设机器人为一可运动的质点，即质点机器人不考虑其外形尺寸；3）假设机器人的行进速度可瞬时加减变化，不受条件限制；4）假设机器人可到达边界线而不会发生碰撞，即对边界线不再加10个单位.4 符号说明：机器人的行走路径上各切点，表示路径目的地（A、B、C），表示到达机器人行走路线的第种方案，表示机器人在该路线上所经过的第个点；: 机器人的行走路径

7、上的线段长或弧长，、同上定义；：机器人的行走路径上的障碍物的顶点，、同上定义； ：机器人在环道中的各线切点、同上定义5 模型准备5.1建立机器人运动坐标系：以为原点，两对应坐标轴，水平方向为轴，垂直方向为轴5.2建立机器人可安全运动到达的区域图：由于保持安全距离个单位，则机器人的实际可到达到区域应由各障碍物的外延10个单位的区域组成如图所示图5.2.1实线外的空白部分.5.3圆弧角三角形定理： 定义1：平面内若两不平行直线所夹的角被一同时与这两条直线相切的圆弧段取代而形成的角，叫做圆弧角.如图5.3.2，称为凸圆弧角（本文主要讨论）；如图5.3.3，称为凹圆弧角.定义2：由有一内角为凸圆弧角的

8、三角形为圆弧角三角形.圆弧角三角形定理：圆弧角在直线及上方范围完全包含圆弧角（即圆弧角DGD各边均在圆弧角的边与线段DD所构成的封闭区间内，如图5.3.1所示）时，则有曲线段的长度恒小于曲线段成立.证明：如图5.3.1，过圆弧的一个端点作该圆弧在该点的切线的垂线交曲线于点，同样过圆弧的另一个端点也作相应的垂线交曲线于点，两条直线的交点显然为圆弧所在圆的圆心.（1）； 曲线段， 曲线段.（2） ； 曲线段；曲线段.（3）将分成等份（如图5.3.5），每部分（见图5.3.4）中，是与边界的交点.令为，两点间直线长度，为,两点间直线长度，则圆弧长度=，曲线长度=又容易证明，故有 .因此，圆弧长度曲线

9、长度.综合（1）（2）（3）的证明，得曲线段+曲线段+曲线长度 +圆弧长度.结论得证.6 模型建立与求解该问题要求路径最短，即不要求速度与时间，则可认为过弯半径允许以最小半径，如图6.1所示.由圆弧角三角形定理可得：本论文问题一求路径最短可采用10单位过弯半径，即以半径为10个单位的圆弧过弯可满足两点避障过弯最短问题.6.1问题一的模型建立与求解：6.1.1：机器人从O(0, 0)出发，的最短路径.由圆弧角三角形定理可得：采用单位半径过弯路径最短，解决过弯避障拐角问题采用单位半径过弯路径.已知机器人所走路线为直线或圆弧，那么通过实际规划可得如下四种避障行进方案：如图6.1.1首先对上述四条路线

10、进行筛选：1） 当机器人以一个连续圆弧过弯，即选择路线二或路线四时,其中路线二：分别过点和障碍物5的切点（72.74，216.88），则可得过该三点的圆的方程：显然当时，有不等的两个根，则该路线超出规定场地.同理路线四的圆方程： (Matlab求解程序见程序01)当时，有不等的两个根，则该路线也超出规定场地.2）当机器人以直线圆弧直线的方式过弯，即有以单位半径过弯模式的线路一和三：比较线路一与线路三：显然路线一的总长，线路三的总长.解得则可知OA的最短路径为路线一总长为，下表5.1.1为线路一的各点的详细参数，表6.1.2为各线的参数.表6.1.1 点号坐标50.1451.68301.6430

11、5.55 线号长度224.509.05237.49表6.1.2：6.1.2机器人从O(0, 0)出发，的最短路径由圆弧角三角形定理可得：采用单位半径过弯路径最短：通过观察可得如下四种较短的避障行进方案，如图6.1.2：由于方案较多，可预先进行粗略筛选：如图所示：大致统计长度仅包括直线段长度如下表6.1.2表6.1.2线段编 号路线号123456总长路线一305.78162.2573.656096.95111.36810路线二224.50175.70230.5096.95111.36839路线三235.37240.05230.5096.95111.36914.22路线四235.37620.851

12、70.301026.52则由上表可知：路线一和路线二相差不大，且路线较短，则可进一步仅考虑该两路线的精确长度：设：、 分别表示点到点，点到点之间的向量；为、两点之间的向量的模；表示切点坐标；记为障碍物顶点的坐标； 联立方程解得(50.14,30.64)由于点，分别是以点，为圆心为半径圆的外公切线切点，所以由点到直线的距离公式得 并且线段 由于直线由斜率相等得 联立方程解得点的坐标(51.6795,305.547)的坐标(141.68,440.55)线路一和线路二的各段路线及总长分别如下表6.1.2,6.1.3表6.1.2总长长度305.784.24162.257.7573.6515.71609

13、.8996.956.15111.36853.73表6.1.3总长长度224.58.37178.1212.22230.499.8996.956.15111.36878.05由上两表可知：线路一总长最短.同理可解得各点坐标如下表6.2.4表6.1.450.1451.68141.68147.94220230230225.5144.5140.69301.64305.55440.55444.78460470530538.35591.65596.35的最短路径为：6.1.3机器人从O(0, 0)出发，的最短路径由圆弧角三角形定理可得：采用单位半径过弯路径最短：通过观察可得如下避障行进方案，如图6.1.3由

14、于该线路同样较复杂，可通过大致筛选，仅考虑其中的直线段长度.将通过障碍物1上边沿的线路称为上线路，通过下边沿的线路称为下线路1） 考虑上线路中最短路径：上线路中如图6.1.3.1分两大段，上半段：线路A、B、C，下半段：线路D、E对上半段的线路进行只计算线段的粗筛选：计算统计可得三线路的粗选长度：如表6.1.5线段号路线号1234线段A(695.94)306.6957162.249875.6637151.3275线段B(728.32)225.4398178.1151306.3087线段C(780.77)237.54543.23如表统计可知，线段A距离最短.对下半段的线路进行只计算线段的粗筛选：

15、计算统计可得三线路的粗选长度：如表6.1.6表6.1.6线段号路线号12345总长线段D151.33119.16413094.34494.834线段E200160808043.59563.59如表统计可知，线段D距离最短2） 考虑下线路中最短路径：如图图6.1.3.2对下线路的线路进行只计算线段的筛选：计算统计可得线路的长度： 下表6.1.7为路线一的各段线路总长对于同一条路径上的两个相邻点、来说，如果这两点之间的路径为直线段时，用通式计算；如果这两点之间的路径为弧线段时，可用通式计算：表6.1.7总长长度237.540184.47.31330.73387.86.5806.943.6950.8

16、4下表6.2.8为路线二的各段线路总长表6.1.8长度237.548.5293318.43378.8448169.705647.5281707.8958806.891743.589237.548.5293总长960.5814下线路的两段线路对比得：线路一最短为：950.84综合上线段、下线段可得：线路一最短.各切点坐标如下表6.1.9表6.1.9切点号232.9412.6418.7492492.4728.3730.4730.4728.151.291.195.3206206.9514.8520.9600.9607.2的最短路径为：6.1.4机器人从O(0, 0)出发，的最短路径由圆弧角三角形定理

17、可得：采用单位半径过弯路径最短：6.1.4.1的最短路径求解：通过实际规划可得如下的避障行进最短方案：如图6.1.4.16.1.4.2的最短路径求解：通过实际规划可得如下的避障行进最短方案：如图6.1.4.1对线路一、二进行大致选可得下表线段编号路线号12345总长路线一97.9860119.1613094.34501.48路线二243.52160808043.59607.11表6.1.10则可知路线一距离最近对于同一条路径上的两个相邻点、来说，如果这两点之间的路径为直线段时，用通式计算；如果这两点之间的路径为弧线段时，可用通式计算：6.1.4.3线路经过、的圆弧处理问题为使经过、的圆弧路线最

18、短，在A与相邻切点的连线形成的夹角的平分线，以该角的平分线为基础，在该线上做与点A相切的半径为10个单位的圆，则此时通过该构造圆与相邻圆弧的切线连接就产生了，进而保证了机器人的圆弧过弯和线路最短.点A的圆弧处理结果如图6.1.4.3则综上所述：求得各线短的最短路径，则可计算并统计出线段总长及各切点坐标如下表表6.1.11切点号12345678910111270.50677.797294.34300.597229.54144.5140.8698.96108.96270.87368.01435.59213.14219.7295.03307.485533.01591.65595.93690.0670

19、4.09689.96670.2671.71切点号1314151617181920212223534.41679.77699.21701.31727.67730.3851727.94492.06418.35412.17232.17738.29732.11642.27637.97606.41520513.92206.0894.4990.2450.24表6.1.12线序号123456789101112长度224.5230.3815.417236.459.8896.955.7103.0320.767162.5297.9860线序号131415161718192021222324长度5.92119.16

20、5.9213013.5891.924.8341.137.85806.54387.81线序号252627长度7.685184.4237.49的最短路径为6.2问题二的模型建立与求解：由于OA过程中，机器人至少要经过一次转弯；因为转弯时的速度一般小于直线行走的最大速度，又由分析指出转弯次数越多，转弯路径越远，转弯所花费的时间也越长.所以可以确定有且只有一次转弯时才存在最短时间路径.故以下就仅考虑只经过一次转弯的情形.机器人由起点到终点所用时间，对于每种固定的转弯半径来说，转弯路径所在的圆的圆心与点连线垂直平分该转弯路径所在的圆弧时，所得的总路径长度最短.如图6.2.1所示.对于已知条件中的最大转弯

21、速度为 ，其中是转弯半径通过matlab画出其图像，见程序02 如图6.2.2根据图6.1中所示，当时，随增加而增加；当时，已非常趋近于5单位/秒，此时可以看做不随增加而变化了.于是可以分两种情况解决本问题：1)当时，由于OA整个过程的平均速度可以达到最大单位/秒，以这样的速度沿最小的路径就可以使到达A的时间最短.通过问题一中对机器人OA最短路径的分析，可知其最小时间路径应在连线左上方区域；同时根据所建立并证明的圆弧角三角形定理可以知道，所得路径的转弯半径应为13个单位（如图6.2.3）,总长度：总时间：（秒）2)当时，图6.2取自原题目图中的一部分，其中，点的坐标均已给出.、分别为OQ1和O

22、Q2与的切点，其中又与相切于点.假设半径已知，、的坐标分别为、，则可列出如下方程组：分别取=10，11，12，13并解方程组可以得到总时间随转弯半径变化的数据，根据弧长公式得,最终计算数据如下表：6.2.1表6.2.1项目转弯速度（单位/秒）总时间（秒）10224.49958.8405237.69732.595.975511224.20319.966236.89134.45594.455912223.773310.8816236.43654.93994.245213236.139211.8001223.1903594.2259通过比较总时间的变化趋势可以知道，当时，总时间随增加而增加，最终会趋于94.22秒.因此，可以确定出最短时间路径.经过以上两种情况的讨论，可得最短时间路径， 具体坐标信息见表6.2.2表6.2.2坐标起点切点切点终点圆弧圆心0130.5224138.4764300142.86850226.6562234.8207300222.58517 模型的评价与推广7.1优点：