2012年建模比賽D題機(jī)器人最優(yōu)路徑

參賽隊(duì)員：隊(duì)員1：黃榮程隊(duì)員2：楊松泉隊(duì)員3：陳宣傳指導(dǎo)教師：教練組單位： 江西環(huán)境工程職業(yè)學(xué)院承諾書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的,如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫(xiě)）：_D 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）：江西環(huán)境工程職業(yè)學(xué)院 參賽隊(duì)員（打印并簽名）：1. 楊松泉 黃榮程 陳宣傳 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）： 教練組 日期：2012年9月10日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：編號(hào)專(zhuān)用頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：機(jī)器人避障問(wèn)題摘要在一個(gè)800x800的平面場(chǎng)景中，我們研究分析了計(jì)算機(jī)器人避障最短路徑和避障最短時(shí)間問(wèn)題。我們通過(guò)證明最短路徑是由兩部分組成：第一部分是在可安全行駛的平面區(qū)域內(nèi)的自然最短路徑，即直線段，第二部分是行駛過(guò)程遇到障礙物轉(zhuǎn)彎時(shí)距離障礙物10單位以內(nèi)不可行駛的圓弧邊界，且第一部分和第二部分是相切，并相互連接。所以最短路徑一定是由線段和圓弧組成，我們把機(jī)器人在平面場(chǎng)景中行駛情況分為三類(lèi)情景。情景一：機(jī)器人由O(0,0)出發(fā)以最短的路程分別順利到達(dá)A(300,300)、B(100,700)、C(700,640)。情景二：機(jī)器人由0(0,0)出發(fā)以最短的路程分別依次順利經(jīng)過(guò)A(300,300)、B(100,700)、C(700,640)回到點(diǎn)O(0,0)。情景三：機(jī)器人由0(0,0)出發(fā)以最短的時(shí)間到達(dá)A(300,300)。針對(duì)問(wèn)題一，我們建立線圓結(jié)構(gòu)模型，把障礙路徑分為若干個(gè)線段和圓弧將模型進(jìn)行分解，并對(duì)分解的模型一一進(jìn)行求解，最后得出了如下結(jié)論：經(jīng)過(guò)OtA的最短路程S=472.6219，1經(jīng)過(guò)OtB的最短路程S=864.4233，2經(jīng)過(guò)OtC的最短路程S3二1084.6057，經(jīng)過(guò)0tatbtct0的最短路徑S二OA+AB+BC+CO=2609.1685。針對(duì)問(wèn)題二，建立線圓結(jié)構(gòu)模型的基礎(chǔ)上，我們改變機(jī)器人在遇到障礙物轉(zhuǎn)彎時(shí)圓弧的半徑r，分別求出他們所用的時(shí)間，在路程S和時(shí)間V找出規(guī)律，OA OA得到時(shí)間T最小平衡點(diǎn)。根據(jù)表6-14，我們得到：當(dāng)圓弧半徑為10，T最小OA OA為96.23。關(guān)鍵詞：最短路徑 模型分解障礙路徑平衡點(diǎn)

一、問(wèn)題重述行駛區(qū)域限制機(jī)器人只可在一個(gè)800X800的平面場(chǎng)景中行走，圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，且在距離障礙物10單位之外為機(jī)器人安全行駛區(qū)域。

障礙物的數(shù)學(xué)描述如下表：編號(hào)障礙物名稱(chēng)左下頂點(diǎn)坐標(biāo)其它特性描述1正方形(300,400)邊長(zhǎng)2002圓形圓心坐標(biāo)(550,450)，半徑703平行四邊形(360,240)底邊長(zhǎng)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)邊長(zhǎng)1506三角形(60,300)上頂點(diǎn)坐標(biāo)(150,435)，右下頂點(diǎn)坐標(biāo)(235,300)7長(zhǎng)方形(0,470)長(zhǎng)220，寬608平行四邊形(150,600)底邊長(zhǎng)90，左上頂點(diǎn)坐標(biāo)(180,680)9長(zhǎng)方形(370,680)長(zhǎng)60，寬12010正方形(540,600)邊長(zhǎng)13011正方形(640,520)邊長(zhǎng)8012長(zhǎng)方形(500,140)長(zhǎng)300，寬602．速度限制機(jī)器人直線行走最大的安全速度為v=5個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎最大轉(zhuǎn)彎o最大安全行走速度為和轉(zhuǎn)彎圓弧的關(guān)系為v(p)=―—，其中P是轉(zhuǎn)彎半徑。1+eio-0.1p23．所求問(wèn)題問(wèn)題一：機(jī)器人由O(0,0)出發(fā)以最短的路程分別順利到達(dá)A(300，300)、B(100,700)、C(700，640)的路程，和行走中每個(gè)拐點(diǎn)的坐標(biāo)。機(jī)器人由0(0,0)出發(fā)以最短的路程分別依次順利經(jīng)過(guò)A(300,300)、B(100,700)、C(700，640))的路程，和行走中每個(gè)拐點(diǎn)的坐標(biāo)。問(wèn)題二：機(jī)器人由0(0,0)出發(fā)以最短的時(shí)間到達(dá)A(300,300)的時(shí)間，和行走中每個(gè)拐點(diǎn)的坐標(biāo)。二、問(wèn)題分析針對(duì)問(wèn)題一：?jiǎn)栴}一中要求定點(diǎn)0(0,0)按照一定的行走規(guī)則繞過(guò)障礙物到達(dá)目標(biāo)點(diǎn)的最短路徑,我們以包絡(luò)線畫(huà)出機(jī)器人行走的危險(xiǎn)區(qū)域,然后采用窮舉法列出R到每個(gè)目標(biāo)點(diǎn)的可能路徑的最短路徑,去除明顯較長(zhǎng)的路徑。計(jì)算最短的若干條路徑,然后通過(guò)計(jì)算比較其大小便可得出0到目標(biāo)點(diǎn)的最短路徑。針對(duì)問(wèn)題二：要求時(shí)間最短,我們首先要考慮的是,路程和速度。分解為機(jī)器人在行走沿直線行走和圓弧路線行走路程,然后根據(jù)條件分別求出機(jī)器人在直線和圓弧行走的最大安全速度,用最短路徑除以最大速度,即為他們的最小時(shí)間。三、模型假設(shè)機(jī)器人在每段線段和圓弧行走過(guò)程中保持勻速。機(jī)器人活動(dòng)的平面場(chǎng)景為水平平面。機(jī)器人只能走直線和弧線,不能折線轉(zhuǎn)彎,但弧線半徑的隨意控制。機(jī)器人行走過(guò)程中不發(fā)生意外。四、符號(hào)說(shuō)明符號(hào)詮釋SOfA—BfCfO的最短路徑S1O—A的最短路程S2OfB的最短路程S3O—C的最短路程P轉(zhuǎn)彎半徑V0直線最大安全速度TOAOtA的最短時(shí)間ai,bi,ci,di(i=1,2,…)行走路線的直線段和圓弧相切的點(diǎn)L](i=1,2,…)直線路徑線段長(zhǎng)度五、模型建立5.1證明猜想：猜想：具有圓形限定區(qū)域的最短路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。（即問(wèn)題分析中的拉繩子拉到最緊時(shí)的狀況）證明：假設(shè)在平面中有A（a,0）和B（-a,0）兩點(diǎn)，中間有一個(gè)半圓形的障礙物，證明從A到B的最路徑為AEFB。圖5-1平面上連接兩點(diǎn)最短的路徑是通過(guò)這兩點(diǎn)的直線段，但是連接兩點(diǎn)的線段于障礙物相交，所以設(shè)法嘗試折線路徑。在y軸上取一點(diǎn)C（0,y），若y適當(dāng)大，則折線ACB與障礙物不相交，折線ACB的長(zhǎng)度為：IACB1=2ja2+y2顯然IACBI隨著y的減小而減小，減小y得yty，即CtC，使得AC與CB與1111障礙物相切，切點(diǎn)分別為E和F,顯然ACB是這種折線路徑中最短的。由于滿足10<a<1的角滿足a<tana,所以易知弧度EF小于ECF的長(zhǎng)，即EF<ECF,211從而AE+EF+FB<ACp,記線段AE、弧度EF、線段FB為AEFB,那么AEFB比任何折線路徑都短。1下面在考察一條不穿過(guò)障礙物的任何一條路徑，設(shè)其分別于OE和OF的延長(zhǎng)線交與P、Q兩點(diǎn)，記A和P之間的路徑長(zhǎng)度為AP,顯然AP>|AP|,又由AE丄EO,所以|AP|>AE,從而AP>AE,同理可得BC>BF。再來(lái)比較PQ之間路徑長(zhǎng)度PQ和圓弧EF的長(zhǎng)度的大小。若PQ之間的路徑可有極坐標(biāo)方程P=P(a),則有p>1,可得：兀PQ二f^p2+p2d0>fd0-3EF亦即路徑APQB的長(zhǎng)度超過(guò)路徑AEFB的長(zhǎng)度 AEFB是滿足條件A到B的最短路徑。5.2針對(duì)情景一O到A我們考慮最短的兩條路徑OTETFTA和OTMTNTA,具體情況如圖：線段OA為如果沒(méi)有障礙物50點(diǎn)到A最短路徑，E,F和M,N分別為障礙物5左上頂點(diǎn)和右下頂點(diǎn)在邊長(zhǎng)延長(zhǎng)10單位的點(diǎn)。EF和MN為以其兩頂點(diǎn)為圓心半徑為10單位的四分之一圓弧，且兩段圓弧相等。因?yàn)樵诖?00x300的平面場(chǎng)景中，障礙物5偏向右下，所以E,F點(diǎn)到0A的距離小于M,N到0A的距離。由此我們可知0到A最短的路徑為OTEtFtA，我們把路徑分為三段線段0E、線段FA、圓弧EF進(jìn)行求解.0到B由0點(diǎn)到B點(diǎn)的路徑可以說(shuō)有無(wú)限多種，我們選擇明顯最短的四條分別為：路徑一：OTa2Ta3TbTb5Tc2Tc3TdTd1TB路徑二：OTa2Ta3Td3Td2TB路徑三;OTb1Tb2Tb3Tb4TcTc1Tc2Tc3TdTd1TB

路徑四：OTalTaTbTb5Tc2Tc3TdTdiTB段圓弧a—Tal,b—Tb5,c2—Tc3,d—Tdl。路徑二分為：3段直線OTa2,a3Td3,d2TB,段圓弧a2ta3,d3Td2。路徑三分為：6段直線OTbl,b2Tb3,b4Tc,clTc2,c3Td,dlTB段圓弧blTb2,b3Tb4,ctcl,c2tc3,dTdl。路徑四分為：5段直線OTa,alTb,b5Tc2,c3Td,dlTB,4段圓弧aTal,bTb5,c2Tc3,dTdl。求得他們路程之后，進(jìn)行比較得出最短的路徑及路程和各點(diǎn)的坐標(biāo)。O到C排除若干條明顯較長(zhǎng)的路徑，我們得到兩條最短路徑

1路^徑:O-》a-》al-》c-》cl-》c2—》c3-》d-》di-》d2—》d3-》C路徑二：OTa3Ta2tbTblTb2tb3TdTdlTd2td3TCd3clAcaab3b2a2ba3ODr￡wingl-IM“?QQQpng?pn-1024￡L28D?60%-2d3clAcaab3b2a2ba3ODr￡wingl-IM“?QQQpng?pn-1024￡L28D?60%-2皿2?09?兇-9KB?/圖5-4rC*xx1d5.3針對(duì)情景二由于我們已經(jīng)求了O到A和O到C的最短路徑，所以對(duì)于OTATBTCTO的最短路徑我們只要求解A到B和B到C的最短路徑。

d7a4d8a3d6ad4Dwwirigl?IVI???QQQpng?pM?1024Q2M?6096?2012fM?9KB?3/3圖5-5c5c6c7c8沁d7a4d8a3d6ad4Dwwirigl?IVI???QQQpng?pM?1024Q2M?6096?2012fM?9KB?3/3圖5-5c5c6c7c8沁b2b— /'廠初冷述3%d對(duì)于OTATBTCTO的最短路徑。因?yàn)橐阎狾TA的最短路徑，，cTO的最短路徑，而且機(jī)器人在A,B,C三點(diǎn)轉(zhuǎn)彎時(shí)，因?yàn)樗鼈儾皇钦系K物，也沒(méi)有安全距離限制且我們假設(shè)轉(zhuǎn)彎圓弧角度可以隨意控制。我們把轉(zhuǎn)彎圓弧的半徑視為無(wú)限小，則機(jī)器人在A,B,C所行走的路程無(wú)限小。我們把這三段圓弧納入計(jì)算內(nèi)。所以只要求出Btc的最短路徑和ATB的最短路徑就可以了。如圖所示，對(duì)于BTC,有兩種最短可能路徑，通過(guò)我們的計(jì)算并且進(jìn)行對(duì)比,我們得出BTC的最短路徑為上面那條。六、模型求解針對(duì)情景一：6.1O點(diǎn)到A從OA如圖所示，圓的半徑為10個(gè)單位，E、F為兩個(gè)切點(diǎn)，已知O點(diǎn)的坐標(biāo)為(0,0),P點(diǎn)坐標(biāo)為(80,210),A點(diǎn)坐標(biāo)為(300,300)。根據(jù)三角函數(shù)定理，我們可求出OP和AP的線段長(zhǎng)度和他們與障礙物5邊形成的角的角度。如此我們就知道了三角形OEP和三角形AFP的兩邊加一直角，可求OE和FA的長(zhǎng)，和兩三角形與P為頂點(diǎn)角的角度。再用360度減去所求到的4個(gè)角，即為機(jī)器人所要行走弧度的角度。N=56S1=9.77OE=237.9075FA=224.9444S二S1+OE+FA二9.77+237.9075+224.9444二472.6219OA我們做一條水平輔助性MP,根據(jù)以上所求角度我們可以求得ZEPM=14。,ZFPM=20。在根據(jù)三角形之間的關(guān)系，我們科求得 L=9.702957,L1=3.4202,L2=9.39。則E、F的坐標(biāo)分別為(70.3,207.6);(70.6,213.4)。

EMEM圖6-2E=(70.29704,212.4192)F=(70.603,213.4202)O點(diǎn)到B經(jīng)我們計(jì)算，和比較。我們得到機(jī)器人從O到B最短的路徑為路徑四：OTalTaTbTb5Tc2tc3TdTdiTB。我們具體分段計(jì)算了他們的弧長(zhǎng)EF=8.55和它的角度=4911切點(diǎn)F和E的坐標(biāo)為(70.30,212.42)，(75.93,219.14)

線段L=230.52弧長(zhǎng)EF=12.34EF的夾角為70.7°EF的坐標(biāo)分別為（239.07，290.86）；（244.99，300.70）線段L=96.953弧長(zhǎng)EF=4.1EF的夾角為23.522EF的坐標(biāo)分別為（220.98，530.21）；（223.54，527.34）22

弧長(zhǎng)EF=6.02133EF的夾角為24.7°33EF的坐標(biāo)分別為(147.34,597.45)；(148.25,596.57)33O點(diǎn)到C經(jīng)我們計(jì)算，和比較。我們得到機(jī)器人從O到C最短路徑為路徑二：OTa3Ta2tbTblTb2tb3TdTdiTd2td3TC。我們具體分段計(jì)算了他們的路程和坐標(biāo)如下。5AL5F45AL5F4E4線段L=237.49線段L=237.494弧長(zhǎng)EF=0.12244EF的夾角為0.7°44E、F的坐標(biāo)分別為44圖6-6L=184.395232.08,50.22）；（239.78，57.92）線段L=166.436弧長(zhǎng)EF=7.853EF的夾角為45°55EF的坐標(biāo)分別為（412.08，90.22）；（418.38，94.55）55線段L=356.097弧長(zhǎng)EF=0.87366EF的夾角為5°66EF的坐標(biāo)分別為（502.37，237.65）；（504.12，238.23）66E7E7L8線段L=808弧長(zhǎng)EF=6.63277EF的夾角為38EF的坐標(biāo)分別為（727.88，513.84）；（730，520）778E88E8線段L=44.729弧長(zhǎng)EF=6.89488EF的夾角為39.5°88EF的坐標(biāo)分別為（730，600）；（726.43，607.66）88B點(diǎn)到C經(jīng)我們計(jì)算，和比較。我們得到機(jī)器人從B到C最短路徑為：。我們具體分段計(jì)算了他們的路程和坐標(biāo)如下。10弧長(zhǎng)EF=0.2699EF的夾角為1.5°99EF的坐標(biāo)分別為（271.91，189.82）；（279.78，182.08）

圖6-12線段L=101.98L=601112弧長(zhǎng)圖6-12線段L=101.98L=601112弧長(zhǎng)EF=2.09EF的夾角為12°EF的坐標(biāo)分別為（367.92，670.22）；（370，670）1010圖6-13線段L=119.1613弧長(zhǎng)EF=7.51E11E11E12EF的夾角為43°F的坐標(biāo)分別為F的坐標(biāo)分別為12F的坐標(biāo)分別為L(zhǎng)=6715EL=13014EF=7.511212EF的夾角為43°1212430，670）；（437.43，663.31）533.31，737.43）；（540，740）670，740）；（672.08，739.78）F=13.6141313EF的夾角為78°1313所以當(dāng)機(jī)器人從O(0,0)出發(fā)時(shí)，經(jīng)過(guò)°TA的最短路程計(jì)=472-6219經(jīng)過(guò)°TB的最短路程S2二864-4233經(jīng)過(guò)°TC的最短路程S3二1084.6057

和經(jīng)過(guò)OtAtBtCtO的最短路徑S=OA+AB+BC+CO=2609.1685針對(duì)情景三要使時(shí)間最短，我們把最短路徑分為直線段和圓弧。則其半徑和圓心(M,N)的關(guān)系為：x2=(M-80)2+(210-N)2。知道我們圓心可以求出O到(M,N)，又已知半徑和相切我們可得到直線段的長(zhǎng)度。在用其角度求出機(jī)器人行走圓弧的角度，再求出其圓弧長(zhǎng)度。之后用直線段長(zhǎng)度除以最大直線單位5加上圓弧長(zhǎng)度除以最大圓弧速度得到其最短時(shí)間。我們分別使半徑為1