機器人壁障問題——數(shù)學建模

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

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

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

4、而協(xié)助或者相應地取代人類的工作，可以說機器人的創(chuàng)新與改進正一步步影響著人類的發(fā)展。如圖1所示，該圖是一個800×800的平面場景圖，在原點O(0，0)點處有一個機器人，它只能在該平面范圍內(nèi)活動。機器人在活動中不能碰到障礙物及其向外延伸10個單位的區(qū)域，障礙物由12個不同形狀的圖形組成，障礙物的數(shù)學描述如下表：編號障礙物名稱左下頂點坐標其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(550, 450)，半徑703平行四邊形(360, 240)底邊長140，左上頂點坐標(400, 330)4三角形(280, 100)上頂點坐標(345, 210)，右下頂點坐標(410,

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

6、弧的直徑不小于10個單位。機器人直線行走的最大速度為個單位/秒。機器人轉彎時，最大轉彎速度為，其中是轉彎半徑。如果超過該速度，機器人將發(fā)生側翻，無法完成行走。要解決機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑，請建立數(shù)學模型，以達到最短路徑和時間。對場景圖中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的最短時間路徑。注：要給出路徑中每段直線段或圓弧的起點和終點坐標、圓弧的圓心坐標以及機器人行走的總距離和總

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

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

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

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

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

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

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

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

15、在所得時間點的附件擺動。為了能更精確的求出最短時間，我們繼續(xù)以比上次取值小的值在所求的點的附近做有序的加減。以此類推，經(jīng)過多輪對時間的取值，就可以解出比較精確的解。六、模型求解6.1.1 O A的最短距離如圖：D1(70.5060,213.1406)D2(76.6064,219.4066)弧OA的長等于兩條切線（OD1，D2A）與?。―1，D2）的和通過用matlab計算可知：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.73

16、3)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)同理如上，通過用matlab計算可知：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,

17、600)J3(730,520)J4(727.802,606.252)同理如上，通過用matlab計算可知：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)同理如上，通過用matlab計算可知：A B的最短距離為454.3989 B C的

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

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

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

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

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