2012年数学建模D题
- 格式：doc
- 大小：719.00 KB
- 文档页数：27
2012高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等)与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等).
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D
我们的参赛报名号为（如果赛区设置报名号的话)：
所属学校（请填写完整的全名）：**＊＊**＊＊****＊＊＊***
参赛队员(打印并签名） ：1。
2．
3．
指导教师或指导教师组负责人 (打印并签名)：
日期：2012年9月9日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2012高教社杯全国大学生数学建模竞赛题目
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号)：
赛区评阅记录：
评
卷
人
评分
备注
全国统一编号（由赛区组委会送交全国前编号）:
机器人避障问题
摘要
二十一世纪科技发展迅速,机器人作业逐渐兴盛.本文研究了机器人避障最短路径和最短时间的问题。主要研究了在一个区域中存在12个障碍物，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的两种情形.我们通过证明具有圆形限定区域的最短路径是由两部分组成的:一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。依据这个结果，我们可以认为最短路径一定是由线和圆弧做组成，因此我们建立了线圆结构，这样无论路径多么复杂，我们都可以将路径划分为若干个这种线圆结构来求解。
一、问题重述
图1是一个800×800的平面场景图，在原点O(0， 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：
编号 障碍物名称 左下顶点坐标 其它特性描述
1 正方形 （300， 400） 边长200
2 圆形 圆心坐标（550， 450），半径70
3 平行四边形 （360， 240) 底边长140，左上顶点坐标（400, 330)
4 三角形 （280, 100） 上顶点坐标（345, 210）,右下顶点坐标(410,
100)
5 正方形 (80, 60) 边长150
6 三角形 (60, 300) 上顶点坐标（150, 435)，右下顶点坐标(235,
300)
7 长方形 （0, 470） 长220,宽60
8 平行四边形 （150, 600） 底边长90，左上顶点坐标（180， 680)
9 长方形 （370, 680) 长60，宽120
10 正方形 (540, 600） 边长130
11 正方形 （640， 520） 边长80
12 长方形 (500, 140） 长300,宽60
在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞,若碰撞发生，则机器人无法完成行走。
机器人直线行走的最大速度为50v个单位/秒.机器人转弯时，最大转弯速度为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的最短时间路径。
注:要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。
图1 800×800平面场景图
二、问题分析
本题可以用AutoCAD作图软件完成部分路线及线段、弧线、坐标的标注等。
问题一
O点到A点
理论上是直线最短,但不能折点转弯（必须切线转弯)、必须与障碍物保持10单位的距离，转弯弧线半径最短为10个单位,则可以以障碍物5的左上角和右下角点位圆心画半径为10单位的圆，并在障碍物4的左下角画同样的圆,那么我们可以用拉绳子的方法模拟机器人行走路线，求出到达目标点的最短距离。
O到B与O到C
O到B与O到C最短路线求解分析原理与O到A一样不再重述。
O到A到B到C再到O 要求机器人到达各目标点在回到原点，此时不但要考虑障碍物的问题还要考虑从以目标点到另一目标点的转弯问题,此时简单的拉线一不满足。
问题二
时间与路程和速度的关系ST=V，速度与转弯半径的关系21.0100e1)(vvv，根据此公式不难得出半径与速度的关系，即半径越大速度约接近5，但半径越大路程越长，消耗时间也越多.
三、模型假设与约定
1、假设机器人无体积。
2、假设切线转弯时速度变化为瞬间，即没有加速度。
3、做题所用的数据全部保留两位小数
4、用AutoCAD软件作图过程不予描述，例举两条路线进行分析。
四、符号说明及名词定义
V:机器人行走速度
V（ρ)：机器人弧线行走速度
OV：机器人直线行走最大速度
ρ：机器人转弯半径
T:机器人行走时间
S：机器人行走路程
五、模型建立
模型建立
1、先来证明一个猜想：
猜想一:具有圆形限定区域的最短路径是由两部分组成的:一部分是平面上的自然最短路径(即直线段）,另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。（即问题分析中的拉绳子拉到最紧时的状况）
证明：假设在平面中有A（a，0）和B（—a,0）两点，中间有一个半圆形的障碍物,证明从A到B的最路径为AB。
平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于障碍物相交,所以设法尝试折线路径。在y轴上取一点C(0，y）,若y适当大，则折线ACB与障碍物不相交,折线ACB的长度为：
22||2a+yACB
显然||ACB随着y的减小而减小，减小y得1yy,即1CC,使得1AC与1CB与障碍物相切，切点分别为E和F,显然1ACB是这种折线路径中最短的.由于满足02的角满足tan，所以易知弧度EF小于1ECF的长, 即1ECFEF,从而
1EFFBACB,记线段AE、弧度EF、线段FB为AEFB，那么AEFB比任何折线路径都短.
下面在考察一条不穿过障碍物的任何一条路径，设其分别于OE和OF的延长线交与P、Q两点，记A和P之间的路径长度为AP，显然APAP,又由AEEO,所以｜APAE，从而APAE,同理可得BQBF.
再来比较PQ之间路径长度PQ和圆弧EF的长度的大小。若PQ之间的路径可有极坐标方程rr，则有10r，可得：
22r3PQrddEF
亦即路径APQB的长度超过路径AEFB的长度。以上证明足以说明了AEFB是满足条件A到B的最短路径。
猜想二：如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一根绳子，并以该圆环为支撑拉紧绳子，达到平衡状态时,圆心与该顶点以及两条切线的延长线的交点共线。
图3
证明猜想：
如图4.31所示，E点就是圆环上的一个顶点，ACDB就是拉紧的绳子，2O就是切线AC和BD的延长线的交点，证明1O、E、2O三点共线。
我们可以用力学的知识进行证明,因为是拉紧的绳子，所以两边的绳子拉力相等，设为1F,它们的合力设为0F，定点对圆环的作用力设为1F.
那么由几何学的知识我们可以知道0F一定与12OO共线，而又由力的平衡条件可知：
0F=1F
即12OO12OO与2EO共线。
综上所述1O、E和2O三点一定共线。
2、有了以上这个定理我们可以建立以下模型：
如图4，要求求出机器人从A绕过障碍物经过M点到达目标点B的最短路径，我们采用以下方法：
用一根钉子使一个圆环定在M点，使这个圆环能够绕M点转动。然后连接A和B的绳子并以这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯半径来计算)，拉紧绳子,那么绳子的长度就是A到B的最短距离.我们可以把路径图抽象为以下的几何图形。下面我们对这段路径求解:
图4
如图，A1,1xy是起点，B2,2xy是终点，13,3Oxy和34,4Oxy是两个固定的圆， 2O是一个可以绕M(p，q）点转动的圆环，三个圆的半径均为r，C、D、E、F、G、H均为切点。a、b、c、e，f分别是A1O、12OO、A2O、A3O、23OO的长度。A、B、1O、3O均是已知点，2O是未知点。那么最短路径就可以表示为：
LACDEFGHBCDEFGH
因为2O点的坐标未知,所以我们就不能用模型一中的线圆结构对其进行求解。故得先求出2O点的坐标。设2O坐标为（m,n），1AOC、12AOO、21AOO、23AOO、32OOF分别为i（i=1、2、3、4、5），1COD、2EOF、2EOM分别为1、2、。这样便有以下关系：
