2012年數(shù)學(xué)建模論文.docx

2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網(wǎng)上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： D 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 164D01 所屬學(xué)校（請?zhí)顚懲暾娜?浙江同濟科技職業(yè)學(xué)院 參賽隊員 (打印并簽名) ：1. 張強 2. 毛園梅 3. 林文義 指導(dǎo)教師或指導(dǎo)教師組負責(zé)人 (打印并簽名)： 建模指導(dǎo)組 日期：2012年 10月 9 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：機器人避障路徑研究模型摘要本文研究的是機器人避障行進到達目的地的最短路徑或者最短時間的問題。根據(jù)對題意的分析發(fā)現(xiàn)兩問題的研究重點不同，一個側(cè)重最短路線，另一個側(cè)重最短時間。線路是由直線與直線路徑相切的一段圓弧組成。我們對問題進行了深入的理解與分析，建立了兩個模型。并用此模型解機器人避障行進到達目的地的最短路徑或最短時間。針對問題一，我們考慮將問題分成兩部分討論，建立兩個不同的模型。一、建立一個求機器人從O點出發(fā)，到達允許區(qū)域內(nèi)的任意一點的最短路徑模型；二、通過路線之間的比較，求出路線OABCO的最短路徑。第一部分中先用AutoCAD畫出距離每個障礙物10個單位以外的區(qū)域范圍，并按照到達目的地所經(jīng)的拐彎次數(shù)將其劃分為六個區(qū)塊，用遞歸算法對到達允許區(qū)域的任意一點規(guī)劃最短路線，得出OA、OB、OC路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間。再對結(jié)果進行分析整理，并用AutoCAD將其線路表示出來，第二部分根據(jù)第一部分的路線模型進一步的分析，考慮到機器人轉(zhuǎn)彎的時圓弧必須經(jīng)過A、B、C三個點。同時還需要考慮ABC之間的路線選擇，則將任意相同兩點間的不同線路進行比較得出最短的路徑，結(jié)合四段最短的路徑即可得出我們需要的結(jié)果。最終通過matlab編程運行得到如下結(jié)果： OA: 最短路徑：471.0372個單位；最短路徑所需時間：96.0176s；OB: 最短路徑：878.0465個單位；最短路徑所需時間：183.1084s；OC: 最短路徑：1093個單位； 最短路徑所需時間：224.1254s； OABCO: 最短路徑：2715.3個單位；最短路徑所需時間：577.5709s。針對問題二，要求從O (0, 0)出發(fā)，到達A的最短時間路徑。針對不同路徑的拐彎，拐彎的路徑總長及拐彎時的速度都不同。我們假設(shè)機器人行走路線從直線轉(zhuǎn)換為彎道時的速度是突變的。分析得到各障礙物各點的坐標(biāo)，進而分析考慮最大轉(zhuǎn)彎速度v=v01+e10-0.12會隨（拐彎半徑）的改變而改變。在后期驗證得到在10,15范圍內(nèi)=11.5使得OA路徑時間最短。然后根據(jù)路線分析圖結(jié)合坐標(biāo)列出相關(guān)方程組解得兩內(nèi)切圓坐標(biāo)。同理假設(shè)一個普通的最小半徑內(nèi)切圓的圓心坐標(biāo)，結(jié)合求解分析運用兩點之間距離公式、點到直線距離公式、以及勾股定理、反三角函數(shù)等方法，建立規(guī)劃模型。并結(jié)合matlab編程求得最短路徑L=473.1588個單位,最短時間T=94.8016s，以及每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)。關(guān)鍵詞：最短路徑 遞歸算法 matlab 劃分區(qū)塊 模型規(guī)劃一 問題重述圖1是一個800800的平面場景圖，在原點O(0, 0)點處有一個機器人，它只能在該平面場景范圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：編號障礙物名稱左下頂點坐標(biāo)其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(biāo)(550, 450)，半徑703平行四邊形(360, 240)底邊長140，左上頂點坐標(biāo)(400, 330)4三角形(280, 100)上頂點坐標(biāo)(345, 210)，右下頂點坐標(biāo)(410, 100)5正方形(80, 60)邊長1506三角形(60, 300)上頂點坐標(biāo)(150, 435)，右下頂點坐標(biāo)(235, 300)7長方形(0, 470)長220，寬608平行四邊形(150, 600)底邊長90，左上頂點坐標(biāo)(180, 680)9長方形(370, 680)長60，寬12010正方形(540, 600)邊長13011正方形(640, 520)邊長8012長方形(500, 140)長300，寬60在圖1的平面場景中，障礙物外指定一點為機器人要到達的目標(biāo)點（要求目標(biāo)點與障礙物的距離至少超過10個單位）。規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑。機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走。機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速度，機器人將發(fā)生側(cè)翻，無法完成行走。請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景圖中4個點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計算：(1) 機器人從O(0, 0)出發(fā)，OA、OB、OC和OABCO的最短路徑。(2) 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑。注：要給出路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間。圖1見附錄一二 問題背景隨著科技的發(fā)展，機器人運用越來越廣泛，已經(jīng)深入到很多領(lǐng)域，它的產(chǎn)生給社會發(fā)展帶來很多方便。以往都是傳統(tǒng)的機器人，而現(xiàn)在是智能避障機器人，現(xiàn)在機器人避障與路徑規(guī)劃是研究機器人的又一個方向，它在某一程度上代表了當(dāng)代的信息技術(shù)，自動化技術(shù)以及系統(tǒng)集成的技術(shù)的最新的發(fā)展。隨著我國對移動機器人深入的研究，對處理移動機器人避障與路徑規(guī)劃的方法有：勢場法、柵格法等解決方法。也有根據(jù)坐標(biāo)建立模型求得機器人通過障礙的最短路徑、最短時間以及各個點的坐標(biāo)。需要從多方面研究機器人避障與路徑規(guī)劃的關(guān)系。三 問題分析由問題得知機器人的行走路徑是由直線段和圓弧組成，機器人拐彎的路徑有與直線路徑相切的圓弧組成，且每個圓弧的半徑最小為10各單位，以及與障礙物的最近距離也為10個單位。只有與障礙物相切并且拐彎半徑最小行走路徑才會最短。根據(jù)這些條件對問題一、二進行分析： 對于問題一：根據(jù)題目要求，用AutoCAD對圖1平面場景圖中的障礙物進行處理。先對OA路徑進行分析，經(jīng)分析我們知道要使所有路徑計算方便，可以將路徑進行分割。在分析中得圓弧路徑與相切直線，以及各拐彎圓弧所在圓的圓心的連線之間的關(guān)系。分為兩種情況：1.兩圓弧相切的公共直線與兩圓弧所在圓的圓心連線平行；2.兩圓弧相切的公共直線與兩圓弧所在圓的圓心連線相交。分別列出式子求出平行、相交時相切圓弧直線中點坐標(biāo)。在兩直線相交的情況下，中點坐標(biāo)為兩直線交點坐標(biāo)；而平行情況下，中點坐標(biāo)則需更詳細的計算分析。再對四種路徑進行分析求解（見圖），在路徑OA模型并且對平面場景圖進行分區(qū)。將處理圖劃分為六塊區(qū)域，分別用六種顏色表示，我們考慮將路徑分段求解再相加，根據(jù)OA模型一直擴展到使平面內(nèi)的任意一點都能求出最短路徑。 對于問題二：由于機器人行走路線從直線轉(zhuǎn)換為彎道時的速度是突變的，要求從O點到A點的最短時間路徑，必須考慮最大直線速度v0,最大拐彎速度v。模型建立中為了更直觀的表示，將改為r。r越大，路徑總距離越大；r越小，v會趨向為5個單位每秒。要使機器人不發(fā)生側(cè)翻并且拐彎速度達到最大，就要使在合適的范圍內(nèi)，并且有一個臨界值使時間最短。針對問題一給出的OA的最短路徑圖分析，給出一個最短半徑圓，要使路徑總和最短，需要建立一個與最短半徑圓的內(nèi)切圓，使所經(jīng)的圓弧最短。結(jié)合路徑分析圖（圖）聯(lián)立方程組解的內(nèi)切圓切點坐標(biāo)，進而得到拐彎所在圓的圓心坐標(biāo)，得到坐標(biāo)和拐彎半徑的關(guān)系，再結(jié)合兩點間距離公式，勾股定理，反三角函數(shù)等方法，得到直線與角度之間的關(guān)系，并運用Matlab編程得出每段直線段或圓弧的起點和終點坐標(biāo)，以及路徑總長與最短總時間。根據(jù)分析建立一個統(tǒng)一的規(guī)劃模型。四 模型假設(shè)1. 假設(shè)機器人為一個點，不考慮其寬度；2. 假設(shè)機器人在避障行走中地面無破損；3. 假設(shè)機器人行走時未出現(xiàn)能量耗盡等自身故障；4. 假設(shè)拐彎時未出現(xiàn)事故，能順利完成避障任務(wù)；5. 假設(shè)機器人行走路線從直線轉(zhuǎn)換為彎道時的速度是突變的；五 符號說明a:OB兩點間直線距離；b:AB兩點間直線距離；l:OA兩點間直線距離；l1:OM兩點間直線距離；l2:ON兩點間直線距離；L:OA三段路徑總長；c:點B到直線OA的距離；ki:為直線斜率i=OA、OB、AB；t1、t2、t3:分別為OM、ON、弧MB段的最短時間；T:最短時間路徑的最短時間；六 模型建立與求解問題一：題中需要我們給出一個從區(qū)域中一點到達另一點的避障最短路徑，首先我們先對任意類似OA的路徑進行求解分析，給出OA路徑圖（見模型分析圖）。OA的最短路徑圖一：模型分析圖圖二：OA路徑圖由題可知，O0,0,A300，300,Q80，210，最小半徑圓的半徑為10,運用兩點間距離公式求得OB、AB、OA間距離：a=802+2102b=80-3002+210-3002l=3002+3002結(jié)合圖形分析，給出與圓B相切所在的直線，與圓相切于M、N點，分別求OM、AN的距離在OBM中，同上方法所得l1=a2-102在ABN中同理可得l2=b2-102OA最短路徑長度L=n180+l1+l2=473.1588根據(jù)問題分析:為了使兩圓相切路線（如圖）轉(zhuǎn)化為類OA型，我們將所有情況做如下處理。將公共切線的中點作為分割點。情況一：相交圖三我們假設(shè)兩圓心坐標(biāo)分別為Ox1,y1和O,x2,y2,半徑均為r，中點M坐標(biāo)為x3,y3化解可得:x3=x1+x22y3=y1+y22M為分割點將兩個圓轉(zhuǎn)變?yōu)閮啥晤愃朴贠A路徑建立模型進行求解。情況二：平行(斜率k存在)圖四化簡得x3=x1+y12+x1-y1*100x1-y12+y2-x22y3=x2+y22+y2-x2*100x1-y12+y2-x22情況三：平行（斜率k不存在）圖五 化簡得 x3=x1+10y3=x2+y22由此多次分割我們得到OB、OC、OABCO的最短路徑。 圖六：OB路徑圖OC的最短路徑 圖七：OC路徑圖 經(jīng)過對以上模型的分析，我們總結(jié)歸納出從O點出發(fā)到安全區(qū)域的任意一點的最短路線模型，通過matlab使用遞歸算法，幾何解析等方法通過比較拐彎次數(shù)及路徑大小將區(qū)域劃分為6大塊。（見附錄二）程序（見附錄四）中X,Y為目標(biāo)點的坐標(biāo)，O1,O2,Cx,Cy,Dx,Dy,ST,SL分別為圓心的坐標(biāo)，圓弧起點坐標(biāo)，圓弧終點坐標(biāo)，行走總時間，行走總路程。利用上面證得的原理找到原點到區(qū)域各點的路徑，在對比得出最短路徑。結(jié)果分別如下：OA:圓弧的起點:70.5060,213.1406; 圓弧的終點:76.6064,219.4066;圓弧圓心：80，210；最短路徑：471.0372個單位；最短路徑所需時間：96.0176sOB：圓弧的起點:70.5060，213.1406、152.4384，268.1000、175.9256，498.8335、144.5033，591.6462 圓弧的終點:75.9750，219.1542、172.3506，382.7149、177.7514，547.4135、140.6916， 596.3458; 圓弧圓心：80，210、235 ，300、220，530、150，600；最短路徑：878.0465個單位；最短路徑所需時間：183.1084s OC：圓弧的起點:226.4680 ，71.2297、367.7400，141.1797、479.0629， 208.5977、689.1846，534.0218705.8604，587.6600 圓弧的終點:228.5009， 71.6627 、416.0461，154.3346、482.7379，215.1680、705.6055，546.9896、701.1507，599.4649; 圓弧圓心：230 ，60、410 ，100、500 ，200 、720 ，520 720 ，600； 最短路徑：1093個單位；最短路徑所需時間：224.1254s由于第二部分各個目標(biāo)點在路線中，所以為了使路線最短我們將各點分布在拐彎圓弧之上。OABCO的最短路徑 圖八： OABCO路徑圖類比上面結(jié)論不難的到結(jié)果：OABCO：圓弧的起點:70.5060,213.1406、186.7802，251.2321、190.1206， 504.7330、144.5033 ，591.6462、101.1882，687.2114、 268.7281，693.9368、368.0000，689.7980、410.7227，699.9869 、 534.4122，738.2932、668.6667，739.9107 、728.0510 ，605.931、 730.0000，512.0000、508.5213 ，194.7666、 418.3448，94.4897、 237.8946，40.5474。 圓弧的終點: 76.8805,219.5010、237.3618，415.1749、 183.9472， 531.1203、140.0833 ，598.7119、109.3883， 702.7106、 273.8711， 693.3629、375.0000 ，688.6603、432.2849，709.1343 、 541.8182， 739.8333、679.8865，731.5023 、730.0000 ，512.0000、 727.9377 ，513.9178、506.3559，192.2797、 411.4860，90.1110 、 233.4928，39.1902。 圓弧圓心：80,030、290，300、 220,530、150,600、107,693、 270,860、370,680、430,680 、 540，730、670,730、720,600、 720,520、500,200、 410,010 、0,0。 最短路徑：2715.3個單位；最短路徑所需時間： 577.5709s 問題二：要求出最短時間內(nèi)能完成的路徑，從直線行走路線進入彎道時的速度是變化的。，根據(jù)問題分析，發(fā)現(xiàn)問題二與問題一中OA模型的求解相類似，所以建立的規(guī)劃模型，求得路徑長度。設(shè)與最短半徑圓相切的圓的圓心B坐標(biāo)B1,B2，且該圓的半徑為,同理可得切點與圓心距離方程：x-B12+y-B22=由于圓心在對角線上，所以得圓心所在直線方程：B2=-B1+290將x、y的值代入，與聯(lián)立方程得B1與的關(guān)系：B1=802+10-2帶入方程得B2與r的關(guān)系：B2=2102-10+2上述總結(jié)得圓心B為802+10-2，2102-10+2運用兩點間距離公式求得OB、AB、OA間距離：a=B1-O12+B2-O22同理可得b=B1-A12+B2-A22同理可得l=A1-O12+A2-O22結(jié)合圖形分析，給出與圓B相切所在的直線，與圓相切于M、N點，分別求OM、AN的距離在OBM中，同上方法所得l1=a2-2在ABN中同理可得l2=b2-2設(shè)OA直線方程：y=A2-O2A1-O1x+d點B到直線OA的距離：c=kOAB1+B2-kOAA1+A2k2+-12角1所對應(yīng)的弧度角：1=arcsinca在OBM中角2所對應(yīng)的弧度角：2=arcsina角3所對應(yīng)的弧度角：1=arcsincb在OBN角4所對應(yīng)的弧度角：2=arcsinb將兩個式子代入OB直線的斜率式子中：kOB=tan1+2+arctankOA將兩式子代入AB直線的斜率式子中：kAB=tanarctankOA-1-2根據(jù)得出的相應(yīng)弧度角，結(jié)合弧長公式l=nr180得到OA路徑總長： L=n180+l1+l2OA是由三段路徑組成，算出與彎道圓弧相切的兩段直線路徑的長度，結(jié)合速度v0、v，得到三段最短路徑的最短時間。OA路徑最短時間：T=t1+t1+t3=l15+l25+nv01+e10-0.12根據(jù)題目條件 分析v-關(guān)系圖九：v-p關(guān)系圖根據(jù)題目要求需給出路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間。當(dāng)O點為原點，坐標(biāo)為O0,0,A300,300時，根據(jù)編程求得各點坐標(biāo)。OM直線段起點坐標(biāo)O0，0，終點坐標(biāo)68.5169,214.2400；NA直線段起點坐標(biāo)75.4711,221.3863，終點坐標(biāo)A300，300；圓弧的圓心坐標(biāo)80,210最短時間路徑總距離：L=473.1588最短總時間： T=94.8016s最短時間路徑，并且在最大拐彎速度不側(cè)翻，需驗證拐彎速度的范圍。經(jīng)驗證r的范圍在10,20之間有一個值，能使機器人從OA達到最短時間，并且不側(cè)翻。看驗證-T關(guān)系圖（圖）圖十：p-T關(guān)系圖綜上所述，運用matlab編程得出最優(yōu)結(jié)果。（程序見附錄三）我們對得到的就過進行檢驗得到下圖可見結(jié)果符合要求。七 模型評價問題一與問題二都建立了規(guī)劃模型，對于最短路徑問題，都考慮與拐彎圓弧相切，計算最短半徑所在圓的圓弧長度。對于解決最短路徑問題有很多解決方法；在本文中問題一建立了動態(tài)規(guī)劃模型，通過對障礙物進行分區(qū)規(guī)劃，對不同路線進行觀察分析，編制程序得出結(jié)果，該結(jié)果有一定的參考價值。問題二的模型建立是模型一求解OA最短路徑問題的一個衍生可以運用在其他路徑規(guī)劃的實際問題中，具有實際意義。 本文建立的遞歸算法模型具有一定的廣泛性，該方法還可以解決漢諾塔等問題，可以解決優(yōu)化問題。缺點：有個別邊境附近的點，由于算法無法做到很精確，存在一定誤差。參考文獻1深圳杯數(shù)學(xué)建模D題算法最短路徑matlab程序/p-375880093460.html2行走機器人避障問題/view/59fd857aa26925c52cc5bf4c.html3周品，趙新芳；MATLAB數(shù)學(xué)建模與仿真；國防工業(yè)出版社；2009年4月第1版附錄一：附錄二：附錄三：functi