數(shù)學(xué)建模D題論文

1、機(jī)器人避障問題摘要本文根據(jù)兩點(diǎn)之間線段最短，從機(jī)器人路徑由直線與圓弧組成且圓弧半徑最小10個單位和機(jī)器人與障礙物距離至少10個單位，機(jī)器人不能折線轉(zhuǎn)彎，彎道必須是圓弧，且與直線相切。直線上最大速度為個單位/秒，彎道最大速度為（p為轉(zhuǎn)彎圓弧半徑）的要求來進(jìn)行研究探討問題。分別通過對這些要求深入研究從而制定出各自有關(guān)到達(dá)目標(biāo)地的最短路徑與最短時間路徑。像這種避開障礙物來尋求最短路徑與最短時間路徑的問題一般可以用蟻群算法、走迷宮算法來解。模塊1中，我們將焦點(diǎn)鎖定在最短路徑是兩點(diǎn)之間線段最短。我們連接兩點(diǎn)，再選取障礙物的一個到直線垂直距離最短的端點(diǎn)，以它為圓心10個單位為半徑做圓。在以目標(biāo)點(diǎn)與起點(diǎn)各作

2、條直線與圓相切。即得到最短路徑。模塊2中，我們將焦點(diǎn)鎖定在直線上的最大速度大于圓弧的速度，或則圓弧半徑很大其速才接近直線速度。我們要得到最短時間的路徑那我們要在模塊1的條件下盡量減少圓弧段或則半徑大到使速度接近5?！娟P(guān)鍵字】至少 最大 直線與圓弧相切 蟻群算法 最短一、 問題提出最短路徑問題是VLSI設(shè)計和幾何信息系統(tǒng)中的基本問題 ,是一種計算機(jī)圖形搜索算法 ,即在出發(fā)點(diǎn)和目標(biāo)點(diǎn)之間找出最短的路徑。路徑尋優(yōu)算法一方面要完成探索最短路徑 , 另一方面要做到盡可能快 。通常求最短路徑是在一個連通圖中進(jìn)行 , 各個節(jié)點(diǎn)由有向或無向的連線連接 ,而障礙物群中最短路徑指的是圖中兩點(diǎn)通過直線與曲線相連 ,

3、 不與任一障礙物發(fā)生碰撞 ,且直線與曲線的路徑長度最小。機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景圖中4個點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計算：機(jī)器人從O(0, 0)出發(fā)，OA、OB、OC和OABCO的最短路徑、機(jī)器人從O (0, 0)出發(fā)，到達(dá)A的最短時間路徑。所出要靠慮的問題：1) 機(jī)器人是以何種情況運(yùn)動。2) 機(jī)器人在運(yùn)動中有加速段，那他的加速度為多少呢是否時間很短可忽略。（此模型，忽略了加速度的問題）3) 如何在障礙物之間選擇最合適的路徑到達(dá)指定地點(diǎn)。二、 問題分析（一） 障礙物與所要到達(dá)目標(biāo)

4、地現(xiàn)狀如圖1-1（二） 由O點(diǎn)到達(dá)目的地A、B、C中所考慮的因素1) 機(jī)器人要離障礙物最少10個單位。2) 機(jī)器人所走的路徑必須是有直線與圓弧構(gòu)成并且直線與圓弧要相切。3) 機(jī)器人在直線走時的最大速度為在圓弧的最大速度為。4) 機(jī)器人所走的圓弧的半徑最少為10個單位。（三） 機(jī)器人在行走時速度的因素1) 機(jī)器人在直線上是一直加速還是有勻速與減速時短2) 在圓弧段機(jī)器人是以怎樣的情況行走，是勻速還是加速或者是減速過圓弧3) 在直線與圓弧交接段機(jī)器人的行走是否有速度變換三、 模型假設(shè)1) 假設(shè)收集的數(shù)據(jù)均真實(shí)有效。2) 假設(shè)機(jī)器人的加速度與減速度沒有。3) 假設(shè)圓弧半徑很大時，機(jī)器人在圓弧行走的速

5、度趨近于直線最大速度，在計算中可用直線最大速度來計算。4) 機(jī)器人起步速度是直線最大速度，在直線段與圓弧段交接處，以圓弧最大速度前行。 四、 定義與符號說明E、F、W、Q： 障礙物5的右上角的圓的切點(diǎn)： E點(diǎn)的橫坐標(biāo)與縱坐標(biāo)： F點(diǎn)的橫坐標(biāo)與縱坐標(biāo)： Q點(diǎn)的橫坐標(biāo)與縱坐標(biāo)： W點(diǎn)的橫坐標(biāo)與縱坐標(biāo)弧長EFa、b障礙物6的頂點(diǎn)的圓的切點(diǎn)c、d障礙物6的左下角的圓的切點(diǎn)e、f障礙物7的右下角的圓的切點(diǎn)g、h障礙物7的右上角的圓的切點(diǎn)m、n障礙物8的左下角的圓的切點(diǎn)a點(diǎn)的橫坐標(biāo)與縱坐標(biāo)b點(diǎn)的橫坐標(biāo)與縱坐標(biāo)c點(diǎn)的橫坐標(biāo)與縱坐標(biāo)d點(diǎn)的橫坐標(biāo)與縱坐標(biāo)e點(diǎn)的橫坐標(biāo)與縱坐標(biāo)h點(diǎn)的橫坐標(biāo)與縱坐標(biāo)m點(diǎn)的橫坐標(biāo)與縱坐

6、標(biāo)n點(diǎn)的橫坐標(biāo)與縱坐標(biāo)cc、dd障礙物3左上角的圓的切點(diǎn)ee、ff障礙物2同心圓的切點(diǎn)gg、hh障礙物11右下角的圓的切點(diǎn)ii、jj障礙物11右上角的圓的切點(diǎn)bb點(diǎn)的橫坐標(biāo)與縱坐標(biāo)cc點(diǎn)的橫坐標(biāo)與縱坐標(biāo)dd點(diǎn)的橫坐標(biāo)與縱坐標(biāo)ee點(diǎn)的橫坐標(biāo)與縱坐標(biāo)ff點(diǎn)的橫坐標(biāo)與縱坐標(biāo)gg點(diǎn)的橫坐標(biāo)與縱坐標(biāo)jj點(diǎn)的橫坐標(biāo)與縱坐標(biāo)x3,x4經(jīng)過A點(diǎn)的圓的切點(diǎn)x9,x10 經(jīng)過B點(diǎn)的圓的切點(diǎn)x21,x22經(jīng)過C點(diǎn)的圓的切點(diǎn)r圓弧半徑t時間五、 模型的建立與求解（一） 基于兩點(diǎn)之間直線最短模塊11、 模型的分析首先，起點(diǎn)與目的地的最短距離是直連，但要避開所穿過的障礙物，要避開障礙物得找到一個合適的點(diǎn)作圓，在作切線。要

7、路程最短那兩切線得盡量的靠近兩點(diǎn)的連線。即切線與兩點(diǎn)的連線的夾角越小。但兩切線不能與障礙物有交集。其次，在選擇障礙物的時候，要考慮是選擇哪個方向，哪個障礙物附近作為合適的點(diǎn)作圓，把一些不必要，不在路線范圍內(nèi)的障礙物可忽略選擇。最后，在多種路線中比較出哪條路線才是最優(yōu)路線。若考慮是時間問題，那必須是直線距離遠(yuǎn)遠(yuǎn)大于弧線距離，若考慮路程問題，那必須是少作圓弧少走彎路。2、 模型的建立與求解1) 求解OA的最短路徑從O到A,最短路線為O與A的直連，但中途有障礙物，要繞過障礙物行走，所形成的路線與直線OA形成一個近似三角形，OA長度始終不變，根據(jù)三角形其周長要越短則其它兩邊與OA的夾角必須越小。則圓弧

8、的圓心必在障礙物左上角、右下角與障礙物的中心對稱點(diǎn)。如圖2-1，可求出其最短路徑。因?yàn)檎系K物5（正方形）的中心對稱點(diǎn)在線段OA的下方，所以O(shè)EFA一定小于OGHA，ONMA。圓的半徑越大，則切線OE、FA、OW、QA與OA的夾角必然越大，且機(jī)器人與障礙物的最近距離最少10個單位，所以左上角圓的半徑為10個單位，QW所在圓的直徑為障礙物5的對角線加20個單位。所以求解出OEFA和OWQA的長度并比較大小，得出最優(yōu)路徑。 圖2-1障礙物的數(shù)學(xué)描述如下表：1-1編號障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(biāo)(550, 450)，半徑703平行四邊形(360

9、, 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)邊長1506三角形(60, 300)上頂點(diǎn)坐標(biāo)(150, 435)，右下頂點(diǎn)坐標(biāo)(235, 300)7長方形(0, 470)長220，寬608平行四邊形(150, 600)底邊長90，左上頂點(diǎn)坐標(biāo)(180, 680)9長方形(370, 680)長60，寬12010正方形(540, 600)邊長13011正方形(640, 520)邊長8012長方形(500, 140)長300，寬60根據(jù)表1-1，可計算出左上角圓心S坐標(biāo)為(

10、80，210)，外切圓的圓心D坐標(biāo)為（155，135）。已知O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)。設(shè)E點(diǎn)坐標(biāo)為（）、F點(diǎn)坐標(biāo)為（）、Q點(diǎn)坐標(biāo)為() 、W點(diǎn)坐標(biāo)為()。圓S的方程為。根據(jù)方程組解得：，OE= 224.4994同理可得：，F(xiàn)A= 237.4870要求弧長EF，則我們得求出ESF的大小，由于三角形ESF為等腰三角形且腰為ES、SF。所以ESF=acrsin(EF*)用lingo軟件可求出ESF=51.7度,根據(jù)公式可得弧長=9.0183?？傻肙EFA路徑總長度為:。同理可得出OWQA路徑總長度為: 根據(jù)直線上最大速度為個單位/秒，彎道

11、最大速度為可求出時間。圓弧起點(diǎn)坐標(biāo)圓弧終點(diǎn)坐標(biāo)圓的圓心坐標(biāo)弧長時間E（70.50578,213.1407）F（84.17236,200.9120）80，2109.01833.60732線段長度時間OE224.499444.89988FA237.48747.4974綜上所述：O到A的最短距離為471.0047，總時間為：96.0046 2) 求解OB的最短路徑根據(jù)求解OA方法一樣，只要不斷靠近OB直線并且盡量少走彎路且圓弧盡量小則就是最近的路徑。從如圖3-1可看出圖3-1 根據(jù)表1-1可得出經(jīng)過a,b的圓心坐標(biāo)為（60,300）、經(jīng)過c,d的圓心坐標(biāo)為（150,435）、經(jīng)過e,f的圓心坐標(biāo)為（

12、220,470）、經(jīng)過g,h的圓心坐標(biāo)為（220,530）、m,n上的圓心坐標(biāo)為（150,600）。f()、g(),fg=60。設(shè)a()、b()、c()、d()、e()、h()、m()、n()、經(jīng)過a,b的圓的方程為。根據(jù)方程組解得： Oa= 305.7777因?yàn)榻?jīng)過a、b，c、d的兩圓的半徑一樣，所以同時與這兩圓的切線是與三角形的一邊是平行線且長度相等，bc= 162.2498;根據(jù)方程組解得： bc= 162.2498經(jīng)過cd圓的方程為：?；￠Lab=8.22根據(jù)方程解得：如圖3-2，來求得d、e坐標(biāo)。圖3-2根據(jù)方程組解得： 弧長cd=8.85 de= 75.66366如圖3-3，求得h、

13、m坐標(biāo)。圖3-3根據(jù)方程組解得： =211.6456 =524.5029 弧長ef=10.47 =158.3539 =605.4966 hm=96.95352 弧長gh=10.47如圖3-4，求得n點(diǎn)坐標(biāo)圖3-4根據(jù)方程組解得：弧長mn=15.57根據(jù)直線上最大速度為個單位/秒，彎道最大速度為可求出時間。圓弧起點(diǎn)坐標(biāo)圓弧終點(diǎn)坐標(biāo)圓的圓心坐標(biāo)弧長時間a()b()60,3008.223.288c()d()150,4358.853.54e()f()220,47010.474.188g()h(211.6456,524.5029)220,53010.474.188m(158.3539,605.4966)

14、n()150,60015.576.228線段長度時間Oa305.777761.15554bc162.249832.44996de75.6636615.132732fg6014hm96.9535219.390704Bn22.27106綜上所述：O到B的最短路徑的長度為:865.57998，總時間為：185.832。3) 求解OC的最短路徑根據(jù)兩點(diǎn)之間直線最短，要求OC最短路徑則避開障礙物的轉(zhuǎn)彎點(diǎn)必離OC直線最近，從而畫出圖3-5圖形，根據(jù)它求出OC的最短路徑的路程。圖3-5根據(jù)表1-1可得出經(jīng)過aa、bb的圓心坐標(biāo)為（80,210）， cc、dd的圓心坐標(biāo)為（400，330），ee、ff的圓心坐

15、標(biāo)為（550，450），hh的圓心坐標(biāo)為（720，520）， jj的圓心坐標(biāo)為（720,600）、hh坐標(biāo)()、ii坐標(biāo) ()。在求OA最短路徑時以求出aa坐標(biāo)（70.50578,213.1407）且Oaa=224.4994，hhii=80設(shè)坐標(biāo)bb()、坐標(biāo)cc()、坐標(biāo)dd()、坐標(biāo)ee()、坐標(biāo)ff()、坐標(biāo)gg()、坐標(biāo)jj()。根據(jù)方程組解出：從中看出則說明直線bbcc過A點(diǎn)則弧長aabb=8.0183。bbcc= 347.9115同理可得：弧長ccdd=14.50,eeff=9.89,gghh=7.636,iijj=6.659ddee=124.1239ffgg=166.8448Cj

16、j=43.58899根據(jù)直線上最大速度為個單位/秒，彎道最大速度為可求出時間。圓弧起點(diǎn)坐標(biāo)圓弧終點(diǎn)坐標(biāo)圓的圓心坐標(biāo)弧長時間aa(70.50578,213.1407)bb()80,2108.01833.20732cc()dd()400，33014.55.8ee()ff()550，4509.891.978gg()hh()720，5207.6363.0544ii()jj()720,6006.6592.6636線段長度時間Oaa224.499444.89988bbcc347.911569.5823ddee124.123924.82478ffgg166.844833.36896hhii8016Cjj43

17、.588998.717798綜上所述：OC的最短路徑的路程為：1033.9728?？倳r間為：214.0974) 求解OABCO的最短路徑根據(jù)兩點(diǎn)之間直線最短，分別找出兩點(diǎn)的最近距離，方法與前幾次是一樣的，如圖3-6，求出OABCO的最短路徑的路程。圖3-6根據(jù)圖3-6,設(shè)各個切點(diǎn)坐標(biāo)為x1()、x2()、x3()、x4()、x5()、x6()、x7()、x8()、x9()、x10()、x11()、x12()、x13()、x14()、x15()、x16()、x17()、x18()、x19()、x20()、x21()、x22()、x23()、x24()、x25()、x26()、x27()、x28(

18、)、x29()、x30()。根據(jù)圓的公式（a.b為圓心坐標(biāo)r為半徑）與勾股定理、余弦定理（為直角所對的邊為其它角對的邊）可求出各個切點(diǎn)坐標(biāo)與。直線上最大速度為個單位/秒，彎道最大速度為可求出時間。各切點(diǎn)坐標(biāo)、弧長、圓心坐標(biāo)為：圓的兩切點(diǎn)坐標(biāo)圓的半徑圓的圓心坐標(biāo)兩切點(diǎn)的弧長時間x1()X2()103.6204X3()X4()106.07288X5()X6()102.78068X7()X8()102.45896X9()X10()108.01416x11()x12()100.57568x13()x14()101.0436x15()x16()102.4676x17()x18()102.36696x19

19、()X20()105.4008X21()X22()101.87424X23()X24()102.75664X25()X26()102.61524X27()X28()100.79288X29()X30()10337236各直線段長度：線段長度時間Ox1224.499444.89988x2x3227.99245.59984x4x5233.822946.76458x6x796.953619.39072x8x995.720519.1441x10x11155.245331.04906x12x1396.7119.342x14x156012x16x17119.139423.82788x18x1913026X

20、20x2192.090918.41818X22x2341.20138.24046X24x258016X26x27387.588677.51772X28x29126.209325.24186X30O431.582886.31856綜上所述：OABCO的最短路徑的總路程為:2714.3,總時間為:565.96(二) 基于要求最短時間到達(dá)目的地建立模塊21、 模型的分析根據(jù)要求O到A的時間要最短，且直線上最大速度為個單位/秒，彎道最大速度為，彎道上的速度只能隨著半徑的增大而加大，但是無論半徑如何加大，彎道上的速度無限趨近于5個單位/秒，在直線上的速度大于彎道速度，要想時間最短，那在相同路程上，直線的

21、路程要遠(yuǎn)遠(yuǎn)多于彎道的路程，則時間消耗最短。圓弧半徑很大時其速度近似為5個單位/秒，在相同路徑時，其所消耗的時間是最短。2、 模型的建立與求解1) 在模塊1中的OA最短距離的求解下，我們可以明白它距離雖然是最短但它那弧長段的速度是2.5 所以說它的時間不可能是最短的，當(dāng)我們的半經(jīng)不斷增大，根據(jù)lingo計算出當(dāng)半徑大于15時，彎道速度就幾乎趨近于5。所以可用如圖3-7 來計算 圖3-7因無法確定圓心坐標(biāo)，此方案不能得出解。2) 根據(jù)模塊1中OA的最短路程，因?yàn)橹本€的速度最大，所以可以讓圓弧段盡量減小，從而減小時間。我們做出不同半徑r時所用時間t。如表1-2： r101111.411.511.53

22、11.5511.611.7t96.017794.635594.567194.564994.565094.565394.566694.5715r11.81212.513141516t94.579094.600194.673894.760794.945695.134295.3248表1-2從表中看出r由10遞增到16時，時間在r=10,11.5是遞減的，在r=11.53,16是遞增的。所以最短時間在r=11.5,11.53之間。且最短時間近視為：94.56。六、 模型的評價像此類避開障礙物求最短路徑法的模型有走迷宮算法，線搜索算法，A*，蟻群法，但由于能力有限，均未采用，最短路徑問題是VLSI設(shè)計和幾何信息系統(tǒng)中的基本問題 ,是一種計算機(jī)圖形搜索算法 ,即在出發(fā)點(diǎn)和目標(biāo)點(diǎn)之間找出總代價最低的路徑。路徑尋優(yōu)算法一方面要完成探索最短的路徑 ,另一方面要做到盡可能快。通常求最短路徑是在一個連通圖中進(jìn)行 ,各個節(jié)點(diǎn)由有向或無向的連線連接 ,而障礙物群中最短路徑指的是圖中兩點(diǎn)通過一條折線或曲線相連 ,不與任一障礙物發(fā)生碰撞 ,且這