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

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

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

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

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針對情景二由于我們已經(jīng)求了O到A和O到C的最短路徑，所以對于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對于OTATBTCTO的最短路徑。因為已知OTA的最短路徑，，cTO的最短路徑，而且機器人在A,B,C三點轉(zhuǎn)彎時，因為它們不是障礙物，也沒有安全距離限制且我們假設(shè)轉(zhuǎn)彎圓弧角度可以隨意控制。我們把轉(zhuǎn)彎圓弧的半徑視為無限小，則機器人在A,B,C所行走的路程無限小。我們把這三段圓弧納入計算內(nèi)。所以只要求出Btc的最短路徑和ATB的最短路徑就可以了。如圖所示，對于BTC,有兩種最短可能路徑，通過我們的計算并且進行對比,我們得出BTC的最短路徑為上面那條。六、模型求解針對情景一：6.1O點到A從OA如圖所示，圓的半徑為10個單位，E、F為兩個切點，已知O點的坐標為(0,0),P點坐標為(80,210),A點坐標為(300,300)。根據(jù)三角函數(shù)定理，我們可求出OP和AP的線段長度和他們與障礙物5邊形成的角的角度。如此我們就知道了三角形OEP和三角形AFP的兩邊加一直角，可求OE和FA的長，和兩三角形與P為頂點角的角度。再用360度減去所求到的4個角，即為機器人所要行走弧度的角度。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的坐標分別為(70.3,207.6);(70.6,213.4)。

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

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

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

圖6-12線段L=101.98L=601112弧長圖6-12線段L=101.98L=601112弧長EF=2.09EF的夾角為12°EF的坐標分別為（367.92，670.22）；（370，670）1010圖6-13線段L=119.1613弧長EF=7.51E11E11E12EF的夾角為43°F的坐標分別為F的坐標分別為12F的坐標分別為L=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所以當機器人從O(0,0)出發(fā)時，經(jīng)過°TA的最短路程計=472-6219經(jīng)過°TB的最短路程S2二864-4233經(jīng)過°TC的最短路程S3二1084.6057

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