2015年数学建模D题

2012高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）

与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成

果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必

须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，

我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括

进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D

我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）：******************

参赛队员（打印并签名）：L__________________________

2.

X_________________________

指导教师或指导教师组负责人（打印并签名）：

II期：20期年9月9日

赛区评阅编号（山赛区组委会评阅前进行编号）：

2012高教社杯全国大学生数学建模竞赛题目

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录:

评

卷

人

评分

备注

全国统一编号（由赛区组委会送交全国前编号）：

机器人避障问题

摘要

二十一世纪科技发展迅速，机器人作业逐渐兴盛。本文研究了机器人避障最短路径和最短时

间的问题。主要研究了在一个区域中存在12个障碍物，由出发点到达目标点以及由出发点

经过途中的若干目标点到达最终目标点的两种情形。我们通过证明具有圆形限定区域的最短

路径是由两部分组成的：一部分是平面上的自然最短路径(即直线段)，另一部分是限定区

域的部分边界，这两部分是相切的，互相连接的。依据这个结果，我们可以认为最短路径一

定是由线和圆弧做组成，因此我们建立了线圆结构，这样无论路径多么复杂，我们都可以将

路径划分为若干个这种线圆结构来求解。

一、问题重述

图1是一个800x800的平面场景图，在原点0(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个单位，否则将发生碰撞，

若碰撞发生，则机器人无法完成行走。

机器人直线行走的最大速度为%=5个单位/秒。机器人转弯时，最大转弯速度为

v=v(/?)=-~令它，其中"是转弯半径。如果超过该速度，机器人将发生侧

翻，无法完成行走。

请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景

图中4个点0(0,0),A(300,300),B(100,700),C(700,640),具体计算：

(1)机器人从0(0,0)出发，0-A、O-B、0"和0-A-B-C-0的最短路径。

(2)机器人从0(0,0)出发，到达A的最短时间路径。

注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的

总距离和总时间。

二、问题分析

本题可以用AutoCAD作图软件完成部分路线及线段、弧线、坐标的标注等。

问题一

0点到A点

理论上是直线最短，但不能折点转弯(必须切线转弯)、必须与障碍物保持10单位的距离，

转弯弧线半径最短为10个单位，则可以以障碍物5的左上角和右下角点位圆心画半径为10

单位的圆，并在障碍物4的左下角画同样的圆，那么我们可以用拉绳子的方法模拟机器人行

走路线，求出到达目标点的最短距离。

0至IjB与0至UC

0到B与0到C最短路线求解分析原理与0到A一样不再重述。

0到A到B到C再到0

要求机器人到达各目标点在回到原点，此时不但要考虑障碍物的问题还要考虑从以目标点到

另一目标点的转弯问题，此时简单的拉线一不满足。

问题二

时间与路程和速度的关系T=9,速度与转弯半径的关系U=V(/9)=―2k，根据此

公式不难得出半径与速度的关系，即半径越大速度约接近5,但半径越大路程越长，消耗时

间也越多。

三、模型假设与约定

1、假设机器人无体积。

2、假设切线转弯时速度变化为瞬间，即没有加速度。

3、做题所用的数据全部保留两位小数

4、用AutoCAD软件作图过程不予描述，例举两条路线进行分析。

四、符号说明及名词定义

V：机器人行走速度

V(P):机器人弧线行走速度

%:机器人直线行走最大速度

P：机器人转弯半径

T：机器人行走时间

S：机器人行走路程

五、模型建立

模型建立

1、先来证明一个猜想：

猜想一：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径

(即直线段)，另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。(即问

题分析中的拉绳子拉到最紧时的状况)

证明：假设在平面中有A(a,0)和B(-a,0)两点，中间有一个半圆形的障碍物，证明从

A到B的最路径为A£FB。

C（0.y）

平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于障碍物相交，所

以设法尝试折线路径。在y轴上取一点C(0,y),若y适当大，则折线ACB与障碍物不相

交，折线ACB的长度为：

14函=2舟+丫2

显然IAC刚随着丫的减小而减小，减小丫得y-必，即cfq,使得AG与G8与障碍

物相切，切点分别为E和F，显然ACR是这种折线路径中最短的。由于满足0<夕<]•的角

满足夕<tan°,所以易知弧度EF小于EC.F的长，即EC.F>，从而

AE+EF+FB<AC.B，记线段AE、弧度EF、线段FB为AEFB,那么AEFB比任何折线路径

都短。

下面在考察一条不穿过障碍物的任何一条路径，设其分别于0E和0F的延长线交与P、Q两

点，记A和P之间的路径长度为AP,显然AP>|AP|,又由AE,EO,所以||AP|>AE,从

而同理可得。

再来比较PQ之间路径长度PQ和圆弧EF的长度的大小。若PQ之间的路径可有极坐标方程

r=r(6),则有r>10,可得：

PQ^^r2+r2d0>Jd6—9—EF

亦即路径APQB的长度超过路径AEFB的长度。以上证明足以说明了AEFB是满足条件A到B

的最短路径。

猜想二:如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一根绳子，并

以该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以及两条切线的延长线的交点共

线。

图3

证明猜想：

如图4.31所示，E点就是圆环上的一个顶点，ACDB就是拉紧的绳子，O?就是切线AC和

BD的延长线的交点，证明。「E、。2三点共线。

我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等，设为月，

它们的合力设为应，定点对圆环的作用力设为转。

那么由几何学的知识我们可以知道月一定与丽2共线，而又由力的平衡条件可知：

既*

即丽2丽2与葩共线。

综上所述E和。2三点一定共线。

2、有了以上这个定理我们可以建立以下模型：

如图4,要求求出机器人从A绕过障碍物经过M点到达目标点B的最短路径，我们采用以下

方法：

用一根钉子使一个圆环定在M点，使这个圆环能够绕M点转动。然后连接A和B的绳子并以

这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯半径来计算），拉紧绳子,

那么绳子的长度就是A到B的最短距离。我们可以把路径图抽象为以下的几何图形。下面我

们对这段路径求解:

如图，A（玉J1）是起点，B（X2）2）是终点，。1（七）3）和。314.%）是两个固定的圆，°2是

一个可以绕M（p,q）点转动的圆环，三个圆的半径均为r,C、D、E、F、G、H均为切点。a、

b、c、e,f分别是AQ、。02、A。?、A。?、。2°3的长度。A、B、均是已知点，

。2是未知点。那么最短路径就可以表示为：

L=|AC|+CD+|DE|+EF+|FG|+GH+|HB|

因为。2点的坐标未知，所以我们就不能用模型一中的线圆结构对其进行求解。故得先求出

。2点的坐标。设。2坐标为（m,n）,ZAO.C、ZAO}O2、NA。2。1、ZAO2O3>ZO3O2F

分别为a,（i=l、2、3、4、5）,NCOQ、2EOJ、NEO2M分别为q、4、6。这

样便有以卜关系：

4=小(玉_尤3)2+(弘—>3)2

2

b=yl(x3-m)+(y3-n)-

22

<c=A/(x,-/n)+(y1-n)

22

e=yJ(x]-x4)+(y}-y4)

f=+(y4-nf

在RfA401C中：

r

a-arccos—

xa

在AAO02中:

a2+b2-c2

a=arccos

22ab

b2+c2-a2

a=arccos

32bc

在AAO2O3中:

aA-arccos

2cf

在一Rtg!0[F中:

2r

a5=arccos—

则:

加

4-一

2一四一小

加

a一

--

2-a3-a4-a5

又因为MQ一定会在NEQ尸的角平分线上，所以满足：

6=%

2

02我们采用向量的形式来求，易知丽，的一个方向向量:

:=(12)

x2-n

而厚与丽2垂直，故其一个方向向量:

而:

02M=(p-m,q-n)

所以:

上£丝

112II02MI

综合以上式子可以求得。2的坐标，从而可以得出路径的长为:

2

L—Ja2一厂+4r+b+ar+2J(--)-厂+10

1{=GH+HB,这可以采用模型一中的线圆结构来求解。

建立模型

绳子套在一个环上，环套在一个定圆上。如图5

图5

可证明此路线为最短路径。

六、模型求解

问题一

用AutoCAD软件对机器人的行走路径进行作图分析。

1,0点到A点（0-A）

目测从0点到A点比较短的路线有两条，即从障碍物5顶部绕和从其底部绕（如图6）。

用AutoCAD软件对路线进行标注（如图7）,计算两条路线的长度。

路线1：SAl=224.50+9.05+237.49=471.04

线路2：5A2=237.49+11.14+249.8=498.43

两条路线进行比较可知线路1最短。

2、0点到B点（OfB）

目测可知从0点到B点的最短路线必从0点到B点线路1（如图8）和0点到B点线路2（如

图9）中产生，分别对两条路进行标注，线路1标注图（如图6）,线路2标注图（如图10）,

计算两条路线的长度。

图4

图5

图6

图7

线路1：

SR=111.36+6.15+96.95+9.89+60+13.66+76.41+7.78+76.41+4.23+305.78=800.46

线路2：

Sa=111.36+96.95+6.15+9.24+230.49+12.22+224.5+8.37+178.12=877.4

对和品进行比较可知）,线路为最短线路。

SDsiDi（5B<SB1

3、0点到C点（0-C）

作图分析可得出两条路线距离比较近，线路1（如图11）和线路2（如图12）。分别对两条

路进行标注，线路1标注图（如图13）,线路2标注图（如图14）,计算两条路线的长度。

图8

图9

图

图11

线路1

=43.59+6.89+80+6.54+387.81+0.7+7.69+133.04+237.49+0.06+184.39=1088.2

线路2

SCr2=43.59+6.89+80+7.9+170+47.53+169.71+1.72+341.76+8.93+224.5=1102.53

对、进行比较可知线路最短。

5ScclScc2<Sc,1

4、0-A—B-C-0

若使此路径最短，则取0-A和0-C的最短路线,A-B和B-C的最短线路不难看出，0-A

-B-CfO的最短线路如图15,对此线路进行标注，如图16。

问题二

此问题可以用模型二解决，根据公式v=v(p)=一黑L可知弧线速度与转弯半径的关

1+eO-Olp

系，即随着「的增大v(P)的增长幅度逐渐最终趋近与0(弧度线的行走速度趋近与5)o

根据公式/=Op可知弧线长度与转弯半径的关系。由此可知机器人行走距离与行走速度和时

间的关系。

最短时间路线如图17,标注层如图18.

七、模型检验和模型评价

一、模型优点

1、运用AutoCAD作图软件，方便快捷的标注出各线段，各点的相关信息。

2、小数点保留两位，精确度较高。

3、模型简单易懂，便于实际检验及应用。

二、模型缺陷

1、问题二求解精确度不高。没有相关程序作支持。

2、在障碍物较多时，且形状不规则时，模型需要进一步改进。

八、参考文献

[1]尤承业，解析儿何，北京，北京大学出版社，2004

[2]邦辿，图论及其应用，西安，西安科学出版社1984

[3]谭永基，数学模型，上海，复旦大学出版社，2011

[4]周培德，计算几何一算法与设计，北京清华大学出版社，2005

[5]胡海星，RPG游戏中精灵的移动问题，杂志《程序员》2011；

九、附录

各路线的相关信息（0到A、。到B、。到C的最短路线，O-A-B-CfO的最短

路线，0到A的最短时间路线）

豳

询OT4

思

遇

W帝

>繇

弱

与

A犀

泄

品

魅K

11—1事

900765432132

O加

-黄S

叫

二-口=7S爆法

烯烯浴燃城曜盘玲屣

((((

11((211(((

442((244(577

04532322715060

...00...1...B

6..5968.065

1底

9,5,0268,41,

,66,,,,,2

33底

555,,4443321

993544009139

1笠

6..854940519.

.37......

363005041

555))2875)414

)))))9)5)))

((((((

1((211(77

412((244(560

04522227150(..

(3316凑

1...00.....315

06..596800,1

09,5,5268,4,,达

,,66,,,,2

7555,3,344433321滕

099354400013

061.8549405109.弟

),.37.....).

630085441

5355))275))14

)))))9)5))

长度圆心坐标总距离总时间

224.5

行走路线序号类型起始坐标终点坐标

9.05(80,210)471.0496.02

1直线(0,0)(232.11,50.23)

237.49

2弧线(232.11,50.23)(232.17,50.24)

305.78

3直线(232.17,50.24)(412.17,90.24)

4.23(60,300)

4弧线(412.17,90.24)(417.82,94.83)

162.25

5直线(417.82,94.83)(491.66,205.51)

7.78(150,435)OfC最短

6弧线(491.66,205.51)(492.06,206.08)

76.41

距离路线

7直线(492.06,206.08)(727.94,513.92)

13.66(220,470)800.46180.65

8弧线(727.94,513.92)(730,520)

60

9直线(730,520)(730,600)

9.89(220,530)

10弧线(730,600)(727.65,606.44)

96.95

11直线(727.65,606.44)(700.640)

6.15(150,600)

111.36

长度圆心坐标总距离总时间

237.49

0.06(230,60)

184.39

7.69(410,100)

133.04

0.7(500,200)1088.2228.01

387.81

6.54(720,520)

80

6.89(720,600)

43.59

行走路线序号类型起始坐标终点坐标长度圆心坐标总距离总时间

1直线(0,0)(70.51,213.14)224.5

2弧线(70.51,213.14)(76.61,219.41)9.05(80,210)

03直线(76.73,219.45)(294.15,294.66)230.06

―►4弧线(294.15,294.66)(300.43,307.11)15.42(290.88,304.11)

5(300.43,307.11)(229.54,532.99)236.75

A直线

6弧线(229.54,532.99)(225.5,538.35)6.85(220,530)

―►

7一自：线(225.5,538.35)(144.5,591.65)96.95

B2730568.66

8弧线(144.5,591.65)(140.86,595.94)5.71(150,600)

―►

9直线(140.86595.94)(99.04,690.2)103.11

C10弧线(99.04,690.2)(109.06,704.22)20.76(108.18,694.25)

—►11直线(109.06,704.22)(270.88,689.96)162.44

012弧线(270.88,689.96)(272,689.8)1.13(270,680)

13直线(272,689.8)(368,670.2)97.98

14弧线(368,670.2)(370,670)2.01(370,680)

行走路线序号类型起始坐标终点坐标长度圆心坐标总距离总时间

15直线(370,670)(430,670)60

16弧线(430,670)(435.59,671.71)5.93(430,680)

17直线(435.59,671.71)(543.41,738.29)119.16

18