機(jī)器人壁障問(wèn)題——數(shù)學(xué)建模

1、 機(jī)器人避障問(wèn)題 摘 要：當(dāng)今科學(xué)技術(shù)日益發(fā)達(dá)，高科技產(chǎn)品尤其是機(jī)器人在我們?nèi)粘Ｉ钪羞\(yùn)用的越來(lái)越廣泛，它能夠代替人類(lèi)完成許許多多的工作，但如何能讓機(jī)器人自動(dòng)化的完成人類(lèi)交給的任務(wù)成為設(shè)計(jì)機(jī)器人的關(guān)鍵。我們做此題就是為了更好的利用機(jī)器人為我們提供方便，提高生活質(zhì)量，若機(jī)器人程序設(shè)計(jì)不當(dāng)不僅不會(huì)給人類(lèi)帶來(lái)方便，還很有可能給我們的生活帶來(lái)更多的麻煩。本題中提出了如何讓機(jī)器人能夠自動(dòng)識(shí)別障礙物，保證機(jī)器人能夠在合理區(qū)域行走，并設(shè)計(jì)出如何能讓機(jī)器人自動(dòng)判斷最短路程于最短時(shí)間下行走路線的問(wèn)題。所以解決好本題可以為我們的生活提供幫助。本文通過(guò)運(yùn)用兩點(diǎn)之間直線最短理論，優(yōu)化問(wèn)題，最短路問(wèn)題，圖論，以及運(yùn)用m

2、atlab軟件編程及作圖的方法，闡述了機(jī)器人避障問(wèn)題的相對(duì)優(yōu)化方案的解決辦法，即“兩點(diǎn)之間直線最好，轉(zhuǎn)彎半徑最小”的理論，通過(guò)計(jì)算中的比較與選擇把四條最短路徑都求出了相對(duì)最優(yōu)解，論證了轉(zhuǎn)彎速度不會(huì)隨著r的增加一直增大或減小，而是有一個(gè)最小極點(diǎn)的思想。從而求出了r，以及最短的時(shí)間。 問(wèn)題一，通過(guò)對(duì)最短路問(wèn)題的分析，我們很容易分解成線圓結(jié)構(gòu)來(lái)求解，然后把可能路徑的最短路徑采用窮舉法列舉出來(lái)，最終得出最短路徑：O A 最短路徑為：471.0372O B 最短路徑為：838.0466O C 最短路徑為：1085.7531OABCO 最短路徑為：2834.6591問(wèn)題二，通過(guò)建立時(shí)間t與r的關(guān)系式，得出

3、r在11.504時(shí)，從O到A的時(shí)間相對(duì)最短，最短時(shí)間為98.606004。 我們可以利用此篇論文解決生活中實(shí)際的問(wèn)題，在計(jì)算時(shí)可以節(jié)省大量的時(shí)間，使機(jī)器人又準(zhǔn)確又完善的完成我們給定的任務(wù)，從而進(jìn)行拓展，給定區(qū)域內(nèi)任何兩個(gè)點(diǎn)，我們都可求出其最短路徑和走完全程的最快時(shí)間。從而可以讓機(jī)器人幫助我們給家里打掃衛(wèi)生或設(shè)計(jì)自動(dòng)吸塵器等，也可使機(jī)器人在最短的時(shí)間完成工作，提高效率，延長(zhǎng)機(jī)器人的使用壽命。關(guān)鍵字：最短路問(wèn)題 優(yōu)化問(wèn)題 matlab 一 問(wèn)題重述 隨著現(xiàn)代科學(xué)技術(shù)日新月異的發(fā)展，機(jī)器人越來(lái)越多的出現(xiàn)在日常生活中,它既可以通過(guò)運(yùn)行預(yù)先編排的程序?yàn)槿祟?lèi)服務(wù)，根據(jù)人工智能程序自動(dòng)處理一些生活中問(wèn)題，進(jìn)

4、而協(xié)助或者相應(yīng)地取代人類(lèi)的工作，可以說(shuō)機(jī)器人的創(chuàng)新與改進(jìn)正一步步影響著人類(lèi)的發(fā)展。如圖1所示，該圖是一個(gè)800×800的平面場(chǎng)景圖，在原點(diǎn)O(0，0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面范圍內(nèi)活動(dòng)。機(jī)器人在活動(dòng)中不能碰到障礙物及其向外延伸10個(gè)單位的區(qū)域，障礙物由12個(gè)不同形狀的圖形組成，障礙物的數(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,

5、 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，寬60在圖1中，在障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)，機(jī)器人的行走路線由直線和與直線相切的圓弧組成，也可以由兩條及以上圓弧組成。機(jī)器人不能折線轉(zhuǎn)彎，必須經(jīng)過(guò)與直線相切的圓弧轉(zhuǎn)彎。每條圓

6、弧的直徑不小于10個(gè)單位。機(jī)器人直線行走的最大速度為個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過(guò)該速度，機(jī)器人將發(fā)生側(cè)翻，無(wú)法完成行走。要解決機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑，請(qǐng)建立數(shù)學(xué)模型，以達(dá)到最短路徑和時(shí)間。對(duì)場(chǎng)景圖中4個(gè)點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計(jì)算：(1) 機(jī)器人從O(0, 0)出發(fā)，OA、OB、OC和OABCO的最短路徑。(2) 機(jī)器人從O (0, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑。注：要給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總

7、時(shí)間。 圖1二 問(wèn)題分析2.1問(wèn)題一問(wèn)題一中要求機(jī)器人從O（0,0）出發(fā)，按照上述規(guī)則求繞過(guò)障礙物到達(dá)目標(biāo)點(diǎn)的最短路徑，我們可以先設(shè)想機(jī)器人所走過(guò)的路徑的各種情況。通過(guò)設(shè)想然后采用兩點(diǎn)之間直線最短的原理尋找可能的最短路徑（比如求O和A之間的最短路徑，我們就可以連接O和A，發(fā)現(xiàn)OA的對(duì)角線在OA的下方，所以從OA對(duì)角線的上方行走比下方距離短。在第一問(wèn)求路徑最短時(shí)盡量少走圓弧，所以在可能的情況下拐彎時(shí)最好走10為半徑的圓?。?。之后采用窮舉法列出O到每個(gè)目標(biāo)點(diǎn)的可能路徑的最短路徑，最短路徑由圓弧和直線組成，求出圓弧和直線的長(zhǎng)就能求得路徑，通過(guò)建立優(yōu)化模型可求出最短路徑。進(jìn)而聯(lián)立切線和圓的方程組及運(yùn)用

8、matlab軟件求出各點(diǎn)坐標(biāo)。 2.2問(wèn)題二問(wèn)題二需要求O到A的最短時(shí)間，這讓我們考慮的就不僅僅是路長(zhǎng)的問(wèn)題，還有了速度的問(wèn)題。已知公式和得出直線比轉(zhuǎn)彎的速度快且轉(zhuǎn)彎速度與圓弧半徑有關(guān)。我們可通過(guò)建立路程和速度的關(guān)系方程 求得時(shí)間的最優(yōu)解。 三 模型假設(shè)1、 假設(shè)機(jī)器人能夠抽象成點(diǎn)來(lái)處理。 2、 假設(shè)機(jī)器人能完整的走到終點(diǎn)，中途不會(huì)發(fā)生故障。3、 假設(shè)機(jī)器人在離路障10個(gè)單位處不會(huì)發(fā)生故障，可以正常行走。四 符號(hào)說(shuō)明符號(hào)符號(hào)解釋切 點(diǎn)：表示5號(hào)圖形包絡(luò)線上的點(diǎn). i=1,2,3E：表示6號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2,3,4Fi：表示7號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2,3,4,5Gi：表示8號(hào)圖

9、形包絡(luò)線上的點(diǎn) i=1,2,3,4Hi：表示9號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2,3,4Ii：表示10號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2,3,4Ji：表示11號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2,3,4Ki：表示2號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2Li：表示3號(hào)圖形包絡(luò)線上的點(diǎn) i=1,2五 模型建立5.1證明點(diǎn)到直線距離最短理論在最短路問(wèn)題中起重要作用通過(guò)起點(diǎn)與終點(diǎn)的連線，判斷哪邊路徑離這條連線距離較近，進(jìn)而選擇出最優(yōu)路徑。如果中間有較多路障的話也可采取分步判斷的方法，判斷由較近路障附近的點(diǎn)決定。如圖二，求O到A最短路徑。正方形對(duì)角線為BC，EE，DD分別為E,D到OA的距離，顯然EE< DD,所以從O

10、A的上方通過(guò)為最短路徑。 5.2基本模型求路徑（1題）5.2.1線圓模型已知O(x1，y1）為起點(diǎn),B（x2，y2）為目標(biāo)點(diǎn),D（x3，y3）和E（x4，y4）分別為機(jī)器人經(jīng)過(guò)拐點(diǎn)分別于隔離危險(xiǎn)線拐角小圓弧的切點(diǎn)，圓心為O1（x5，y5），圓的半徑為r，OB的長(zhǎng)度為a，OO1的長(zhǎng)度為b，BO1的長(zhǎng)度為c，角度 ，.通過(guò)余弦定理可算出，弧長(zhǎng)=圓心角*r，可求出OB的長(zhǎng)度。由此解法在matlab編程，可求出已知起點(diǎn)與終點(diǎn)及圓心和半徑的所有最短路（見(jiàn)附錄10.1） 5.2.2相交切線模型當(dāng)兩圓半徑相同時(shí)，由于半徑已知以及K(x1，y1）,M（x2，y2）,L（x3，y3）我們很容易求得L點(diǎn)的坐標(biāo)已知

11、后用上述線圓模型即可求出弧長(zhǎng)當(dāng)兩圓半徑不同時(shí)，根據(jù)半徑比值可算出斜邊比值，斜邊端點(diǎn)已知，即可求出H坐標(biāo)，再利用附錄10.1求解可得。5.2.3平行切線模型當(dāng)兩圓半徑相同時(shí)，其中已知O1(x1，y1）O2（x2，y2）,P（x3，y3）,半徑已知，所以切線方程為再利用matlab運(yùn)算出弧長(zhǎng)（詳見(jiàn)附錄10.1）當(dāng)兩圓半徑不同時(shí)，兩圓心斜率k可知，=a，切線斜率再利用上述方程式即可求得C，切線方程與圓聯(lián)立方程即可求得切點(diǎn)（見(jiàn)附錄10.2和10.3），再用線圓模型即可求出路徑。5.3基本模型求拐點(diǎn)（1題）已知條件為O(x1，y1）O1（x2，y2）DO1=r設(shè)D(x，y)，由于兩直線垂直即有D點(diǎn)在圓上

12、，與圓的方程聯(lián)立即可求出D點(diǎn)。此處先運(yùn)用matlab中expand函數(shù)將方程式化解成多項(xiàng)式形式，再用solve函數(shù)求出方程的根即D點(diǎn)坐標(biāo)。（詳見(jiàn)附錄10.2和10.3）5.3時(shí)間模型的建立（2題） 根據(jù)線圓模型我們可以知道：若一個(gè)機(jī)器人穿過(guò)的圓弧所在圓的半徑已知，則機(jī)器人行走的路程就是可求得。由于機(jī)器人在轉(zhuǎn)彎時(shí)的速度是關(guān)于半徑（r）的函數(shù)，再根據(jù)“時(shí)間（T）=路程（S）/速度（V）”，我們可以求出時(shí)間（T）關(guān)于半徑（r）的函數(shù)關(guān)系式。已知直線行走的速度和轉(zhuǎn)彎行走速度的關(guān)系式，可以建立一個(gè)自變量為r的關(guān)于時(shí)間的函數(shù)，通過(guò)求導(dǎo)讓函數(shù)值等于0，可以得出r的解，從而確定最短時(shí)間。我們根據(jù)對(duì)前面路程的求

13、解，可以判斷機(jī)器人在轉(zhuǎn)彎時(shí)所走的弧形路程相對(duì)于直線路程是很小的，那么我們可以斷定：當(dāng)機(jī)器人以最短的時(shí)間走到目標(biāo)點(diǎn)時(shí)，它所經(jīng)過(guò)的路線與它以最短的路程所走的路線大致一樣。求函數(shù)表達(dá)式具體過(guò)程：如圖：已知O（x1,y1） B=(x2,y2) O1=(x3,y3),點(diǎn)D，點(diǎn)E分別為圓的切點(diǎn)， 設(shè)圓的半徑為r,求出O-àB的時(shí)間。求解過(guò)程：L12=(x2-x1)2+(y2-x1)2L22=(x3-x2)2+（y3-y22L32=(x3-x1)2+(y3-y1)2設(shè)O, O1,B為a, D,O1,O為b，E,O1,B為c，cos(a) =(L32- L22- L12)/2*L1*L2a=arcc

14、os(L32- L22- L12)/2*L1*L2b=arccos(r/L1)c=arcos(r/L2)弧長(zhǎng)DE=r*(2*pi-a-b-c)V=v0/5*(1+e(10-0.12)時(shí)間T1=(L12-r2)(1/2)/v0 T2=(L22-r2)(1/2)/v0 T3=弧長(zhǎng)DE/VTzong=T1+T2+T3 在求出時(shí)間關(guān)于半徑的方程后，我們可數(shù)值解法求解最短時(shí)間。我們知道半徑的大小影響了時(shí)間的長(zhǎng)短，半徑的長(zhǎng)度是大于10的實(shí)數(shù)，我們可以先讓自變量（半徑）比較大范圍的有序變化（因?yàn)樽宰兞康姆秶淮螅?，求出?duì)應(yīng)的時(shí)間。再觀察時(shí)間隨半徑變化的規(guī)律，得出最短時(shí)間時(shí)所對(duì)應(yīng)的時(shí)間，就可以確定最短時(shí)間就在

15、所得時(shí)間點(diǎn)的附件擺動(dòng)。為了能更精確的求出最短時(shí)間，我們繼續(xù)以比上次取值小的值在所求的點(diǎn)的附近做有序的加減。以此類(lèi)推，經(jīng)過(guò)多輪對(duì)時(shí)間的取值，就可以解出比較精確的解。六、模型求解6.1.1 O A的最短距離如圖：D1(70.5060,213.1406)D2(76.6064,219.4066)弧OA的長(zhǎng)等于兩條切線（OD1，D2A）與?。―1，D2）的和通過(guò)用matlab計(jì)算可知：l OA的最短距離為471.03726.1.2 O B的最短距離l 如圖E1(50.1353,301.6396)E2(52.198,306.252)E3(142.198,441.252)E4(147.709,444.733

16、)F1(222.29,406.264)F2(230,470)F3(230,530)F4(225.4967,538.3538）G1(144.5033,591.6462)G2(140.6916,596.3458)同理如上，通過(guò)用matlab計(jì)算可知：O B的最短距離為838.04666.1.3 OC的最短距離 如圖D1(70.5060,213.1406) D3(75.736,219.044)L1(395.798,339.055)L2(397.709,339.736)K1(568.331,372.115)K2(600.019,387.588)J1(727.7178,710.2822)J2(730,6

17、00)J3(730,520)J4(727.802,606.252)同理如上，通過(guò)用matlab計(jì)算可知：O_C的最短距離為1085.7531如圖G3(270.5862,689.9828)G4(272,689.7980)H1(368.8934,670.0614)H2(370,670)H3(430,670)H4(435.5878,671.7068)I1(534.4122,738.2932)I2(540,740)I3(670,740)I4(679.7673,732.1447)F5(229.4472,533.2789)同理如上，通過(guò)用matlab計(jì)算可知：A B的最短距離為454.3989 B C的最

18、短距離為823.4609 O A B C O的最短距離為2834.65916.2問(wèn)題二的求解：如圖：已知：坐標(biāo)點(diǎn)O（0，0），A（300 ，300），O1（80，210）根據(jù)上面模型，將三點(diǎn)的坐標(biāo)分別代入，我們可以得到半徑（r）關(guān)于時(shí)間(t)的方程：根據(jù)上面算出的方程，表示如圖注：左右下圖的均縱軸為5倍的時(shí)間t，為了便于比較不同時(shí)間下時(shí)間的大小。當(dāng)時(shí)間t取值為10,11,12,13,14時(shí)，由圖可以看到r=12時(shí)，時(shí)間5*t為最小，故而判斷精確值在12的附近。 表圖示中在半徑r=11.5時(shí)，時(shí)間最短。圖示中r=11 .505時(shí)， 時(shí)間最短 當(dāng)半徑r=11.5045時(shí)，時(shí)間最短 上圖為給半徑r規(guī)

19、律性賦值的過(guò)程解得：半徑（r）=11.504時(shí)，最短時(shí)間（t）=98606004 。七、模型推廣7.1 問(wèn)題深入分析 在本題中有十二個(gè)障礙物，按照線圓結(jié)構(gòu)畫(huà)出從起點(diǎn)到達(dá)目標(biāo)點(diǎn)的路徑是有限的，我們完全可以采用窮舉法把這些路徑列出來(lái)，然后比較大小取最小者即可，但是我們可以設(shè)想如果這個(gè)區(qū)域內(nèi)有n個(gè)障礙物，那么按照線圓結(jié)構(gòu)從起點(diǎn)到達(dá)目標(biāo)點(diǎn)的可能路徑就有無(wú)數(shù)多條，這時(shí)我們?nèi)绻俨捎酶F舉法是不現(xiàn)實(shí)的。所以我們必須尋求新的算法來(lái)解決這個(gè)問(wèn)題。 由上述分析我們有了這樣一個(gè)想法：先求出所有的切線，包括出發(fā)點(diǎn)和目標(biāo)點(diǎn)到所有圓弧的切線以及所有圓弧與圓弧之間的切線，然后把這且曲線看成是圖6.11中的，給這些定點(diǎn)賦一個(gè)

20、等于切線長(zhǎng)度的權(quán)值，如果某兩條切線有一個(gè)公切圓弧，則代表這兩條曲線的頂點(diǎn)是一條直線的兩個(gè)端點(diǎn)，邊上的權(quán)值等于這兩條切線之間的劣弧長(zhǎng)度。然后在這張圖中加一個(gè)源點(diǎn)和終點(diǎn)，那么在所有代表出發(fā)點(diǎn)與其它圓弧之間切線的頂點(diǎn)與源點(diǎn)連成一條邊，權(quán)值均為0，同理在所有代表目標(biāo)點(diǎn)到其它圓弧切線的頂點(diǎn)與終點(diǎn)連成一條邊，權(quán)值均為0，這樣題目就轉(zhuǎn)化成了求源點(diǎn)到達(dá)終點(diǎn)之間的最短路徑問(wèn)題了，這里最短路徑就是指經(jīng)過(guò)所有頂點(diǎn)與邊的權(quán)值之和最小。我們可以采用Dijkstra算法進(jìn)行求解。7.2 模型的進(jìn)一步求解 根據(jù)6.1的分析，在有若干個(gè)障礙物的區(qū)域中，我們把按照線圓結(jié)構(gòu)畫(huà)出從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路徑圖依據(jù)6.1中的想法轉(zhuǎn)換成了下

21、面這張圖，圖中的A和G點(diǎn)就是添加的源點(diǎn)和終點(diǎn)，其它節(jié)點(diǎn)均是出發(fā)點(diǎn)和目標(biāo)點(diǎn)到圓弧的切線和圓弧與圓弧之間的切線轉(zhuǎn)化而成，依據(jù)Dijkstra算法求得最短路徑。八 模型評(píng)價(jià)8.1模型優(yōu)點(diǎn) （1）在本題中，我們對(duì)該模型進(jìn)行優(yōu)化是通過(guò)一些指標(biāo)進(jìn)行評(píng)判的，具有相對(duì)的客觀性和一般性；（2）在構(gòu)造數(shù)學(xué)模型時(shí)我們給出了客觀的理由和數(shù)據(jù)，避免了過(guò)分的主觀判斷；（3）本文利用枚舉和數(shù)學(xué)編程的方法，將定性問(wèn)題定量化，運(yùn)用多個(gè)方案對(duì)路徑進(jìn)行優(yōu)化，在相對(duì)優(yōu)化之中取得最優(yōu)解，最后達(dá)到題目所要求的最優(yōu)解； （4）該模型可以解決日常生活中機(jī)器人的基本避障問(wèn)題，使得機(jī)器人在工業(yè)，醫(yī)學(xué)，建筑，軍事等領(lǐng)域發(fā)揮應(yīng)有的基本作用； 8.2

22、模型缺點(diǎn)（1）由于分析時(shí)間限制和能力水平有限，加上計(jì)算量大且復(fù)雜，得到的不一定是最佳結(jié)果。（2）題中所涉及的各項(xiàng)比較、判斷直到結(jié)果的得出都是粗糙的，不適用于精度要求很高的問(wèn)題。（3）在障礙物較多時(shí)形狀不規(guī)則時(shí)，模型需要進(jìn)一步改進(jìn)。（4）不可避免的具有主觀性。 九 參考文獻(xiàn)1 馮俊， 數(shù)據(jù)結(jié)構(gòu)， 北京： 清華大學(xué)出版社， 20072 邦迪，圖論及其應(yīng)用，西安：西安科學(xué)出版社， 19843 劉來(lái)福，數(shù)學(xué)模型與數(shù)學(xué)建模，北京：北京師范大學(xué)出版社， 20115 趙東方，數(shù)學(xué)模型與計(jì)算， 北京：科學(xué)出版社， 2007十 附錄本題的計(jì)算量較大，我們用matlab軟件來(lái)解決此問(wèn)題10.1該程序用于解決已知起點(diǎn)，終點(diǎn)，相切圓圓心，可以求得起點(diǎn)到終點(diǎn)的