2015年數(shù)學(xué)建模D題

2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽

承諾書

我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.

我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）

與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成

果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必

須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。

我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，

我們將受到嚴(yán)肅處理。

我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競賽組委會，可將我們的論文以任何形式進(jìn)行公開展示（包括

進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。

我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：D

我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）：

所屬學(xué)校（請?zhí)顚懲暾娜?*****************

參賽隊員（打印并簽名）：L__________________________

2.

X_________________________

指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：

II期：20期年9月9日

賽區(qū)評閱編號（山賽區(qū)組委會評閱前進(jìn)行編號）：

2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目

編號專用頁

賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：

賽區(qū)評閱記錄:

評

卷

人

評分

備注

全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：

機(jī)器人避障問題

摘要

二十一世紀(jì)科技發(fā)展迅速，機(jī)器人作業(yè)逐漸興盛。本文研究了機(jī)器人避障最短路徑和最短時

間的問題。主要研究了在一個區(qū)域中存在12個障礙物，由出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)以及由出發(fā)點(diǎn)

經(jīng)過途中的若干目標(biāo)點(diǎn)到達(dá)最終目標(biāo)點(diǎn)的兩種情形。我們通過證明具有圓形限定區(qū)域的最短

路徑是由兩部分組成的：一部分是平面上的自然最短路徑(即直線段)，另一部分是限定區(qū)

域的部分邊界，這兩部分是相切的，互相連接的。依據(jù)這個結(jié)果，我們可以認(rèn)為最短路徑一

定是由線和圓弧做組成，因此我們建立了線圓結(jié)構(gòu)，這樣無論路徑多么復(fù)雜，我們都可以將

路徑劃分為若干個這種線圓結(jié)構(gòu)來求解。

一、問題重述

圖1是一個800x800的平面場景圖，在原點(diǎn)0(0,0)點(diǎn)處有個機(jī)器人，它只能在該平面場

景范圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物

的數(shù)學(xué)描述如下表：

編號障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述

1正方形(300,400)邊長200

2圓形圓心坐標(biāo)(550,450),半徑70

3平行四邊形(360,240)底邊長140,左上頂點(diǎn)坐標(biāo)(400,330)

4三角形(280,100)上頂點(diǎn)坐標(biāo)(345,210),右下頂點(diǎn)坐標(biāo)(410,

100)

5正方形(80,60)邊長150

6三角形(60,300)上頂點(diǎn)坐標(biāo)(150,435),右下頂點(diǎn)坐標(biāo)(235,

300)

7長方形(0,470)長220,寬60

8平行四邊形(150,600)底邊長90,左上頂點(diǎn)坐標(biāo)(180,680)

9長方形(370,680)長60,寬120

10正方形(540,600)邊長130

11正方形(640,520)邊長80

12長方形(500,140)長300,寬60

在圖1的平面場景中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)(要求目標(biāo)點(diǎn)與障礙物的

距離至少超過10個單位)。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器

人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑山與直線路徑相切的一段圓弧組成，也可以由

兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)

生碰撞，同時要求機(jī)器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，

若碰撞發(fā)生，則機(jī)器人無法完成行走。

機(jī)器人直線行走的最大速度為%=5個單位/秒。機(jī)器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為

v=v(/?)=-~令它，其中"是轉(zhuǎn)彎半徑。如果超過該速度，機(jī)器人將發(fā)生側(cè)

翻，無法完成行走。

請建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景

圖中4個點(diǎn)0(0,0),A(300,300),B(100,700),C(700,640),具體計算：

(1)機(jī)器人從0(0,0)出發(fā)，0-A、O-B、0"和0-A-B-C-0的最短路徑。

(2)機(jī)器人從0(0,0)出發(fā)，到達(dá)A的最短時間路徑。

注：要給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的

總距離和總時間。

二、問題分析

本題可以用AutoCAD作圖軟件完成部分路線及線段、弧線、坐標(biāo)的標(biāo)注等。

問題一

0點(diǎn)到A點(diǎn)

理論上是直線最短，但不能折點(diǎn)轉(zhuǎn)彎(必須切線轉(zhuǎn)彎)、必須與障礙物保持10單位的距離，

轉(zhuǎn)彎弧線半徑最短為10個單位，則可以以障礙物5的左上角和右下角點(diǎn)位圓心畫半徑為10

單位的圓，并在障礙物4的左下角畫同樣的圓，那么我們可以用拉繩子的方法模擬機(jī)器人行

走路線，求出到達(dá)目標(biāo)點(diǎn)的最短距離。

0至IjB與0至UC

0到B與0到C最短路線求解分析原理與0到A一樣不再重述。

0到A到B到C再到0

要求機(jī)器人到達(dá)各目標(biāo)點(diǎn)在回到原點(diǎn)，此時不但要考慮障礙物的問題還要考慮從以目標(biāo)點(diǎn)到

另一目標(biāo)點(diǎn)的轉(zhuǎn)彎問題，此時簡單的拉線一不滿足。

問題二

時間與路程和速度的關(guān)系T=9,速度與轉(zhuǎn)彎半徑的關(guān)系U=V(/9)=―2k，根據(jù)此

公式不難得出半徑與速度的關(guān)系，即半徑越大速度約接近5,但半徑越大路程越長，消耗時

間也越多。

三、模型假設(shè)與約定

1、假設(shè)機(jī)器人無體積。

2、假設(shè)切線轉(zhuǎn)彎時速度變化為瞬間，即沒有加速度。

3、做題所用的數(shù)據(jù)全部保留兩位小數(shù)

4、用AutoCAD軟件作圖過程不予描述，例舉兩條路線進(jìn)行分析。

四、符號說明及名詞定義

V：機(jī)器人行走速度

V(P):機(jī)器人弧線行走速度

%:機(jī)器人直線行走最大速度

P：機(jī)器人轉(zhuǎn)彎半徑

T：機(jī)器人行走時間

S：機(jī)器人行走路程

五、模型建立

模型建立

1、先來證明一個猜想：

猜想一：具有圓形限定區(qū)域的最短路徑是由兩部分組成的：一部分是平面上的自然最短路徑

(即直線段)，另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。(即問

題分析中的拉繩子拉到最緊時的狀況)

證明：假設(shè)在平面中有A(a,0)和B(-a,0)兩點(diǎn)，中間有一個半圓形的障礙物，證明從

A到B的最路徑為A￡FB。

C（0.y）

平面上連接兩點(diǎn)最短的路徑是通過這兩點(diǎn)的直線段，但是連接兩點(diǎn)的線段于障礙物相交，所

以設(shè)法嘗試折線路徑。在y軸上取一點(diǎn)C(0,y),若y適當(dāng)大，則折線ACB與障礙物不相

交，折線ACB的長度為：

14函=2舟+丫2

顯然IAC剛隨著丫的減小而減小，減小丫得y-必，即cfq,使得AG與G8與障礙

物相切，切點(diǎn)分別為E和F，顯然ACR是這種折線路徑中最短的。由于滿足0<夕<]?的角

滿足夕<tan°,所以易知弧度EF小于EC.F的長，即EC.F>，從而

AE+EF+FB<AC.B，記線段AE、弧度EF、線段FB為AEFB,那么AEFB比任何折線路徑

都短。

下面在考察一條不穿過障礙物的任何一條路徑，設(shè)其分別于0E和0F的延長線交與P、Q兩

點(diǎn)，記A和P之間的路徑長度為AP,顯然AP>|AP|,又由AE,EO,所以||AP|>AE,從

而同理可得。

再來比較PQ之間路徑長度PQ和圓弧EF的長度的大小。若PQ之間的路徑可有極坐標(biāo)方程

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

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

亦即路徑APQB的長度超過路徑AEFB的長度。以上證明足以說明了AEFB是滿足條件A到B

的最短路徑。

猜想二:如果一個圓環(huán)可以繞著環(huán)上一個定點(diǎn)轉(zhuǎn)動，那么過圓環(huán)外兩定點(diǎn)連接一根繩子，并

以該圓環(huán)為支撐拉緊繩子，達(dá)到平衡狀態(tài)時，圓心與該頂點(diǎn)以及兩條切線的延長線的交點(diǎn)共

線。

圖3

證明猜想：

如圖4.31所示，E點(diǎn)就是圓環(huán)上的一個頂點(diǎn)，ACDB就是拉緊的繩子，O?就是切線AC和

BD的延長線的交點(diǎn)，證明?！窫、。2三點(diǎn)共線。

我們可以用力學(xué)的知識進(jìn)行證明，因為是拉緊的繩子，所以兩邊的繩子拉力相等，設(shè)為月，

它們的合力設(shè)為應(yīng)，定點(diǎn)對圓環(huán)的作用力設(shè)為轉(zhuǎn)。

那么由幾何學(xué)的知識我們可以知道月一定與麗2共線，而又由力的平衡條件可知：

既*

即麗2麗2與葩共線。

綜上所述E和。2三點(diǎn)一定共線。

2、有了以上這個定理我們可以建立以下模型：

如圖4,要求求出機(jī)器人從A繞過障礙物經(jīng)過M點(diǎn)到達(dá)目標(biāo)點(diǎn)B的最短路徑，我們采用以下

方法：

用一根釘子使一個圓環(huán)定在M點(diǎn)，使這個圓環(huán)能夠繞M點(diǎn)轉(zhuǎn)動。然后連接A和B的繩子并以

這些轉(zhuǎn)彎處的圓弧為支撐（這里轉(zhuǎn)彎處圓弧的半徑均按照最小轉(zhuǎn)彎半徑來計算），拉緊繩子,

那么繩子的長度就是A到B的最短距離。我們可以把路徑圖抽象為以下的幾何圖形。下面我

們對這段路徑求解:

如圖，A（玉J1）是起點(diǎn)，B（X2）2）是終點(diǎn)，。1（七）3）和。314.%）是兩個固定的圓，°2是

一個可以繞M（p,q）點(diǎn)轉(zhuǎn)動的圓環(huán)，三個圓的半徑均為r,C、D、E、F、G、H均為切點(diǎn)。a、

b、c、e,f分別是AQ、。02、A。?、A。?、。2°3的長度。A、B、均是已知點(diǎn)，

。2是未知點(diǎn)。那么最短路徑就可以表示為：

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

因為。2點(diǎn)的坐標(biāo)未知，所以我們就不能用模型一中的線圓結(jié)構(gòu)對其進(jìn)行求解。故得先求出

。2點(diǎn)的坐標(biāo)。設(shè)。2坐標(biāo)為（m,n）,ZAO.C、ZAO}O2、NA。2。1、ZAO2O3>ZO3O2F

分別為a,（i=l、2、3、4、5）,NCOQ、2EOJ、NEO2M分別為q、4、6。這

樣便有以卜關(guān)系：

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的坐標(biāo)，從而可以得出路徑的長為:

2

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

1{=GH+HB,這可以采用模型一中的線圓結(jié)構(gòu)來求解。

建立模型

繩子套在一個環(huán)上，環(huán)套在一個定圓上。如圖5

圖5

可證明此路線為最短路徑。

六、模型求解

問題一

用AutoCAD軟件對機(jī)器人的行走路徑進(jìn)行作圖分析。

1,0點(diǎn)到A點(diǎn)（0-A）

目測從0點(diǎn)到A點(diǎn)比較短的路線有兩條，即從障礙物5頂部繞和從其底部繞（如圖6）。

用AutoCAD軟件對路線進(jìn)行標(biāo)注（如圖7）,計算兩條路線的長度。

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

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

兩條路線進(jìn)行比較可知線路1最短。

2、0點(diǎn)到B點(diǎn)（OfB）

目測可知從0點(diǎn)到B點(diǎn)的最短路線必從0點(diǎn)到B點(diǎn)線路1（如圖8）和0點(diǎn)到B點(diǎn)線路2（如

圖9）中產(chǎn)生，分別對兩條路進(jìn)行標(biāo)注，線路1標(biāo)注圖（如圖6）,線路2標(biāo)注圖（如圖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

對和品進(jìn)行比較可知）,線路為最短線路。

SDsiDi（5B<SB1

3、0點(diǎn)到C點(diǎn)（0-C）

作圖分析可得出兩條路線距離比較近，線路1（如圖11）和線路2（如圖12）。分別對兩條

路進(jìn)行標(biāo)注，線路1標(biāo)注圖（如圖13）,線路2標(biāo)注圖（如圖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

對、進(jìn)行比較可知線路最短。

5ScclScc2<Sc,1

4、0-A—B-C-0

若使此路徑最短，則取0-A和0-C的最短路線,A-B和B-C的最短線路不難看出，0-A

-B-CfO的最短線路如圖15,對此線路進(jìn)行標(biāo)注，如圖16。

問題二

此問題可以用模型二解決，根據(jù)公式v=v(p)=一黑L可知弧線速度與轉(zhuǎn)彎半徑的關(guān)

1+eO-Olp

系，即隨著「的增大v(P)的增長幅度逐漸最終趨近與0(弧度線的行走速度趨近與5)o

根據(jù)公式/=Op可知弧線長度與轉(zhuǎn)彎半徑的關(guān)系。由此可知機(jī)器人行走距離與行走速度和時

間的關(guān)系。

最短時間路線如圖17,標(biāo)注層如圖18.

七、模型檢驗和模型評價

一、模型優(yōu)點(diǎn)

1、運(yùn)用AutoCAD作圖軟件，方便快捷的標(biāo)注出各線段，各點(diǎn)的相關(guān)信息。

2、小數(shù)點(diǎn)保留兩位，精確度較高。

3、模型簡單易懂，便于實際檢驗及應(yīng)用。

二、模型缺陷

1、問題二求解精確度不高。沒有相關(guān)程序作支持。

2、在障礙物較多時，且形狀不規(guī)則時，模型需要進(jìn)一步改進(jìn)。

八、參考文獻(xiàn)

[1]尤承業(yè)，解析兒何，北京，北京大學(xué)出版社，2004

[2]邦辿，圖論及其應(yīng)用，西安，西安科學(xué)出版社1984

[3]譚永基，數(shù)學(xué)模型，上海，復(fù)旦大學(xué)出版社，2011

[4]周培德，計算幾何一算法與設(shè)計，北京清華大學(xué)出版社，2005

[5]胡海星，RPG游戲中精靈的移動問題，雜志《程序員》2011；

九、附錄

各路線的相關(guān)信息（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,,達(dá)

,,66,,,,2

7555,3,344433321滕

099354400013

061.8549405109.弟

),.37.....).

630085441

5355))275))14

)))))9)5))

長度圓心坐標(biāo)總距離總時間

224.5

行走路線序號類型起始坐標(biāo)終點(diǎn)坐標(biāo)

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

長度圓心坐標(biāo)總距離總時間

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

行走路線序號類型起始坐標(biāo)終點(diǎn)坐標(biāo)長度圓心坐標(biāo)總距離總時間

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)

行走路線序號類型起始坐標(biāo)終點(diǎn)坐標(biāo)長度圓心坐標(biāo)總距離總時間

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